# Maximizing $\|APBPA\|_2$ subject to $0 \leq P \leq I$

Given positive semidefinite matrices $A,B$, how to compute

$$\max_{0 \leq P \leq I}\|APBPA\|$$

where the norm is the spectral norm, i.e., the largest singular value?

• Is $P$ symmetric? Does $P \geq 0$ mean that $P$ is nonnegative or positive semidefinite? Is this related to Markov chains? Jul 7, 2016 at 0:03
• Related: Based on the answer of user p.s. below, this problem boils down to maximising $(u^TBu)(u^TA^2u)$ on the unit sphere. The minimisation problem in Minimize Product of Sums of Squared Distances also reduces to this form. Jul 7, 2016 at 1:13

If $\tilde{P}$ is optimal, let $v = \mbox{arg }\max_{\|x\|\le1} x^TA\tilde{P}B\tilde{P}Ax$ (a maximal singular vector of $A\tilde{P}B\tilde{P}A$) and let $u = \tilde{P}Av/\|\tilde{P}Av\|$. Then $P = uu^T$ is also optimal to the original problem, since

$$v^T APBPA v=(u^T B u)(u^TAv)^2 \ge(u^T B u)\|\tilde{P}Av\|^2 = v^T A\tilde{P}B\tilde{P}Av.$$ (Where we use the fact that $\tilde{P}\le I$, so that $u^TA v \ge \|\tilde{P}Av\|$.) So we can assume $P$ is rank 1. So then the problem reduces to:

$$\max_{\|u\| \le 1, \|v\| \le 1} (u^T B u)(u^TAv)^2=\max_{\|u\| \le 1} (u^T B u)(u^TA^2u)$$

Then we get a characterization for the entire optimal set of the original problem. In general, $P^*$ is optimal if and only if it is both feasible and satisfies $P^*A^2 u^* = \|A u^*\|^2 u^*$ for some $u^* \in \arg \max_{\|u\| \le 1} (u^T B u)(u^TA^2u)$.

By applying Lagrange multipliers to the subproblem, one can get a necessary (but not sufficient) condition for optimality:

$$u^* = \frac{1}{2}\left( \frac{Bu^*}{{u^*}^TBu^*} + \frac{A^2 u^*}{{u^*}^T A^2 u^*} \right)$$

If you want a numerical solution, you can converge to an optimal $u^*$ by an iterative update similar to the power method:

$$\begin{eqnarray} y_{k} &=& Bu_k (u_k^TA^2u_k) + A^2 u_k(u_k^T B u_k) \\ u_{k+1} &=& y_k/\|y_k\| \end{eqnarray}$$