Lagrangian bounds in multiextremal polynomial and discrete optimization problems
type: Item
instance of: scholarly article
title: Lagrangian bounds in multiextremal polynomial and discrete optimization problems
zbMATH Open document ID: 1009.90084
DOI: 10.1023/A:1014004625997
author: P. I. Stetsyuk
author: N. Z. Shor
published in: Journal of Global Optimization
publication date: 2002-05-28T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90C25
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 49J52
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90C57
zbMATH DE Number: 1746309
zbMATH Keywords: symmetric matrices
zbMATH Keywords: eigenvalues
zbMATH Keywords: lagrangian bounds
zbMATH Keywords: discrete optimization problems on graphs
zbMATH Keywords: superfluous constraints
zbMATH Keywords: quadratic type problems
zbMATH Keywords: nondifferentiable optimization
reviewed by: Marcin Studniarski
MaRDI profile type: Publication
full work available at URL: a:1014004625997
OpenAlex ID: W1545882088
description: scientific article; zbMATH DE number 1746309