# Quadratic Programming with Linear Equality Constraints

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?

• I’m voting to close this question because this is not about signal processing in particular, but about math / optimization in general. math.SE would be an appropriate place to ask. Commented Apr 29, 2020 at 19:50
• What are the optimisation variables? What is given? Commented Apr 29, 2020 at 20:57
• I added a closed form solution to the problem. Enjoy..
– Royi
Commented Apr 29, 2020 at 21:09

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().

• The problem here is the matrix $X$ is very huge of order $10^7\times 512$. How can we solve it without getting out of memory issue. :( Commented Apr 30, 2020 at 3:43
• @user5045, Is $X$ Sparse? Can you tell us about it more. Also, You wrote closed form solution which I gave you. Please mark it. If you need iterative algorithm to solve large system I will add it.
– Royi
Commented Apr 30, 2020 at 10:33
• Dear Royi, it would be of great help if you can give a numerical method to solve it. Commented Apr 30, 2020 at 10:41
• Sorry to bother again. To be precise, let me give the sizes of the matrices I am using. $R\in \mathbb{R}^{512\times 512}$ is symmetric PSD, $X\in R^{22439\times 512}$. If try to fill in the matrix $F$ as mentioned above, I get out of memory issue in MATLAB. To use any solver given above, first I need to create the matrix $F \in \mathbb{R}^{22951 \times 22951}$ which is huge. Please help. Commented May 4, 2020 at 15:20
• Unless $X$ is Sparse you need a computer which can handle this sizes. What does $X$ represent?
– Royi
Commented May 4, 2020 at 17:20

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)

• Linear equality constraints are convex. No need to transform. You may see my answer below for a closed form solution. Inequality means no closed form solution.
– Royi
Commented Apr 30, 2020 at 10:35