Lagrangian bounds in multiextremal polynomial and discrete optimization problems |
| |
Authors: | Naum Z. Shor Petro I. Stetsyuk |
| |
Affiliation: | (1) Institute of Cybernetics, NAS of Ukraine, Kiev, Ukraine |
| |
Abstract: | Many polynomial and discrete optimization problems can be reduced to multiextremal quadratic type models of nonlinear programming. For solving these problems one may use Lagrangian bounds in combination with branch and bound techniques. The Lagrangian bounds may be improved for some important examples by adding in a model the so-called superfluous quadratic constraints which modify Lagrangian bounds. Problems of finding Lagrangian bounds as a rule can be reduced to minimization of nonsmooth convex functions and may be successively solved by modern methods of nondifferentiable optimization. This approach is illustrated by examples of solving polynomial-type problems and some discrete optimization problems on graphs. |
| |
Keywords: | symmetric matrices eigenvalues Lagrangian bounds discrete optimization problems on graphs superfluous constraints quadratic type problems nondifferentiable optimization |
本文献已被 SpringerLink 等数据库收录! |