# Maximizing sum of vector norms

Given matrices $$A, B \in \mathbb{R}^{n\times n}$$, I would like to solve the following optimization problem,

$$\begin{array}{ll} \underset{v \in \mathbb{R}^n}{\text{maximize}} & \|Av\|_2+\|Bv\|_2\\ \text{subject to} & \|v\|_2 = 1\end{array}$$

I'm hoping to solve this with some sort of convex optimization approach, such as SDP or SOCP. When $$B=0$$, the problem reduces to simply asking for the largest singular value of $$A$$, which can be solved by an SDP (see here for instance although it's very well known). It can also be computed with SVD of course.

I've tried lots of different approaches but can't seem to write it in a convex way. I would be okay with an SVD-like solution, that is, one that is iterative not a convex program, but I would much prefer a convex program because ultimately I would like to use this as an inner program to something else, ideally.

As a note on one attempt that got a decent ways, I did manage to establish that it was equivalent to the problem,

$$\begin{array}{ll} \underset{u, v \in \mathbb{R}^n}{\text{maximize}} & \|A^T u + B^T v\|_2\\ \text{subject to} & \|u\|_2 = \|v\|_2 = 1\end{array}$$

• Is squaring the norms in the 2nd maximisation problem admissible? If so, how about something simple like this? Aug 26, 2021 at 18:08
• I did a route much like that (before posting on MathOverflow), did the same Lagrangian etc., until I realized that I was maximizing $[u v]^T A^T A[u v]$, not minimizing, so normal convex methods wouldn't work. I tried substitution like you describe in that answer, but since there were now two lagrange multipliers it came out much messier. Instead of $x_1 = -(A^T A)^{-1} A^T B x_2$, it was $x_1 = (1-\lambda_1 A^T A)^{-1} A^T B x_2$. This loses nice properties like it being a projector. And if I plug $x_1$ in, it's very hard to solve for $x_2$, because that $\lambda_2$ is floating around. Aug 26, 2021 at 18:18
• I do appreciate the ideas though! Aug 26, 2021 at 18:19

I have no doubt that someone will come with some brighter idea but here are my 2 cents anyway.

If you don't aim at something very fast, I would just use the inequality $$(a+b)^2\le (ta^2+(1-t)b^2)(t^{-1}+(1-t)^{-1})=F_t(a,b)$$ and try to find $$\min_{t\in[0,1]}\max_v F_t(\|Av\|,\|Bv\|)$$. The maximum inside is just $$(t^{-1}+(1-t)^{-1})$$ times the maximal eigenvalue of $$tA^*A+(1-t)B^*B$$ and the function $$F_t$$ is convex in $$t$$, so the maximum in $$v$$ is also convex, which makes simple one-dimensional tools for finding the minimum like bisection quite efficient.

The reason it will work is simple: the maximal unit eigenvector $$v$$ will move continuously (when you have a multiple eigenvalue, you can slowly move it from one limiting position to the other keeping the parameter $$t$$ constant), so there will be a moment in that process where $$\|Av\|/\|Bv\|=(1-t)/t$$. At that moment the inequality in the Cauchy-Schwarz will become equality, so the sum of the norms will achieve the upper bound coming from the quadratic relaxation (I assume that $$A,B$$ are both non-degenerate in this argument). Thus, the minimax we created really equals the maximin.

Note that it will all work nicely if you want just the value of the maximum, not the maximizing vector itself. The difficulty with the latter is that you may achieve the minimum in $$t$$ where the maximal eigenvalue is multiple, in which case not every eigenvector will be good but only the one for which the ratio of the norms is just right. Fortunately, generically it should not happen. However, you should be ready for this nuisance.

• Thanks! This works perfectly, and I can use it to write an SDP. Expanding $(tA'A+(1-t)B'B)(t^{-1}+(1-t)^{-1}) = A'A/(1-t) + B'B/t$, the problem is sqrt[minimum_t of [max eigenvalue (A'A/(1-t) + B'B/t)]]. The functions $1/(1-t)$ and $1/t$ are convex and can be expressed with $\begin{bmatrix} u & 1 \\ 1& t\end{bmatrix}\succeq 0$ implying $u \ge 1/t$, similarly $r \ge 1/(1-t)$. Then the maximum eigenvalue is the minimum $a$ such that $aI - rA^\dagger A - uB^\dagger B\succeq 0$. You minimize this program over $a$, $r$, $t$, and $u$ as an SDP to get (the square of) the final answer. Thanks a bunch! Aug 26, 2021 at 5:31
• If one wanted an SDP to produce the exact value, not just the square of the exact value, you could do that too: turn it all into a maximization problem by going to the dual SDP. Let the maximization objective be $m$. Then add the matrix constraint $\begin{bmatrix}1 & p \\ p & m\end{bmatrix} \succeq 0$ and switch to maximizing $p$. This will be maximized with $p = \sqrt{m}$ and give the true value. Aug 26, 2021 at 5:39
• @fedja It is not clear to me how to do in the case of multiple eigenvalues, say at time $t_0$. Crossing it you can loose the continuity of the eigenvector but then you vary it, with $t_0$ fixed, having the same $F_{t_0}$, but possibly changing the ratio $\|Av\|/\|Bv\|$. I understand it only vaguely, could you explain more? Aug 27, 2021 at 16:14
• @GiorgioMetafune The details in the general case are a bit ugly, but if you have just a jump discontinuity, you just move the vector from the left limit to the right limit along the eigenspace. Alternatively, you can consider the whole set of eigenvectors at each moment and all possible ratios. Then you'll have an interval-valued function with some weird "continuity" (the intervals at close points cannot be at distance more than $\varepsilon$ from the interval at a point), under which the IVT still applies. Aug 27, 2021 at 17:05
• @fedja Thank you Aug 27, 2021 at 17:58