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

A penalty-free method for equality constrained optimization

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.
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]

Nobuko Sagara, Masao Fukushima. trust region method for nonsmooth convex optimization. Journal of Industrial & Management Optimization, 2005, 1 (2) : 171-180. doi: 10.3934/jimo.2005.1.171

[2]

Liang Zhang, Wenyu Sun, Raimundo J. B. de Sampaio, Jinyun Yuan. A wedge trust region method with self-correcting geometry for derivative-free optimization. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 169-184. doi: 10.3934/naco.2015.5.169

[3]

Bülent Karasözen. Survey of trust-region derivative free optimization methods. Journal of Industrial & Management Optimization, 2007, 3 (2) : 321-334. doi: 10.3934/jimo.2007.3.321

[4]

Jun Chen, Wenyu Sun, Zhenghao Yang. A non-monotone retrospective trust-region method for unconstrained optimization. Journal of Industrial & Management Optimization, 2013, 9 (4) : 919-944. doi: 10.3934/jimo.2013.9.919

[5]

Lijuan Zhao, Wenyu Sun. Nonmonotone retrospective conic trust region method for unconstrained optimization. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 309-325. doi: 10.3934/naco.2013.3.309

[6]

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

[7]

Songqiang Qiu, Zhongwen Chen. An adaptively regularized sequential quadratic programming method for equality constrained optimization. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-14. doi: 10.3934/jimo.2019075

[8]

Boshi Tian, Xiaoqi Yang, Kaiwen Meng. An interior-point $l_{\frac{1}{2}}$-penalty method for inequality constrained nonlinear optimization. Journal of Industrial & Management Optimization, 2016, 12 (3) : 949-973. doi: 10.3934/jimo.2016.12.949

[9]

Jun Takaki, Nobuo Yamashita. A derivative-free trust-region algorithm for unconstrained optimization with controlled error. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 117-145. doi: 10.3934/naco.2011.1.117

[10]

Changjun Yu, Kok Lay Teo, Liansheng Zhang, Yanqin Bai. A new exact penalty function method for continuous inequality constrained optimization problems. Journal of Industrial & Management Optimization, 2010, 6 (4) : 895-910. doi: 10.3934/jimo.2010.6.895

[11]

A. M. Bagirov, Moumita Ghosh, Dean Webb. A derivative-free method for linearly constrained nonsmooth optimization. Journal of Industrial & Management Optimization, 2006, 2 (3) : 319-338. doi: 10.3934/jimo.2006.2.319

[12]

Xin Zhang, Jie Wen, Qin Ni. Subspace trust-region algorithm with conic model for unconstrained optimization. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 223-234. doi: 10.3934/naco.2013.3.223

[13]

M. S. Lee, B. S. Goh, H. G. Harno, K. H. Lim. On a two-phase approximate greatest descent method for nonlinear optimization with equality constraints. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 315-326. doi: 10.3934/naco.2018020

[14]

Honglan Zhu, Qin Ni, Meilan Zeng. A quasi-Newton trust region method based on a new fractional model. Numerical Algebra, Control & Optimization, 2015, 5 (3) : 237-249. doi: 10.3934/naco.2015.5.237

[15]

Dan Xue, Wenyu Sun, Hongjin He. A structured trust region method for nonconvex programming with separable structure. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 283-293. doi: 10.3934/naco.2013.3.283

[16]

Wen-ling Zhao, Dao-jin Song. A global error bound via the SQP method for constrained optimization problem. Journal of Industrial & Management Optimization, 2007, 3 (4) : 775-781. doi: 10.3934/jimo.2007.3.775

[17]

Wei-Zhe Gu, Li-Yong Lu. The linear convergence of a derivative-free descent method for nonlinear complementarity problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 531-548. doi: 10.3934/jimo.2016030

[18]

Regina S. Burachik, C. Yalçın Kaya. An update rule and a convergence result for a penalty function method. Journal of Industrial & Management Optimization, 2007, 3 (2) : 381-398. doi: 10.3934/jimo.2007.3.381

[19]

Ahmet Sahiner, Gulden Kapusuz, Nurullah Yilmaz. A new smoothing approach to exact penalty functions for inequality constrained optimization problems. Numerical Algebra, Control & Optimization, 2016, 6 (2) : 161-173. doi: 10.3934/naco.2016006

[20]

Qiang Long, Changzhi Wu. A hybrid method combining genetic algorithm and Hooke-Jeeves method for constrained global optimization. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1279-1296. doi: 10.3934/jimo.2014.10.1279

2018 Impact Factor: 1.025

Metrics

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

Other articles
by authors

[Back to Top]