User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

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

Primary tabs

Baes, Michel [ETH Zurich] Del Pia, Alberto [ETH Zurich] Nesterov, Yurii [UCL] Onn, Schmuel [Technion, Haifa, Israel] Weismantel, Robert [ETH Zurich]

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.

Document type Article de périodique (Journal article) – Article de recherche
Access type Accès restreint
Publication date 2012
Language Anglais
Journal information "Mathematical Programming" - Vol. Ser. B, no.134, p. 305-322 (2012)
Peer reviewed yes
Publisher Springer ((Germany) Heidelberg)
issn 0025-5610
e-issn 1436-4646
Publication status Publié
Affiliations UCL - SSH/LIDAM/CORE - Center for operations research and econometrics
UCL - SST/ICTM/INMA - Pôle en ingénierie mathématique
Links
  1. Berstein Yael, Lee Jon, Maruri-Aguilar Hugo, Onn Shmuel, Riccomagno Eva, Weismantel Robert, Wynn Henry, Nonlinear Matroid Optimization and Experimental Design, 10.1137/070696465
  2. Berstein Y., Lee J., Onn S., Weismantel R., Parametric nonlinear discrete optimization over well-described sets and matroid intersections, 10.1007/s10107-010-0358-6
  3. Bonami Pierre, Biegler Lorenz T., Conn Andrew R., Cornuéjols Gérard, Grossmann Ignacio E., Laird Carl D., Lee Jon, Lodi Andrea, Margot François, Sawaya Nicolas, Wächter Andreas, An algorithmic framework for convex mixed integer nonlinear programs, 10.1016/j.disopt.2006.10.011
  4. Duran Marco A., Grossmann Ignacio E., An outer-approximation algorithm for a class of mixed-integer nonlinear programs, 10.1007/bf02592064
  5. Fletcher Roger, Leyffer Sven, Solving mixed integer nonlinear programs by outer approximation, 10.1007/bf01581153
  6. Geoffrion A. M., Generalized Benders decomposition, 10.1007/bf00934810
  7. Heinz Sebastian, Complexity of integer quasiconvex polynomial optimization, 10.1016/j.jco.2005.04.004
  8. De Loera Jesús A., Hemmecke Raymond, Onn Shmuel, Weismantel Robert, N-fold integer programming, 10.1016/j.disopt.2006.06.006
  9. Hemmecke Raymond, Onn Shmuel, Weismantel Robert, A polynomial oracle-time algorithm for convex integer minimization, 10.1007/s10107-009-0276-7
  10. Kelley, Jr. J. E., The Cutting-Plane Method for Solving Convex Programs, 10.1137/0108053
  11. Khachiyan L., Porkolab L., Integer Optimization on Convex Semialgebraic Sets, 10.1007/pl00009496
  12. Lee Jon, Onn Shmuel, Weismantel Robert, Approximate Nonlinear Optimization over Weighted Independence Systems, 10.1137/080718103
  13. Nesterov Yurii, Introductory Lectures on Convex Optimization, ISBN:9781461346913, 10.1007/978-1-4419-8853-9
  14. Stubbs Robert A., Mehrotra Sanjay, A branch-and-cut method for 0-1 mixed convex programming, 10.1007/s101070050103
  15. Westerlund Tapio, Pettersson Frank, An extended cutting plane method for solving convex MINLP problems, 10.1016/0098-1354(95)87027-x
Bibliographic reference Baes, Michel ; Del Pia, Alberto ; Nesterov, Yurii ; Onn, Schmuel ; Weismantel, Robert. Minimizing Lipschitz-continuous strongly convex functions over integer points in polytopes. In: Mathematical Programming, Vol. Ser. B, no.134, p. 305-322 (2012)
Permanent URL http://hdl.handle.net/2078.1/121614