0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
  • $\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

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.