Role of redundant constraints for improving dual bounds in polynomial optimization problems
type: Item
instance of: scholarly article
title: Role of redundant constraints for improving dual bounds in polynomial optimization problems
zbMATH Open document ID: 0978.90079
DOI: 10.1007/BF02667001
published in: Cybernetics and Systems Analysis
publication date: 2002-02-12T00:00:00Z
review text: The author considers some extremum quadratic and Boolean combinatorial problem of infimum and their dual Lagrangian problems of supremum. The used techniques introduce functionally redundant constraints that reduce the duality gap. (1) The problem of finding the maximum weighted set of graph nodes is a linear programming problem that is reducible to the minimization of a nonsmooth convex function by the method of nonsmooth penalty functions in the form of a maximum function. (2) The maximum cut problem is written as a quadratic nonlinear programming problem and for its solution the Lagrange multiplier method is used. This problem is also written as a linear programming problem, but with a number of constraints, excessively large. This inconvenience is raised by the utilization of a special shortest path problem for an auxiliary graph. (3) Bounds for the global minimum of polynomial functions. The polynomial are represented as quadratic functions, using some linear transformations. For minimization the Lagrange multiplier method is used.
reviewed by: Stefan Mititelu
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C09
Mathematics Subject Classification ID: 90C25
Mathematics Subject Classification ID: 90C57
zbMATH DE Number: 1287601
zbMATH Keywords: combinatorial optimization
zbMATH Keywords: Boolean programming
zbMATH Keywords: convex programming
zbMATH Keywords: cut method
zbMATH Keywords: dual Lagrangian
zbMATH Keywords: functionally redundant constraints
zbMATH Keywords: nonsmooth convex function
zbMATH Keywords: nonsmootth penalty functions
zbMATH Keywords: quadratic nonlinear programming
zbMATH Keywords: Lagrange multiplier method
author: N. Z. Shor
MaRDI profile type: Publication
cites work: Geometric algorithms and combinatorial optimization
cites work: On the Shannon capacity of a graph
cites work: A comparison of the Delsarte and Lovász bounds
cites work: The ellipsoid method and its consequences in combinatorial optimization
cites work: Nondifferentiable optimization and polynomial problems
cites work: On the cut polytope
cites work: On Odd Cuts and Plane Multicommodity Flows
cites work: Q5659589
cites work: Finding a Maximum Cut of a Planar Graph in Polynomial Time
cites work: The max-cut problem on graphs not contractible to \(K_ 5\)
cites work: Weakly bipartite graphs and the max-cut problem
cites work: Facets of the Bipartite Subgraph Polytope
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: An approach to obtaining global extremums in polynomial mathematical programming problems
cites work: Cones of Matrices and Set-Functions and 0–1 Optimization
cites work: Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
cites work: Semidefinite relaxation and nonconvex quadratic optimization
cites work: Copositive realxation for genera quadratic programming
Wikidata QID: Q126226926
Recommended article: On duality gap with polynomial multipliers for polynomial optimization problems
Recommended article: Strong duality in lasserre's hierarchy for polynomial optimization
Recommended article: Improved dual algorithm for constrained optimization problems
Recommended article: Functionally redundant constraints for Boolean quadratic-type optimization problems
Recommended article: Using dual presolving reductions to reformulate cumulative constraints
Recommended article: The duality framework for constrained optimization problems
Recommended article: Application of canonical duality theory to global optimization with polynomials
Recommended article: A polynomial time constraint-reduced algorithm for semidefinite optimization problems
Recommended article: Redundancies in positive-semidefinite quadratic programming
Recommended article: Dual techniques for constrained optimization
description: scientific article; zbMATH DE number 1287601