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

DOI10.1137/22M1489988zbMATH Open1519.90170arXiv2204.05266OpenAlexW4378375458MaRDI QIDQ6155880FDOQ6155880

Authors: Christoph Hunkenschröder, Sebastian Pokutta, Robert Weismantel 

Publication date: 7 June 2023

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

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.

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

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

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)

Cites Work

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

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)