What is the dual of a norm that is the sum of two-norms? Specifically, say we have the following norm for $\mathbf{x}\in \mathbb{R}^n$ and $\mathbf{A}\_i \in \mathbb{R}^{m \times n}$


$\|\mathbf{x}\| = \displaystyle{ \sum\_{i=0}^{k} \|\mathbf{A}\_i \cdot \mathbf{x} \|\_2}$.


How would you then find


$\|\mathbf{y}\|\_\* = \underset{\mathbf{x}}{\mathrm{max}} \left\{ \mathbf{y}^T \mathbf{x} \;\; \mathrm{s.t.} \;\; \|\mathbf{x}\| \leq 1\right\}$?


I've tried solving for the convex conjugate looking for hints, but was unable to come up with anything meaningful.


Also, if anyone has recommendations for packages that I could use (preferably matlab-based) to solve the above numerically for systems as small as $10^3$ and as large as $10^6$, I'd greatly appreciate it. CVX, of which I am admittedly a novice and a hack, will not maximize convex functions.


Edit: So using the advice in the below comments, I end up with an eigen equation for the critical point $\mathbf{x}\_\*$:


$ \displaystyle{ \sum\_{i=0}^{k} {\|\mathbf{A}\_i \mathbf{x}\_\* \|\_2 } } \cdot \mathbf{y} = \displaystyle{ \sum\_{i=0}^{k} { {\mathbf{A}\_i^T \mathbf{A\_i} } \over{ \|\mathbf{A}\_i \cdot \mathbf{x}\_\* \|\_2 } } } \mathbf{x}\_\* \mathbf{x}\_\*^{T} \cdot \mathbf{y}$


The only other idea I have had is that we know that $\|y\|\_\*$ is the function such that $ \underset{\mathbf{x}}{\sup} \{ \mathbf{y}^T \mathbf{x} - \|\mathbf{x}\|\}$ is zero whenever $\|y\|\_\* \leq 1$ and is $\infty$ otherwise. I have not been able to use this in any meaningful way however.



Dual Norm For Sum of 2-Norms
Here is an answer. This is certainly the right answer theoretically (and almost a tautology, but I do not think much more can be said in general). I am really not sure it will be helpful numerically, sorry. 


So the dual norm is given by
$$ \|y\|\_\* = \inf \{\max\_{i=1}^k \|y\_i\|\_2, y\_i \in \mathbf R^m, \sum\_i A\_i y\_i=y\}.$$


A justification is the following:
If $X$ is $\mathbf R^n$ with the norm you defined, $X$ is isometrically a subspace of $\ell^1\_k(\ell^2\_m)$ via the embedding $i:x \mapsto (A\_i x)\_{i=1}^k$. Here I adopt the classical notation $\ell^1\_k(\ell^2\_m)$ for the space of sequences $(x\_1,\dots,x\_k)$ with $x\_i \in \mathbf R^m$, with the norm $\sum\_i \|x\_i\|\_2$.


Now consider the adjoint $i^\*:\ell^1\_k(\ell^2\_m)^\* \to X^\*$. There are two things to say. The first one is that $\ell^1\_k(\ell^2\_m)^\* \simeq \ell^\infty\_k(\ell^2\_m)^\*$, and that with this identification $i^\*((y\_i)\_{i=1}^k)=\sum A\_i y\_i$.


The second is that $i^\*$ is a "metric quotient map", which means that $i^\*$ has norm $1$ and that any element in $X^\*$ has an antecedent of the same norm in $\ell^1\_k(\ell^2\_m)^\*$. This fact holds if $i:X \to Y$ is any isometry between Banach spaces, and is just the Hahn-Banach theorem (any linear functional $X \to \mathbf R$ can be extended to a linear functional $Y \to \mathbf R$ with the same norm). 


