Minimization Problem: Deriving Dual Problem

Question

Consider the following minimization problem $\min\{H(x,z) \equiv h_1(x) + h_2(z): Ax + Bz = c\}$, where $A \in \Bbb{R}^{m \times n}, B \in \Bbb{R}^{m \times p}$ and $c \in \Bbb{R}^{m}$ and $h_1, h_2$ are proper, closed and convex.

To find the dual problem of the optimization problem, one can construct a Lagrangian:

$L(x,z;y) = h_1(x)+h_2(z) + \langle y, Ax + Bz - c \rangle$

The objective function is therefore given by

$q(y) = \min_{x, z} \{h_1(x) + h_2(z) + \langle y, Ax+Bz-c \rangle\}$

Apparently, the last line is the same $\max_{y}h_1^{*}(-A^{T}y)-h_2^{*}(-B^{T}y) - \langle c,y \rangle$

I guess that his is an application of some duality principle but I don't see how it exactly works.

Answer 1

Our problem is equivalent (with some domain qualification conditions) to

$$\min_{x,z}\max_{y} L(x,z,y) =\max_y \Big\{\min_{x} \{ h_1(x) + \langle y, Ax\rangle \} + \min_z \{h_2(z) + \langle y, Bz\rangle\} -\langle y, c\rangle\Big\}$$

Now use the definition of the convex conjugate to get

$$\min_{x,z}\max_y L(x,z,y) = \max_y \{-h_1^*(-A^* y) -h_2^*(-B^*y) - \langle y,c\rangle\}$$

Answer 2

We can simplify the expression for $q$ without invoking a duality principle. Notice that \begin{align} q(y) &= -\langle c,y\rangle + \left(\min_x h_1(x) - \langle y, Ax \rangle \right) + \left(\min_z h_2(z) - \langle y, Bz\rangle \right) \\ &= -\langle c,y\rangle - \left(\max_x \langle -A^T y, x \rangle - h_1(x) \right) - \left( \max_z \langle -B^T y, z \rangle - h_2(z) \right) \\ &= -\langle c,y\rangle - h_1^*(-A^T y) - h_2^*(-B^T y). \end{align}

By the way, as a matter of notational style, I prefer to use $x$ and $y$ for primal variables and $z$ for a dual variable.