Quadratic Programming with Linear Equality Constraints

Question

I need to solve an equality constrained minimization problem as give below $$\min_{\textbf{w}} \mathbf{w}^TR\mathbf{w} $$ such that $$X\mathbf{w} = \mathbf{1}$$ where $R\in \mathbb{R}^{n\times n}$ is covariance matrix (hence positive semi-definite)

$X\in \mathbb{R}^{m\times n}$ matrix with $m\gg n$,

$\mathbf{1}$ is column vector of size $m$ with all $1's$

$\mathbf{w}\in \mathbb{R}^n$ is an unknown vector.

Is there any closed form solution for this? If yes, can anyone provide it?

If no can we solve it by GD or any other algorithm?

Thanks in advance.

Answer 1

Let's solve a more general problem (Least Squares with Linear Equality Constraints):

$$ \begin{alignat*}{3} \arg \min_{x} & \quad & \frac{1}{2} \left\| A x - b \right\|_{2}^{2} \\ \text{subject to} & \quad & C x = d \end{alignat*} $$

The Lagrangian is given by:

$$ L \left( x, \nu \right) = \frac{1}{2} \left\| A x - b \right\|_{2}^{2} + {\nu}^{T} \left( C x - d \right) $$

From KKT Conditions the optimal values of $ \hat{x}, \hat{\nu} $ obeys:

$$ \begin{bmatrix} {A}^{T} A & {C}^{T} \\ C & 0 \end{bmatrix} \begin{bmatrix} \hat{x} \\ \hat{\nu} \end{bmatrix} = \begin{bmatrix} {A}^{T} b \\ d \end{bmatrix} $$

The trick here is to have a look at:

$$ \frac{1}{2} \left\| A x - b \right\|_{2}^{2} = \frac{1}{2} {x}^{T} {A}^{T} A x - {x}^{T} A b + \frac{1}{2} {b}^{T} b $$

So if we set $ w = x $, $ b = \boldsymbol{0} $, $ X = C $, $ d = \boldsymbol{1} $ and $ \frac{1}{2} {A}^{T} A = R $ then your solution is given by:

$$ \begin{bmatrix} 2 R & {X}^{T} \\ X & 0 \end{bmatrix} \begin{bmatrix} \hat{w} \\ \hat{\nu} \end{bmatrix} = \begin{bmatrix} \boldsymbol{0} \\ \boldsymbol{1} \end{bmatrix} $$

This is easy to solve in MATLAB or Python.

Handling Large System

As a request from @user5045 I add some info how to handle this in case $ R $ and $ X $ are large matrices.

We basically need to solve large scale matrix equation:

$$ \begin{bmatrix} 2 R & {X}^{T} \\ X & 0 \end{bmatrix} \begin{bmatrix} \hat{w} \\ \hat{\nu} \end{bmatrix} = \begin{bmatrix} \boldsymbol{0} \\ \boldsymbol{1} \end{bmatrix} = e = F g $$

The way to solve it is using an iterative solver. I case $ R $ is a PSD matrix then the solver should be Preconditioned Conjugate Gradient. In MATLAB it is implemented using pcg().
In case $ R $ is only symmetric one should use Minimum Residual Solver. In MATLAB it is implemented as minres(). For a a general square matrix I'd go with cgs().

Answer 2

I will give you a hint: you can first relax this problem to be a convex optimization problem by editing the second constraint as $$Xw <= \vec{1}$$

where the inequality is elementwise, then form the dual problem or the lagrangian as it is known popularly

$$ w^TRw + \lambda^T(Xw -1) \tag{1}$$

where $$\lambda <=\vec{0}$$

Differencate (1) with respect to $w$ and set the result to 0 to find the Maxima (remember we are trying to find the minimum of the original problem so in the dual problem we are maximizing, solve for $w$ in terms of vector $\lambda$, call this equation (2), then use the equality constraint( $Xw = 1$) to evaluate vector $\lambda$, once you have lambda you know the vector $w$ by substituting $\lambda$ in equation (2)