Let $x \in \mathbb{R}^n$ and let $P$ be a $n \times n$ positive definite symmetrix matrix. It is known that the maximum of

$$\begin{array}{ll} \text{maximize} & x^T P \, x\\ \text{subject to} & x^T x \leq 1\end{array}$$

is $\lambda_{\text{max}}(P)$, the largest eigenvalue of $P$. Now consider the following problem

$$\begin{array}{ll} \text{maximize} & x^T P \, x\\ \text{subject to} & (x-a)^T (x-a) \leq 1\end{array}$$

where $a \in \mathbb{R}^n$ is known. What is the analytical solution?

  • 1
    $\begingroup$ The keyword here is "quadratic programming". I am afraid there is no analytical solution in general. For obtaining numerical solutions, take a look to (en.wikipedia.org/wiki/Quadratic_programming). $\endgroup$ – Jean Marie Sep 22 '17 at 10:25
  • $\begingroup$ Thanks, yes I know there is no analytical solution in general. Though, in the case of the unit sphere constraint, it can be shown that the analytical solution is the max eigenvalue of $P$. So, I was wondering if the analytical solution can be found also in the case of the shifted sphere. $\endgroup$ – pulosky Sep 22 '17 at 10:27
  • $\begingroup$ @Rodrigo de Azevedo You are right. $\endgroup$ – Jean Marie Sep 22 '17 at 11:29

This is (a variant of) the trust-region problem, and the solution can be computed rather easily, although not an analytical solution

See, e.e., https://www8.cs.umu.se/kurser/5DA001/HT07/lectures/trust-handouts.pdf

I'm reparameterizing your problem slightly, you can easily change your model to be $\max x^TQx + c^Tx + b$ subject to $x^Tx\leq 1$. At optimality, you will be at the border of feasibility, and the constraint gradient will be pointing in the same direction as the objective gradient (draw this geometrically!), i.e., you have $2Qx + c = \lambda 2x$ for some unknown $\lambda$. Solve for $x$ to obtain $x = -(2Q-\lambda I)^{-1}c$. To find lambda, solve $x^Tx = 1$ which is an equation in $\lambda$ (possibly tricky, numerical methods required, line-search, bisection etc)


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.