Minimizing a Low-Dimensional Convex Function Over a High-Dimensional Cube

DOI10.1137/22M1489988MaRDI QIDQ6155880zbMATH OpenOpenAlexFDO

Authors Christoph Hunkenschröder, Sebastian Pokutta, Robert Weismantel

Publication date 7 June 2023

Published in SIAM Journal on Optimization (Search for Journal in Brave)

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

zbMATH Keywords

convex minimizationdiscrete optimizationpolynomial time algorithm

Mathematics Subject Classification ID

Convex programming (90C25) Combinatorial optimization (90C27) Convexity of real functions of several variables, generalizations (26B25)

Abstract: For a matrix $Winmathbb{Z}^{mimesn}$, $mleqn$, and a convex function $g:mathbb{R}^{m}ightarrowmathbbR$, we are interested in minimizing $f(x)=g(Wx)$ over the set ${0,1}^n$. We will study separable convex functions and sharp convex functions $g$. Moreover, the matrix $W$ is unknown to us. Only the number of rows $mleqn$ and $|W{|}_{infty}$ is revealed. The composite function $f(x)$ is presented by a zeroth and first order oracle only. Our main result is a proximity theorem that ensures that an integral minimum and a continuous minimum for separable convex and sharp convex functions are always "close" by. This will be a key ingredient to develop an algorithm for detecting an integer minimum that achieves a running time of roughly $(m|W{|}_{infty}{)}^{mathcalO(m^3)}cdotextpoly(n)$. In the special case when $(i)$ $W$ is given explicitly and $(ii)$ $g$ is separable convex one can also adapt an algorithm of Hochbaum and Shanthikumar. The running time of this adapted algorithm matches with the running time of our general algorithm.

Recommendations

• Minimization of an M-convex function
• scientific article; zbMATH DE number 1377657
• Minimizing a concave function over a compact convex set
• Minimizing uniformly convex functions by cubic regularization of Newton method
• Minimizing Piecewise-Concave Functions Over Polyhedra
• scientific article; zbMATH DE number 1421262
• Minimisation de fonctionnelles dans un ensemble de fonctions convexes
• scientific article; zbMATH DE number 3993310
• scientific article; zbMATH DE number 4079167
• Minimization of convex functions on the convex hull of a point set

Cites work

• scientific article; zbMATH DE number 5060482 (Why is no real title available?)
• A Polyhedral Frobenius Theorem with Applications to Integer Optimization
• A polynomial oracle-time algorithm for convex integer minimization
• Constructing lattice-free gradient polyhedra in dimension two
• Convex combinatorial optimization
• Convex integer maximization via Graver bases
• Convex separable optimization is not much harder than linear optimization
• Convexity in cristallographical lattices
• Geometric algorithms and combinatorial optimization
• Integer convex minimization by mixed integer linear optimization
• Nonlinear discrete optimization. An algorithmic theory
• Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma
• Sensitivity theorems in integer linear programming
• Value of the Steinitz constant

Cited in

(1)

• Optimizing low dimensional functions over the integers

This page was built for publication: Minimizing a Low-Dimensional Convex Function Over a High-Dimensional Cube

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