11.4 Quadratic and Quadratically Constrained Optimization¶
A convex quadratic and quadratically constrained optimization problem has the form
where all variables and bounds have the same meaning as for linear problems (see Sec. 11.1 (Linear Optimization)) and
The convexity requirement is very important and MOSEK checks whether it is fulfilled.
11.4.1 A Recommendation¶
Any convex quadratic optimization problem can be reformulated as a conic quadratic optimization problem, see Modeling Cookbook and [And13]. In fact MOSEK does such conversion internally as a part of the solution process for the following reasons:
the conic optimizer is numerically more robust than the one for quadratic problems.
the conic optimizer is usually faster because quadratic cones are simpler than quadratic functions, even though the conic reformulation usually has more constraints and variables than the original quadratic formulation.
it is easy to dualize the conic formulation if deemed worthwhile potentially leading to (huge) computational savings.
However, instead of relying on the automatic reformulation we recommend to formulate the problem as a conic problem from scratch because:
it saves the computational overhead of the reformulation including the convexity check. A conic problem is convex by construction and hence no convexity check is needed for conic problems.
usually the modeler can do a better reformulation than the automatic method because the modeler can exploit the knowledge of the problem at hand.
To summarize we recommend to formulate quadratic problems and in particular quadratically constrained problems directly in conic form.
11.4.2 Duality for Quadratic and Quadratically Constrained Optimization¶
The dual problem corresponding to the quadratic and quadratically constrained optimization problem (11.22) is given by
The dual problem is related to the dual problem for linear optimization (see Sec. 11.1.1 (Duality for Linear Optimization)), but depends on the variable
11.4.3 Infeasibility for Quadratic Optimization¶
In case MOSEK finds a problem to be infeasible it reports a certificate of infeasibility. We write them out explicitly for quadratic problems, that is when
The certificate of primal infeasibility is a solution to the problem (11.5) such that the objective value is strictly positive.
The certificate of dual infeasibility is a solution to the problem (11.6) together with an additional constraint
such that the objective value is strictly negative.