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, SIAM, Philadelphia, 2001.  Google Scholar

[2]

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

[3]

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

[4]

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

[5]

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

[6]

G. D. Erdmann, "A New Minimax Algorithm and Its Application to Optics Problems," Ph. D. Thesis, University of Minnesota, USA, 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-60.  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-222.  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-127. 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-429.  Google Scholar

[11]

X. S. Li, An entropy-based aggregate method for minimax optimization, Eng. Optim., 18 (1992), 277-285. 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, ICS AS CR, 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-1021. 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-89. 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-397.  Google Scholar

[16]

E. Polak, "Optimization: Algorithms and Consistent Approximations," Springer-Verlag, New York, NY, 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-176.  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-484. 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-1286.  Google Scholar

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

[21]

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

[22]

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

[23]

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

[24]

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

[25]

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

[26]

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

[27]

A. D. Warren, L. S. Lasdon and D. F. Suchman, Optimization in engineering design, Proc. IEEE, 55 (1967), 1885-1897. 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-589. 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-371. 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-59.  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, SIAM, Philadelphia, 2001.  Google Scholar

[2]

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

[3]

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

[4]

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

[5]

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

[6]

G. D. Erdmann, "A New Minimax Algorithm and Its Application to Optics Problems," Ph. D. Thesis, University of Minnesota, USA, 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-60.  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-222.  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-127. 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-429.  Google Scholar

[11]

X. S. Li, An entropy-based aggregate method for minimax optimization, Eng. Optim., 18 (1992), 277-285. 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, ICS AS CR, 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-1021. 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-89. 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-397.  Google Scholar

[16]

E. Polak, "Optimization: Algorithms and Consistent Approximations," Springer-Verlag, New York, NY, 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-176.  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-484. 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-1286.  Google Scholar

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

[21]

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

[22]

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

[23]

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

[24]

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

[25]

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

[26]

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

[27]

A. D. Warren, L. S. Lasdon and D. F. Suchman, Optimization in engineering design, Proc. IEEE, 55 (1967), 1885-1897. 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-589. 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-371. 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-59.  Google Scholar

[1]

Rafał Kamocki, Marek Majewski. On the continuous dependence of solutions to a fractional Dirichlet problem. The case of saddle points. Discrete & Continuous Dynamical Systems - B, 2014, 19 (8) : 2557-2568. doi: 10.3934/dcdsb.2014.19.2557
[2]

Hssaine Boualam, Ahmed Roubi. Dual algorithms based on the proximal bundle method for solving convex minimax fractional programs. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1897-1920. doi: 10.3934/jimo.2018128
[3]

Brahim El Asri. The value of a minimax problem involving impulse control. Journal of Dynamics & Games, 2019, 6 (1) : 1-17. doi: 10.3934/jdg.2019001
[4]

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 & Management Optimization, 2015, 11 (1) : 65-81. doi: 10.3934/jimo.2015.11.65
[5]

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
[6]

Yazheng Dang, Jie Sun, Honglei Xu. Inertial accelerated algorithms for solving a split feasibility problem. Journal of Industrial & Management Optimization, 2017, 13 (3) : 1383-1394. doi: 10.3934/jimo.2016078
[7]

Luis Bayón, Jose Maria Grau, Maria del Mar Ruiz, Pedro Maria Suárez. A hydrothermal problem with non-smooth Lagrangian. Journal of Industrial & Management Optimization, 2014, 10 (3) : 761-776. doi: 10.3934/jimo.2014.10.761
[8]

Simon Hubmer, Andreas Neubauer, Ronny Ramlau, Henning U. Voss. On the parameter estimation problem of magnetic resonance advection imaging. Inverse Problems & Imaging, 2018, 12 (1) : 175-204. doi: 10.3934/ipi.2018007
[9]

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 & Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37
[10]

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 & Management Optimization, 2012, 8 (2) : 485-491. doi: 10.3934/jimo.2012.8.485
[11]

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 & Applied Analysis, 2009, 8 (1) : 143-160. doi: 10.3934/cpaa.2009.8.143
[12]

S. J. Li, Z. M. Fang. On the stability of a dual weak vector variational inequality problem. Journal of Industrial & Management Optimization, 2008, 4 (1) : 155-165. doi: 10.3934/jimo.2008.4.155
[13]

Andaluzia Matei, Mircea Sofonea. Dual formulation of a viscoplastic contact problem with unilateral constraint. Discrete & Continuous Dynamical Systems - S, 2013, 6 (6) : 1587-1598. doi: 10.3934/dcdss.2013.6.1587
[14]

Antonio Giorgilli, Stefano Marmi. Convergence radius in the Poincaré-Siegel problem. Discrete & Continuous Dynamical Systems - S, 2010, 3 (4) : 601-621. doi: 10.3934/dcdss.2010.3.601
[15]

Saeid Abbasi-Parizi, Majid Aminnayeri, Mahdi Bashiri. Robust solution for a minimax regret hub location problem in a fuzzy-stochastic environment. Journal of Industrial & Management Optimization, 2018, 14 (3) : 1271-1295. doi: 10.3934/jimo.2018083
[16]

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 & Management Optimization, 2017, 13 (2) : 681-695. doi: 10.3934/jimo.2016040
[17]

Yifan Xu. Algorithms by layer-decomposition for the subgraph recognition problem with attributes. Journal of Industrial & Management Optimization, 2005, 1 (3) : 337-343. doi: 10.3934/jimo.2005.1.337
[18]

Ethel Mokotoff. Algorithms for bicriteria minimization in the permutation flow shop scheduling problem. Journal of Industrial & Management Optimization, 2011, 7 (1) : 253-282. doi: 10.3934/jimo.2011.7.253
[19]

Xueyong Wang, Yiju Wang, Gang Wang. An accelerated augmented Lagrangian method for multi-criteria optimization problem. Journal of Industrial & Management Optimization, 2020, 16 (1) : 1-9. doi: 10.3934/jimo.2018136
[20]

Giuseppe Marino, Hong-Kun Xu. Convergence of generalized proximal point algorithms. Communications on Pure & Applied Analysis, 2004, 3 (4) : 791-808. doi: 10.3934/cpaa.2004.3.791

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences