Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

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$

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.