Role of redundant constraints for improving dual bounds in polynomial optimization problems

DOI10.1007/BF02667001zbMath0978.90079WikidataQ126226926 ScholiaQ126226926MaRDI QIDQ1288665

Naum Z. Shor

Publication date: 12 February 2002

Published in: Cybernetics and Systems Analysis (Search for Journal in Brave)

zbMATH Keywords

combinatorial optimizationconvex programmingBoolean programmingLagrange multiplier methodfunctionally redundant constraintsdual Lagrangiannonsmooth convex functioncut methodnonsmootth penalty functionsquadratic nonlinear programming

Mathematics Subject Classification ID

Convex programming (90C25) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Boolean programming (90C09)

Related Items

Functionally redundant constraints for Boolean quadratic-type optimization problems, A conjugate Rosen's gradient projection method with global line search for piecewise linear concave optimization, Dual approaches to finite element model updating, A computational approach to non-smooth optimization by diffusion equations, A method for computing lowest eigenvalues of symmetric polynomial differential operators by semidefinite programming, Constructing a quasi-concave quadratic objective function from interviewing a decision maker

Cites Work

• Unnamed Item
• The max-cut problem on graphs not contractible to \(K_ 5\)
• The ellipsoid method and its consequences in combinatorial optimization
• Weakly bipartite graphs and the max-cut problem
• Geometric algorithms and combinatorial optimization
• Nondifferentiable optimization and polynomial problems
• Facets of the Bipartite Subgraph Polytope
• An approach to obtaining global extremums in polynomial mathematical programming problems
• A comparison of the Delsarte and Lovász bounds
• On Odd Cuts and Plane Multicommodity Flows
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• On the Shannon capacity of a graph
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Semidefinite relaxation and nonconvex quadratic optimization
• Copositive realxation for genera quadratic programming
• On the cut polytope
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization