EUVIMEDEUVIMED entdecken
Crossref

Separable Convex Optimization with Nested Lower and Upper Constraints

Thibaut Vidal, Daniel Gribel, Patrick Jaillet

INFORMS Journal on Optimization · 2019

DOI: 10.1287/ijoo.2018.0004 ↗

Kurz gefasst

Fachartikel in der Zeitschrift INFORMS Journal on Optimization, 2019. Verfasst von Thibaut Vidal und 2 weiteren Autor:innen. Die Arbeit wurde bisher 11-mal zitiert (Crossref) und nennt 60 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study a convex resource allocation problem in which lower and upper bounds are imposed on partial sums of allocations. This model is linked to a large range of applications, including production planning, speed optimization, stratified sampling, support vector machines, portfolio management, and telecommunications. We propose an efficient gradient-free divide-and-conquer algorithm, which uses monotonicity arguments to generate valid bounds from the recursive calls, and eliminate linking constraints based on the information from subproblems. This algorithm does not need strict convexity or differentiability. It produces an [Formula: see text]-approximate solution for the continuous problem in [Formula: see text] time and an integer solution in [Formula: see text] time, where [Formula: see text] is the number of decision variables, [Formula: see text] is the number of constraints, and [Formula: see text] is the resource bound. A complexity of [Formula: see text] is also achieved for the linear and quadratic cases. These are the best complexities known to date for this important problem class. Our experimental analyses confirm the good performance of the method, which produces optimal solutions for problems with up to 1,000,000 variables in a few seconds. Promising applications to the support vector ordinal regression problem are also investigated.

Zitieren

APA

Vidal, T., Gribel, D., & Jaillet, P. (2019). Separable Convex Optimization with Nested Lower and Upper Constraints. INFORMS Journal on Optimization. https://doi.org/10.1287/ijoo.2018.0004

Vancouver

Vidal T, Gribel D, Jaillet P. Separable Convex Optimization with Nested Lower and Upper Constraints. INFORMS Journal on Optimization. 2019. doi:10.1287/ijoo.2018.0004

BibTeX
@article{Vidal2019,
  author = {Vidal, Thibaut and Gribel, Daniel and Jaillet, Patrick},
  title = {Separable Convex Optimization with Nested Lower and Upper Constraints},
  journal = {INFORMS Journal on Optimization},
  year = {2019},
  doi = {10.1287/ijoo.2018.0004}
}
Kostenlos starten →