0

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.

Ahmed Zeki
  • 67
  • 1
    Why don't you turn it into a LP and then compute the dual? – user251257 Jul 30 '15 at 01:34
  • The conditions are equivalent to $A^T v \le 1$ and $-A^T v \ge 1$. Depending on what you have defined as your standard form, you can use this to transform the problem into standard form in some way and then apply your dual theorem. Where are you stuck? – AlexR Jul 30 '15 at 02:10
  • I first defined the Lagrangian function, and take the minimum with respect to $v$. The problem is that when solving the dual problem, the optimum value is not equal to the primal optimum value (this should happen because of the strong duality). – Ahmed Zeki Jul 30 '15 at 02:27
  • OK. Converting the problem to LP solves the problem. Thanks for your advice – Ahmed Zeki Jul 30 '15 at 02:51

1 Answers1

1

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

dohmatob
  • 9,535