A penalty-free method for equality constrained optimization

Zhongwen Chen; Songqiang Qiu; Yujie Jiao

doi:10.3934/jimo.2013.9.391

Article Contents

2013, Volume 9, Issue 2: 391-409. Doi: 10.3934/jimo.2013.9.391

This issue Previous Article Pricing American options under proportional transaction costs using a penalty approach and a finite difference scheme Next Article Risk-minimizing portfolio selection for insurance payment processes under a Markov-modulated model

A penalty-free method for equality constrained optimization

1.
School of Mathematics Science, Soochow University, Suzhou, 215006

Received: August 31, 2011

Revised: December 31, 2012

Published: March 2013

Abstract Related Papers Cited by

Abstract

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:

Nonlinear equality-constrained optimization,
penalty-free method,
trust region,
global convergence.

Mathematics Subject Classification: Primary: 65K05; Secondary: 90C26, 90C30.

Citation:

Related Papers

Cited by

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-32.doi: 10.1007/s10107-006-0077-1.
[2]	R. H. Bielschowsky and F. A. M. Gomes, Dynamic control of infeasibility in equality constrained optimization, SIAM J. Optim., 19 (2008), 1299-1325.doi: 10.1137/070679557.
[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-160.
[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, Departement de Mathematique, Faculties Universitaires de Namur, 1997.
[5]	R. H. Byrd, F. E. Curtis and J. Nocedal, An inexact SQP method for equality constrained optimization, SIAM J Optim., 19 (2008), 351-369.doi: 10.1137/060674004.
[6]	R. H. Byrd, F. E. Curtis and J. Nocedal, An inexact Newton method for nonconvex equality constrained optimization, Math. Prog., 122 (2010), 273-299.doi: 10.1007/s10107-008-0248-3.
[7]	Z. W. Chen, A penalty-free-type nonmonotone trust-region method for nonlinear constrained optimization, Appl. Math. and Comput., 173 (2006), 1014-1046.doi: 10.1016/j.amc.2005.04.031.
[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-177.
[9]	A. R. Conn, N. I. M. Gould and Ph. L. Toint, "Trust-Region Methods," MPS-SIAM Ser. Optim., SIAM, Philadelphia, PA, Mathematical Programming Society (MPS), Philadelphia, PA, 2000.doi: 10.1137/1.9780898719857.
[10]	E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles, Math. Prog. Serial A., 91 (2002), 201-213.doi: 10.1007/s101070100263.
[11]	R. Fletcher and S. Leyffer, Nonlinear programming without a penalty function, Math. Prog. Ser. A, 91 (2002), 239-269.doi: 10.1007/s101070100244.
[12]	R. Fletcher, S. Leyffer and Ph. L. Toint, On the global convergence of a filter-SQP algorithm, SIAM J. Optim., 13 (2002), 44-59.doi: 10.1137/S105262340038081X.
[13]	R. Fletcher, S. Leyffer and Ph. L. Toint, "A Brief History of Filter Methods," Optimization Online, September 26, 2006.
[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-196.doi: 10.1007/s10107-008-0244-7.
[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-571.doi: 10.1137/080739884.
[16]	S. Qiu and Z. Chen, A new penalty-free-type algorithm that based on trust region techniques, Appl. Math. Comput., 218 (2012), 11089-11099.doi: 10.1016/j.amc.2012.04.065.
[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-135.doi: 10.1007/s10107-002-0343-9.
[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-410.doi: 10.1007/s10107-003-0477-4.
[19]	A. Wächter and L. T. Biegler, Line search filter methods for nonlinear programming: Local convergence, SIAM J. Optim., 16 (2005), 32-48.doi: 10.1137/S1052623403426544.
[20]	H. Yamashita, "A Globally Convergent Quasi-Newton Method for Equality Constrained Optimization that Does Not Use a Penalty Function," Technical Report, Mathematical System Inc., Tokyo, Japan, June 1979 (revised September 1982).
[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, Mathematical System Inc., Tokyo, Japan, September 2003 (revised July 2007).
[22]	C. Zoppke-Donaldson, "A Tolerance Tube Approach to Sequential Quadratic Programming with Applications," Ph.D Thesis, Department of Mathematics and Computer Science, University of Dundee, Dundee, Scotland, UK, 1995.