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

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

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

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

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

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

[7]

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

[8]

X. J. Chen, Smoothing methods for nonsmooth, nonconvex minimization,, Mathematical Programming, 134 (2012), 71. 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. doi: 10.1007/s101070050112.

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

[11]

E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles,, Mathematical Programming, 91 (2002), 201. 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. 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. doi: 10.1007/BF02275347.

[14]

R. Fletcher, Practical Methods of Optimization,, Second edition. A Wiley-Interscience Publication, (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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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, 1989 (2010), 215. doi: 10.1007/978-3-642-11339-0_4.

[31]

R. T. Rockafellar and R. J. B. Wets, Variational Analysis,, Springer-Verlag, (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. 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. 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. 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. 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. 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, 23 (2012), 1013.

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

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

[41]

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

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

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

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

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

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

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

[7]

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

[8]

X. J. Chen, Smoothing methods for nonsmooth, nonconvex minimization,, Mathematical Programming, 134 (2012), 71. 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. doi: 10.1007/s101070050112.

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

[11]

E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles,, Mathematical Programming, 91 (2002), 201. 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. 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. doi: 10.1007/BF02275347.

[14]

R. Fletcher, Practical Methods of Optimization,, Second edition. A Wiley-Interscience Publication, (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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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, 1989 (2010), 215. doi: 10.1007/978-3-642-11339-0_4.

[31]

R. T. Rockafellar and R. J. B. Wets, Variational Analysis,, Springer-Verlag, (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. 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. 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. 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. 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. 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, 23 (2012), 1013.

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

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

[41]

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

[1]

Yu-Hong Dai, Xin-Wei Liu, Jie Sun. A primal-dual interior-point method capable of rapidly detecting infeasibility for nonlinear programs. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-27. doi: 10.3934/jimo.2018190

[2]

Siqi Li, Weiyi Qian. Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37

[3]

Yanqin Bai, Xuerui Gao, Guoqiang Wang. Primal-dual interior-point algorithms for convex quadratic circular cone optimization. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 211-231. doi: 10.3934/naco.2015.5.211

[4]

Guoqiang Wang, Zhongchen Wu, Zhongtuan Zheng, Xinzhong Cai. Complexity analysis of primal-dual interior-point methods for semidefinite optimization based on a parametric kernel function with a trigonometric barrier term. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 101-113. doi: 10.3934/naco.2015.5.101

[5]

Gianni Di Pillo, Giampaolo Liuzzi, Stefano Lucidi. A primal-dual algorithm for nonlinear programming exploiting negative curvature directions. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 509-528. doi: 10.3934/naco.2011.1.509

[6]

Jen-Yen Lin, Hui-Ju Chen, Ruey-Lin Sheu. Augmented Lagrange primal-dual approach for generalized fractional programming problems. Journal of Industrial & Management Optimization, 2013, 9 (4) : 723-741. doi: 10.3934/jimo.2013.9.723

[7]

Yanqin Bai, Pengfei Ma, Jing Zhang. A polynomial-time interior-point method for circular cone programming based on kernel functions. Journal of Industrial & Management Optimization, 2016, 12 (2) : 739-756. doi: 10.3934/jimo.2016.12.739

[8]

Soodabeh Asadi, Hossein Mansouri. A Mehrotra type predictor-corrector interior-point algorithm for linear programming. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 147-156. doi: 10.3934/naco.2019011

[9]

Behrouz Kheirfam. A full Nesterov-Todd step infeasible interior-point algorithm for symmetric optimization based on a specific kernel function. Numerical Algebra, Control & Optimization, 2013, 3 (4) : 601-614. doi: 10.3934/naco.2013.3.601

[10]

Cheng Ma, Xun Li, Ka-Fai Cedric Yiu, Yongjian Yang, Liansheng Zhang. On an exact penalty function method for semi-infinite programming problems. Journal of Industrial & Management Optimization, 2012, 8 (3) : 705-726. doi: 10.3934/jimo.2012.8.705

[11]

Yanqin Bai, Lipu Zhang. A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization. Journal of Industrial & Management Optimization, 2011, 7 (4) : 891-906. doi: 10.3934/jimo.2011.7.891

[12]

Zhiqing Meng, Qiying Hu, Chuangyin Dang. A penalty function algorithm with objective parameters for nonlinear mathematical programming. Journal of Industrial & Management Optimization, 2009, 5 (3) : 585-601. doi: 10.3934/jimo.2009.5.585

[13]

Yanqin Bai, Chuanhao Guo. Doubly nonnegative relaxation method for solving multiple objective quadratic programming problems. Journal of Industrial & Management Optimization, 2014, 10 (2) : 543-556. doi: 10.3934/jimo.2014.10.543

[14]

Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353

[15]

Fengmin Wang, Dachuan Xu, Donglei Du, Chenchen Wu. Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 91-100. doi: 10.3934/naco.2015.5.91

[16]

Xiaojing Ye, Haomin Zhou. Fast total variation wavelet inpainting via approximated primal-dual hybrid gradient algorithm. Inverse Problems & Imaging, 2013, 7 (3) : 1031-1050. doi: 10.3934/ipi.2013.7.1031

[17]

Behrouz Kheirfam, Morteza Moslemi. On the extension of an arc-search interior-point algorithm for semidefinite optimization. Numerical Algebra, Control & Optimization, 2018, 8 (2) : 261-275. doi: 10.3934/naco.2018015

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

Yinghong Xu, Lipu Zhang, Jing Zhang. A full-modified-Newton step infeasible interior-point algorithm for linear optimization. Journal of Industrial & Management Optimization, 2016, 12 (1) : 103-116. doi: 10.3934/jimo.2016.12.103

[20]

Liming Sun, Li-Zhi Liao. An interior point continuous path-following trajectory for linear programming. Journal of Industrial & Management Optimization, 2018, 13 (5) : 1-18. doi: 10.3934/jimo.2018107

2017 Impact Factor: 0.994

Metrics

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

Other articles
by authors

[Back to Top]