An interior-point $l_{\frac{1}{2}}$-penalty method for inequality constrained nonlinear optimization

Boshi  Tian; Xiaoqi Yang; Kaiwen  Meng

doi:10.3934/jimo.2016.12.949

Article Contents

2016, Volume 12, Issue 3: 949-973. Doi: 10.3934/jimo.2016.12.949

This issue Previous Article The risk-averse newsvendor game with competition on demand Next Article Bounds for the spectral radius of nonnegative tensors

An interior-point $l_{\frac{1}{2}}$-penalty method for inequality constrained nonlinear optimization

1.
Business School, Hunan University, Changsha 410082, Hunan Province
2.
Department of Applied Mathematics, The Hong Kong Polytechnic University, Kowloon, Hong Kong
3.
School of Economics and Management, Southwest Jiaotong University, Chengdu 610031

Received: January 31, 2014

Revised: March 31, 2015

Published: June 2016

Abstract Related Papers Cited by

Abstract

In this paper, we study inequality constrained nonlinear programming problems by virtue of an $\ell{\frac12}$-penalty function and a quadratic relaxation. Combining with an interior-point method, we propose an interior-point $\ell_{\frac12}$-penalty method. We introduce different kinds of constraint qualifications to establish the first-order necessary conditions for the quadratically relaxed problem. We apply the modified Newton method to a sequence of logarithmic barrier problems, and design some reliable algorithms. Moreover, we establish the global convergence results of the proposed method. We carry out numerical experiments on 266 inequality constrained optimization problems. Our numerical results show that the proposed method is competitive with some existing interior-point $\ell_1$-penalty methods in term of iteration numbers and better when comparing the values of the penalty parameter.

Keywords:

Mathematics Subject Classification: Primary: 90C30; Secondary: 49M20, 90C51.

Citation:

Related Papers

Cited by

References

[1]	H. Y. Benson, A. Sen and D. F. Shanno, Interior-point methods for nonconvex nonlinear programming: Convergence analysis and computational performance, http://rutcor.rutgers.edu/~shanno/converge5.pdf, 2009.
[2]	H. Y. Benson, D. F. Shanno and R. J. Vanderbei, Interior-point methods for nonconvex nonlinear programming: Jamming and numerical testing, Mathematical Programming, 99 (2004), 35-48.doi: 10.1007/s10107-003-0418-2.
[3]	R. H. Byrd, G. Lopez-Calva and J. Nocedal, A line search exact penalty method using steering rules, Mathematical Programming, 133 (2012), 39-73.doi: 10.1007/s10107-010-0408-0.
[4]	R. H. Byrd, J. Nocedal and R. A. Waltz, Steering exact penalty methods for nonlinear programming, Optimization Methods and Software, 23 (2008), 197-213.doi: 10.1080/10556780701394169.
[5]	R. Chartrand and V. Staneva, Restricted isometry properties and nonconvex compressive sensing, Inverse Problems, 24 (2008), 035020, 14 pp.doi: 10.1088/0266-5611/24/3/035020.
[6]	L. Chen and D. Goldfarb, Interior-point $l_2$-penalty methods for nonlinear programming with strong global convergence properties, Mathematical Programming, 108 (2006), 1-36.doi: 10.1007/s10107-005-0701-5.
[7]	L. Chen and D. Goldfarb, On the Fast Local Convergence of Interior-point $l_2$-penalty Methods for Nonlinear Programming, Technical report, Columbia University, 2006.
[8]	X. J. Chen, Smoothing methods for nonsmooth, nonconvex minimization, Mathematical Programming, 134 (2012), 71-99.doi: 10.1007/s10107-012-0569-0.
[9]	A. R. Conn, N. I. M. Gould, D. Orban and P. L. Toint, A primal-dual trust-region algorithm for non-convex nonlinear programming, Mathematical Programming, 87 (2000), 215-249.doi: 10.1007/s101070050112.
[10]	F. E. Curtis, A penalty-interior-point algorithm for nonlinear constrained optimization, Mathematical Programming Computation, 4 (2012), 181-209.doi: 10.1007/s12532-012-0041-4.
[11]	E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles, Mathematical Programming, 91 (2002), 201-213.doi: 10.1007/s101070100263.
[12]	C. Durazzi, On the Newton interior-point method for nonlinear programming problems, Journal of Optimization Theory and Applications, 104 (2000), 73-90.doi: 10.1023/A:1004624721836.
[13]	A. S. El-Bakry, R. A. Tapia, T. Tsuchiya and Y. Zhang, On the formulation and theory of the Newton interior-point method for nonlinear programming, Journal of Optimization Theory and Applications, 89 (1996), 507-541.doi: 10.1007/BF02275347.
[14]	R. Fletcher, Practical Methods of Optimization, Second edition. A Wiley-Interscience Publication, John Wiley & Sons, Ltd., Chichester, 1987.
[15]	P. E. Gill, W. Murray and M. H. Wright, Practical Optimization, Academic Press, 1981.
[16]	N. I. M. Gould, P. L. Toint and D. Orban, An Interior-point $l_1$-penalty Method for Nonlinear Optimization, Groupe d'études et de recherche en analyse des décisions, 2010.
[17]	M. Guignard, Generalized Kuhn-Tucker conditions for mathematical programming problems in a Banach space, SIAM Journal on Control, 7 (1969), 232-241.doi: 10.1137/0307016.
[18]	X. X. Huang and X. Q. Yang, Convergence analysis of a class of nonlinear penalization methods for constrained optimization via first-order necessary optimality conditions, Journal of Optimization Theory and Applications, 116 (2003), 311-332.doi: 10.1023/A:1022503820909.
[19]	X. X. Huang and X. Q. Yang, A unified augmented Lagrangian approach to duality and exact penalization, Mathematics of Operations Research, 28 (2003), 533-552.doi: 10.1287/moor.28.3.533.16395.
[20]	X. W. Liu and J. Sun, A robust primal-dual interior-point algorithm for nonlinear programs, SIAM Journal on Optimization, 14 (2004), 1163-1186.doi: 10.1137/S1052623402400641.
[21]	X. W. Liu and J. Sun, Global convergence analysis of line search interior-point methods for nonlinear programming without regularity assumptions, Journal of Optimization Theory and Applications, 125 (2005), 609-628.doi: 10.1007/s10957-005-2092-4.
[22]	Z. Q. Luo, J. S. Pang and D. Ralph, Mathematical Programs with Equilibrium Constraints, Cambridge University Press, 1996.doi: 10.1017/CBO9780511983658.
[23]	K. W. Meng, S. J. Li and X. Q. Yang, A robust SQP method based on a smoothing lower order penalty functions, Optimization, 58 (2009), 23-38.doi: 10.1080/02331930701761193.
[24]	K. W. Meng and X. Q. Yang, First- and second-order necessary conditions via exact penalty functions, Journal of Optimization Theory and Applications, 165 (2015), 720-752.doi: 10.1007/s10957-014-0664-x.
[25]	K. W. Meng and X. Q. Yang, Optimality conditions via exact penalty functions, SIAM Journal on Optimization, 20 (2010), 3208-3231.doi: 10.1137/090771016.
[26]	Z. Q. Meng, C. Y. Dang and X. Q. Yang, On the smoothing of the square-root exact penalty function for inequality constrained optimization, Computational Optimization and Applications, 35 (2006), 375-398.doi: 10.1007/s10589-006-8720-6.
[27]	M. Mongeau and A. Sartenaer, Automatic decrease of the penalty parameter in exact penalty function methods, European Journal of Operational Research, 83 (1995), 686-699.doi: 10.1016/0377-2217(93)E0339-Y.
[28]	A. S. Nemirovski and M. J. Todd, Interior-point methods for optimization, Acta Numerica, 17 (2008), 191-234.doi: 10.1017/S0962492906370018.
[29]	J. Nocedal and S. J. Wright, Numerical Optimization, Springer Verlag, 2006.
[30]	I. Pólik and T. Terlaky, Interior point methods for nonlinear optimization, Nonlinear optimization, Lecture Notes in Math., Springer, Berlin, 1989 (2010), 215-276.doi: 10.1007/978-3-642-11339-0_4.
[31]	R. T. Rockafellar and R. J. B. Wets, Variational Analysis, Springer-Verlag, Berlin, 1998.doi: 10.1007/978-3-642-02431-3.
[32]	A. M. Rubinov, B. M. Glover and X. Q. Yang, Decreasing functions with applications to penalization, SIAM Journal on Optimization, 10 (1999), 289-313.doi: 10.1137/S1052623497326095.
[33]	D. F. Shanno and R. J. Vanderbei, Interior-point methods for nonconvex nonlinear programming: Orderings and higher-order methods, Mathematical Programming, 87 (2000), 303-316.doi: 10.1007/s101070050116.
[34]	G. Still and M. Streng, Optimality conditions in smooth nonlinear programming, Journal of Optimization Theory and Applications, 90 (1996), 483-515.doi: 10.1007/BF02189792.
[35]	R. J. Vanderbei and D. F. Shanno, An interior-point algorithm for nonconvex nonlinear programming, Computational Optimization and Applications, 13 (1999), 231-252.doi: 10.1023/A:1008677427361.
[36]	A. Wächter and L. T. Biegler, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Mathematical Programming, 106 (2006), 25-57.doi: 10.1007/s10107-004-0559-y.
[37]	S. J. Wright, Primal-dual Interior-Point Methods, SIAM, 1987.doi: 10.1137/1.9781611971453.
[38]	Z. B. Xu, X. Y. Chang, F. M. Xu and H. Zhang, $L_{1/2}$ Regularization: A thresholding representation theory and a fast solver, Neural Networks and Learning Systems, IEEE Transactions on, 23 (2012), 1013-1027.
[39]	X. Q. Yang and Z. Q. Meng, Lagrange multipliers and calmness conditions of order $p$, Mathematics of Operations Research, 32 (2007), 95-101.doi: 10.1287/moor.1060.0217.
[40]	X. Q. Yang, Z. Q. Meng, X. X. Huang and G. T. Y. Pong, Smoothing nonlinear penalty functions for constrained optimization problems, Numerical Functional Analysis and Optimization, 24 (2003), 351-364.doi: 10.1081/NFA-120022928.
[41]	Y. Y. Ye, Interior Point Algorithms: Theory and Analysis, Wiley-Interscience, 1997.doi: 10.1002/9781118032701.