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 and 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, 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.

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

[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 and Management Optimization, 2020, 16 (2) : 1009-1035. 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 and 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 and 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 and 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 and Optimization, 2011, 1 (3) : 509-528. doi: 10.3934/naco.2011.1.509

[6]

Nadia Hazzam, Zakia Kebbiche. A primal-dual interior point method for $ P_{\ast }\left( \kappa \right) $-HLCP based on a class of parametric kernel functions. Numerical Algebra, Control and Optimization, 2021, 11 (4) : 513-531. doi: 10.3934/naco.2020053

[7]

Xiayang Zhang, Yuqian Kong, Shanshan Liu, Yuan Shen. A relaxed parameter condition for the primal-dual hybrid gradient method for saddle-point problem. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022008

[8]

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

[9]

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

[10]

Kai Wang, Deren Han. On the linear convergence of the general first order primal-dual algorithm. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021134

[11]

Yixuan Yang, Yuchao Tang, Meng Wen, Tieyong Zeng. Preconditioned Douglas-Rachford type primal-dual method for solving composite monotone inclusion problems with applications. Inverse Problems and Imaging, 2021, 15 (4) : 787-825. doi: 10.3934/ipi.2021014

[12]

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

[13]

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

[14]

Ayache Benhadid, Fateh Merahi. Complexity analysis of an interior-point algorithm for linear optimization based on a new parametric kernel function with a double barrier term. Numerical Algebra, Control and Optimization, 2022  doi: 10.3934/naco.2022003

[15]

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

[16]

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 and Management Optimization, 2012, 8 (3) : 705-726. doi: 10.3934/jimo.2012.8.705

[17]

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

[18]

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

[19]

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

[20]

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

2020 Impact Factor: 1.801

Metrics

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

Other articles
by authors

[Back to Top]