scientific article; zbMATH DE number 16323

MaRDI QIDQ3972976zbMATH OpenFDO

Authors N. Z. Shor

Publication date 26 June 1992

zbMATH Keywords

Lagrange functionmaximum stable set problemnonconvex problemsnonsmooth optimizationquadratic dual boundsscheme of decompositionspace dilatationsubgradient type methods

Mathematics Subject Classification ID

Nonsmooth analysis (49J52) Computational methods for problems pertaining to operations research and mathematical programming (90-08) Quadratic programming (90C20) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30)

Review text

[For the entire collection see Zbl 0719.00020.] The article deals with constructing quadratic dual bounds for some nonconvex problems. In the introduction the process of getting dual bounds with the use of a Lagrange function is described. It is shown that finding the dual bound can be considered as a coordinating problem in decomposition scheme with respect to constraints. Finding optimum in a coordinating problem is usually a non-smooth problem and subgradient type methods with space dilatation proved to solve it well. The procedure of finding a dual bounds, for a quadratic non-convex optimization problem is studied and an algorithm for its evaluation is described. Several examples demonstrate how to use this technique for finding a global minimum of a polynomial function and to solve a maximum stable set problem. The properties of quadratic dual bounds for the maximum stable set problem and the problem of finding a global minimum of a polynomial function are given alongside with results of numerical tests.

Recommendations

• Exact dual bounds for some nonconvex minimax quadratic optimization problems
• Dual quadratic estimates in polynomial and Boolean programming
• scientific article; zbMATH DE number 6667271
• Role of redundant constraints for improving dual bounds in polynomial optimization problems
• Duality bound method for the general quadratic programming problem with quadratic constraints

Cited in

(9)

• Dual quadratic estimates in polynomial and Boolean programming
• Dual estimates in multiextremal problems
• Exact dual bounds for some nonconvex minimax quadratic optimization problems
• Dualize, split, randomize: toward fast nonsmooth optimization algorithms
• scientific article; zbMATH DE number 6667271 (Why is no real title available?)
• On duality for nonsmooth Lipschitz optimization problems
• scientific article; zbMATH DE number 1159218 (Why is no real title available?)
• Dual bounds in convex and nonconvex nondifferentiable optimization problems and applications
• A class of problems where dual bounds beat underestimation bounds

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3972976)