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]

Min Chen, Olivier Goubet, Shenghao Li. Mathematical analysis of bump to bucket problem. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5567-5580. doi: 10.3934/cpaa.2020251
[2]

Kimie Nakashima. Indefinite nonlinear diffusion problem in population genetics. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3837-3855. doi: 10.3934/dcds.2020169
[3]

George W. Patrick. The geometry of convergence in numerical analysis. Journal of Computational Dynamics, 2021, 8 (1) : 33-58. doi: 10.3934/jcd.2021003
[4]

Vo Van Au, Hossein Jafari, Zakia Hammouch, Nguyen Huy Tuan. On a final value problem for a nonlinear fractional pseudo-parabolic equation. Electronic Research Archive, 2021, 29 (1) : 1709-1734. doi: 10.3934/era.2020088
[5]

Nguyen Huu Can, Nguyen Huy Tuan, Donal O'Regan, Vo Van Au. On a final value problem for a class of nonlinear hyperbolic equations with damping term. Evolution Equations & Control Theory, 2021, 10 (1) : 103-127. doi: 10.3934/eect.2020053
[6]

Wenjun Liu, Hefeng Zhuang. Global attractor for a suspension bridge problem with a nonlinear delay term in the internal feedback. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 907-942. doi: 10.3934/dcdsb.2020147
[7]

Ningyu Sha, Lei Shi, Ming Yan. Fast algorithms for robust principal component analysis with an upper bound on the rank. Inverse Problems & Imaging, 2021, 15 (1) : 109-128. doi: 10.3934/ipi.2020067
[8]

Vo Van Au, Mokhtar Kirane, Nguyen Huy Tuan. On a terminal value problem for a system of parabolic equations with nonlinear-nonlocal diffusion terms. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1579-1613. doi: 10.3934/dcdsb.2020174
[9]

Matúš Tibenský, Angela Handlovičová. Convergence analysis of the discrete duality finite volume scheme for the regularised Heston model. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1181-1195. doi: 10.3934/dcdss.2020226
[10]

Qingfang Wang, Hua Yang. Solutions of nonlocal problem with critical exponent. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5591-5608. doi: 10.3934/cpaa.2020253
[11]

Giulio Ciraolo, Antonio Greco. An overdetermined problem associated to the Finsler Laplacian. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021004
[12]

Guoliang Zhang, Shaoqin Zheng, Tao Xiong. A conservative semi-Lagrangian finite difference WENO scheme based on exponential integrator for one-dimensional scalar nonlinear hyperbolic equations. Electronic Research Archive, 2021, 29 (1) : 1819-1839. doi: 10.3934/era.2020093
[13]

Wei Ouyang, Li Li. Hölder strong metric subregularity and its applications to convergence analysis of inexact Newton methods. Journal of Industrial & Management Optimization, 2021, 17 (1) : 169-184. doi: 10.3934/jimo.2019105
[14]

Stefano Bianchini, Paolo Bonicatto. Forward untangling and applications to the uniqueness problem for the continuity equation. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020384
[15]

Kien Trung Nguyen, Vo Nguyen Minh Hieu, Van Huy Pham. Inverse group 1-median problem on trees. Journal of Industrial & Management Optimization, 2021, 17 (1) : 221-232. doi: 10.3934/jimo.2019108
[16]

Xinfu Chen, Huiqiang Jiang, Guoqing Liu. Boundary spike of the singular limit of an energy minimizing problem. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3253-3290. doi: 10.3934/dcds.2020124
[17]

Constantine M. Dafermos. A variational approach to the Riemann problem for hyperbolic conservation laws. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 185-195. doi: 10.3934/dcds.2009.23.185
[18]

Marco Ghimenti, Anna Maria Micheletti. Compactness results for linearly perturbed Yamabe problem on manifolds with boundary. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020453
[19]

Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031
[20]

Fioralba Cakoni, Pu-Zhao Kow, Jenn-Nan Wang. The interior transmission eigenvalue problem for elastic waves in media with obstacles. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020075

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences