1
$\begingroup$

I am working on a quadratically constrained quadratic program (QCQP) of the form:$$ \min_{x} \quad \frac{1}{2} x^T P x + q^T x + r$$ $$ \text{subject to} \qquad x^{T}x \leq 1 $$

where $P \in S^{++}_{n}$ is a symmetric positive definite matrix, and $q \in \mathbb{R}^{n}$ is a given vector. I aim to show that the optimal solution $x^{*}$ satisfies:$$ x^{*}=-(P+ \lambda I)^{-1}q$$ where $ \lambda$ =$\max\{ 0,\bar{\lambda}\}$ and $\bar{\lambda}$ is the largest solution to the nonlinear equation:$$q^{T}(P+\lambda I)^{-2}q=1 $$ I tried solving this by using the necessary and sufficient conditions for the optimal solution:$$ x \text{ is optimal if and only if } x \in X \text{ and} \\ \nabla f_0(x)^T (y - x) \geq 0 \quad \text{for all} \quad y \in X. $$ But I wasn't able to make progress.Is there an alternative approach to solve this problem, or any hints on how to use the optimality conditions more effectively? Any suggestions would be greatly appreciated!

$\endgroup$
1
  • $\begingroup$ You may want to read up on Trust Region methods. $\endgroup$
    – Hannes
    Commented Dec 6 at 14:18

1 Answer 1

0
$\begingroup$

$\newcommand\R{\Bbb R}\newcommand\la{\lambda}$Remark 1:

Let \begin{equation*} g(s):=q^T(P+sI)^{-2}q \end{equation*} for real $s$ such that $P+sI$ is invertible. The function $g$ is nonnegative and nonincreasing on the interval $I_P:=(-\la_{\min},\infty)$, and $g(\infty-)=0$, where $\la_{\min}>0$ is the smallest eigenvalue of the symmetric positive-definite matrix $P$. Moreover, the equation \begin{equation*} g(s)=1 \tag{0}\label{0} \end{equation*} $s\in I_P$ has at most one root, because (i) if $q\ne0$, then $g'(s)=-2q^T(P+sI)^{-3}q<0$ for all $s\in I_P$ and hence $g$ is strictly decreasing and (ii) if $q=0$, then $g(s)=0$ for all $s\in I_P$ and hence equation \eqref{0} has no roots. So,

  • if $q\ne0$, then equation \eqref{0} has at most one nonnegative root, and then this root is the largest real root of \eqref{0};

  • if $q=0$, then equation \eqref{0} has no real roots.

Let now \begin{equation*} f(z):=\frac12\,z^T Pz+q^T z+r \end{equation*} for $z\in\R^n$. The function $f$ is strictly convex. So, $f$ attains its minimum on the closed unit ball $B$ at a unique point $x\in B$. As you noted, we have \begin{equation*} 0\le\min_{y\in B}a^T(y-x)=-|a|-a^T x, \tag{1}\label{1} \end{equation*} where \begin{equation*} a:=\nabla f(x)=Px+q \tag{2}\label{2} \end{equation*} and $|\cdot|$ is the Euclidean norm. Since $x\in B$, we have $-a^T x\le|a|$. So, by \eqref{1}, \begin{equation*} -a^T x=|a|. \tag{3}\label{3} \end{equation*} So, for $$t:=|a|,$$ we have one of the following two cases:

Case 1: $t>0$. Then, since $x\in B$, \eqref{3} and \eqref{2} imply $x=-a/|a|=-\frac1t\,(Px+q)$, so that $|x|=1$ and
\begin{equation*} x=-(P+tI)^{-1}q, \tag{4}\label{4} \end{equation*} whence $g(t)=x^T x=1$ and therefore, by Remark 1, $t>0$ is the largest root $s$ of equation \eqref{0} -- as desired, because, obviously, here $t=\max(0,t)$.

Case 2: $t=0$, that is, $a=0$, that is, $x=-P^{-1}q$ -- so that \eqref{4} still holds. In this case $1\ge x^T x=q^TP^{-2}q$, so that $g(t)=g(0)\le1$. So, in this case, $t$ is a root of \eqref{0} if and only if $|x|=1$. So, in view of Remark 1, in this case your claim about the minimizer will hold if and only if $q\ne0$ and $|x|=1$. The latter condition will not of course hold in general even if $q\ne0$: e.g., if $n=1$ and $f(z)=z^2+z$, then $x=-1/2$ and $|x|<1$.

We conclude that, in both cases, \eqref{4} holds for the unique minimizer $x$ of $f$. Moreover, your claim about the minimizer $x$ will hold if and only if $q\ne0$ and $|x|=1$.


These conclusions can also be obtained a bit more elementarily, by first diagonalizing $P$ and using the spherical symmetry of $B$.

$\endgroup$
4
  • $\begingroup$ Thanks for such an explicit and clear explanation! $\endgroup$ Commented Dec 8 at 12:49
  • $\begingroup$ In case2, you mean g(s)=1 may have no root. But if s < -$\lambda$ , will g(s)=1 may still have root? On this basis, my claim about the minimizer still holds in general? $\endgroup$ Commented Dec 8 at 13:06
  • $\begingroup$ @nuobeitang : Good point. I have made the corresponding changes. $\endgroup$ Commented Dec 8 at 13:46
  • $\begingroup$ I really want to vote your answer.Since I’m new here, I don’t have enough reputation to cast a vote. $\endgroup$ Commented Dec 11 at 12:55

You must log in to answer this question.

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