Lagrangian bounds in multiextremal polynomial and discrete optimization problems (Q1598884)

The authors consider the problem of finding the best Lagrangian bound (i.e., a lower bound obtained by minimization of the Lagrange function) for the optimal value function in a nonlinear programming problem with equality constraints. They show that for quadratic-type minimization problems the Lagrangian lower bounds may be improved by using the so-called functionally superfluous constraints which do not change the optimal value of initial problem but lead to modification of the Lagrange function. They also show that the finding of Lagrangian bounds can be reduced in many cases to some problems of nondifferentiable optimization with specific constraints in the form of semidefiniteness of some parametric families of symmetric matrices, and may be solved by using certain known algorithms of nondifferentiable optimization. This approach is illustrated by examples of solving polynomial-type problems and some discrete optimization problems on graphs.