A class of nonlinear Lagrangian algorithms for minimax problems

Suxiang He; Yunyun Nie

doi:10.3934/jimo.2013.9.75

Article Contents

2013, Volume 9, Issue 1: 75-97. Doi: 10.3934/jimo.2013.9.75

This issue Previous Article Stability analysis for set-valued vector mixed variational inequalities in real reflexive Banach spaces Next Article Solution properties and error bounds for semi-infinite complementarity problems

A class of nonlinear Lagrangian algorithms for minimax problems

Suxiang He^1, and
Yunyun Nie^1,

1.
School of Science, Wuhan University of Technology, Wuhan Hubei, 430070

Received: November 30, 2011

Revised: April 30, 2012

Published: December 2012

Abstract Related Papers Cited by

Abstract

This paper studies a class of nonlinear Lagrangian algorithms for solving unconstrained minimax problems, which will provide an approach to constructing a concrete and novel Lagrangian algorithm and simplify the relevant theory analysis. A class of nonlinear Lagrangians is constructed and a set of mild conditions on them are proposed to guarantee the convergence theory of the corresponding algorithms. The unified convergence analysis framework for the class of algorithms is established. It is shown that the sequence solutions obtained by the class of algorithms are Q-linearly convergent when the controlling parameter is less than a threshold under some assumptions and the error bounds of the sequence solutions are obtained at the same time. The properties of dual problem framework based on the unified nonlinear Lagrangians are analyzed, which the classical Lagrangian lacks. Furthermore, it is presented that the proposed class of nonlinear Lagrangians contains four well-known nonlinear Lagrangians for unconstrained minimax problems appearing in the literatures. At last, numerical results for ten typical test problems are reported, based on the four nonlinear Lagrangians in the proposed class.

Keywords:

Mathematics Subject Classification: Primary: 90C47; Secondary: 49K35.

Citation:

Related Papers

Cited by

References

[1]	A. Ben-Tal and A. Nemirovski, "Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications," MPS/SIAM Ser. Optim. 2, SIAM, Philadelphia, 2001.
[2]	D. P. Bertsekas, "Constrained Optimization and Lagrange Multiplier Methods," Academic Press, New York, 1982.
[3]	C. Charalambous, Acceleration of the least $p$th algorithm for minimax optimization with engineering applications, Math. Program., 19 (1979), 270-297.
[4]	G. Dipillo, L. Grippo and S. Lucidi, A smooth method for the finite minimax problem, Math. Program., 60 (1993), 187-214.
[5]	J. P. Dussault, Augmented non-quadratic penalty algorithms, Math. Program., 99 (2004), 467-486.
[6]	G. D. Erdmann, "A New Minimax Algorithm and Its Application to Optics Problems," Ph. D. Thesis, University of Minnesota, USA, 2003.
[7]	S. X. He and L. W. Zhang, Convergence of a dual algorithm for minimax problems, Arch. Control Sci., 10 (2000), 47-60.
[8]	Q. J. Hu, Y. Chen, N. P. Chen and X. Q. Li, A modified SQP algorithm for minimax problems, J. Math. Anal. Appl., 360 (2009), 211-222.
[9]	J. B. Jian, R. Quan and X. L. Zhang, Generalized monotone line search algorithm for degenerate nonlinear minimax problems, Bull. Austral. Math. Soc., 73 (2006), 117-127.doi: 10.1017/S0004972700038673.
[10]	J. B. Jian, R. Quan and X. L. Zhang, Feasible generalized monotone line search SQP algorithm for nonlinear minimax problems with inequality constraints, J. Comput. Appl. Math., 205 (2007), 406-429.
[11]	X. S. Li, An entropy-based aggregate method for minimax optimization, Eng. Optim., 18 (1992), 277-285.
[12]	L. Lukšan, C. Matonoha and J. Vlček, Primal interior-point method for large sparse minimax optimization, Tech. Rep. V-941, ICS AS CR, 2005.
[13]	E. Y. Pee and J. O. Royset, On solving large-scale finite minimax problems using exponential smoothing, J. Optimiz. Theory App., 148 (2011), 390-1021.doi: 10.1007/s10957-010-9759-1.
[14]	E. Polak, On the mathematical foundations of nondifferentiable optimization in engineering design, SIAM Rev., 29 (1987), 21-89.doi: 10.1137/1029002.
[15]	E. Polak, S. Salcudean and D. Q. Mayne, Adaptive control of ARMA plants using worst-case design by semi-infinite optimization, IEEE Trans. Autom. Control, 32 (1987), 388-397.
[16]	E. Polak, "Optimization: Algorithms and Consistent Approximations," Springer-Verlag, New York, NY, 1997.
[17]	E. Polak, J. E. Higgins and D. Q. Mayne, A barrier function method for minimax problems, Math. Program., 54 (1992), 155-176.
[18]	E. Polak, J. O. Royset and R. S. Womersley, Algorithms with adaptive smoothing for finite minimax problems, J. Optimiz. Theory App., 119 (2003), 459-484.doi: 10.1023/B:JOTA.0000006685.60019.3e.
[19]	R. A. Polyak, Smooth optimization methods for minimax problems, SIAM J. Control Optim., 26 (1988), 1274-1286.
[20]	R. A. Polyak, Nonlinear rescaling in discrete minimax, in "Nonsmooth/Nonconvex Mechanics: Modeling, Analysis, Numerical Methods" (eds. R. Ogden and G. Stavroulakis), Kluwer Academic Publishers, Norwell, (2000) (with L. Griva, J. Sobieski).
[21]	R. A. Polyak, Modified barrier function: Theory and mehtods, Math. Program., 54 (1992), 177-222.
[22]	R. A. Polyak, Log-Sigmoid multipliers method in constrained optimization, Ann. Oper. Res., 101 (2001), 427-460.
[23]	R. A. Polyak, Nonlinear rescaling vs. smoothing technique in convex optimization, Math. Program., 92 (2002), 197-235.
[24]	S. Xu, Smoothing method for minimax problems, Comput. Optim. Appl., 20 (2001), 267-279.
[25]	S. E. Sussman-Fort, Approximate direct-search minimax circuit optimization, Int. J. Numer. Methods Eng., 28 (1989), 359-368.
[26]	F. S. Wang and Y. P. Wang, Nonmontone algorithm for minimax optimization problems, Appl. Math. Comput., 217 (2011), 6296-6308.
[27]	A. D. Warren, L. S. Lasdon and D. F. Suchman, Optimization in engineering design, Proc. IEEE, 55 (1967), 1885-1897.
[28]	F. Ye, H. W. Liu, S. S. Zhou and S. Y. Liu, A smoothing trust-region Newton-CG method for minimax problem, Appl. Math. Comput., 199 (2008), 581-589.doi: 10.1016/j.amc.2007.10.070.
[29]	L. W. Zhang, Y. H. Ren, Y. Wu and X. T. Xiao, A class of nonlinear Lagrangians: Theory and algorithm, Asia-Pac. J. Oper. Res., 25 (2008), 327-371.doi: 10.1142/S021759590800178X.
[30]	L. W. Zhang and H. W. Tang, A maximum entropy algorithm with parameters for solving minimax problem, Arch. Control Sci., 6 (1997), 47-59.