Fulltext

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

Baes, Michel ; Del Pia, Alberto ; Nesterov, Yurii ; Onn, Shmuel ; Weismantel, Robert

In: Mathematical Programming, 2012, vol. 134, no. 1, p. 305-322

Add to personal list
    Title
    • Minimizing Lipschitz-continuous strongly convex functions over integer points in polytopes
    Author
    • Baes, Michel. IFOR, ETH Zurich, Zurich, Switzerland
    • Del Pia, Alberto. IFOR, ETH Zurich, Zurich, Switzerland
    • Nesterov, Yurii. CORE, UCL Belgium, Louvain-la-Neuve, Belgium
    • Onn, Shmuel. Technion, Haifa, Israel
    • Weismantel, Robert. IFOR, ETH Zurich, Zurich, Switzerland
    Document Type
    • Postprint
    OAI-PMH Identifier
    • oai:doc.rero.ch:321355
    Summary
    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