Let $x \in \mathbb{R}^n$ and $P$ a $n \times n$ positive definite symmetrix matrix. It is known that $\max_{x|~x^Tx\leq 1} x^TPx=\lambda_{\text{max}}(P)$, where $\lambda_{\text{max}}(P)$ is the largest eigenvalue of $P$.

Now split the vector $x$ in two parts as $x=\begin{bmatrix}x_1\\\tilde{x}\end{bmatrix}$, where $x_1 \in \mathbb{R}^{n_1}$ and $\tilde{x}$ is constant. Consider the following optimization problem $$y=\text{arg}\max_{x|~{x_1}^Tx_1\leq 1} x^TPx$$ that is, the subvector $x_1$ is required to be in a sphere, while the subvector $\tilde{x}$ is known and constant. The only decision variable is then $x_1$. Can I find the solution analytically?


You can divide $P$ into blocks:

$$P = \begin{bmatrix} P_1 & Q \\ Q^t & R \end{bmatrix}$$

Then we get

$$\begin{align*} x^t P x &= x_1^t P_1 x_1 + x_1^t Q \bar x + \bar x^tQ^tx_1 + \bar x^t R \bar x\\ & = x_1^t (P_1 x_1 + 2Q\bar x)+ \underbrace{\bar x^t R\bar x^t}_{const}\end{align*}$$

As $P$ is positive definite, all it is leading principal minors are positive and therefore $P_1$ is SPD as well. Furthermore we see that

$$\arg\max_{x_1: x_1^tx_1 \leq 1} x^t P x = \arg\max_{x_1: x_1^tx_1 \leq 1} x_1^t(P_1x_1 + 2Q\bar x)$$

Can you continue from here?

Edit: To use the same tool from above again, we have to complete the square, this means bringing that expression to the form $(x_1-a)^tP_1 (x_1-a) + c$. By expanding we get

$$(x_1-a)^tP_1 (x_1-a) + c = x_1^t P_1 x_1 - 2x_1^t P_1 a + a^t P_1 a+c$$

So we see $P_1 a = Q\bar x$ or $a = P_1^{-1}Q\bar x$ and $c = -a^t P_1 a$. So for $y := x_1 - a$ we are looking now for the $y$ maximizing $y^tP_1y$. Make sure to also express the condition $x_1^tx_1 \leq 1$ in terms of $y$.

  • $\begingroup$ Thanks! I had actually come to your reformulation. Now it is a QCQP, but I can't see how the analytical solution is obtained. Seems to me that the $2Q\overline{x}$ term ruins the max eigenvalue result. $\endgroup$ – pulosky Sep 22 '17 at 9:49
  • $\begingroup$ You can eliminate this term by "completing the square", i.e. transforming it to an expression of the form $(x_1-a)^tP_1 (x_1-a) + const$. After that, you can define the variable transformation $y = x_1 -a$ and continue. $\endgroup$ – flawr Sep 22 '17 at 9:52
  • $\begingroup$ Thanks. I can get to: $$\text{arg}\max_{||y-P_1^{-1}Q\overline{x}|| \leq 1} y^TP_1 y - \overline{x}^TQ^TP^{-T}Q \overline{x} $$. However, $y$ is now constrained in a shifted sphere. How could I continue? $\endgroup$ – pulosky Sep 22 '17 at 10:03
  • $\begingroup$ Opened a new question for the reformulated problem: math.stackexchange.com/questions/2440218/… $\endgroup$ – pulosky Sep 22 '17 at 10:30

Your Answer

