Next Articles

AN AUGMENTED LAGRANGIAN TRUST REGION METHOD WITH A BI-OBJECT STRATEGY

Caixia Kou1, Zhongwen Chen2, Yuhong Dai3, Haifei Han2   

  1. 1. School of Sciences, Beijing University of Posts and Telecommunications, Beijing 100876, China;
    2. School of Mathematical Sciences, Soochow University, Suzhou 215006, China;
    3. LSEC, ICMSEC, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China
  • Received:2016-12-28 Revised:2017-04-26 Online:2018-05-15 Published:2018-05-15
  • Supported by:

    The research of Kou is supported by Chinese NSF grant (Nos. 11401038, 11471052); the research of Chen is supported by Chinese NSF grant (No. 11371273), and the research of Dai is supported by the Chinese NSF (Nos. 11631013, 11331012, 71331001) and the National 973 Program of China (No. 2015CB856000).

Caixia Kou, Zhongwen Chen, Yuhong Dai, Haifei Han. AN AUGMENTED LAGRANGIAN TRUST REGION METHOD WITH A BI-OBJECT STRATEGY[J]. Journal of Computational Mathematics, 2018, 36(3): 331-350.

An augmented Lagrangian trust region method with a bi-object strategy is proposed for solving nonlinear equality constrained optimization, which falls in between penalty-type methods and penalty-free ones. At each iteration, a trial step is computed by minimizing a quadratic approximation model to the augmented Lagrangian function within a trust region. The model is a standard trust region subproblem for unconstrained optimization and hence can efficiently be solved by many existing methods. To choose the penalty parameter, an auxiliary trust region subproblem is introduced related to the constraint violation. It turns out that the penalty parameter need not be monotonically increasing and will not tend to infinity. A bi-object strategy, which is related to the objective function and the measure of constraint violation, is utilized to decide whether the trial step will be accepted or not. Global convergence of the method is established under mild assumptions. Numerical experiments are made, which illustrate the efficiency of the algorithm on various difficult situations.

CLC Number: 

[1] R. Andreani, E.G. Birgin, J.M. Martínez and M.L. Schuverdt, Augmented Lagrangian methods under the constant positive linear dependence constraint qualification, Math. Program., 111(2008), 5-32.

[2] N.S. Aybat and G. Iyengar, A first-order augmented Lagrangian method for compressed sensing, SIAM J. Optim., 22(2012), 429-459.

[3] D.P. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods, Athena Scientific, Belmont, Massachusetts, 1996.

[4] E.G. Birgin and J.M. Martínez, Augmented Lagrangian method with nonmonotone penalty parameters for constrained optimization, Comput. Optim. Appl., 51(2012), 941-965.

[5] P.T. Boggs and J.W. Tolle, Sequential quadratic programming, Acta Numer., 4(1995), 1-51.

[6] S. Boyd, N. Parikh, E. Chu, B. Peleato and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends in Machine Learning, 3:1(2011), 1-122.

[7] R.H. Byrd, G. Lopez-Calva and J. Nocedal, A line search exact penalty method using steering rules, Math. Program., 133(2012), 39-73.

[8] R.H. Byrd, J. Nocedal and R.A. Waltz, Steering exact penalty methods, Optim. Methods Softw., 23:2(2008), 197-213.

[9] Z.W. Chen and Y.H. Dai, A line search exact penalty method with bi-object strategy for nonlinear constrained optimization, J. Comput. Appl. Math., 300(2016), 245-258.

[10] L. Chen and D. Goldfarb, Interior-point l2 penalty methods for nonlinear programming with strong global convergence properties, Math. Program., 108:1, (2006), 1-36.

[11] A.R. Conn, N.I.M. Gould and Ph. L. Toint, A globally convergent augmented Lagrangian algorithm for optimization with general constraints and simple bounds, SIAM J. Numer. Anal., 28(1991), 545-572.

[12] A.R. Conn, N.I.M. Gould and Ph. L. Toint, Lancelot:A Fortran Package for Large Scale Nonlinear Optimization (Released A), Springer, New York, 1992.

[13] R. Fletcher, Practical Methods of Optimization, 2nd ed., John Wiley and Sons, Chichester, UK, 1987.

[14] R. Fletcher, S. Leyffer and Ph. L. Toint, On the global convergence of a filter-SQP algorithm, SIAM J. Optim., 13:1(2002), 44-59.

[15] H.W. Ge and Z.W. Chen, A penalty-free method with line search for nonlinear equality constrained optimization, Appl. Math. Model., 37(2013), 9934-9949.

[16] N.I.M. Gould and P.L. Toint, Nonlinear programming without a penalty function or a filter, Math. Program., 122(2010), 155-196.

[17] M.R. Hestense, Multiplier and gradient method, J. Optim. Theory Appl., 4(1969), 303-320.

[18] X.W. Liu and Y.X. Yuan, A robust algorithm for optimization with general equality and inequality constraints, SIAM J. Sci. Comput., 22(2000), 517-534.

[19] X W. Liu and Y.X. Yuan, A sequential quadratic programming method without a penalty function or a filter for nonlinear equality constrained optimization, SIAM J. Optim., 21(2011), 545-571.

[20] L.F. Niu and Y.X. Yuan, A trust-region algorithm for nonlinear constrained optimization, J. Comput. Math., 1(2010), 72-86.

[21] J. Nocedal and S.J. Wright, Numerical Optimization, Springer, 2nd ed., 2006.

[22] M.J.D. Powell, A method for nonlinear constraints in minimization problems, in Optimization, Fletcher R., ed., Academic Press, London, 1969, 283-298.

[23] S.Q. Qiu and Z.W. Chen, A globally convergent penalty-free method for optimization with general constraints and simple bounds, Acta Appl. Math., 142, (2016), 39-60.

[24] X. Wang and Y. X. Yuan, An augmented Lagrangian trust region method for equality constrained optimization, Optim. methods softw., 30(2015), 559-582.

[25] J. Yang, Y. Zhang and W. Yin, A fast alternating direction method for tv11-12 signal reconstruction from partial fourier data, IEEE J. Sel. Top. Signal Proces., 4(2010), 288-297.

[26] Y.X. Yuan, On the convergence of a new trust region algorithm, Numer. Math., 70(1995), 515-539.

[27] Y.X. Yuan, Recent advances in trust region algorithms, Math. Program., 151(2015), 249-281.
[1] Xiaoyu Wang, Ya-xiang Yuan. STOCHASTIC TRUST-REGION METHODS WITH TRUST-REGION RADIUS DEPENDING ON PROBABILISTIC MODELS [J]. Journal of Computational Mathematics, 2022, 40(2): 294-334.
[2] Yuting Chen, Mingyuan Cao, Yueting Yang, Qingdao Huang. AN ADAPTIVE TRUST-REGION METHOD FOR GENERALIZED EIGENVALUES OF SYMMETRIC TENSORS [J]. Journal of Computational Mathematics, 2021, 39(3): 358-374.
[3] Keke Zhang, Hongwei Liu, Zexian Liu. A NEW ADAPTIVE SUBSPACE MINIMIZATION THREE-TERM CONJUGATE GRADIENT ALGORITHM FOR UNCONSTRAINED OPTIMIZATION [J]. Journal of Computational Mathematics, 2021, 39(2): 159-177.
[4] Wenjuan Xue, Weiai Liu. A MULTIDIMENSIONAL FILTER SQP ALGORITHM FOR NONLINEAR PROGRAMMING [J]. Journal of Computational Mathematics, 2020, 38(5): 683-704.
[5] Bothina El-Sobky, Abdallah Abotahoun. A TRUST-REGION ALGORITHM FOR SOLVING MINI-MAX PROBLEM [J]. Journal of Computational Mathematics, 2018, 36(6): 776-791.
[6] Fan Jiang, Deren Han, Xiaofei Zhang. A TRUST-REGION-BASED ALTERNATING LEAST-SQUARES ALGORITHM FOR TENSOR DECOMPOSITIONS [J]. Journal of Computational Mathematics, 2018, 36(3): 351-373.
[7] Yangyang Xu. FAST ALGORITHMS FOR HIGHER-ORDER SINGULAR VALUE DECOMPOSITION FROM INCOMPLETE DATA [J]. Journal of Computational Mathematics, 2017, 35(4): 397-422.
[8] Jinkui Liu, Shengjie Li. SPECTRAL DY-TYPE PROJECTION METHOD FOR NONLINEAR MONOTONE SYSTEM OF EQUATIONS [J]. Journal of Computational Mathematics, 2015, 33(4): 341-355.
[9] Jinghui Liu, Changfeng Ma. A NEW NONMONOTONE TRUST REGION ALGORITHM FOR SOLVING UNCONSTRAINED OPTIMIZATION PROBLEMS [J]. Journal of Computational Mathematics, 2014, 32(4): 476-490.
[10] Fusheng Wang, Chuanlong Wang, Li Wang. A NEW TRUST-REGION ALGORITHM FOR FINITE MINIMAX PROBLEM [J]. Journal of Computational Mathematics, 2012, 30(3): 262-278.
[11] Xuebin Wang, Changfeng Ma, Meiyan Li. A SMOOTHING TRUST REGION METHOD FOR NCPS BASED ON THE SMOOTHING GENERALIZED FISCHER-BURMEISTER FUNCTION [J]. Journal of Computational Mathematics, 2011, 29(3): 261-286.
[12] Duoquan Li. A NEW SQP-FILTER METHOD FOR SOLVING NONLINEAR PROGRAMMING PROBLEMS [J]. Journal of Computational Mathematics, 2006, 24(5): 609-634.
[13] Chang-yin Zhou,Guo-ping He,Yong-li Wang . A NEW CONSTRAINTS IDENTIFICATION TECHNIQUE-BASED QP-FREE ALGORITHM FOR THE SOLUTION OF INEQUALITY CONSTRAINED MINIMIZATION PROBLEMS [J]. Journal of Computational Mathematics, 2006, 24(5): 591-608.
[14] Xin-long Luo. Singly Diagonally Implicit Runge-Kutta Methods Combining Line Search Techniques for Unconstrained Optimization [J]. Journal of Computational Mathematics, 2005, 23(2): 153-164.
[15] De Ren HAN. A TRULY GLOBALLY CONVERGENT FEASIBLE NEWTON-TYPE METHOD FOR MIXED COMPLEMENTARITY PROBLEMS [J]. Journal of Computational Mathematics, 2004, 22(3): 347-360.
Viewed
Full text


Abstract