American Institute of Mathematical Sciences

Advanced
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

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 & 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, (2001).   Google Scholar

[2]

D. P. Bertsekas, "Constrained Optimization and Lagrange Multiplier Methods,", Academic Press, (1982).   Google Scholar

[3]

C. Charalambous, Acceleration of the least $p$th algorithm for minimax optimization with engineering applications,, Math. Program., 19 (1979), 270.   Google Scholar

[4]

G. Dipillo, L. Grippo and S. Lucidi, A smooth method for the finite minimax problem,, Math. Program., 60 (1993), 187.   Google Scholar

[5]

J. P. Dussault, Augmented non-quadratic penalty algorithms,, Math. Program., 99 (2004), 467.   Google Scholar

[6]

G. D. Erdmann, "A New Minimax Algorithm and Its Application to Optics Problems,", Ph. D. Thesis, (2003).   Google Scholar

[7]

S. X. He and L. W. Zhang, Convergence of a dual algorithm for minimax problems,, Arch. Control Sci., 10 (2000), 47.   Google Scholar

[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.   Google Scholar

[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.  doi: 10.1017/S0004972700038673.  Google Scholar

[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.   Google Scholar

[11]

X. S. Li, An entropy-based aggregate method for minimax optimization,, Eng. Optim., 18 (1992), 277.   Google Scholar

[12]

L. Lukšan, C. Matonoha and J. Vlček, Primal interior-point method for large sparse minimax optimization,, Tech. Rep. V-941, (2005).   Google Scholar

[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.  doi: 10.1007/s10957-010-9759-1.  Google Scholar

[14]

E. Polak, On the mathematical foundations of nondifferentiable optimization in engineering design,, SIAM Rev., 29 (1987), 21.  doi: 10.1137/1029002.  Google Scholar

[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.   Google Scholar

[16]

E. Polak, "Optimization: Algorithms and Consistent Approximations,", Springer-Verlag, (1997).   Google Scholar

[17]

E. Polak, J. E. Higgins and D. Q. Mayne, A barrier function method for minimax problems,, Math. Program., 54 (1992), 155.   Google Scholar

[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.  doi: 10.1023/B:JOTA.0000006685.60019.3e.  Google Scholar

[19]

R. A. Polyak, Smooth optimization methods for minimax problems,, SIAM J. Control Optim., 26 (1988), 1274.   Google Scholar

[20]

R. A. Polyak, Nonlinear rescaling in discrete minimax,, in, (2000).   Google Scholar

[21]

R. A. Polyak, Modified barrier function: Theory and mehtods,, Math. Program., 54 (1992), 177.   Google Scholar

[22]

R. A. Polyak, Log-Sigmoid multipliers method in constrained optimization,, Ann. Oper. Res., 101 (2001), 427.   Google Scholar

[23]

R. A. Polyak, Nonlinear rescaling vs. smoothing technique in convex optimization,, Math. Program., 92 (2002), 197.   Google Scholar

[24]

S. Xu, Smoothing method for minimax problems,, Comput. Optim. Appl., 20 (2001), 267.   Google Scholar

[25]

S. E. Sussman-Fort, Approximate direct-search minimax circuit optimization,, Int. J. Numer. Methods Eng., 28 (1989), 359.   Google Scholar

[26]

F. S. Wang and Y. P. Wang, Nonmontone algorithm for minimax optimization problems,, Appl. Math. Comput., 217 (2011), 6296.   Google Scholar

[27]

A. D. Warren, L. S. Lasdon and D. F. Suchman, Optimization in engineering design,, Proc. IEEE, 55 (1967), 1885.   Google Scholar

[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.  doi: 10.1016/j.amc.2007.10.070.  Google Scholar

[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.  doi: 10.1142/S021759590800178X.  Google Scholar

[30]

L. W. Zhang and H. W. Tang, A maximum entropy algorithm with parameters for solving minimax problem,, Arch. Control Sci., 6 (1997), 47.   Google Scholar

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, (2001).   Google Scholar

[2]

D. P. Bertsekas, "Constrained Optimization and Lagrange Multiplier Methods,", Academic Press, (1982).   Google Scholar

[3]

C. Charalambous, Acceleration of the least $p$th algorithm for minimax optimization with engineering applications,, Math. Program., 19 (1979), 270.   Google Scholar

[4]

G. Dipillo, L. Grippo and S. Lucidi, A smooth method for the finite minimax problem,, Math. Program., 60 (1993), 187.   Google Scholar

[5]

J. P. Dussault, Augmented non-quadratic penalty algorithms,, Math. Program., 99 (2004), 467.   Google Scholar

[6]

G. D. Erdmann, "A New Minimax Algorithm and Its Application to Optics Problems,", Ph. D. Thesis, (2003).   Google Scholar

[7]

S. X. He and L. W. Zhang, Convergence of a dual algorithm for minimax problems,, Arch. Control Sci., 10 (2000), 47.   Google Scholar

[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.   Google Scholar

[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.  doi: 10.1017/S0004972700038673.  Google Scholar

[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.   Google Scholar

[11]

X. S. Li, An entropy-based aggregate method for minimax optimization,, Eng. Optim., 18 (1992), 277.   Google Scholar

[12]

L. Lukšan, C. Matonoha and J. Vlček, Primal interior-point method for large sparse minimax optimization,, Tech. Rep. V-941, (2005).   Google Scholar

[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.  doi: 10.1007/s10957-010-9759-1.  Google Scholar

[14]

E. Polak, On the mathematical foundations of nondifferentiable optimization in engineering design,, SIAM Rev., 29 (1987), 21.  doi: 10.1137/1029002.  Google Scholar

[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.   Google Scholar

[16]

E. Polak, "Optimization: Algorithms and Consistent Approximations,", Springer-Verlag, (1997).   Google Scholar

[17]

E. Polak, J. E. Higgins and D. Q. Mayne, A barrier function method for minimax problems,, Math. Program., 54 (1992), 155.   Google Scholar

[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.  doi: 10.1023/B:JOTA.0000006685.60019.3e.  Google Scholar

[19]

R. A. Polyak, Smooth optimization methods for minimax problems,, SIAM J. Control Optim., 26 (1988), 1274.   Google Scholar

[20]

R. A. Polyak, Nonlinear rescaling in discrete minimax,, in, (2000).   Google Scholar

[21]

R. A. Polyak, Modified barrier function: Theory and mehtods,, Math. Program., 54 (1992), 177.   Google Scholar

[22]

R. A. Polyak, Log-Sigmoid multipliers method in constrained optimization,, Ann. Oper. Res., 101 (2001), 427.   Google Scholar

[23]

R. A. Polyak, Nonlinear rescaling vs. smoothing technique in convex optimization,, Math. Program., 92 (2002), 197.   Google Scholar

[24]

S. Xu, Smoothing method for minimax problems,, Comput. Optim. Appl., 20 (2001), 267.   Google Scholar

[25]

S. E. Sussman-Fort, Approximate direct-search minimax circuit optimization,, Int. J. Numer. Methods Eng., 28 (1989), 359.   Google Scholar

[26]

F. S. Wang and Y. P. Wang, Nonmontone algorithm for minimax optimization problems,, Appl. Math. Comput., 217 (2011), 6296.   Google Scholar

[27]

A. D. Warren, L. S. Lasdon and D. F. Suchman, Optimization in engineering design,, Proc. IEEE, 55 (1967), 1885.   Google Scholar

[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.  doi: 10.1016/j.amc.2007.10.070.  Google Scholar

[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.  doi: 10.1142/S021759590800178X.  Google Scholar

[30]

L. W. Zhang and H. W. Tang, A maximum entropy algorithm with parameters for solving minimax problem,, Arch. Control Sci., 6 (1997), 47.   Google Scholar

[1]

Jiangxing Wang. Convergence analysis of an accurate and efficient method for nonlinear Maxwell's equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2429-2440. doi: 10.3934/dcdsb.2020185
[2]

Namsu Ahn, Soochan Kim. Optimal and heuristic algorithms for the multi-objective vehicle routing problem with drones for military surveillance operations. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021037
[3]

Hailing Xuan, Xiaoliang Cheng. Numerical analysis and simulation of an adhesive contact problem with damage and long memory. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2781-2804. doi: 10.3934/dcdsb.2020205
[4]

Enkhbat Rentsen, Battur Gompil. Generalized nash equilibrium problem based on malfatti's problem. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 209-220. doi: 10.3934/naco.2020022
[5]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021
[6]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271
[7]

Hildeberto E. Cabral, Zhihong Xia. Subharmonic solutions in the restricted three-body problem. Discrete & Continuous Dynamical Systems - A, 1995, 1 (4) : 463-474. doi: 10.3934/dcds.1995.1.463
[8]

Michel Chipot, Mingmin Zhang. On some model problem for the propagation of interacting species in a special environment. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020401
[9]

Fritz Gesztesy, Helge Holden, Johanna Michor, Gerald Teschl. The algebro-geometric initial value problem for the Ablowitz-Ladik hierarchy. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 151-196. doi: 10.3934/dcds.2010.26.151
[10]

Gloria Paoli, Gianpaolo Piscitelli, Rossanno Sannipoli. A stability result for the Steklov Laplacian Eigenvalue Problem with a spherical obstacle. Communications on Pure & Applied Analysis, 2021, 20 (1) : 145-158. doi: 10.3934/cpaa.2020261
[11]

Marco Ghimenti, Anna Maria Micheletti. Compactness results for linearly perturbed Yamabe problem on manifolds with boundary. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1757-1778. doi: 10.3934/dcdss.2020453
[12]

Rongchang Liu, Jiangyuan Li, Duokui Yan. New periodic orbits in the planar equal-mass three-body problem. Discrete & Continuous Dynamical Systems - A, 2018, 38 (4) : 2187-2206. doi: 10.3934/dcds.2018090
[13]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056
[14]

Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028
[15]

Yuri Chekanov, Felix Schlenk. Notes on monotone Lagrangian twist tori. Electronic Research Announcements, 2010, 17: 104-121. doi: 10.3934/era.2010.17.104
[16]

Jiaquan Liu, Xiangqing Liu, Zhi-Qiang Wang. Sign-changing solutions for a parameter-dependent quasilinear equation. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1779-1799. doi: 10.3934/dcdss.2020454
[17]

Habib Ammari, Josselin Garnier, Vincent Jugnon. Detection, reconstruction, and characterization algorithms from noisy data in multistatic wave imaging. Discrete & Continuous Dynamical Systems - S, 2015, 8 (3) : 389-417. doi: 10.3934/dcdss.2015.8.389
[18]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024
[19]

Jan Prüss, Laurent Pujo-Menjouet, G.F. Webb, Rico Zacher. Analysis of a model for the dynamics of prions. Discrete & Continuous Dynamical Systems - B, 2006, 6 (1) : 225-235. doi: 10.3934/dcdsb.2006.6.225
[20]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (46)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences