How can I show that these two problems have the same optimal solution:

$$\inf \{ x^TAx + b^Tx : 1-x^Tx \ge 0,\ x \in \mathbb R^n\}$$

$$\inf \{ x^TAx + b^Tx : 1-x^Tx = 0,\ x \in \mathbb R^n\}$$

when $A$ is not positive semi-definite?


Start with $\|x^{\text{opt}}\|_2 < 1$ as a hypothetical optimal solution for $(1)$ and improve the value of the objective function by scaling $x^{\text{opt}}$. The infinmum exists because $\overline{B_1(0)}$ is compact in $\mathbb R^n$.

This gives a contradiction and shows that the infimum is attained on $\|x^{\text{opt}}\|_2 = 1$ so the problems are equivalent.

  • $\begingroup$ Thank you! I am unfamiliar with the notation; what does $B_1(0)$ mean? $\endgroup$ – user192348 Dec 4 '14 at 22:27
  • 1
    $\begingroup$ @user2340818 The (in this case closed) unit ball. Usually it refers to the open ball: $$B_r(x) = \{ y | \|x-y\|_2 < r \}$$ I changed the notation to use the open ball, wich is more standard. $\endgroup$ – AlexR Dec 4 '14 at 22:35
  • $\begingroup$ Sorry this coming slow to me, I don't understand what contradiction occurred? $\endgroup$ – user192348 Dec 4 '14 at 22:37
  • 1
    $\begingroup$ @user2340818 We assumed $x^{\text{opt}}$ to be an interior point on wich the infimum is attained and we can see that $\frac1{\|x^{\text{opt}}\|_2} x^{\text{opt}}$ is a point with smaller objective function. $\endgroup$ – AlexR Dec 4 '14 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy