A primal-dual algorithm for nonlinear programming exploiting negative curvature directions

Previous Article
A unified nonlinear augmented Lagrangian approach for nonconvex vector optimization
NACO Home
This Issue
Next Article
A smoothing Broyden-like method for polyhedral cone constrained eigenvalue problem

2011, 1(3): 509-528. doi: 10.3934/naco.2011.1.509

A primal-dual algorithm for nonlinear programming exploiting negative curvature directions

Gianni Di Pillo ^1, , Giampaolo Liuzzi ^2, and Stefano Lucidi ^1,

1.	Sapienza University of Rome, Department of Computer and System Sciences ``A. Ruberti'', Via Ariosto 25, 00185 Roma, Italy, Italy
2.	Italian National Research Council, Institute for Systems Analysis and Computer Science ``A. Ruberti'', Viale Manzoni 30, 00185 Roma, Italy

Received April 2011 Revised August 2011 Published September 2011

Abstract
Related Papers

In this paper we propose a primal-dual algorithm for the solution of inequality constrained optimization problems. The distinguishing feature of the proposed algorithm is that of exploiting as much as possible the local non-convexity of the problem to the aim of producing a sequence of points converging to second order stationary points. In the unconstrained case this task is accomplished by computing a suitable negative curvature direction of the objective function. In the constrained case it is possible to gain analogous information by exploiting the non-convexity of a particular exact merit function. The algorithm hinges on the idea of comparing, at every iteration, the relative effects of two directions and then selecting the more promising one. The first direction conveys first order information on the problem and can be used to define a sequence of points converging toward a KKT pair of the problem. Whereas, the second direction conveys information on the local non-convexity of the problem and can be used to drive the algorithm away from regions of non-convexity. We propose a proper selection rule for these two directions which, under suitable assumptions, is able to generate a sequence of points that is globally convergent to KKT pairs that satisfy the second order necessary optimality conditions, with superlinear convergence rate if the KKT pair satisfies also the strong second order sufficiency optimality conditions.

Keywords: Nonlinear Programming, second order stationary point., primal-dual algorithm, exact augmented Lagrangian.

Mathematics Subject Classification: Primary: 90C30; Secondary: 65K0.

Citation: 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

References:

[1]	A. Auslender, Penalty methods for computing points that satisfy second order necessary conditions,, Mathematical Programming, 17 (1979), 229. doi: 10.1007/BF01588245. Google Scholar
[2]	R. H. Byrd, R. B. Schnabel and G. A. Shultz, A trust region algorithm for nonlinearly constrained optimization,, SIAM Journal on Numerical Analysis, 24 (1987), 1152. doi: 10.1137/0724076. Google Scholar
[3]	F. H. Clarke, "Optimization and Nonsmooth Analysis,", John Wiley & Sons, (1983). Google Scholar
[4]	T. F. Coleman, J. G. Liu and W. Yuan, A new trust-region algorithm for equality constrained optimization,, Computational Optimization and Applications, 21 (2002), 177. doi: 10.1023/A:1013764800871. Google Scholar
[5]	A. R. Conn, N. I. M. Gould, D. Orban and Ph. L. Toint, A primal-dual trust region algorithm for non-convex nonlinear programming,, Math. Programming, 87 (2000), 215. Google Scholar
[6]	R. S. Dembo, S. C. Eisenstat and T. Steihaug, Inexact Newton methods,, SIAM Journal on Numerical Anlysis, 19 (1982), 400. doi: 10.1137/0719025. Google Scholar
[7]	J. E. Dennis and L. N. Vicente, On the convergence theory of trust-region-based algorithms for equality-constrained optimization,, SIAM Journal on Optimization, 7 (1994), 527. Google Scholar
[8]	J. E. Dennis, M. Heinkenschloss and L. N. Vicente, Trust-region interior-point SQP algorithms for a class of nonlinear programming problems,, SIAM Journal on Control and Optimization, 36 (1998), 1750. doi: 10.1137/S036012995279031. Google Scholar
[9]	G. Di Pillo and L. Grippo, Exact penalty functions in constrained optimization,, SIAM J. on Control and Optimization, 27 (1989), 1333. doi: 10.1137/0327068. Google Scholar
[10]	G. Di Pillo, G. Liuzzi, S. Lucidi and L. Palagi, A truncated Newton method in an augmented Lagrangian framework for nonlinear programming,, Computational Optimization and Applications, 45 (2010), 311. doi: 10.1007/s10589-008-9216-3. Google Scholar
[11]	G. Di Pillo and S. Lucidi, On exact Augmented Lagrangian functions in nonlinear programming,, In, (1996), 85. Google Scholar
[12]	G. Di Pillo and S. Lucidi, An augmented Lagrangian function with improved exactness properties,, SIAM Journal on Optimization, 12 (2001), 376. doi: 10.1137/S1052623497321894. Google Scholar
[13]	G. Di Pillo, S. Lucidi and L. Palagi, Convergence to second-order stationary points of a primal-dual algorithm model for nonlinear programming,, Mathematics of Operations Research, 30 (2005), 897. doi: 10.1287/moor.1050.0150. Google Scholar
[14]	M. M. El-Alem, Convergence to a second-order point of a trust-region algorithm with a nonmonotonic penalty parameter for constrained optimization,, Journal of Optimization Theory and Applications, 91 (1996), 61. doi: 10.1007/BF02192282. Google Scholar
[15]	F. Facchinei, Minimization of SC1 functions and the Maratos effect,, Operations Research Letters, 17 (1995), 131. doi: 10.1016/0167-6377(94)00059-F. Google Scholar
[16]	F. Facchinei, A. Fischer and C. Kanzow, On the accurate identification of active constraints,, SIAM Journal on Optimization, 9 (1998), 14. doi: 10.1137/S1052623496305882. Google Scholar
[17]	F. Facchinei and S. Lucidi, Quadratically and superlinearly convergent algorithms for the solution of inequality constrained minimization problems,, Journal of Optimization Theory and Applications, 85 (1995), 265. doi: 10.1007/BF02192227. Google Scholar
[18]	F. Facchinei and S. Lucidi, Convergence to second order stationary points in inequality constrained optimization,, Mathematics of Operations Research, 23 (1998), 746. doi: 10.1287/moor.23.3.746. Google Scholar
[19]	G. Fasano and S. Lucidi, A nonmonotone truncated Newton-Krylov method exploiting negative curvature directions, for large scale unconstrained optimization,, Optimization Letters, 3 (2009), 521. doi: 10.1007/s11590-009-0132-y. Google Scholar
[20]	A. Forsgren and W. Murray, Newton methods for large-scale linear inequality constrained minimization,, SIAM Journal on Optimization, 7 (1997), 162. doi: 10.1137/S1052623494279122. Google Scholar
[21]	L. Grippo, F. Lampariello and S. Lucidi, A truncated Newton method with nomonotone linesearch for unconstrained optimization,, Journal of Optimization Theory and Applications, 60 (1989), 401. doi: 10.1007/BF00940345. Google Scholar
[22]	J. B. Hiriart-Urruty, J. J. Strodiot and V. H. Nguyen, Generalized Hessian matrix and second-order optimality conditions for problems with C^1,1 data,, Applied Mathematics and Optimization, 11 (1984), 43. doi: 10.1007/BF01442169. Google Scholar
[23]	S. Lucidi, F. Rochetich and M. Roma, Curvilinear stabilization techniques for truncated Newton methods in large scale unconstrained optimization: The complete results,, SIAM Journal on Optimization, 8 (1998), 916. doi: 10.1137/S1052623495295250. Google Scholar
[24]	G. P. McCormick, "Nonlinear Programming: Theory, Algorithms and Applications,", John Wiley & Sons, (1983). Google Scholar
[25]	J. M. Moguerza and F. J. Prieto, An augmented Lagrangian interior point method using directions of negative curvature,, Mathematical Programming, 95 (2003), 573. doi: 10.1007/s10107-002-0360-8. Google Scholar
[26]	J. J. Moré and D. C. Sorensen, On the use of directions of negative curvature in a modified Newton method,, Mathematical Programming, 16 (1979), 1. doi: 10.1007/BF01582091. Google Scholar
[27]	J. J. Moré and D. C. Sorensen, Computing a trust region step,, SIAM Journal on Scientific and Statistical Computing, 4 (1983), 553. Google Scholar
[28]	H. Mukai and E. Polak, A second-order method for the general nonlinear programming problem,, Journal of Optimization Theory and Applications, 26 (1978), 515. doi: 10.1007/BF00933150. Google Scholar
[29]	L. Qi and J. Sun, A nonsmooth version of Newton's method,, Mathematical Programming, 58 (1993), 353. doi: 10.1007/BF01581275. Google Scholar
[30]	D. C. Sorensen, Newton's method with a model trust region modification,, SIAM Journal on Numerical Analysis, 19 (1982), 409. doi: 10.1137/0719026. Google Scholar
[31]	P. Tseng, A convergent infeasible interior-point trust-region method for constrained optimization,, SIAM Journal on Optimization, 13 (2002), 432. doi: 10.1137/S1052623499357945. Google Scholar

show all references

References:

[1]	A. Auslender, Penalty methods for computing points that satisfy second order necessary conditions,, Mathematical Programming, 17 (1979), 229. doi: 10.1007/BF01588245. Google Scholar
[2]	R. H. Byrd, R. B. Schnabel and G. A. Shultz, A trust region algorithm for nonlinearly constrained optimization,, SIAM Journal on Numerical Analysis, 24 (1987), 1152. doi: 10.1137/0724076. Google Scholar
[3]	F. H. Clarke, "Optimization and Nonsmooth Analysis,", John Wiley & Sons, (1983). Google Scholar
[4]	T. F. Coleman, J. G. Liu and W. Yuan, A new trust-region algorithm for equality constrained optimization,, Computational Optimization and Applications, 21 (2002), 177. doi: 10.1023/A:1013764800871. Google Scholar
[5]	A. R. Conn, N. I. M. Gould, D. Orban and Ph. L. Toint, A primal-dual trust region algorithm for non-convex nonlinear programming,, Math. Programming, 87 (2000), 215. Google Scholar
[6]	R. S. Dembo, S. C. Eisenstat and T. Steihaug, Inexact Newton methods,, SIAM Journal on Numerical Anlysis, 19 (1982), 400. doi: 10.1137/0719025. Google Scholar
[7]	J. E. Dennis and L. N. Vicente, On the convergence theory of trust-region-based algorithms for equality-constrained optimization,, SIAM Journal on Optimization, 7 (1994), 527. Google Scholar
[8]	J. E. Dennis, M. Heinkenschloss and L. N. Vicente, Trust-region interior-point SQP algorithms for a class of nonlinear programming problems,, SIAM Journal on Control and Optimization, 36 (1998), 1750. doi: 10.1137/S036012995279031. Google Scholar
[9]	G. Di Pillo and L. Grippo, Exact penalty functions in constrained optimization,, SIAM J. on Control and Optimization, 27 (1989), 1333. doi: 10.1137/0327068. Google Scholar
[10]	G. Di Pillo, G. Liuzzi, S. Lucidi and L. Palagi, A truncated Newton method in an augmented Lagrangian framework for nonlinear programming,, Computational Optimization and Applications, 45 (2010), 311. doi: 10.1007/s10589-008-9216-3. Google Scholar
[11]	G. Di Pillo and S. Lucidi, On exact Augmented Lagrangian functions in nonlinear programming,, In, (1996), 85. Google Scholar
[12]	G. Di Pillo and S. Lucidi, An augmented Lagrangian function with improved exactness properties,, SIAM Journal on Optimization, 12 (2001), 376. doi: 10.1137/S1052623497321894. Google Scholar
[13]	G. Di Pillo, S. Lucidi and L. Palagi, Convergence to second-order stationary points of a primal-dual algorithm model for nonlinear programming,, Mathematics of Operations Research, 30 (2005), 897. doi: 10.1287/moor.1050.0150. Google Scholar
[14]	M. M. El-Alem, Convergence to a second-order point of a trust-region algorithm with a nonmonotonic penalty parameter for constrained optimization,, Journal of Optimization Theory and Applications, 91 (1996), 61. doi: 10.1007/BF02192282. Google Scholar
[15]	F. Facchinei, Minimization of SC1 functions and the Maratos effect,, Operations Research Letters, 17 (1995), 131. doi: 10.1016/0167-6377(94)00059-F. Google Scholar
[16]	F. Facchinei, A. Fischer and C. Kanzow, On the accurate identification of active constraints,, SIAM Journal on Optimization, 9 (1998), 14. doi: 10.1137/S1052623496305882. Google Scholar
[17]	F. Facchinei and S. Lucidi, Quadratically and superlinearly convergent algorithms for the solution of inequality constrained minimization problems,, Journal of Optimization Theory and Applications, 85 (1995), 265. doi: 10.1007/BF02192227. Google Scholar
[18]	F. Facchinei and S. Lucidi, Convergence to second order stationary points in inequality constrained optimization,, Mathematics of Operations Research, 23 (1998), 746. doi: 10.1287/moor.23.3.746. Google Scholar
[19]	G. Fasano and S. Lucidi, A nonmonotone truncated Newton-Krylov method exploiting negative curvature directions, for large scale unconstrained optimization,, Optimization Letters, 3 (2009), 521. doi: 10.1007/s11590-009-0132-y. Google Scholar
[20]	A. Forsgren and W. Murray, Newton methods for large-scale linear inequality constrained minimization,, SIAM Journal on Optimization, 7 (1997), 162. doi: 10.1137/S1052623494279122. Google Scholar
[21]	L. Grippo, F. Lampariello and S. Lucidi, A truncated Newton method with nomonotone linesearch for unconstrained optimization,, Journal of Optimization Theory and Applications, 60 (1989), 401. doi: 10.1007/BF00940345. Google Scholar
[22]	J. B. Hiriart-Urruty, J. J. Strodiot and V. H. Nguyen, Generalized Hessian matrix and second-order optimality conditions for problems with C^1,1 data,, Applied Mathematics and Optimization, 11 (1984), 43. doi: 10.1007/BF01442169. Google Scholar
[23]	S. Lucidi, F. Rochetich and M. Roma, Curvilinear stabilization techniques for truncated Newton methods in large scale unconstrained optimization: The complete results,, SIAM Journal on Optimization, 8 (1998), 916. doi: 10.1137/S1052623495295250. Google Scholar
[24]	G. P. McCormick, "Nonlinear Programming: Theory, Algorithms and Applications,", John Wiley & Sons, (1983). Google Scholar
[25]	J. M. Moguerza and F. J. Prieto, An augmented Lagrangian interior point method using directions of negative curvature,, Mathematical Programming, 95 (2003), 573. doi: 10.1007/s10107-002-0360-8. Google Scholar
[26]	J. J. Moré and D. C. Sorensen, On the use of directions of negative curvature in a modified Newton method,, Mathematical Programming, 16 (1979), 1. doi: 10.1007/BF01582091. Google Scholar
[27]	J. J. Moré and D. C. Sorensen, Computing a trust region step,, SIAM Journal on Scientific and Statistical Computing, 4 (1983), 553. Google Scholar
[28]	H. Mukai and E. Polak, A second-order method for the general nonlinear programming problem,, Journal of Optimization Theory and Applications, 26 (1978), 515. doi: 10.1007/BF00933150. Google Scholar
[29]	L. Qi and J. Sun, A nonsmooth version of Newton's method,, Mathematical Programming, 58 (1993), 353. doi: 10.1007/BF01581275. Google Scholar
[30]	D. C. Sorensen, Newton's method with a model trust region modification,, SIAM Journal on Numerical Analysis, 19 (1982), 409. doi: 10.1137/0719026. Google Scholar
[31]	P. Tseng, A convergent infeasible interior-point trust-region method for constrained optimization,, SIAM Journal on Optimization, 13 (2002), 432. doi: 10.1137/S1052623499357945. Google Scholar

[1]	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
[2]	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
[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]	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
[5]	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
[6]	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
[7]	Li Jin, Hongying Huang. Differential equation method based on approximate augmented Lagrangian for nonlinear programming. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-15. doi: 10.3934/jimo.2019053
[8]	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
[9]	Chunrong Chen, T. C. Edwin Cheng, Shengji Li, Xiaoqi Yang. Nonlinear augmented Lagrangian for nonconvex multiobjective optimization. Journal of Industrial & Management Optimization, 2011, 7 (1) : 157-174. doi: 10.3934/jimo.2011.7.157
[10]	Yu Tian, John R. Graef, Lingju Kong, Min Wang. Existence of solutions to a multi-point boundary value problem for a second order differential system via the dual least action principle. Conference Publications, 2013, 2013 (special) : 759-769. doi: 10.3934/proc.2013.2013.759
[11]	Chunrong Chen. A unified nonlinear augmented Lagrangian approach for nonconvex vector optimization. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 495-508. doi: 10.3934/naco.2011.1.495
[12]	Xiantao Xiao, Liwei Zhang, Jianzhong Zhang. On convergence of augmented Lagrangian method for inverse semi-definite quadratic programming problems. Journal of Industrial & Management Optimization, 2009, 5 (2) : 319-339. doi: 10.3934/jimo.2009.5.319
[13]	Yuan Shen, Wenxing Zhang, Bingsheng He. Relaxed augmented Lagrangian-based proximal point algorithms for convex optimization with linear constraints. Journal of Industrial & Management Optimization, 2014, 10 (3) : 743-759. doi: 10.3934/jimo.2014.10.743
[14]	Xinmin Yang. On second order symmetric duality in nondifferentiable multiobjective programming. Journal of Industrial & Management Optimization, 2009, 5 (4) : 697-703. doi: 10.3934/jimo.2009.5.697
[15]	Anis Theljani, Ke Chen. An augmented lagrangian method for solving a new variational model based on gradients similarity measures and high order regulariation for multimodality registration. Inverse Problems & Imaging, 2019, 13 (2) : 309-335. doi: 10.3934/ipi.2019016
[16]	Chuanhao Guo, Erfang Shan, Wenli Yan. A superlinearly convergent hybrid algorithm for solving nonlinear programming. Journal of Industrial & Management Optimization, 2017, 13 (2) : 1009-1024. doi: 10.3934/jimo.2016059
[17]	Nicolás Borda, Javier Fernández, Sergio Grillo. Discrete second order constrained Lagrangian systems: First results. Journal of Geometric Mechanics, 2013, 5 (4) : 381-397. doi: 10.3934/jgm.2013.5.381
[18]	Yi Zhang, Yong Jiang, Liwei Zhang, Jiangzhong Zhang. A perturbation approach for an inverse linear second-order cone programming. Journal of Industrial & Management Optimization, 2013, 9 (1) : 171-189. doi: 10.3934/jimo.2013.9.171
[19]	Shiyun Wang, Yong-Jin Liu, Yong Jiang. A majorized penalty approach to inverse linear second order cone programming problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 965-976. doi: 10.3934/jimo.2014.10.965
[20]	Xiaoni Chi, Zhongping Wan, Zijun Hao. Second order sufficient conditions for a class of bilevel programs with lower level second-order cone programming problem. Journal of Industrial & Management Optimization, 2015, 11 (4) : 1111-1125. doi: 10.3934/jimo.2015.11.1111

Impact Factor:

American Institute of Mathematical Sciences