Conic optimization: A survey with special focus on copositive optimization and binary quadratic problems
A conic optimization problem is a problem involving a constraint that the optimization variable be in some closed convex cone. Prominent examples are linear programs (LP), second order cone programs (SOCP), semidefinite problems (SDP), and copositive problems. We survey recent progress made in this...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2021-01-01
|
| Series: | EURO Journal on Computational Optimization |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S2192440621001489 |
| _version_ | 1819096528399106048 |
|---|---|
| author | Mirjam Dür Franz Rendl |
| author_facet | Mirjam Dür Franz Rendl |
| author_sort | Mirjam Dür |
| collection | DOAJ |
| description | A conic optimization problem is a problem involving a constraint that the optimization variable be in some closed convex cone. Prominent examples are linear programs (LP), second order cone programs (SOCP), semidefinite problems (SDP), and copositive problems. We survey recent progress made in this area. In particular, we highlight the connections between nonconvex quadratic problems, binary quadratic problems, and copositive optimization. We review how tight bounds can be obtained by relaxing the copositivity constraint to semidefiniteness, and we discuss the effect that different modelling techniques have on the quality of the bounds. We also provide some new techniques for lifting linear constraints and show how these can be used for stable set and coloring relaxations. |
| first_indexed | 2024-12-22T00:00:38Z |
| format | Article |
| id | doaj.art-f136d5fba5254566a11a3a59133648da |
| institution | Directory Open Access Journal |
| issn | 2192-4406 |
| language | English |
| last_indexed | 2024-12-22T00:00:38Z |
| publishDate | 2021-01-01 |
| publisher | Elsevier |
| record_format | Article |
| series | EURO Journal on Computational Optimization |
| spelling | doaj.art-f136d5fba5254566a11a3a59133648da2022-12-21T18:45:43ZengElsevierEURO Journal on Computational Optimization2192-44062021-01-019100021Conic optimization: A survey with special focus on copositive optimization and binary quadratic problemsMirjam Dür0Franz Rendl1Corresponding author.; Department of Mathematics, Augsburg University, Augsburg 86135, GermanyDepartment of Mathematics, Alpen-Adria-University Klagenfurt, Klagenfurt 9020, AustriaA conic optimization problem is a problem involving a constraint that the optimization variable be in some closed convex cone. Prominent examples are linear programs (LP), second order cone programs (SOCP), semidefinite problems (SDP), and copositive problems. We survey recent progress made in this area. In particular, we highlight the connections between nonconvex quadratic problems, binary quadratic problems, and copositive optimization. We review how tight bounds can be obtained by relaxing the copositivity constraint to semidefiniteness, and we discuss the effect that different modelling techniques have on the quality of the bounds. We also provide some new techniques for lifting linear constraints and show how these can be used for stable set and coloring relaxations.http://www.sciencedirect.com/science/article/pii/S219244062100148990C2290C2090C27 |
| spellingShingle | Mirjam Dür Franz Rendl Conic optimization: A survey with special focus on copositive optimization and binary quadratic problems EURO Journal on Computational Optimization 90C22 90C20 90C27 |
| title | Conic optimization: A survey with special focus on copositive optimization and binary quadratic problems |
| title_full | Conic optimization: A survey with special focus on copositive optimization and binary quadratic problems |
| title_fullStr | Conic optimization: A survey with special focus on copositive optimization and binary quadratic problems |
| title_full_unstemmed | Conic optimization: A survey with special focus on copositive optimization and binary quadratic problems |
| title_short | Conic optimization: A survey with special focus on copositive optimization and binary quadratic problems |
| title_sort | conic optimization a survey with special focus on copositive optimization and binary quadratic problems |
| topic | 90C22 90C20 90C27 |
| url | http://www.sciencedirect.com/science/article/pii/S2192440621001489 |
| work_keys_str_mv | AT mirjamdur conicoptimizationasurveywithspecialfocusoncopositiveoptimizationandbinaryquadraticproblems AT franzrendl conicoptimizationasurveywithspecialfocusoncopositiveoptimizationandbinaryquadraticproblems |