Abstract
We consider unconstrained minimax problems where the objective function is the maximum of a finite number of smooth functions. We prove that, under usual assumptions, it is possible to construct a continuously differentiable function, whose minimizers yield the minimizers of the max function and the corresponding minimum values. On this basis, we can define implementable algorithms for the solution of the minimax problem, which are globally convergent at a superlinear convergence rate. Preliminary numerical results are reported.
Similar content being viewed by others
References
J.W. Bandler and C. Charalambous, “Practical leastpth optimization of networks,”IEEE Transactions on Microwave Theory and Techniques (1972 Symposium Issue) MTT-20 (1972) 834–840.
D.P. Bertsekas, “Nondifferentiable optimization via approximation,”Mathematical Programming Study 3 (1975) 1–25.
C. Charalambous, “Acceleration of the leastpth algorithm for minimax optimization with engineering applications,”Mathematical Programming 17 (1979) 270–297.
C. Charalambous and A.R. Conn, “An efficient method to solve the minimax problem directly,”SIAM Journal on Numerical Analysis 15 (1978) 162–187.
F.H. Clarke, V.F. Dem'yanov and F. Giannessi, eds.,Nonsmooth Optimization and Related Topics (Plenum, New York, 1989).
V.F. Dem'yanov and V.N. Malozemov,Introduction to Minimax (Wiley, New York, 1974).
V.F. Dem'yanov and V. Vasil'ev,Nondifferentiable Optimization (Springer, New York, 1986).
G. Di Pillo and L. Grippo, “An exact penalty method with global convergence properties for nonlinear programming problems,”Mathematical Programming 36 (1986) 1–18.
G. Di Pillo, L. Grippo and S. Lucidi, “Superlinearly convergent algorithms for finite minimax problems,” Technical Report, IASI, National Research Council (Rome), to appear.
R.A. El-Attar, M. Vidyasagar and S.R.K. Dutta, “An algorithm forl l-approximation,”SIAM Journal on Numerical Analysis 16 (1979) 70–86.
R. Fletcher, “A model algorithm for composite nondifferentiable optimization problems,”Mathematical Programming Study 17 (1982) 67–76.
R. Fletcher, “Second order correction for nondifferentiable optimization,” in: G.A. Watson, ed.,Numerical Analysis (Springer, Berlin, 1982) pp. 85–114.
M. Gaudioso and M.F. Monaco, “A bundle type approach to the unconstrained minimization of convex nonsmooth functions,”Mathematical Programming 23 (1982) 216–226.
C. Gigola and S. Gomez, “A regularization method for solving the finite convex min—max problem,”SIAM Journal and Numerical Analysis 27 (1990) 1621–1634.
T. Glad and E. Polak, “A multiplier method with automatic limitation of penalty growth,”Mathematical Programming 17 (1979) 140–155.
A. Griewank, “On automatic differentiation,” in: M. Iri and K. Tanabe, eds.,Mathematical programming (Kluwer Academic Publishers, Tokyo) pp. 83–107.
L. Grippo, F. Lampariello and S. Lucidi, “A class of nonmonotone stabilization methods in unconstrained optimization,”Numerische Mathematik 59 (1991) 779–805.
J. Hald and K. Madsen, “Combined LP and quasi-Newton methods for minimax optimization,”Mathematical Programming 20 (1981) 49–62.
S.P. Han, “Variable metric methods for minimizing a class of nondifferentiable functions,”Mathematical Programming 20 (1981) 1–13.
M.R. Hestenes,Optimization Theory. The Finite Dimensional Case (Wiley, New York, 1975).
K.C. Kiwiel,Methods of Descent for Nondifferentiable Optimization, Lecture Notes in Mathematics No. 1133 (Springer, Berlin, 1985).
C. Lemaréchal, “An extension of Davidson method to nondifferentiable problems,”Mathematical Programming Study 3 (1975) 95–109.
C. Lemaréchal, “Numerical experiments in nonsmooth optimization,” in: E.A. Nurminskii, ed.,Progress in Nondifferentiable Optimization (IIASA Proceedings, Laxenburg, 1982).
C. Lemaréchal, “Nondifferentiable optimization,” in: G.L. Nemhauser, A.H.G. Rinnooy Kan and M.J. Todd, eds.,Handbooks in Operations Research and Management Science, Vol. 1: Optimization (North-Holland, Amsterdam, 1989) pp. 529–572.
C. Lemaréchal and R. Mifflin, eds.,Nonsmooth Optimization (Pergamon, Oxford, 1978).
C. Lemaréchal and R. Mifflin, “A set of nonsmooth optimization test problems,” in: C. Lemaréchal and R. Mifflin, eds.,Nonsmooth Optimization (Pergamon, Oxford, 1978).
S. Lucidi, “New results on a continuously differentiable exact penalty function,” Report R-277, IASI, National Research Council (Rome, 1989).
K. Madsen, “Minimization of non-linear approximation functions,” Ph.D. Thesis, Technical University of Denmark (Lyngby, 1985).
M.M. Mäkelä, “Nonsmooth optimization,” Ph.D. Thesis, University of Jyväskylä (Jyväskylä, 1990).
R. Mifflin, “An algorithm for constrained optimization with semismooth functions,”Mathematics of Operations Research 2 (1977) 191–207.
E. Polak, “Basics of minimax algorithms,” in: F.H. Clarke, V.F. Dem'yanov and F. Giannessi, eds.,Nonsmooth Optimization and Related Topics (Plenum, New York, 1989) pp. 343–369.
E. Polak, D.H. Mayne and J.E. Higgins, “Superlinearly convergent algorithm for min—max problems,”Journal of Optimization Theory and Applications 69 (1991) 407–439.
R.A. Polyak, “Smooth optimization methods for minimax problems,”SIAM Journal on Control and Optimization 26 (1988) 1274–1286.
B.N. Pshenichny and Y.M. Danilin,Numerical Methods in Extremal Problems (Mir, Moscow, 1978).
H. Schramm and J. Zowe, “A version of the bundle ideal for minimizing a nonsmooth function: conceptual idea, convergence analysis, numerical results,” Report N.206, DFG-Schwerpunktprogramms “Anwendungsbezogene Optimierung und Steuerung,” Universität Bayreuth (Bayreuth, 1990).
N.Z. Shor,Minimization Methods for Nondifferentiable Functions (Springer, Berlin, 1985).
P. Wolfe, “A Method of conjugate subgradients for minimizing nondifferentiable convex functions,”Mathematical Programming Study 3 (1975) 145–173.
Y. Yuan, “On the superlinear convergence of a trust region algorithm for nonsmooth optimization,”Mathematical Programming 31 (1985) 269–285.
I. Zang, “A smoothing-out technique for min—max optimization,”Mathematical Programming 19 (1980) 61–77.
J. Zowe, “Nondifferentiable optimization,” in: K. Schittkowski, eds.,Computational Mathematical Programming (Springer, Berlin, 1985).
Author information
Authors and Affiliations
Additional information
This research was partially supported by the National Research Program on “Metodi di ottimizzazione per le decisioni”, Ministero dell'Università e della Ricerca Scientifica e Tecnologica, Italy.
Rights and permissions
About this article
Cite this article
Di Pillo, G., Grippo, L. & Lucidi, S. A smooth method for the finite minimax problem. Mathematical Programming 60, 187–214 (1993). https://doi.org/10.1007/BF01580609
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01580609