4
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 29 '20 at 19:50
  • $\begingroup$ What are the optimisation variables? What is given? $\endgroup$ Apr 29 '20 at 20:57
  • $\begingroup$ I added a closed form solution to the problem. Enjoy.. $\endgroup$
    – Royi
    Apr 29 '20 at 21:09
6
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ 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. :( $\endgroup$
    – user5045
    Apr 30 '20 at 3:43
  • $\begingroup$ @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. $\endgroup$
    – Royi
    Apr 30 '20 at 10:33
  • $\begingroup$ Dear Royi, it would be of great help if you can give a numerical method to solve it. $\endgroup$
    – user5045
    Apr 30 '20 at 10:41
  • $\begingroup$ 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. $\endgroup$
    – user5045
    May 4 '20 at 15:20
  • $\begingroup$ Unless $ X $ is Sparse you need a computer which can handle this sizes. What does $ X $ represent? $\endgroup$
    – Royi
    May 4 '20 at 17:20
1
$\begingroup$

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)

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Royi
    Apr 30 '20 at 10:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.