I have a question related to the dual problem of a maximization primal problem with norm inequalities constraints.
I want to find the dual problem for the following primal optimization problem:
$\text {max} -b^Tv $
$\text{subject to }\Vert A^Tv\Vert_\infty\le 1$
Thanks.
Answer: $\underset{x}{\text{min }}\|x\|_1\text{ subject to }Ax = b$.
Indeed, your primal problem can be conveniently rewritten as
\begin{eqnarray}\underset{v}{\text{max }}-g^*(-A^Tv)-f^*(v)\end{eqnarray}
where the "*" superscript denotes convex conjugation, and we have introduced the functions $g(x) := \begin{cases}0, &\mbox{ if }\|x\|_\infty \le 1,\\+\infty, &\mbox{ otherwise.}\end{cases}$,
$f(v) := \begin{cases}0, &\mbox{ if }v = b,\\+\infty &\mbox{ otherwise.}\end{cases}$
Thus, by Fenchel-Rockerfellar duality, the dual of your problem is simply \begin{eqnarray}\underset{x}{\text{min }}g(x) + f(Ax),\end{eqnarray} i.e \begin{eqnarray}\underset{x}{\text{min }}\|x\|_1\text{ subject to }Ax = b\end{eqnarray}.