American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Risk-minimizing portfolio selection for insurance payment processes under a Markov-modulated model
  • JIMO Home
  • This Issue
  • Next Article
    Pricing American options under proportional transaction costs using a penalty approach and a finite difference scheme
April  2013, 9(2): 391-409. doi: 10.3934/jimo.2013.9.391

A penalty-free method for equality constrained optimization

Zhongwen Chen 1, , Songqiang Qiu 1, and  Yujie Jiao 1,

1. 

School of Mathematics Science, Soochow University, Suzhou, 215006, China, China, China

Received  September 2011 Revised  January 2013 Published  February 2013

A penalty-free method is introduced for solving nonlinear programming with nonlinear equality constraints. This method does not use any penalty function, nor a filter. It uses trust region technique to compute trial steps. By comparing the measures of feasibility and optimality, the algorithm either tries to reduce the value of objective function by solving a normal subproblem and a tangential subproblem or tries to improve feasibility by solving a normal subproblem only. In order to guarantee global convergence, the measure of constraint violation in each iteration is required not to exceed a progressively decreasing limit. Under usual assumptions, we prove that the given algorithm is globally convergent to first order stationary points. Preliminary numerical results on CUTEr problems are reported.
Keywords: penalty-free method, trust region, Nonlinear equality-constrained optimization, global convergence..
Mathematics Subject Classification: Primary: 65K05; Secondary: 90C26, 90C3.
Citation: Zhongwen Chen, Songqiang Qiu, Yujie Jiao. A penalty-free method for equality constrained optimization. Journal of Industrial & Management Optimization, 2013, 9 (2) : 391-409. doi: 10.3934/jimo.2013.9.391
References:
[1]

R. Andreani, E. G. Birgin, J. M. Martinez and M. L. Schuverdt, Augmented Lagrangian methods under the constant positive linear dependence constraint qualification,, Math. Prog. Ser. B, 111 (2008), 5.  doi: 10.1007/s10107-006-0077-1.  Google Scholar

[2]

R. H. Bielschowsky and F. A. M. Gomes, Dynamic control of infeasibility in equality constrained optimization,, SIAM J. Optim., 19 (2008), 1299.  doi: 10.1137/070679557.  Google Scholar

[3]

I. Bongartz, A. R. Conn, N. I. M. Gould and Ph. L. Toint, CUTE: Constrained and unconstrained testing enviroment,, ACM Tran. Math. Software, 21 (1995), 123.   Google Scholar

[4]

I. Bongartz, A. R. Conn, N. I. M. Gould, M. A. Saunders and Ph. L. Toint, "A Numerical Comparison between the LANCELOT and MINOS Packages for Large-Scale Constrained Optimization: The Complete Numerical Results,", Report 97/14, (1997).   Google Scholar

[5]

R. H. Byrd, F. E. Curtis and J. Nocedal, An inexact SQP method for equality constrained optimization,, SIAM J Optim., 19 (2008), 351.  doi: 10.1137/060674004.  Google Scholar

[6]

R. H. Byrd, F. E. Curtis and J. Nocedal, An inexact Newton method for nonconvex equality constrained optimization,, Math. Prog., 122 (2010), 273.  doi: 10.1007/s10107-008-0248-3.  Google Scholar

[7]

Z. W. Chen, A penalty-free-type nonmonotone trust-region method for nonlinear constrained optimization,, Appl. Math. and Comput., 173 (2006), 1014.  doi: 10.1016/j.amc.2005.04.031.  Google Scholar

[8]

C. M. Chin and R. Fletcher, On the global convergence of an SLP-filter algorithm that takes EQP steps,, Math. Prog. Ser. A, 96 (2003), 161.   Google Scholar

[9]

A. R. Conn, N. I. M. Gould and Ph. L. Toint, "Trust-Region Methods,", MPS-SIAM Ser. Optim., (2000).  doi: 10.1137/1.9780898719857.  Google Scholar

[10]

E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles,, Math. Prog. Serial A., 91 (2002), 201.  doi: 10.1007/s101070100263.  Google Scholar

[11]

R. Fletcher and S. Leyffer, Nonlinear programming without a penalty function,, Math. Prog. Ser. A, 91 (2002), 239.  doi: 10.1007/s101070100244.  Google Scholar

[12]

R. Fletcher, S. Leyffer and Ph. L. Toint, On the global convergence of a filter-SQP algorithm,, SIAM J. Optim., 13 (2002), 44.  doi: 10.1137/S105262340038081X.  Google Scholar

[13]

R. Fletcher, S. Leyffer and Ph. L. Toint, "A Brief History of Filter Methods,", Optimization Online, (2006).   Google Scholar

[14]

N. I. M. Gould and Ph. L. Toint, Nonlinear programming without a penalty function or a filter,, Math. Prog. Ser. A, 122 (2010), 155.  doi: 10.1007/s10107-008-0244-7.  Google Scholar

[15]

X. Liu and Y. Yuan, A sequential quadratic programming method without a penalty function or a filter for nonlinear equality constrained optimization,, SIAM J. Optim., 21 (2011), 545.  doi: 10.1137/080739884.  Google Scholar

[16]

S. Qiu and Z. Chen, A new penalty-free-type algorithm that based on trust region techniques,, Appl. Math. Comput., 218 (2012), 11089.  doi: 10.1016/j.amc.2012.04.065.  Google Scholar

[17]

M. Ulbrich and S. Ulbrich, Non-monotone trust region methods for nonlinear equality constrained optimization without a penalty function,, Math. Prog. Ser. B, 95 (2003), 103.  doi: 10.1007/s10107-002-0343-9.  Google Scholar

[18]

M. Ulbrich, S. Ulbrich and L. N. Vicente, A globally convergent primal-dual interior-point filter method for nonlinear programming,, Math. Prog. Ser. A, 100 (2004), 379.  doi: 10.1007/s10107-003-0477-4.  Google Scholar

[19]

A. Wächter and L. T. Biegler, Line search filter methods for nonlinear programming: Local convergence,, SIAM J. Optim., 16 (2005), 32.  doi: 10.1137/S1052623403426544.  Google Scholar

[20]

H. Yamashita, "A Globally Convergent Quasi-Newton Method for Equality Constrained Optimization that Does Not Use a Penalty Function,", Technical Report, (1979).   Google Scholar

[21]

H. Yamashita and H. Yabe, "A Globally and Superlinearly Convergent Trust-Region SQP Method Without a Penalty Function for Nonlinearly Constrained Optimization,", Technical Report, (2003).   Google Scholar

[22]

C. Zoppke-Donaldson, "A Tolerance Tube Approach to Sequential Quadratic Programming with Applications,", Ph.D Thesis, (1995).   Google Scholar

show all references

References:
[1]

R. Andreani, E. G. Birgin, J. M. Martinez and M. L. Schuverdt, Augmented Lagrangian methods under the constant positive linear dependence constraint qualification,, Math. Prog. Ser. B, 111 (2008), 5.  doi: 10.1007/s10107-006-0077-1.  Google Scholar

[2]

R. H. Bielschowsky and F. A. M. Gomes, Dynamic control of infeasibility in equality constrained optimization,, SIAM J. Optim., 19 (2008), 1299.  doi: 10.1137/070679557.  Google Scholar

[3]

I. Bongartz, A. R. Conn, N. I. M. Gould and Ph. L. Toint, CUTE: Constrained and unconstrained testing enviroment,, ACM Tran. Math. Software, 21 (1995), 123.   Google Scholar

[4]

I. Bongartz, A. R. Conn, N. I. M. Gould, M. A. Saunders and Ph. L. Toint, "A Numerical Comparison between the LANCELOT and MINOS Packages for Large-Scale Constrained Optimization: The Complete Numerical Results,", Report 97/14, (1997).   Google Scholar

[5]

R. H. Byrd, F. E. Curtis and J. Nocedal, An inexact SQP method for equality constrained optimization,, SIAM J Optim., 19 (2008), 351.  doi: 10.1137/060674004.  Google Scholar

[6]

R. H. Byrd, F. E. Curtis and J. Nocedal, An inexact Newton method for nonconvex equality constrained optimization,, Math. Prog., 122 (2010), 273.  doi: 10.1007/s10107-008-0248-3.  Google Scholar

[7]

Z. W. Chen, A penalty-free-type nonmonotone trust-region method for nonlinear constrained optimization,, Appl. Math. and Comput., 173 (2006), 1014.  doi: 10.1016/j.amc.2005.04.031.  Google Scholar

[8]

C. M. Chin and R. Fletcher, On the global convergence of an SLP-filter algorithm that takes EQP steps,, Math. Prog. Ser. A, 96 (2003), 161.   Google Scholar

[9]

A. R. Conn, N. I. M. Gould and Ph. L. Toint, "Trust-Region Methods,", MPS-SIAM Ser. Optim., (2000).  doi: 10.1137/1.9780898719857.  Google Scholar

[10]

E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles,, Math. Prog. Serial A., 91 (2002), 201.  doi: 10.1007/s101070100263.  Google Scholar

[11]

R. Fletcher and S. Leyffer, Nonlinear programming without a penalty function,, Math. Prog. Ser. A, 91 (2002), 239.  doi: 10.1007/s101070100244.  Google Scholar

[12]

R. Fletcher, S. Leyffer and Ph. L. Toint, On the global convergence of a filter-SQP algorithm,, SIAM J. Optim., 13 (2002), 44.  doi: 10.1137/S105262340038081X.  Google Scholar

[13]

R. Fletcher, S. Leyffer and Ph. L. Toint, "A Brief History of Filter Methods,", Optimization Online, (2006).   Google Scholar

[14]

N. I. M. Gould and Ph. L. Toint, Nonlinear programming without a penalty function or a filter,, Math. Prog. Ser. A, 122 (2010), 155.  doi: 10.1007/s10107-008-0244-7.  Google Scholar

[15]

X. Liu and Y. Yuan, A sequential quadratic programming method without a penalty function or a filter for nonlinear equality constrained optimization,, SIAM J. Optim., 21 (2011), 545.  doi: 10.1137/080739884.  Google Scholar

[16]

S. Qiu and Z. Chen, A new penalty-free-type algorithm that based on trust region techniques,, Appl. Math. Comput., 218 (2012), 11089.  doi: 10.1016/j.amc.2012.04.065.  Google Scholar

[17]

M. Ulbrich and S. Ulbrich, Non-monotone trust region methods for nonlinear equality constrained optimization without a penalty function,, Math. Prog. Ser. B, 95 (2003), 103.  doi: 10.1007/s10107-002-0343-9.  Google Scholar

[18]

M. Ulbrich, S. Ulbrich and L. N. Vicente, A globally convergent primal-dual interior-point filter method for nonlinear programming,, Math. Prog. Ser. A, 100 (2004), 379.  doi: 10.1007/s10107-003-0477-4.  Google Scholar

[19]

A. Wächter and L. T. Biegler, Line search filter methods for nonlinear programming: Local convergence,, SIAM J. Optim., 16 (2005), 32.  doi: 10.1137/S1052623403426544.  Google Scholar

[20]

H. Yamashita, "A Globally Convergent Quasi-Newton Method for Equality Constrained Optimization that Does Not Use a Penalty Function,", Technical Report, (1979).   Google Scholar

[21]

H. Yamashita and H. Yabe, "A Globally and Superlinearly Convergent Trust-Region SQP Method Without a Penalty Function for Nonlinearly Constrained Optimization,", Technical Report, (2003).   Google Scholar

[22]

C. Zoppke-Donaldson, "A Tolerance Tube Approach to Sequential Quadratic Programming with Applications,", Ph.D Thesis, (1995).   Google Scholar

[1]

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

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

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[4]

Manoel J. Dos Santos, Baowei Feng, Dilberto S. Almeida Júnior, Mauro L. Santos. Global and exponential attractors for a nonlinear porous elastic system with delay term. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2805-2828. doi: 10.3934/dcdsb.2020206
[5]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017
[6]

Irena PawŃow, Wojciech M. Zajączkowski. Global regular solutions to three-dimensional thermo-visco-elasticity with nonlinear temperature-dependent specific heat. Communications on Pure & Applied Analysis, 2017, 16 (4) : 1331-1372. doi: 10.3934/cpaa.2017065
[7]

Jian Yang, Bendong Lou. Traveling wave solutions of competitive models with free boundaries. Discrete & Continuous Dynamical Systems - B, 2014, 19 (3) : 817-826. doi: 10.3934/dcdsb.2014.19.817
[8]

Mingxin Wang, Qianying Zhang. Dynamics for the diffusive Leslie-Gower model with double free boundaries. Discrete & Continuous Dynamical Systems - A, 2018, 38 (5) : 2591-2607. doi: 10.3934/dcds.2018109
[9]

Yizhuo Wang, Shangjiang Guo. A SIS reaction-diffusion model with a free boundary condition and nonhomogeneous coefficients. Discrete & Continuous Dynamical Systems - B, 2019, 24 (4) : 1627-1652. doi: 10.3934/dcdsb.2018223
[10]

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

Rafael Luís, Sandra Mendonça. A note on global stability in the periodic logistic map. Discrete & Continuous Dynamical Systems - B, 2020, 25 (11) : 4211-4220. doi: 10.3934/dcdsb.2020094
[12]

Fernando P. da Costa, João T. Pinto, Rafael Sasportes. On the convergence to critical scaling profiles in submonolayer deposition models. Kinetic & Related Models, 2018, 11 (6) : 1359-1376. doi: 10.3934/krm.2018053
[13]

Alberto Bressan, Carlotta Donadello. On the convergence of viscous approximations after shock interactions. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 29-48. doi: 10.3934/dcds.2009.23.29
[14]

Lakmi Niwanthi Wadippuli, Ivan Gudoshnikov, Oleg Makarenkov. Global asymptotic stability of nonconvex sweeping processes. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1129-1139. doi: 10.3934/dcdsb.2019212
[15]

Caifang Wang, Tie Zhou. The order of convergence for Landweber Scheme with $\alpha,\beta$-rule. Inverse Problems & Imaging, 2012, 6 (1) : 133-146. doi: 10.3934/ipi.2012.6.133
[16]

Eduardo Casas, Christian Clason, Arnd Rösch. Preface special issue on system modeling and optimization. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021008
[17]

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

Carlos Gutierrez, Nguyen Van Chau. A remark on an eigenvalue condition for the global injectivity of differentiable maps of $R^2$. Discrete & Continuous Dynamical Systems - A, 2007, 17 (2) : 397-402. doi: 10.3934/dcds.2007.17.397
[19]

Bernold Fiedler, Carlos Rocha, Matthias Wolfrum. Sturm global attractors for $S^1$-equivariant parabolic equations. Networks & Heterogeneous Media, 2012, 7 (4) : 617-659. doi: 10.3934/nhm.2012.7.617
[20]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences