1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Is $P$ symmetric? Does $P \geq 0$ mean that $P$ is nonnegative or positive semidefinite? Is this related to Markov chains? $\endgroup$ Jul 7, 2016 at 0:03
  • $\begingroup$ 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. $\endgroup$
    – user1551
    Jul 7, 2016 at 1:13

1 Answer 1

2
$\begingroup$

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

$\endgroup$

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.