Some variants of projection methods for large nonlinear optimization problems

• Autorzy: Białoń P.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

projection methods; penalty shifting method; nonlinear optimization

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2003
• Tom: nr 3
• Strony: 43--49
• Opis fizyczny: Bibliogr. 21 poz., rys.

Twórcy

autor

Białoń P.

• National Institute of Telecommunications, Warsaw,

Bibliografia

• [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.
• [2] H. Bauschke and J. Borwein, “On projection algorithms for solving convex feasibility problems”, SIAM Rev., vol. 38, no. 3, pp. 367–426, 1996.
• [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.
• [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.
• [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.
• [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.
• [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).
• [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.
• [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.
• [10] S. Fl ̊am and J. Zowe, “Relaxed outer projections, weighted averages and convex feasibility”, BIT, vol. 30, pp. 289–300, 1990.
• [11] S. Kim, A. Hyunsil, and C. Seong-Cheol, “Variable target value subgradient method”, Math. Progr., vol. 49, pp. 356–369, 1991.
• [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.
• [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.
• [14] K. Kiwiel, “Block-iterative surrogate projection methods for convex feasibility problems”, Lin. Algebra Appl., vol. 15, pp. 225–259, 1995.
• [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.
• [16] C. Lemar ́echal, A. S. Nemirovskii, and Yu. Nesterov, “New variants of bundle methods”, Math. Progr., vol. 69, pp. 111–147, 1995.
• [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.
• [18] M. Minoux, “Network synthesis and optimum network design problems: models, solution methods and applications”, Network, vol. 19, pp. 313–360, 1989.
• [19] T. Polyak, “Minimization of unsmooth functionals”, Zh. Vychisl. Mat. Fiz., vol. 9, Mat. Fiz., vol. 9, pp. 14–29, 1969.
• [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).
• [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.