Minimizing Lipschitz-continuous strongly convex functions over integer points in polytopes

Baes, Michel;Del Pia, Alberto;Nesterov, Yurii;Onn, Schmuel;Weismantel, Robert
(2012) Mathematical Programming — Vol. Ser. B, n° 134, p. 305-322 (2012)

Files

YN_Minimizing.pdf
  • Restricted Access
  • Adobe PDF
  • 217.85 KB
Request a copy

Details

Authors
  • Baes, MichelETH Zurich
    Author
  • Del Pia, AlbertoETH Zurich
    Author
  • Nesterov, YuriiUCLouvain
    Author
  • Onn, SchmuelTechnion, Haifa, Israel
    Author
  • Weismantel, RobertETH Zurich
    Author
Abstract
This paper is about the minimization of Lipschitz-continuous and strongly convex functions over integer points in polytopes. Our results are related to the rate of convergence of a black-box algorithm that iteratively solves special quadratic integer problems with a constant approximation factor. Despite the generality of the underlying problem, we prove that we can find efficiently, with respect to our assumptions regarding the encoding of the problem, a feasible solution whose objective function value is close to the optimal value. We also show that this proximity result is the best possible up to a factor polynomial in the encoding length of the problem.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Baes, M., Del Pia, A., Nesterov, Y., Onn, S., & Weismantel, R. (2012). Minimizing Lipschitz-continuous strongly convex functions over integer points in polytopes. Mathematical Programming, Ser. B(134), 305-322. https://doi.org/10.1007/s10107-012-0545-8 (Original work published 2012)