A class of nonlinear Lagrangian algorithms for minimax problems

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

January 2013, 9(1): 75-97. doi: 10.3934/jimo.2013.9.75

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, China, China

Received December 2011 Revised May 2012 Published December 2012

Abstract
Related Papers

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: controlling parameter, Nonlinear Lagrangian algorithms, unconstrained minimax problem, dual problem., convergence analysis.

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

Citation: Suxiang He, Yunyun Nie. A class of nonlinear Lagrangian algorithms for minimax problems. Journal of Industrial and Management Optimization, 2013, 9 (1) : 75-97. doi: 10.3934/jimo.2013.9.75

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.

show all references

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.

[1]	Hssaine Boualam, Ahmed Roubi. Augmented Lagrangian dual for nonconvex minimax fractional programs and proximal bundle algorithms for its resolution. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022100
[2]	Rafał Kamocki, Marek Majewski. On the continuous dependence of solutions to a fractional Dirichlet problem. The case of saddle points. Discrete and Continuous Dynamical Systems - B, 2014, 19 (8) : 2557-2568. doi: 10.3934/dcdsb.2014.19.2557
[3]	Hssaine Boualam, Ahmed Roubi. Dual algorithms based on the proximal bundle method for solving convex minimax fractional programs. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1897-1920. doi: 10.3934/jimo.2018128
[4]	Brahim El Asri. The value of a minimax problem involving impulse control. Journal of Dynamics and Games, 2019, 6 (1) : 1-17. doi: 10.3934/jdg.2019001
[5]	Xiayang Zhang, Yuqian Kong, Shanshan Liu, Yuan Shen. A relaxed parameter condition for the primal-dual hybrid gradient method for saddle-point problem. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022008
[6]	Yang Li, Yonghong Ren, Yun Wang, Jian Gu. Convergence analysis of a nonlinear Lagrangian method for nonconvex semidefinite programming with subproblem inexactly solved. Journal of Industrial and Management Optimization, 2015, 11 (1) : 65-81. doi: 10.3934/jimo.2015.11.65
[7]	Gabriella Pinzari. Global Kolmogorov tori in the planetary $\boldsymbol N$-body problem. Announcement of result. Electronic Research Announcements, 2015, 22: 55-75. doi: 10.3934/era.2015.22.55
[8]	Yazheng Dang, Jie Sun, Honglei Xu. Inertial accelerated algorithms for solving a split feasibility problem. Journal of Industrial and Management Optimization, 2017, 13 (3) : 1383-1394. doi: 10.3934/jimo.2016078
[9]	Luis Bayón, Jose Maria Grau, Maria del Mar Ruiz, Pedro Maria Suárez. A hydrothermal problem with non-smooth Lagrangian. Journal of Industrial and Management Optimization, 2014, 10 (3) : 761-776. doi: 10.3934/jimo.2014.10.761
[10]	Simon Hubmer, Andreas Neubauer, Ronny Ramlau, Henning U. Voss. On the parameter estimation problem of magnetic resonance advection imaging. Inverse Problems and Imaging, 2018, 12 (1) : 175-204. doi: 10.3934/ipi.2018007
[11]	Changjun Yu, Kok Lay Teo, Liansheng Zhang, Yanqin Bai. On a refinement of the convergence analysis for the new exact penalty function method for continuous inequality constrained optimization problem. Journal of Industrial and Management Optimization, 2012, 8 (2) : 485-491. doi: 10.3934/jimo.2012.8.485
[12]	David Bourne, Howard Elman, John E. Osborn. A Non-Self-Adjoint Quadratic Eigenvalue Problem Describing a Fluid-Solid Interaction Part II: Analysis of Convergence. Communications on Pure and Applied Analysis, 2009, 8 (1) : 143-160. doi: 10.3934/cpaa.2009.8.143
[13]	Siqi Li, Weiyi Qian. Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization. Numerical Algebra, Control and Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37
[14]	Antonio Giorgilli, Stefano Marmi. Convergence radius in the Poincaré-Siegel problem. Discrete and Continuous Dynamical Systems - S, 2010, 3 (4) : 601-621. doi: 10.3934/dcdss.2010.3.601
[15]	S. J. Li, Z. M. Fang. On the stability of a dual weak vector variational inequality problem. Journal of Industrial and Management Optimization, 2008, 4 (1) : 155-165. doi: 10.3934/jimo.2008.4.155
[16]	Andaluzia Matei, Mircea Sofonea. Dual formulation of a viscoplastic contact problem with unilateral constraint. Discrete and Continuous Dynamical Systems - S, 2013, 6 (6) : 1587-1598. doi: 10.3934/dcdss.2013.6.1587
[17]	Thi Tuyet Trang Chau, Pierre Ailliot, Valérie Monbet, Pierre Tandeo. Comparison of simulation-based algorithms for parameter estimation and state reconstruction in nonlinear state-space models. Discrete and Continuous Dynamical Systems - S, 2022 doi: 10.3934/dcdss.2022054
[18]	Saeid Abbasi-Parizi, Majid Aminnayeri, Mahdi Bashiri. Robust solution for a minimax regret hub location problem in a fuzzy-stochastic environment. Journal of Industrial and Management Optimization, 2018, 14 (3) : 1271-1295. doi: 10.3934/jimo.2018083
[19]	Hua-Ping Wu, Min Huang, W. H. Ip, Qun-Lin Fan. Algorithms for single-machine scheduling problem with deterioration depending on a novel model. Journal of Industrial and Management Optimization, 2017, 13 (2) : 681-695. doi: 10.3934/jimo.2016040
[20]	Yifan Xu. Algorithms by layer-decomposition for the subgraph recognition problem with attributes. Journal of Industrial and Management Optimization, 2005, 1 (3) : 337-343. doi: 10.3934/jimo.2005.1.337

2021 Impact Factor: 1.411

Tools

Metrics

Other articles
by authors

on AIMS
Suxiang He Yunyun Nie
on Google Scholar
Suxiang He Yunyun Nie

[Back to Top]