July  2016, 12(3): 949-973. doi: 10.3934/jimo.2016.12.949

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

1. 

Business School, Hunan University, Changsha 410082, Hunan Province, China

2. 

Department of Applied Mathematics, The Hong Kong Polytechnic University, Kowloon, Hong Kong

3. 

School of Economics and Management, Southwest Jiaotong University, Chengdu 610031, China

Received  February 2014 Revised  April 2015 Published  September 2015

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.
Citation: 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
References:
[1]

H. Y. Benson, A. Sen and D. F. Shanno, Interior-point methods for nonconvex nonlinear programming: Convergence analysis and computational performance,, , (2009).   Google Scholar

[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.  doi: 10.1007/s10107-003-0418-2.  Google Scholar

[3]

R. H. Byrd, G. Lopez-Calva and J. Nocedal, A line search exact penalty method using steering rules,, Mathematical Programming, 133 (2012), 39.  doi: 10.1007/s10107-010-0408-0.  Google Scholar

[4]

R. H. Byrd, J. Nocedal and R. A. Waltz, Steering exact penalty methods for nonlinear programming,, Optimization Methods and Software, 23 (2008), 197.  doi: 10.1080/10556780701394169.  Google Scholar

[5]

R. Chartrand and V. Staneva, Restricted isometry properties and nonconvex compressive sensing,, Inverse Problems, 24 (2008).  doi: 10.1088/0266-5611/24/3/035020.  Google Scholar

[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.  doi: 10.1007/s10107-005-0701-5.  Google Scholar

[7]

L. Chen and D. Goldfarb, On the Fast Local Convergence of Interior-point $l_2$-penalty Methods for Nonlinear Programming,, Technical report, (2006).   Google Scholar

[8]

X. J. Chen, Smoothing methods for nonsmooth, nonconvex minimization,, Mathematical Programming, 134 (2012), 71.  doi: 10.1007/s10107-012-0569-0.  Google Scholar

[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.  doi: 10.1007/s101070050112.  Google Scholar

[10]

F. E. Curtis, A penalty-interior-point algorithm for nonlinear constrained optimization,, Mathematical Programming Computation, 4 (2012), 181.  doi: 10.1007/s12532-012-0041-4.  Google Scholar

[11]

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

[12]

C. Durazzi, On the Newton interior-point method for nonlinear programming problems,, Journal of Optimization Theory and Applications, 104 (2000), 73.  doi: 10.1023/A:1004624721836.  Google Scholar

[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.  doi: 10.1007/BF02275347.  Google Scholar

[14]

R. Fletcher, Practical Methods of Optimization,, Second edition. A Wiley-Interscience Publication, (1987).   Google Scholar

[15]

P. E. Gill, W. Murray and M. H. Wright, Practical Optimization,, Academic Press, (1981).   Google Scholar

[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).   Google Scholar

[17]

M. Guignard, Generalized Kuhn-Tucker conditions for mathematical programming problems in a Banach space,, SIAM Journal on Control, 7 (1969), 232.  doi: 10.1137/0307016.  Google Scholar

[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.  doi: 10.1023/A:1022503820909.  Google Scholar

[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.  doi: 10.1287/moor.28.3.533.16395.  Google Scholar

[20]

X. W. Liu and J. Sun, A robust primal-dual interior-point algorithm for nonlinear programs,, SIAM Journal on Optimization, 14 (2004), 1163.  doi: 10.1137/S1052623402400641.  Google Scholar

[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.  doi: 10.1007/s10957-005-2092-4.  Google Scholar

[22]

Z. Q. Luo, J. S. Pang and D. Ralph, Mathematical Programs with Equilibrium Constraints,, Cambridge University Press, (1996).  doi: 10.1017/CBO9780511983658.  Google Scholar

[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.  doi: 10.1080/02331930701761193.  Google Scholar

[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.  doi: 10.1007/s10957-014-0664-x.  Google Scholar

[25]

K. W. Meng and X. Q. Yang, Optimality conditions via exact penalty functions,, SIAM Journal on Optimization, 20 (2010), 3208.  doi: 10.1137/090771016.  Google Scholar

[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.  doi: 10.1007/s10589-006-8720-6.  Google Scholar

[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.  doi: 10.1016/0377-2217(93)E0339-Y.  Google Scholar

[28]

A. S. Nemirovski and M. J. Todd, Interior-point methods for optimization,, Acta Numerica, 17 (2008), 191.  doi: 10.1017/S0962492906370018.  Google Scholar

[29]

J. Nocedal and S. J. Wright, Numerical Optimization,, Springer Verlag, (2006).   Google Scholar

[30]

I. Pólik and T. Terlaky, Interior point methods for nonlinear optimization,, Nonlinear optimization, 1989 (2010), 215.  doi: 10.1007/978-3-642-11339-0_4.  Google Scholar

[31]

R. T. Rockafellar and R. J. B. Wets, Variational Analysis,, Springer-Verlag, (1998).  doi: 10.1007/978-3-642-02431-3.  Google Scholar

[32]

A. M. Rubinov, B. M. Glover and X. Q. Yang, Decreasing functions with applications to penalization,, SIAM Journal on Optimization, 10 (1999), 289.  doi: 10.1137/S1052623497326095.  Google Scholar

[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.  doi: 10.1007/s101070050116.  Google Scholar

[34]

G. Still and M. Streng, Optimality conditions in smooth nonlinear programming,, Journal of Optimization Theory and Applications, 90 (1996), 483.  doi: 10.1007/BF02189792.  Google Scholar

[35]

R. J. Vanderbei and D. F. Shanno, An interior-point algorithm for nonconvex nonlinear programming,, Computational Optimization and Applications, 13 (1999), 231.  doi: 10.1023/A:1008677427361.  Google Scholar

[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.  doi: 10.1007/s10107-004-0559-y.  Google Scholar

[37]

S. J. Wright, Primal-dual Interior-Point Methods,, SIAM, (1987).  doi: 10.1137/1.9781611971453.  Google Scholar

[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, 23 (2012), 1013.   Google Scholar

[39]

X. Q. Yang and Z. Q. Meng, Lagrange multipliers and calmness conditions of order $p$,, Mathematics of Operations Research, 32 (2007), 95.  doi: 10.1287/moor.1060.0217.  Google Scholar

[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.  doi: 10.1081/NFA-120022928.  Google Scholar

[41]

Y. Y. Ye, Interior Point Algorithms: Theory and Analysis,, Wiley-Interscience, (1997).  doi: 10.1002/9781118032701.  Google Scholar

show all references

References:
[1]

H. Y. Benson, A. Sen and D. F. Shanno, Interior-point methods for nonconvex nonlinear programming: Convergence analysis and computational performance,, , (2009).   Google Scholar

[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.  doi: 10.1007/s10107-003-0418-2.  Google Scholar

[3]

R. H. Byrd, G. Lopez-Calva and J. Nocedal, A line search exact penalty method using steering rules,, Mathematical Programming, 133 (2012), 39.  doi: 10.1007/s10107-010-0408-0.  Google Scholar

[4]

R. H. Byrd, J. Nocedal and R. A. Waltz, Steering exact penalty methods for nonlinear programming,, Optimization Methods and Software, 23 (2008), 197.  doi: 10.1080/10556780701394169.  Google Scholar

[5]

R. Chartrand and V. Staneva, Restricted isometry properties and nonconvex compressive sensing,, Inverse Problems, 24 (2008).  doi: 10.1088/0266-5611/24/3/035020.  Google Scholar

[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.  doi: 10.1007/s10107-005-0701-5.  Google Scholar

[7]

L. Chen and D. Goldfarb, On the Fast Local Convergence of Interior-point $l_2$-penalty Methods for Nonlinear Programming,, Technical report, (2006).   Google Scholar

[8]

X. J. Chen, Smoothing methods for nonsmooth, nonconvex minimization,, Mathematical Programming, 134 (2012), 71.  doi: 10.1007/s10107-012-0569-0.  Google Scholar

[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.  doi: 10.1007/s101070050112.  Google Scholar

[10]

F. E. Curtis, A penalty-interior-point algorithm for nonlinear constrained optimization,, Mathematical Programming Computation, 4 (2012), 181.  doi: 10.1007/s12532-012-0041-4.  Google Scholar

[11]

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

[12]

C. Durazzi, On the Newton interior-point method for nonlinear programming problems,, Journal of Optimization Theory and Applications, 104 (2000), 73.  doi: 10.1023/A:1004624721836.  Google Scholar

[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.  doi: 10.1007/BF02275347.  Google Scholar

[14]

R. Fletcher, Practical Methods of Optimization,, Second edition. A Wiley-Interscience Publication, (1987).   Google Scholar

[15]

P. E. Gill, W. Murray and M. H. Wright, Practical Optimization,, Academic Press, (1981).   Google Scholar

[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).   Google Scholar

[17]

M. Guignard, Generalized Kuhn-Tucker conditions for mathematical programming problems in a Banach space,, SIAM Journal on Control, 7 (1969), 232.  doi: 10.1137/0307016.  Google Scholar

[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.  doi: 10.1023/A:1022503820909.  Google Scholar

[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.  doi: 10.1287/moor.28.3.533.16395.  Google Scholar

[20]

X. W. Liu and J. Sun, A robust primal-dual interior-point algorithm for nonlinear programs,, SIAM Journal on Optimization, 14 (2004), 1163.  doi: 10.1137/S1052623402400641.  Google Scholar

[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.  doi: 10.1007/s10957-005-2092-4.  Google Scholar

[22]

Z. Q. Luo, J. S. Pang and D. Ralph, Mathematical Programs with Equilibrium Constraints,, Cambridge University Press, (1996).  doi: 10.1017/CBO9780511983658.  Google Scholar

[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.  doi: 10.1080/02331930701761193.  Google Scholar

[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.  doi: 10.1007/s10957-014-0664-x.  Google Scholar

[25]

K. W. Meng and X. Q. Yang, Optimality conditions via exact penalty functions,, SIAM Journal on Optimization, 20 (2010), 3208.  doi: 10.1137/090771016.  Google Scholar

[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.  doi: 10.1007/s10589-006-8720-6.  Google Scholar

[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.  doi: 10.1016/0377-2217(93)E0339-Y.  Google Scholar

[28]

A. S. Nemirovski and M. J. Todd, Interior-point methods for optimization,, Acta Numerica, 17 (2008), 191.  doi: 10.1017/S0962492906370018.  Google Scholar

[29]

J. Nocedal and S. J. Wright, Numerical Optimization,, Springer Verlag, (2006).   Google Scholar

[30]

I. Pólik and T. Terlaky, Interior point methods for nonlinear optimization,, Nonlinear optimization, 1989 (2010), 215.  doi: 10.1007/978-3-642-11339-0_4.  Google Scholar

[31]

R. T. Rockafellar and R. J. B. Wets, Variational Analysis,, Springer-Verlag, (1998).  doi: 10.1007/978-3-642-02431-3.  Google Scholar

[32]

A. M. Rubinov, B. M. Glover and X. Q. Yang, Decreasing functions with applications to penalization,, SIAM Journal on Optimization, 10 (1999), 289.  doi: 10.1137/S1052623497326095.  Google Scholar

[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.  doi: 10.1007/s101070050116.  Google Scholar

[34]

G. Still and M. Streng, Optimality conditions in smooth nonlinear programming,, Journal of Optimization Theory and Applications, 90 (1996), 483.  doi: 10.1007/BF02189792.  Google Scholar

[35]

R. J. Vanderbei and D. F. Shanno, An interior-point algorithm for nonconvex nonlinear programming,, Computational Optimization and Applications, 13 (1999), 231.  doi: 10.1023/A:1008677427361.  Google Scholar

[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.  doi: 10.1007/s10107-004-0559-y.  Google Scholar

[37]

S. J. Wright, Primal-dual Interior-Point Methods,, SIAM, (1987).  doi: 10.1137/1.9781611971453.  Google Scholar

[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, 23 (2012), 1013.   Google Scholar

[39]

X. Q. Yang and Z. Q. Meng, Lagrange multipliers and calmness conditions of order $p$,, Mathematics of Operations Research, 32 (2007), 95.  doi: 10.1287/moor.1060.0217.  Google Scholar

[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.  doi: 10.1081/NFA-120022928.  Google Scholar

[41]

Y. Y. Ye, Interior Point Algorithms: Theory and Analysis,, Wiley-Interscience, (1997).  doi: 10.1002/9781118032701.  Google Scholar

[1]

Justin Holmer, Chang Liu. Blow-up for the 1D nonlinear Schrödinger equation with point nonlinearity II: Supercritical blow-up profiles. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020264

[2]

Yuxia Guo, Shaolong Peng. A direct method of moving planes for fully nonlinear nonlocal operators and applications. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020462

[3]

Kihoon Seong. Low regularity a priori estimates for the fourth order cubic nonlinear Schrödinger equation. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5437-5473. doi: 10.3934/cpaa.2020247

[4]

Youshan Tao, Michael Winkler. Critical mass for infinite-time blow-up in a haptotaxis system with nonlinear zero-order interaction. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 439-454. doi: 10.3934/dcds.2020216

[5]

Peng Luo. Comparison theorem for diagonally quadratic BSDEs. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020374

[6]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054

[7]

Fioralba Cakoni, Pu-Zhao Kow, Jenn-Nan Wang. The interior transmission eigenvalue problem for elastic waves in media with obstacles. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020075

[8]

Jie Zhang, Yuping Duan, Yue Lu, Michael K. Ng, Huibin Chang. Bilinear constraint based ADMM for mixed Poisson-Gaussian noise removal. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020071

[9]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

[10]

Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020169

[11]

Christian Beck, Lukas Gonon, Martin Hutzenthaler, Arnulf Jentzen. On existence and uniqueness properties for solutions of stochastic fixed point equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020320

[12]

Zonghong Cao, Jie Min. Selection and impact of decision mode of encroachment and retail service in a dual-channel supply chain. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020167

[13]

Christopher S. Goodrich, Benjamin Lyons, Mihaela T. Velcsov. Analytical and numerical monotonicity results for discrete fractional sequential differences with negative lower bound. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020269

[14]

Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296

[15]

Djamel Aaid, Amel Noui, Özen Özer. Piecewise quadratic bounding functions for finding real roots of polynomials. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 63-73. doi: 10.3934/naco.2020015

[16]

Bahaaeldin Abdalla, Thabet Abdeljawad. Oscillation criteria for kernel function dependent fractional dynamic equations. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020443

[17]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013

[18]

Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019

[19]

Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070

[20]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (80)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]