Optimality certificates for convex minimization and Helly numbers

2016/10/27 by Basu, Amitabh, Conforti, Michele, Cornuéjols, Gérard +2
#52Cxx #90C25 #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1610.08648

Abstract

We consider the problem of minimizing a convex function over a subset of Rⁿ that is not necessarily convex (minimization of a convex function over the integer points in a polytope is a special case). We define a family of duals for this problem and show that, under some natural conditions, strong duality holds for a dual problem in this family that is more restrictive than previously considered duals.

Related

• A duality principle for non-convex optimization in ℝⁿ
• Duality for Mixed-Integer Convex Minimization
• Duality suitable for a class of non-convex optimization problems
• A Class of Problems where Dual Bounds Beat Underestimation Bounds
• Strong valid inequalities for a class of concave submodular minimization problems under cardinality constraints