Some variants of projection methods for large nonlinear optimization problems
DOI:
https://doi.org/10.26636/jtit.2003.3.192Keywords:
projection methods, penalty shifting method, nonlinear optimizationAbstract
Two ideas of modifying projection methods for the case of smooth nonlinear optimization are presented. Projection methods were originally successfully used in solving large-scale linear feasibility problems. The proposed instantiations of projection methods fall into two groups. One of them is a decomposition approach in which projections onto sets are realized as optimization problems which themselves involve much portions of original problem constraints. There are two subproblems: one build with linear constraints of the original problem and the second one build with original nonlinear constraints. These approaches use special accelerating cuts so that the separation of nonlinear and linear constraints can be effective and some problem sparsity preserved. The second group bases on penalty-shifting/multiplier methods and draws from the observation that unconstrained subproblems obtained there may solve very slowly due to their nonsmooth character. Thus it is proposed to solve them with modified projection methods which inherit from conjugate gradient methods a multi-dimensional subspace in one epoche.
Downloads
References
[1] A. Altman and J. Gondzio, "Regularized symmetric indefinite systems in interior point methods for linear and quadratic optimization", Optim. Meth. Softw., no. 11-12, pp. 275-302, 2000.
View in Google Scholar
[2] H. Bauschke and J. Borwein, "On projection algorithms for solving convex feasibility problems", SIAM Rev., vol. 38, no. 3, pp. 367-426, 1996.
View in Google Scholar
[3] D. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods. A Series of Monographs and Textbooks: Computer Science and Applied Mathematics. New York, London: Academic Press, 1982.
View in Google Scholar
[4] P. Białoń, "Large-scale nonlinear projection algorithm using projection methods", Discuss. Math. Differ. Inclus., Control Optim., vol. 20, no. 2, pp. 171-194, 1999.
View in Google Scholar
[5] P. Białoń, "A proposition to exploit the partially linear structure of the nonlinear multicommodity flow optimization problem", J. Telecommun. Inform. Technol., no. 3, pp. 49-56, 2002.
View in Google Scholar
[6] A. Cegielski, "A method of projection onto an acute cone with level control in convex minimization", Math. Progr., vol. 85, pp. 469-490, 1999.
View in Google Scholar
[7] A. Cegielski, Metody relaksacyjne w problemach optymalizacji wypukłej. Monografie, nr 67. Zielona Góra: Wyższa Szkoła Inżynierska, 1993 (in Polish).
View in Google Scholar
[8] A. Conn, N. Gould, and P. Toint, "Numerical experience with LANCELOT package (Release A) for large-scale nonlinear optimization", Math. Progr., vol. 73, pp. 73-110, 1996.
View in Google Scholar
[9] R. Dylewski, "Numerical behavior of the method of projection onto an acute cone with level control in convex optimization", Discuss. Math. Differ. Inclus., Control Optim., vol. 20, pp. 147-158, 1999.
View in Google Scholar
[10] S. Fl?m and J. Zowe, "Relaxed outer projections, weighted averages and convex feasibility", BIT, vol. 30, pp. 289-300, 1990.
View in Google Scholar
[11] S. Kim, A. Hyunsil, and C. Seong-Cheol, "Variable target value subgradient method", Math. Progr., vol. 49, pp. 356-369, 1991.
View in Google Scholar
[12] K. Kiwiel, "Monotone Gram matrices and deepest surrogate inequalities in accelerated relaxation methods for convex feasibility problems", Lin. Algebra Appl., vol. 215, pp. 27-33, 1997.
View in Google Scholar
[13] K. Kiwiel, "The efficiency of subgradient projection methods for convex optimization", Part I: "General level methods", SIAM Control Optim., vol. 34, no. 2, pp. 660-676, 1996.
View in Google Scholar
[14] K. Kiwiel, "Block-iterative surrogate projection methods for convex feasibility problems", Lin. Algebra Appl., vol. 15, pp. 225-259, 1995.
View in Google Scholar
[15] T. Kreglewski, J. Granat, and A. P. 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. Laxenburg (Austria): International Institute for Applied Systems Analysis, June 1991.
View in Google Scholar
[16] C. Lemarechal, A. S. Nemirovskii, and Yu. Nesterov, "New variants of bundle methods", Math. Progr., vol. 69, pp. 111-147, 1995.
View in Google Scholar
[17] M. Makowski, LP-DIT data interchange tool for linear programming problems (version 1.20). Working Paper, WP-94-36. Laxenburg (Austria): International Institute for Applied Systems Analysis, 1994.
View in Google Scholar
[18] M. Minoux, "Network synthesis and optimum network design problems: models, solution methods and applications", Network, vol. 19, pp. 313-360, 1989.
View in Google Scholar
[19] T. Polyak, "Minimization of unsmooth functionals", Zh. Vychisl. Mat. Fiz., vol. 9, Mat. Fiz., vol. 9, pp. 14-29, 1969.
View in Google Scholar
[20] M. Shchepakin, "On a modification of a class of algorithms for mathematical programming", Zh. Vychisl. Mat., Mat. Fiz., vol. 19, pp. 1387-1395, 1979 (in Russian).
View in Google Scholar
[21] A. Wierzbicki, "A penalty function shifting method in constrained static optimization and its convergence properties", Archiw. Autom. Telemech., vol. XVI, no. 4, pp. 396-416, 1971.
View in Google Scholar
Downloads
Published
Issue
Section
License
Copyright (c) 2003 Journal of Telecommunications and Information Technology

This work is licensed under a Creative Commons Attribution 4.0 International License.