Large-scale nonlinear programming algorithm using projection methods

Białoń, Paweł

Discussiones Mathematicae. Differential Inclusions, Control and Optimization, Tome 20 (2000) no. 2, pp. 171-194.

Résumé

A method for solving large convex optimization problems is presented. Such problems usually contain a big linear part and only a small or medium nonlinear part. The parts are tackled using two specialized (and thus efficient) external solvers: purely nonlinear and large-scale linear with a quadratic goal function. The decomposition uses an alteration of projection methods. The construction of the method is based on the zigzagging phenomenon and yields a non-asymptotic convergence, not dependent on a large dimension of the problem. The method preserves its convergence properties under limitations in complicating sets by geometric cuts. Various aspects and variants of the method are analyzed theoretically and experimentally.

Détail

Keywords: nonlinear optimization, large scale optimization, projection methods, zigzagging

Bibliographie

[1] A. Altman and J. Gondzio, Regularized Symmetric Indefinite Systems in Interior Point Methods for Linear and Quadratic Optimization, Optimization Methods and Software 11-12 (2000), 275-302.

[2] H. Bauschke and J. Borwein, On projection algorithms for solving convex feasibility problems, SIAM Review 38 (3) (1996), 367-426.

[3] A. Cegielski, A method of projection onto an acute cone with level control in convex minimization, Math. Progr. 85 (1999), 469-490.

[4] A. Cegielski, Relaxation methods in Convex Optimization Problems, Higher College of Engineering, Series Monographies, No. 67, Zielona Góra, Poland (in Polish).

[5] R. Dylewski, Numerical behavior of the method of projection onto an acute cone with level control in convex optimization, Discuss. Math. Differential Inclusions, Control and Optimization 20 (2000), 147-158.

[6] S. Flam and J. Zowe, Relaxed outer projections, weighted averages and convex feasibility, BIT 30 (1990), 289-300.

[7] S. Kim, A. Hyunsil and C. Seong-Cheol, Variable target value subgradient method, Math. Progr. 49 (1991), 356-369.

[8] K. Kiwiel, Monotone Gram matrices and deepest surrogate inequalities in accelerated relaxation methods for convex feasibility problems, Linear Algebra and its Applications 215 (1997), 27-33.

[9] K. Kiwiel, The efficiency of subgradient projection methods for convex optimization, Part I: General level methods, SIAM Control Optim. 34 (2) (1996), 660-676.

[10] K. Kiwiel, Block-Iterative Surrogate Projection Methods for Convex Feasibility Problems, Linear Algebra and its Applications 15 (1995), 225-259.

[11] T. Kręglewski, J. Granat and A. Wierzbicki, IAC-DIDAS-N - A Dynamic Interactive Decision Analysis and Support System for Multicriteria Analysis of Nonlinear Models, v. 4.0, Collaborative Paper, CP-91-101, International Institute for Applied Systems Analysis, Laxenburg, Austria, June 1991.

[12] C. Lemaréchal, A.S. Nemirovskii and Yu. Nesterov, New variants of bundle methods, Math. Progr. 69 (1995), 111-147.

[13] B. Łopuch, Projection methods with an aggregation for convex feasibility problems, Doctoral thesis, Institute of Systems Research, Warsaw 1997 (in Polish).

[14] M. Makowski, LP-DIT data interchange tool for linear programming problems (version 1.20), Working Paper, WP-94-36, International Institute for Applied Systems Analysis, Laxenburg, Austria 1994.

[15] A.S. Nemirovskii and D. Yudin, Optimization Problem Complexity and Method Efficiency, Nauka, Moscow 1979 (in Russian).

[16] T. Polyak, Minimization of unsmooth functionals, Zh. Vychiisl. Mat. Fiz. 9 (1969), 14-29 (in Russian).

[17] M. Shchepakin, On a modification of a class of algorithms for mathematical programming, Zh. Vychisl. Mat. i Mat. Fiz. 19 (1979), 1387-1395 (in Russian).

[18] A. Wierzbicki, A Penalty Function Shifting Method in Constrained Static Optimization and its Convergence Properties, Archiwum Automatyki i Telemechaniki XVI (4) (1971), 396-416.