0

considering following quadratic optimization problem with linear equality constraints \begin{equation} \begin{aligned} \max_w~& r^\top w - \frac{1}{2}w^\top Q w \\ \mathrm{s.t.}& \sum w = 1 \end{aligned} \end{equation} By given $r\in\Re^{N\times 1}$ and positive definite $Q$, it is easy to find the analytical solution: \begin{equation} \begin{bmatrix} -Q & \mathbf{1}_{N\times 1} \\ \mathbf{1}_{1\times N} & 0 \end{bmatrix}\begin{bmatrix} w\\ \lambda \end{bmatrix} = \begin{bmatrix} r\\ 1 \end{bmatrix} \end{equation} where $\lambda$ is the Lagrange multiplier. I was wondering, by given the optimal $w^*$, is it possible to derive the vector $r$?

I thought it would be easy, because \begin{equation} w = Q^{-1} (r + \mathbf{1}_{N\times 1} \lambda) \Longrightarrow \sum(w) = \mathbf{1}_{1\times N}Q^{-1} (r + \mathbf{1}_{N\times 1} \lambda) = 1 \end{equation} hence \begin{equation} \begin{bmatrix} I_N & \mathbf{1}_{N\times 1} \\ \mathbf{1}_{1\times N}Q^{-1} & \mathbf{1}_{1\times N}Q^{-1}\mathbf{1}_{N\times 1} \end{bmatrix}\begin{bmatrix} r\\ \lambda \end{bmatrix} = \begin{bmatrix} Qw\\ 1 \end{bmatrix} \end{equation} However, I found that matrix is not invertible due to rank deficiency. Can anyone help me to obtain the $r$ given $w^*$? Thanks!

Stephen Ge
  • 149

2 Answers2

1

The problem you pose is minimization of $||w-Q^{-1/2}r||_{Q^{1/2}}$ over the simplex, i.e. some weighted projection to the simplex. Given a projection $w^{*}$ there are generically infinitely many $r$ which yield the same projection (thus the issue with non-invertible). A picture in 2d says it all hopefully (here drawn for simple case with $W=I$, red line is the simplex, green line all possible $r$, two centers $r^{*}$ with corresponding level sets of the quadratic, and both of them yield the same projection $w^{*}$

enter image description here

Johan Löfberg
  • 9,497
  • 1
  • 15
  • 15
0

Forming the Lagrangian

$$ L(w,\lambda) = r^{\top}w-\frac 12 w^{\top}Qw+\lambda(1^{\top}w-1) $$

we have

$$ \nabla L = 0 = r^{\top}-w^{\top}Q+\lambda 1^{\top}=0 $$

multiplying by $w$ we have

$$ r^{\top}w-w^{\top}Qw+\lambda 1^{\top}w = 0\Rightarrow r^{\top}w-w^{\top}Qw+\lambda = 0 $$

and finally

$$ r^{\top}-w^{\top}Q+(w^{\top}Qw-r^{\top}w) 1^{\top}=0 $$

or

$$ r - (w^{\top}r) 1 = Q^{\top}w-(w^{\top}Q^{\top}w)1\Rightarrow (I_n-W) r = Q^{\top}w-(w^{\top}Q^{\top}w)1 $$

then

$$ r = (I_n-W)^{-1}\left(Q^{\top}w-(w^{\top}Q^{\top}w)1\right) $$

Here

$$ \cases{ 1^{\top} = (1,\cdots,1)\\ I_n = \text{Identity matrix}\\ W = (w,\cdots,w)^{\top} } $$

Cesareo
  • 33,252
  • $I_n - W$ will not be invertible, you are equivalent solving \begin{equation} \begin{bmatrix} I_N & \mathbf{1}_{N\times 1} \ w^\top & 1 \end{bmatrix}\begin{bmatrix} r\ \lambda \end{bmatrix} = \begin{bmatrix} Qw\ w^\top Q w \end{bmatrix} \end{equation}, which is rank deficient – Stephen Ge Apr 21 '23 at 14:13
  • Invertibility depends on the size of $W$. If $|w| << 1$ is invertible for sure. – Cesareo Apr 21 '23 at 14:59
  • Thanks, but I don't know how to verify your answer, because there is not inequality constraints, how can I ensure that abs(w) is much smaller than 1? – Stephen Ge Apr 21 '23 at 16:17
  • This is an extreme example. The identity matrix being dominant, $I_n-W$ will be invertible. Ill conditioning in the inversion may appear as the identity matrix is not dominant, but even in this case,$I_n- W$ may be numerically invertible. – Cesareo Apr 21 '23 at 18:40