# positive semidefiniteness: a psd matrix substracted by another rank 1 psd matrix

Given that $A$ is a positive semidefinite matrix, $x$ is a vector, $\lambda_0 \in [0, +\infty)$ is a real non-negative number. I want to know the answer to the following optimization problem.

$$\arg \min_{\lambda} |\lambda- \lambda_0| \\ s.t. \;\; A-\lambda xx^T \ge 0$$

Note $A-\lambda xx^T \ge 0$ means that $A-\lambda xx^T$ is a positive semidefinite matrix.

-

This is easy to formulate as a semidefinite programming problem.

First, let $X=xx^{T}$. The semidefiniteness constraint becomes

$A-\lambda X \succeq 0$

Next, use a standard technique to handle the absolute value in the objective by replacing it with an auxiliary variable and two linear inequality constraints. The problem becomes

$\min_{\lambda,t} t$

subject to

$t \geq \lambda-\lambda_{0}$

$t \geq \lambda_{0}-\lambda$

$A-\lambda X \succeq 0$

If $t$ is greater than or equal to $\lambda-\lambda_{0}$ and $t$ is greater than or equal to $\lambda_{0}-\lambda$, then $t$ is clearly greater than or equal to $| \lambda-\lambda_{0} |$. Since $t$ is being minimized and there are no other constraints on $t$, it will end up equal to $| \lambda-\lambda_{0}|$.

This isn't quite in standard SDP format. The two constraints involving $t$ can be brought into semidefinite form by making

$t - \lambda + \lambda_{0}$

and

$t - \lambda_{0} + \lambda$

diagonal elements of the matrix that is constrained to be positive semidefinite. This insures that $t-\lambda+\lambda_{0} \geq 0$ and $t-\lambda_{0}+\lambda \geq 0$.

Let

$F_{0}=\left[ \begin{array}{ccc} A & 0 & 0 \\\ 0 & \lambda_{0} & 0 \\\ 0 & 0 & -\lambda_{0} \end{array} \right]$

$F_{1}=\left[ \begin{array}{ccc} -X & 0 & 0 \\\ 0 & -1 & 0 \\\ 0 & 0 & 1 \end{array} \right]$

$F_{2}=\left[ \begin{array}{ccc} 0 & 0 & 0 \\\ 0 & 1 & 0 \\\ 0 & 0 & 1 \end{array} \right]$

Now, the problem can be written in standard form as

$\min_{\lambda,t} t$

subject to

$F_{0}+\lambda F_{1}+tF_{2} \succeq 0$

-

Assume $x\not=0$. Using an orthonormal change of basis, we may assume $x=[\alpha,0,\cdots,0]^T$ where $\alpha>0$ and let $A=[a_{i,j}]$. Then $A-\lambda xx^T=\begin{pmatrix}a_{1,1}-\lambda\alpha^2&u^T\\u&B\end{pmatrix}$ where $B$ is symmetric $\geq 0$ (as a principal submatrix of $A$). Then $A-\lambda xx^T\geq 0$ iff $\det(A-\lambda xx^T)\geq 0$, that is, $\det A-\lambda\alpha^2\det B\geq 0$. Finally the condition on $\lambda$ is $\lambda\leq \dfrac{\det A}{\alpha^2\det B}$. We deduce an explicit solution $\Lambda$: if $\lambda_0> \dfrac{\det A}{\alpha^2\det B}$, then $\Lambda=\dfrac{\det A}{\alpha^2\det B}$, else $\Lambda=\lambda_0$.

-