Mirror-Descent Methods in Mixed-Integer Convex Optimization

Michel Baes (), Timm Oertel (), Christian Wagner () and Robert Weismantel ()
Additional contact information
Michel Baes: ETH Zürich, Department of Mathematics, Institut für Operations Research
Timm Oertel: ETH Zürich, Department of Mathematics, Institut für Operations Research
Christian Wagner: ETH Zürich, Department of Mathematics, Institut für Operations Research
Robert Weismantel: ETH Zürich, Department of Mathematics, Institut für Operations Research

A chapter in Facets of Combinatorial Optimization, 2013, pp 101-131 from Springer

Abstract: 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 with a novel geometric construction how to implement the oracle efficiently, that is, in $\mathcal {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.

Keywords: Polynomial Time; Convex Function; Convex Optimization; Feasible Point; Integer Variable (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-642-38189-8_5

Ordering information: This item can be ordered from
http://www.springer.com/9783642381898

DOI: 10.1007/978-3-642-38189-8_5

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().