Smooth transformation of the generalized minimax problem. (English) Zbl 0890.90165

Summary: We consider the generalized minimax problem, that is, the problem of minimizing a function \(\varphi(x)= F(g_1,(x),\dots, g_m(x))\), where \(F\) is a smooth function and each \(g_i\) is the maximum of a finite number of smooth functions. We prove that, under suitable assumptions, it is possible to construct a continuously differentiable exact barrier function, whose minimizers yield the minimizers of the function \(\varphi\). In this way, the nonsmooth original problem can be solved by usual minimization techniques for unconstrained differentiable functions.


90C30 Nonlinear programming
49J52 Nonsmooth analysis
49J35 Existence of solutions for minimax problems
Full Text: DOI


[1] DEMYANOV, V. F., and RUBINOV, A. M., Quasidifferential Calculus, Optimization Software, New York, New York, 1986.
[2] BERTSEKAS, D. P., Nondifferentiable Optimization via Approximation, Mathematical Programming Study, Vol. 3, pp. 1–25, 1975. · Zbl 0383.49025
[3] AUSLENDER, A., Minimisation de Fonctions Localement Lipschitziennes: Applications a la Programmation Miconvexe, Midifferentiable, Nonlinear Programming 3, Edited by O. L. Mangasarian, R. R. Meyer, and S. M. Robinson, Academic Press, New York, New York, pp. 429–460, 1978.
[4] PAPAVASSILOPOULOS, G., Algorithms for a Class of Nondifferentiable Problems, Journal of Optimization Theory and Applications, Vol. 34, pp. 41–82, 1981. · Zbl 0426.90079
[5] BEN-TAL, A., and ZOWE, J., Necessary and Sufficient Optimality Conditions for a Class of Nonsmooth Minimization Problems, Mathematical Programming, Vol. 24, pp. 70–91, 1982. · Zbl 0488.90059
[6] KIWIEL, K. C., A Quadratic Approximation Method for Minimizing a Class of Quasidifferentiable Functions, Numerische Mathematik, Vol. 45, pp. 411–430, 1984. · Zbl 0574.65063
[7] LEMARECHAL, C., An Extension of the Davidon Method to Nondifferentiable Problems, Mathematical Programming Study, Vol. 3, pp. 95–109, 1975.
[8] WOLFE, P., A Method of Conjugate Subgradients for Minimizing Nondifferentiable Convex Functions, Mathematical Programming Study, Vol. 3, pp. 145–173, 1975. · Zbl 0369.90093
[9] MIFFLIN, R., An Algorithm for Constrained Optimization with Semismooth Functions, Mathematics of Operations Research, Vol. 2, pp. 191–207, 1977. · Zbl 0395.90069
[10] GAUDIOSO, M., and MONACO, M. F., A Bundle-Type Approach to the Unconstrained Minimization of Convex Nonsmooth Functions, Mathematical Programming, Vol. 23, pp. 216–226, 1982. · Zbl 0479.90066
[11] LEMARECHAL, C., Numerical Experiments in Nonsmooth Optimization, Progress in Nondifferentiable Optimization, Edited by E. A. Nurminskii, IIASA Proceedings, Laxenburg, Austria, pp. 61–84, 1982. · Zbl 0509.65025
[12] SHOR, N. Z., Minimization Methods for Nondifferentiable Functions, Springer Verlag, Berlin, Germany, 1985.
[13] KIWIEL, K. C., Methods of Descent for Nondifferentiable Optimization, Lecture Notes in Mathematics, Springer Verlag, Berlin, Germany, Vol. 1133, 1985. · Zbl 0561.90059
[14] POLAK, E., Basics of Minimax Algorithms, Nonsmooth Optimization and Related Topics, Edited by F. H. Clarke, V. F. Demyanov, and F. Giannessi, Plenum Press, New York, New York, pp. 343–369, 1989. · Zbl 0777.90061
[15] SCHRAMM, H., and ZOWE, J., A Version of the Bundle Idea for Minimizing a Nonsmooth Function: Conceptual Idea, Convergence Analysis, Numerical Results, Report 206, DFG-Schwerpunktprogramms, Anwendungsbezogene Optimierung und Steuerung, Universitat Bayreuth, Bayreuth, Germany, 1990. · Zbl 0761.90090
[16] POLAK, E., MAYNE, D. H., and HIGGINS, J. E., Superlinearly Convergent Algorithm for Min-Max Problems, Journal of Optimization Theory and Applications, Vol. 69, pp. 407–439, 1991. · Zbl 0724.90066
[17] MADSEN, K., Minimization of Nonlinear Approximation Functions, PhD Thesis, Technical University of Denmark, Lyngby, Denmark, 1985.
[18] DI PILLO, G., Exact Penalty Methods, Algorithms for Continuous Optimization: The State of the Art, Edited by E. Spedicato, Kluwer, Dordrecht, Netherlands, pp. 209–253, 1994. · Zbl 0828.90128
[19] DI PILLO, G., GRIPPO, L., and LUCIDI, S., A Smooth Method for the Finite Minimax Problem, Mathematical Programming, Vol. 60, pp. 187–214, 1993. · Zbl 0799.90106
[20] GLAD, T., and POLAK, E., A Multiplier Method with Automatic Limitation of Penalty Growth, Mathematical Programming, Vol. 17, pp. 140–155, 1979. · Zbl 0414.90078
[21] LUCIDI, S., New Results on a Continuously Differentiable Exact Penalty Function, SIAM Journal on Optimization, Vol. 2, pp. 558–574, 1992. · Zbl 0761.90089
[22] POLAK, E., On the Global Stabilization of Locally Convergent Algorithms, Automatica, Vol. 12, pp. 337–342, 1976. · Zbl 0335.49023
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.