Name
Title | ||
|---|---|---|
Minimizing Lipschitz-continuous strongly convex functions over integer points in polytopes |
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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/s10107-012-0545-8 | Math. Program. |
Keywords | Field | DocType |
objective function value,optimal value,convex function,constant approximation factor,minimizing lipschitz-continuous,underlying problem,encoding length,factor polynomial,black-box algorithm,special quadratic integer problem,integer point | Integer,Discrete mathematics,Combinatorics,Mathematical optimization,Polynomial,Integer points in convex polyhedra,Polytope,Convex function,Lipschitz continuity,Convex optimization,Convex analysis,Mathematics | Journal |
Volume | Issue | ISSN |
134 | 1 | 1436-4646 |
Citations | PageRank | References |
3 | 0.40 | 11 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michel Baes | 1 | 24 | 3.83 |
| Alberto Del Pia | 2 | 67 | 11.62 |
| Yurii Nesterov | 3 | 1800 | 168.77 |
| Shmuel Onn | 4 | 420 | 54.77 |
| Robert Weismantel | 5 | 964 | 90.05 |