Skip to main content
2 of 5
added 146 characters in body
Iosif Pinelis
  • 127.9k
  • 8
  • 107
  • 229

$\newcommand\R{\Bbb R}\newcommand\la{\lambda}$Let \begin{equation} g(s):=q^T(P+sI)^{-2}q \end{equation} for real $s$ such that $P+sI$ is invertible, that is, for all real $s$ greater than $-\la_{\min}$, where $\la_{\min}$ is the smallest eigenvalue $\la_{\min}$ of the symmetric positive-definite matrix $P$. The function $g$ is nonnegative, nonincreasing, and $g(\infty-)=0$. Let \begin{equation} f(x):=\frac12\,x^T Px+q^T x+r \end{equation} for $x\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=x_t, \quad\text{where } x_s:=-(P+sI)^{-1}q, \end{equation} whence $g(t)=x^T x=1$ and hence \begin{equation} f(x)=h(t), \end{equation} where \begin{equation} \begin{aligned} h(s)&:=f(x_s)=\frac12\,q^T (P+sI)^{-1} P(P+sI)^{-1}q-q^T (P+sI)^{-1}q+r \\ &:=-\frac12\,q^T (P+sI)^{-1}q-\frac s2\,q^T (P+sI)^{-2}q+r \\ &:=-\frac12\,q^T (P+sI)^{-1}q-\frac s2\,g(s)+r. \end{aligned} \end{equation} Recall that the continuous function $g$ is nonincreasing. So, the set $S:=\{s\in\R\colon g(s)=g(t)\}=\{s\in\R\colon g(s)=1\}$ is of the form $[t_1,t_2]\cap(-\la_{\min},\infty)$ for some real $t_1,t_2$ such that $t_2\ge t$. So, for all $s$ in the interior of the set $S$ we have \begin{equation} \begin{aligned} h'(s)&=\frac12\,q^T (P+sI)^{-2}q-\frac 12\,g(t)=0. \end{aligned} \end{equation} So, $f(x_s)=h(s)=h(t)=f(x)$ for all $s\in S$. Therefore and because $x=x_t$ is the unique minimizer of $f$ on $B$, we conclude that $x_s=x_t=x$ for all $s\in S$. In particular, $x_{t_2}=x$. So, in Case 2, the minimizer of $f$ on $B$ is \begin{equation} x=x_{t_2}=-(P+t_2I)^{-1}q, \end{equation} and $t_2>0$ is the largest real root $s$ of the equation \begin{equation} g(s)[=q^T(P+sI)^{-2}q]=1, \end{equation} as desired.

Case 2: $t=0$, that is, $x=-P^{-1}q$. In this case $1\ge x^T x=q^TP^{-2}q$, so that $g(0)\le1$. However, the equation $g(s)=1$ may not have any real root $s$ at all (e.g. when $q=0$ or, more generally, when $q$ is a short enough nonzero vector orthogonal to the eigenspace of $P$ corresponding to $\la_{\min}$). So, in this case your claim about the minimizer will not hold in general.


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

Iosif Pinelis
  • 127.9k
  • 8
  • 107
  • 229