3
$\begingroup$

I have an optimization problem of the following form

$$\text{minimize} \,\|Qa-b\|_2 \quad \text{ subject to } Q \succeq 0$$

where $a,b \in \mathbb{R}^n$ are given and the $n \times n$ square matrix $Q$ is the variable.

  • It is most probably a semidefinite programming problem. Is there a standard answer to this problem?

  • If not, which algorithm is best suited to solve this problem?

Improve this question
$\endgroup$
1
  • $\begingroup$ Hint: you are trying to project $b$ onto the set $\{Qa \mid Q\succeq 0\} = \{c \mid \langle c, a\rangle \geq 0\}$. $\endgroup$
    – Noah Stein
    Commented May 15, 2017 at 19:55

2 Answers 2

Reset to default
2
$\begingroup$

I will assume throughout that the definition of positive semidefiniteness includes symmetry. The problem is to find the Euclidean projection of $b$ onto the convex set $R = \{Qa \mid Q\succeq 0\}$. Let $S = \{c \mid c^Ta \geq 0\}$, which is closed. We first show that $S$ is the closure of $R$. If $c\in R$ then $c=Qa$ for some $Q\succeq 0$ so $c^Ta = a^TQa \geq 0$ and $c\in S$. Conversely if $c$ is in the interior of $S$, so $c^Ta > 0$, then let $Q = bb^T$ for $b = \frac{c}{\sqrt{c^Ta}}$, so $Q$ is positive semidefinite and $Qa = c\frac{c^Ta}{c^Ta} = c\in R$. Therefore $\overline{R}=S$.

Projecting $b$ onto the closed set $S$ is easy: if $b^Ta \geq 0$ then the projection is $b$, otherwise the projection is $b - \frac{b^Ta}{a^Ta}a$.

This leaves the question of whether this infimum is actually achieved by some $Q$, i.e. whether the projection is in $R$. In general it may not be: for example take $a = \begin{bmatrix}1 \\ 0\end{bmatrix}$ and $b = \begin{bmatrix}0 \\ 1\end{bmatrix}$. Then $b^Ta = 0$, so the projection of $b$ onto $S$ is $b$. But now suppose there is some positive semidefinite $Q$ with $Qa = b$. By symmetry this means $Q = \begin{bmatrix}0 & 1 \\ 1 & q\end{bmatrix}$ for some $q\geq 0$. But then $\det Q = -1$, contradicting positive semidefiniteness.

Improve this answer
$\endgroup$
4
  • $\begingroup$ With a bit more effort you can see that $R$ is the interior of $S$ plus the origin, so the infimum is only achieved when $b^T a >0$ or $b=0$. $\endgroup$
    – Noah Stein
    Commented May 18, 2017 at 15:42
  • $\begingroup$ Thanks for the insight. But in case of $b^Ta >0$, what is the expression for symmetric p.s.d matrix $Q$ ? Also, if I strictly want a symmetric positive definite matrix (may be, under newer assumptions like $b^Ta >0$), what should be the matrix $Q$ ? $\endgroup$
    – user402940
    Commented May 18, 2017 at 17:24
  • $\begingroup$ If you unwind the argument I gave, you get that when $b^Ta >0$ then the objective value of zero is achieved at $Q = \frac{bb^T}{b^Ta}$, which is symmetric and positive semidefinite, being a positive scalar multiple of an outer product of a vector with itself. $\endgroup$
    – Noah Stein
    Commented May 18, 2017 at 18:53
  • $\begingroup$ If $b^Ta > 0$ then you can replace $b$ with some $\hat{b} = b - \epsilon a$ for small enough $\epsilon>0$ that $\hat{b}^Ta > 0$. Then use the same argument to construct a psd $\hat{Q} = \frac{\hat{b}\hat{b}^T}{\hat{b}^Ta}$ with $\hat{Q}a = \hat{b}$. Then let $Q = \hat{Q} + \epsilon I$, so $Qa = \hat{b} + \epsilon a = b$. $\endgroup$
    – Noah Stein
    Commented May 18, 2017 at 19:03
2
$\begingroup$

$$\begin{array}{ll} \text{minimize} & \| \mathrm X \mathrm a - \mathrm b \|_2 \\ \text{subject to} & \mathrm X \succeq \mathrm O_n\end{array}$$

where $\mathrm a, \mathrm b \in \mathbb R^n \setminus \{0_n\}$ are given. Minimizing the squared $2$-norm of $\mathrm X \mathrm a - \mathrm b$, and writing in epigraph form, we obtain a minimization problem in $\rm X$ and $t$

$$\begin{array}{ll} \text{minimize} & t\\ \text{subject to} & \| \mathrm X \mathrm a - \mathrm b \|_2^2 - t \leq 0 \\ & \mathrm X \succeq \mathrm O_n\end{array}$$

Using the Schur complement, the inequality

$$\| \mathrm X \mathrm a - \mathrm b \|_2^2 - t = (\mathrm X \mathrm a - \mathrm b)^{\top} (\mathrm X \mathrm a - \mathrm b) - t \leq 0$$

can be written as the following linear matrix inequality (LMI)

$$\begin{bmatrix} \mathrm I_n & \mathrm X \mathrm a - \mathrm b\\ (\mathrm X \mathrm a - \mathrm b)^{\top} & t\end{bmatrix} \succeq \mathrm O_{n+1}$$

Thus, we have the following SDP in $\rm X$ and $t$

$$\begin{array}{ll} \text{minimize} & t\\ \text{subject to} & \begin{bmatrix} \mathrm I_n & \mathrm X \mathrm a - \mathrm b & \mathrm O_n\\ (\mathrm X \mathrm a - \mathrm b)^{\top} & t & 0_n^{\top}\\ \mathrm O_n & 0_n & \mathrm X\end{bmatrix} \succeq \mathrm O_{2n+1}\end{array}$$

Improve this answer
$\endgroup$
3
  • $\begingroup$ So, you basically formulated it as a SDP problem. But can we have a precise solution to this problem in terms of $a$ and $b$ vectors ? Or is it not possible and we have to solve this problem numerically ? $\endgroup$
    – user402940
    Commented May 15, 2017 at 18:14
  • 1
    $\begingroup$ If $b$ is not a scalar multiple of $a$, then $ba^T$ is not positive semidefinite. To see this let $c$ be such that $c^Ta$ and $c^Tb$ have opposite signs -- this just means picking a hyperplane so that $a$ is on one side and $b$ is on the other. Then $c^T(ba^T)c < 0$. (Personally I always take the definition of positive semidefiniteness to include symmetry by default.) $\endgroup$
    – Noah Stein
    Commented May 18, 2017 at 15:08
  • $\begingroup$ @NoahStein Thanks for the correction. I will edit my answer and remove everything other than the SDP formulation. I will also ask the OP that your answer be accepted, rather than mine. $\endgroup$
    – Rodrigo de Azevedo
    Commented May 18, 2017 at 16:56

Not the answer you're looking for? Browse other questions tagged .