0
$\begingroup$

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.

$\endgroup$

2 Answers 2

1
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

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.