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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmdico_1011,
author = {Pawe\l\ Bia\l o\'n},
title = {Large-scale nonlinear programming algorithm using projection methods},
journal = {Discussiones Mathematicae, Differential Inclusions, Control and Optimization},
volume = {20},
year = {2000},
pages = {171-194},
zbl = {1001.65061},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmdico_1011}
}
Paweł Białoń. Large-scale nonlinear programming algorithm using projection methods. Discussiones Mathematicae, Differential Inclusions, Control and Optimization, Tome 20 (2000) pp. 171-194. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmdico_1011/
[000] [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.
[001] [1] H. Bauschke and J. Borwein, On projection algorithms for solving convex feasibility problems, SIAM Review 38 (3) (1996), 367-426. | Zbl 0865.47039
[002] [2] A. Cegielski, A method of projection onto an acute cone with level control in convex minimization, Math. Progr. 85 (1999), 469-490. | Zbl 0973.90057
[003] [3] A. Cegielski, Relaxation methods in Convex Optimization Problems, Higher College of Engineering, Series Monographies, No. 67, Zielona Góra, Poland (in Polish).
[004] [4] 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. | Zbl 1014.65048
[005] [5] S. Flam and J. Zowe, Relaxed outer projections, weighted averages and convex feasibility, BIT 30 (1990), 289-300. | Zbl 0715.65038
[006] [6] S. Kim, A. Hyunsil and C. Seong-Cheol, Variable target value subgradient method, Math. Progr. 49 (1991), 356-369.
[007] [7] 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. | Zbl 0870.65046
[008] [8] K. Kiwiel, The efficiency of subgradient projection methods for convex optimization, Part I: General level methods, SIAM Control Optim. 34 (2) (1996), 660-676. | Zbl 0846.90084
[009] [9] K. Kiwiel, Block-Iterative Surrogate Projection Methods for Convex Feasibility Problems, Linear Algebra and its Applications 15 (1995), 225-259. | Zbl 0821.65037
[010] [10] 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.
[011] [11] C. Lemaréchal, A.S. Nemirovskii and Yu. Nesterov, New variants of bundle methods, Math. Progr. 69 (1995), 111-147. | Zbl 0857.90102
[012] [12] B. Łopuch, Projection methods with an aggregation for convex feasibility problems, Doctoral thesis, Institute of Systems Research, Warsaw 1997 (in Polish). | Zbl 0915.90220
[013] [13] 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.
[014] [14] A.S. Nemirovskii and D. Yudin, Optimization Problem Complexity and Method Efficiency, Nauka, Moscow 1979 (in Russian).
[015] [15] T. Polyak, Minimization of unsmooth functionals, Zh. Vychiisl. Mat. Fiz. 9 (1969), 14-29 (in Russian). | Zbl 0229.65056
[016] [16] 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). | Zbl 0462.90072
[017] [17] A. Wierzbicki, A Penalty Function Shifting Method in Constrained Static Optimization and its Convergence Properties, Archiwum Automatyki i Telemechaniki XVI (4) (1971), 396-416. | Zbl 0227.90045