3
$\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$
  • 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$ – Marcus Müller Apr 29 at 19:50
  • $\begingroup$ What are the optimisation variables? What is given? $\endgroup$ – Rodrigo de Azevedo Apr 29 at 20:57
  • $\begingroup$ I added a closed form solution to the problem. Enjoy.. $\endgroup$ – Royi Apr 29 at 21:09
5
$\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().

| improve this answer | |
$\endgroup$
  • $\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 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 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 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 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 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)

| improve this answer | |
$\endgroup$
  • $\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 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.