Mirror-Descent Methods in Mixed-Integer Convex Optimization

DOI10.1007/978-3-642-38189-8_5zbMATH Open1317.90207arXiv1209.0686OpenAlexW1545931427MaRDI QIDQ5265166FDOQ5265166

Timm Oertel, Christian Wagner, Robert Weismantel, Michel Baes

Publication date: 22 July 2015

Published in: Facets of Combinatorial Optimization (Search for Journal in Brave)

Abstract: In this paper, we address the problem of minimizing a convex function f over a convex set, with the extra constraint that some variables must be integer. This problem, even when f is a piecewise linear function, is NP-hard. We study an algorithmic approach to this problem, postponing its hardness to the realization of an oracle. If this oracle can be realized in polynomial time, then the problem can be solved in polynomial time as well. For problems with two integer variables, we show that the oracle can be implemented efficiently, that is, in O(ln(B)) approximate minimizations of f over the continuous variables, where B is a known bound on the absolute value of the integer variables.Our algorithm can be adapted to find the second best point of a purely integer convex optimization problem in two dimensions, and more generally its k-th best point. This observation allows us to formulate a finite-time algorithm for mixed-integer convex optimization.

Full work available at URL: https://arxiv.org/abs/1209.0686

Mathematics Subject Classification ID

Convex programming (90C25) Mixed integer programming (90C11)

Cited In (9)

• Mirror descent and convex optimization problems with non-smooth inequality constraints
• Two-step MIR inequalities for mixed integer programs
• Constructing lattice-free gradient polyhedra in dimension two
• Algorithms of inertial mirror descent in stochastic convex optimization problems
• Minimizing cubic and homogeneous polynomials over integers in the plane
• Constructing Lattice-Free Gradient Polyhedra in Dimension Two
• Complexity of optimizing over the integers
• Using Nemirovski's Mirror-Prox method as basic procedure in Chubanov's method for solving homogeneous feasibility problems
• Mirror Prox algorithm for multi-term composite minimization and semi-separable problems

Recommendations

• Mirror descent and nonlinear projected subgradient methods for convex optimization. 👍 👎
• Mirror Prox algorithm for multi-term composite minimization and semi-separable problems 👍 👎
• A weighted mirror descent algorithm for nonsmooth convex optimization problem 👍 👎
• Mixed method for solving the general convex programming problem 👍 👎
• A version of the mirror descent method to solve variational inequalities 👍 👎
• Algorithms of inertial mirror descent in stochastic convex optimization problems 👍 👎
• On the Convergence of Mirror Descent beyond Stochastic Convex Programming 👍 👎
• Integer convex minimization by mixed integer linear optimization 👍 👎
• Mirror descent and convex optimization problems with non-smooth inequality constraints 👍 👎
• Adaptive Mirror Descent Algorithms for Convex and Strongly Convex Optimization Problems with Functional Constraints 👍 👎

This page was built for publication: Mirror-Descent Methods in Mixed-Integer Convex Optimization

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