Quadratic optimization

Optimization of a quadratic form or quadratic-plus-linear objective over specified constraints. Convexity depends on the matrix and feasible domain; discrete restrictions lead to binary quadratic optimization.

A quadratic program is an optimization problem with a quadratic objective and linear equality or inequality constraints. A positive-definite objective Hessian makes it strictly convex and coercive; on a nonempty closed feasible set its minimizer exists and is unique. Such a program resolves tied Lasso knots by constraining tangent signs of currently zero regression coefficients while allowing unrestricted tangents for nonzero ones.

Optimization of a quadratic form over binary choices, here using signs $x_i\in \{-1,1\}$. Lifting $x{x}^T$ turns the objective into a matrix trace; dropping the rank-one condition gives a semidefinite relaxation of binary quadratic optimization.

For a real rectangular matrix $S$, maximize $p^{T}Sq$ over separate sign choices for $p$ and $q$. With $x=(p,q)$, the symmetric block matrix $A=\frac{1}{2}\left(\begin{array}{cc}0& S\\ S^T& 0\end{array}\right)$ satisfies $x^{T}Ax=p^{T}Sq$. Its zero diagonal blocks allow the Krivine rounding scheme to linearize the cross-block expected objective.