Complexity iteration analysis for strongly convex multi-objective optimization using a Newton path-following procedure

El Houcine Bergou; Youssef Diouane; Vyacheslav Kungurtsev

doi:10.1007/s11590-020-01623-x

Complexity iteration analysis for strongly convex multi-objective optimization using a Newton path-following procedure

El Houcine Bergou, Youssef Diouane, Vyacheslav Kungurtsev

Computer, Electrical and Mathematical Sciences and Engineering

Research output: Contribution to journal › Article › peer-review

Abstract

In this note, we consider the iteration complexity of solving strongly convex multi-objective optimization problems. We discuss the precise meaning of this problem, noting that its definition is ambiguous, and focus on the most natural notion of finding a set of Pareto optimal points across a grid of scalarized problems. We prove that, in most cases, performing sensitivity based path-following after obtaining one solution is the optimal strategy for this task in terms of iteration complexity.

Original language	English (US)
Journal	Optimization Letters
DOIs	https://doi.org/10.1007/s11590-020-01623-x
State	Published - Jul 23 2020

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01
Acknowledgements: We would like to thank two anonymous referees for their careful readings and corrections that helped us to improve our manuscript significantly. E. Bergou received support from the AgreenSkills+ fellowship programme which has received funding from the EU’s Seventh Framework Programme under Grant Agreement No. FP7-609398 (AgreenSkills+ contract). V. Kungurtsev received support from the OP VVV Project CZ.02.1.01/0.0/0.0/16_019/0000765 “Research Center for Informatics”.

Access to Document

10.1007/s11590-020-01623-x

Cite this

@article{c83cd6fcb33a47fbafef30a29761600c,

title = "Complexity iteration analysis for strongly convex multi-objective optimization using a Newton path-following procedure",

abstract = "In this note, we consider the iteration complexity of solving strongly convex multi-objective optimization problems. We discuss the precise meaning of this problem, noting that its definition is ambiguous, and focus on the most natural notion of finding a set of Pareto optimal points across a grid of scalarized problems. We prove that, in most cases, performing sensitivity based path-following after obtaining one solution is the optimal strategy for this task in terms of iteration complexity.",

author = "Bergou, {El Houcine} and Youssef Diouane and Vyacheslav Kungurtsev",

note = "KAUST Repository Item: Exported on 2020-10-01 Acknowledgements: We would like to thank two anonymous referees for their careful readings and corrections that helped us to improve our manuscript significantly. E. Bergou received support from the AgreenSkills+ fellowship programme which has received funding from the EU{\textquoteright}s Seventh Framework Programme under Grant Agreement No. FP7-609398 (AgreenSkills+ contract). V. Kungurtsev received support from the OP VVV Project CZ.02.1.01/0.0/0.0/16_019/0000765 “Research Center for Informatics”.",

year = "2020",

month = jul,

day = "23",

doi = "10.1007/s11590-020-01623-x",

language = "English (US)",

journal = "Optimization Letters",

issn = "1862-4480",

publisher = "Springer Verlag",

}

TY - JOUR

T1 - Complexity iteration analysis for strongly convex multi-objective optimization using a Newton path-following procedure

AU - Bergou, El Houcine

AU - Diouane, Youssef

AU - Kungurtsev, Vyacheslav

N1 - KAUST Repository Item: Exported on 2020-10-01 Acknowledgements: We would like to thank two anonymous referees for their careful readings and corrections that helped us to improve our manuscript significantly. E. Bergou received support from the AgreenSkills+ fellowship programme which has received funding from the EU’s Seventh Framework Programme under Grant Agreement No. FP7-609398 (AgreenSkills+ contract). V. Kungurtsev received support from the OP VVV Project CZ.02.1.01/0.0/0.0/16_019/0000765 “Research Center for Informatics”.

PY - 2020/7/23

Y1 - 2020/7/23

N2 - In this note, we consider the iteration complexity of solving strongly convex multi-objective optimization problems. We discuss the precise meaning of this problem, noting that its definition is ambiguous, and focus on the most natural notion of finding a set of Pareto optimal points across a grid of scalarized problems. We prove that, in most cases, performing sensitivity based path-following after obtaining one solution is the optimal strategy for this task in terms of iteration complexity.

AB - In this note, we consider the iteration complexity of solving strongly convex multi-objective optimization problems. We discuss the precise meaning of this problem, noting that its definition is ambiguous, and focus on the most natural notion of finding a set of Pareto optimal points across a grid of scalarized problems. We prove that, in most cases, performing sensitivity based path-following after obtaining one solution is the optimal strategy for this task in terms of iteration complexity.

UR - http://hdl.handle.net/10754/664521

UR - http://link.springer.com/10.1007/s11590-020-01623-x

UR - http://www.scopus.com/inward/record.url?scp=85088401328&partnerID=8YFLogxK

U2 - 10.1007/s11590-020-01623-x

DO - 10.1007/s11590-020-01623-x

M3 - Article

SN - 1862-4480

JO - Optimization Letters

JF - Optimization Letters

ER -

Complexity iteration analysis for strongly convex multi-objective optimization using a Newton path-following procedure

Abstract

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this