Finding quadratic underestimators for optimal value functions of nonconvex all-quadratic problems via copositive optimization
Modeling parts of an optimization problem as an optimal value function that depends on a top-level decision variable is a regular occurrence in optimization and an essential ingredient for methods such as Benders Decomposition. It often allows for the disentanglement of computational complexity and...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2024-01-01
|
| Series: | EURO Journal on Computational Optimization |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S2192440624000170 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850111113939648512 |
|---|---|
| author | Markus Gabl Immanuel M. Bomze |
| author_facet | Markus Gabl Immanuel M. Bomze |
| author_sort | Markus Gabl |
| collection | DOAJ |
| description | Modeling parts of an optimization problem as an optimal value function that depends on a top-level decision variable is a regular occurrence in optimization and an essential ingredient for methods such as Benders Decomposition. It often allows for the disentanglement of computational complexity and exploitation of special structures in the lower-level problem that define the optimal value functions. If this problem is convex, duality theory can be used to build piecewise affine models of the optimal value function over which the top-level problem can be optimized efficiently. In this text, we are interested in the optimal value function of an all-quadratic problem (also called quadratically constrained quadratic problem, QCQP) which is not necessarily convex, so that duality theory can not be applied without introducing a generally unquantifiable relaxation error. This issue can be bypassed by employing copositive reformulations of the underlying QCQP. We investigate two ways to parametrize these by the top-level variable. The first one leads to a copositive characterization of an underestimator that is sandwiched between the convex envelope of the optimal value function and that envelope's lower-semicontinuous hull. The dual of that characterization allows us to derive affine underestimators. The second parametrization yields an alternative characterization of the optimal value function itself, which other than the original version has an exact dual counterpart. From the latter, we can derive convex and nonconvex quadratic underestimators of the optimal value function. In fact, we can show that any quadratic underestimator is associated with a dual feasible solution in a certain sense. |
| format | Article |
| id | doaj-art-83d892b69f4f4d7382c4881cff08ac10 |
| institution | OA Journals |
| issn | 2192-4406 |
| language | English |
| publishDate | 2024-01-01 |
| publisher | Elsevier |
| record_format | Article |
| series | EURO Journal on Computational Optimization |
| spelling | doaj-art-83d892b69f4f4d7382c4881cff08ac102025-08-20T02:37:41ZengElsevierEURO Journal on Computational Optimization2192-44062024-01-011210010010.1016/j.ejco.2024.100100Finding quadratic underestimators for optimal value functions of nonconvex all-quadratic problems via copositive optimizationMarkus Gabl0Immanuel M. Bomze1Department of Mathematics, University of Vienna, Austria; Corresponding author.VCOR and Data Science@Uni Vienna, University of Vienna, AustriaModeling parts of an optimization problem as an optimal value function that depends on a top-level decision variable is a regular occurrence in optimization and an essential ingredient for methods such as Benders Decomposition. It often allows for the disentanglement of computational complexity and exploitation of special structures in the lower-level problem that define the optimal value functions. If this problem is convex, duality theory can be used to build piecewise affine models of the optimal value function over which the top-level problem can be optimized efficiently. In this text, we are interested in the optimal value function of an all-quadratic problem (also called quadratically constrained quadratic problem, QCQP) which is not necessarily convex, so that duality theory can not be applied without introducing a generally unquantifiable relaxation error. This issue can be bypassed by employing copositive reformulations of the underlying QCQP. We investigate two ways to parametrize these by the top-level variable. The first one leads to a copositive characterization of an underestimator that is sandwiched between the convex envelope of the optimal value function and that envelope's lower-semicontinuous hull. The dual of that characterization allows us to derive affine underestimators. The second parametrization yields an alternative characterization of the optimal value function itself, which other than the original version has an exact dual counterpart. From the latter, we can derive convex and nonconvex quadratic underestimators of the optimal value function. In fact, we can show that any quadratic underestimator is associated with a dual feasible solution in a certain sense.http://www.sciencedirect.com/science/article/pii/S2192440624000170Quadratic optimizationConic optimizationBenders decomposition |
| spellingShingle | Markus Gabl Immanuel M. Bomze Finding quadratic underestimators for optimal value functions of nonconvex all-quadratic problems via copositive optimization EURO Journal on Computational Optimization Quadratic optimization Conic optimization Benders decomposition |
| title | Finding quadratic underestimators for optimal value functions of nonconvex all-quadratic problems via copositive optimization |
| title_full | Finding quadratic underestimators for optimal value functions of nonconvex all-quadratic problems via copositive optimization |
| title_fullStr | Finding quadratic underestimators for optimal value functions of nonconvex all-quadratic problems via copositive optimization |
| title_full_unstemmed | Finding quadratic underestimators for optimal value functions of nonconvex all-quadratic problems via copositive optimization |
| title_short | Finding quadratic underestimators for optimal value functions of nonconvex all-quadratic problems via copositive optimization |
| title_sort | finding quadratic underestimators for optimal value functions of nonconvex all quadratic problems via copositive optimization |
| topic | Quadratic optimization Conic optimization Benders decomposition |
| url | http://www.sciencedirect.com/science/article/pii/S2192440624000170 |
| work_keys_str_mv | AT markusgabl findingquadraticunderestimatorsforoptimalvaluefunctionsofnonconvexallquadraticproblemsviacopositiveoptimization AT immanuelmbomze findingquadraticunderestimatorsforoptimalvaluefunctionsofnonconvexallquadraticproblemsviacopositiveoptimization |