The flattened aggregate constraint homotopy method for nonlinear programming problems with many nonlinear constraints. (English) Zbl 1470.90136

Zhou, Zhengyong; Yu, Bo

Abstr. Appl. Anal. 2014, Article ID 430932, 14 p. (2014).

Summary: The aggregate constraint homotopy method uses a single smoothing constraint instead of \(m\)-constraints to reduce the dimension of its homotopy map, and hence it is expected to be more efficient than the combined homotopy interior point method when the number of constraints is very large. However, the gradient and Hessian of the aggregate constraint function are complicated combinations of gradients and Hessians of all constraint functions, and hence they are expensive to calculate when the number of constraint functions is very large. In order to improve the performance of the aggregate constraint homotopy method for solving nonlinear programming problems, with few variables and many nonlinear constraints, a flattened aggregate constraint homotopy method, that can save much computation of gradients and Hessians of constraint functions, is presented. Under some similar conditions for other homotopy methods, existence and convergence of a smooth homotopy path are proven. A numerical procedure is given to implement the proposed homotopy method, preliminary computational results show its performance, and it is also competitive with the state-of-the-art solver KNITRO for solving large-scale nonlinear optimization.

MSC:

90C30	Nonlinear programming
90C06	Large-scale problems in mathematical programming
90C51	Interior-point methods
65K05	Numerical mathematical programming methods

Software:

LANCELOT; SifDec; KNITRO; SNOPT; CUTEr

References:

[1]	Ben-Tal, A.; Nemirovski, A., Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications (2001), Philadelphia, Pa, USA: Society for Industrial and Applied Mathematics, Philadelphia, Pa, USA · Zbl 0986.90032 · doi:10.1137/1.9780898718829
[2]	Boyd, S.; Vandenberghe, L., Convex Optimization (2004), Cambridge, UK: Cambridge University Press, Cambridge, UK · Zbl 1058.90049 · doi:10.1017/CBO9780511804441
[3]	Garcia, C. B.; Zangwill, W. I., Pathways to Solutions, Fixed Points, and Equilibria (1981), Englewood Cliffs, NJ, USA: Prentice Hall, Englewood Cliffs, NJ, USA · Zbl 0512.90070
[4]	Nesterov, Y.; Nemirovskii, A., Interior-Point Polynomial Algorithms in Convex Programming. Interior-Point Polynomial Algorithms in Convex Programming, SIAM Studies in Applied Mathematics, 13 (1994), Philadelphia, Pa, USA: Society for Industrial and Applied Mathematics (SIAM), Philadelphia, Pa, USA · Zbl 0824.90112 · doi:10.1137/1.9781611970791
[5]	Terlaky, T., Interior Point Methods of Mathematical Programming. Interior Point Methods of Mathematical Programming, Applied Optimization, 5 (1996), Dordrecht, The Netherlands: Kluwer Academic Publishers, Dordrecht, The Netherlands · Zbl 0866.00024 · doi:10.1007/978-1-4613-3449-1
[6]	Ye, Y. Y., Interior Point Algorithms. Interior Point Algorithms, Wiley-Interscience Series in Discrete Mathematics and Optimization (1997), New York, NY, USA: John Wiley & Sons, New York, NY, USA · Zbl 0943.90070 · doi:10.1002/9781118032701
[7]	Forsgren, A.; Gill, P. E., Primal-dual interior methods for nonconvex nonlinear programming, SIAM Journal on Optimization, 8, 4, 1132-1152 (1998) · Zbl 0915.90236 · doi:10.1137/S1052623496305560
[8]	Gay, D. M.; Overton, M. L.; Wright, M. H., A primal-dual interior method for nonconvex nonlinear programming, Advances in Nonlinear Programming. Advances in Nonlinear Programming, Applied Optimization, 14, 31-56 (1998), Dordrecht, The Netherlands: Kluwer Academic Publishers, Dordrecht, The Netherlands · Zbl 0908.90236 · doi:10.1007/978-1-4613-3335-7_2
[9]	Vanderbei, R. J.; Shanno, D. F., An interior-point algorithm for nonconvex nonlinear programming, Computational Optimization and Applications, 13, 1-3, 231-252 (1999) · Zbl 1040.90564 · doi:10.1023/A:1008677427361
[10]	Feng, G.; Lin, Z.; Yu, B., Existence of an interior pathway to a Karush-Kuhn-Tucker point of a nonconvex programming problem, Nonlinear Analysis: Theory, Methods & Applications, 32, 6, 761-768 (1998) · Zbl 1060.90692 · doi:10.1016/S0362-546X(97)00516-6
[11]	Feng, G. C.; Yu, B., Combined homotopy interior point method for nonlinear programming problems, Advances in Numerical Mathematics. Advances in Numerical Mathematics, Lecture Notes in Numerical and Applied Analysis, 14, 9-16 (1995) · Zbl 0836.65081
[12]	Watson, L. T., Theory of globally convergent probability-one homotopies for nonlinear programming, SIAM Journal on Optimization, 11, 3, 761-780 (2000/01) · Zbl 0994.65070 · doi:10.1137/S105262349936121X
[13]	Liu, Q. H.; Yu, B.; Feng, G. C., An interior point path-following method for nonconvex programming with quasi normal cone condition, Advances in Mathematics, 19, 4, 281-282 (2000)
[14]	Yu, B.; Liu, Q. H.; Feng, G. C., A combined homotopy interior point method for nonconvex programming with pseudo cone condition, Northeastern Mathematical Journal, 16, 4, 383-386 (2000) · Zbl 1022.90039
[15]	Shang, Y. F., Constraint shifting combined homotopy method for nonlinear programming, equilibrium programming and variational inequalities [Ph.D. thesis] (2006), Jilin University
[16]	Yu, B.; Shang, Y. F., Boundary moving combined homotopy method for nonconvex nonlinear programming, Journal of Mathematical Research and Exposition, 26, 4, 831-834 (2006) · Zbl 1126.65057
[17]	Li, X. S., An aggregate function method for nonlinear programming, Science in China A: Mathematics, Physics, Astronomy, 34, 12, 1467-1473 (1991) · Zbl 0752.90069
[18]	Kort, B. W.; Bertsekas, D. P., A new penalty function algorithm for constrained minimization, Proceedings of the 1972 IEEE Conference on Decision and Control
[19]	Yu, B.; Feng, G. C.; Zhang, S. L., The aggregate constraint homotopy method for nonconvex nonlinear programming, Nonlinear Analysis: Theory, Methods & Applications, 45, 7, 839-847 (2001) · Zbl 1002.90092 · doi:10.1016/S0362-546X(99)00420-4
[20]	Allgower, E. L.; Georg, K., Introduction to Numerical Continuation Methods. Introduction to Numerical Continuation Methods, Classics in Applied Mathematics, 45 (2003), Philadelphia, Pa, USA: Society for Industrial and Applied Mathematics (SIAM), Philadelphia, Pa, USA · Zbl 1036.65047 · doi:10.1137/1.9780898719154
[21]	Gould, N. I. M.; Orban, D.; Toint, P. L., CUTEr (and sifdec), a constrained and unconstrained testing environment, revisited, TR/PA/01/04 (2001), Toulouse, France: CERFACS, Toulouse, France · Zbl 1068.90526
[22]	Li, D. H.; Qi, L.; Tam, J.; Wu, S. Y., A smoothing Newton method for semi-infinite programming, Journal of Global Optimization, 30, 2-3, 169-194 (2004) · Zbl 1066.90131 · doi:10.1007/s10898-004-8266-z
[23]	Byrd, R. H.; Hribar, M. E.; Nocedal, J., An interior point algorithm for large-scale nonlinear programming, SIAM Journal on Optimization, 9, 4, 877-900 (1999) · Zbl 0957.65057 · doi:10.1137/S1052623497325107
[24]	Conn, A. R.; Gould, N. I. M.; Toint, Ph. L., LANCELOT: A Fortran Package for Large-Scale Nonlinear Optimization (Release A). LANCELOT: A Fortran Package for Large-Scale Nonlinear Optimization (Release A), Springer Series in Computational Mathematics, 17 (1992), New York, NY, USA: Springer, New York, NY, USA · Zbl 0761.90087 · doi:10.1007/978-3-662-12211-2
[25]	Fletcher, R.; Leyffer, S., Nonlinear programming without a penalty function, Mathematical Programming A, 91, 2, 239-269 (2002) · Zbl 1049.90088 · doi:10.1007/s101070100244
[26]	Gill, P. E.; Murray, W.; Saunders, M. A., SNOPT: an SQP algorithm for large-scale constrained optimization, SIAM Journal on Optimization, 12, 4, 979-1006 (2002) · Zbl 1027.90111 · doi:10.1137/S1052623499350013