Finding the dual problem of a minimum problem

Question

How to convert the following primal problem into its dual problem:

\begin{align} \min_{x,z}&\quad a^\top x + b^\top z\\\text{s.t.}&\quad Ax-d \le Cz \\&\quad x\ge 0, z \le 0. \end{align}

I first attempted to convert it to canonical where the decision variables are all positive and the constraint is a less than constraint

\begin{align} \min_{x,z}&\quad a^\top x - b^\top z\\\text{s.t.}&\quad -Ax-Cz\ge-d \\&\quad x,z\ge0 \end{align}

for which the dual problem should be

\begin{align} \max&\quad-d^\top y\\\text{s.t.}&\quad(-A)^\top y\le a\\&\quad(-C)^\top y\le b\\&\quad y\ge0. \end{align}

The correct answer is:

\begin{align} \max&\quad d^\top y\\\text{s.t.}&\quad A^\top y\le a\\&\quad-C^\top y\ge b\\&\quad y\le0. \end{align}

I guess my problem is when trying to write the original problem in canonical form?

Answer 1

Primal Problem

$$\begin{align} \text{minimize} \quad & \sum_{i=1}^n a_i x_i + \sum_{i=1}^n b_i z_i \\\ \text{subject to} \quad & A\mathbf x-\mathbf d \le C\mathbf z \\ & x_i \ge 0 \quad \forall i=1,\ldots,n \\ & z_i \le 0 \quad \forall i=1,\ldots,n \end{align}$$

The dual formulation of the primal problem can be obtained by writing the Lagrangian function $L$ of the primal problem and connecting heuristically such a function to the minimax theorem $$\max_\mathbf y \min_{\mathbf x,\mathbf z} L(\mathbf x,\mathbf z,\mathbf y) = \min_{\mathbf x,\mathbf z} \max_\mathbf y L(\mathbf x,\mathbf z,\mathbf y)$$ proven by John von Neumann.

The Lagrangian function to be considered is:

$$L(\mathbf x,\mathbf z,\mathbf y) = \langle\mathbf a, \mathbf x\rangle + \langle \mathbf b, \mathbf z\rangle + \langle\mathbf y, A\mathbf x-\mathbf d - C\mathbf z\rangle$$

where the notation $\langle\cdot,\cdot\rangle$ indicates the scalar product between two vectors and $ \mathbf y = (y_1, y_2, \ldots, y_m)$ are Lagrange multipliers.

Recall the identity $\langle \mathbf v, A\mathbf w\rangle = \langle A^\top\mathbf v, \mathbf w\rangle$. Taking advantage of the linearity of the dot product, and putting in the evidence variable $\mathbf x$ and the variable $\mathbf z$, we get

\begin{align}L(\mathbf x,\mathbf z,\mathbf y) &= \langle\mathbf a,\mathbf x \rangle + \langle\mathbf b,\mathbf z\rangle +\langle\mathbf y,A\mathbf x\rangle - \langle\mathbf y, \mathbf d\rangle - \langle\mathbf y, C\mathbf z\rangle\\&=\langle\mathbf a,\mathbf x \rangle + \langle\mathbf b,\mathbf z\rangle - \langle\mathbf y, \mathbf d\rangle + \langle A^\top\mathbf y,\mathbf x\rangle - \langle C^\top\mathbf y,\mathbf z\rangle\\&=-\langle\mathbf y, \mathbf d\rangle + \langle A^\top\mathbf y + \mathbf a,\mathbf x\rangle + \langle-C^\top\mathbf y + \mathbf b,\mathbf z\rangle.\end{align}

Minimizing $L(\mathbf x,\mathbf z,\mathbf y)$ with respect to variables $\mathbf x$ and $\mathbf z$ is equivalent considering simultaneously the minimum of $\langle A^\top\mathbf y + \mathbf a,\mathbf x\rangle$ and $\langle-C^\top\mathbf y + \mathbf b,\mathbf z\rangle$. This minimum is finite and equal to $0$ if and only if $A^\top\mathbf y + \mathbf a \ge 0$ for $\mathbf x\ge 0 $ and $\mathbf b - C^\top\mathbf y \le 0$ for $\mathbf z\le 0 $.

The dual problem associated with the Lagrangian is by definition

$$ \max_\mathbf y \min_{\mathbf x,\mathbf z} L(\mathbf x,\mathbf z,\mathbf y).$$

In order to obtain an explicit description of the dual problem we minimize $ \min\limits_{\mathbf x,\mathbf z} L(\mathbf x,\mathbf z,\mathbf y)$ with respect to $\mathbf x $ and $\mathbf z $. Fixing $\mathbf y $, we get

$$\min_{\mathbf x,\mathbf z} L(\mathbf x,\mathbf z,\mathbf y)=-\langle\mathbf y, \mathbf d\rangle + \min_{\mathbf x,\mathbf z} [\langle A^\top\mathbf y + \mathbf a,\mathbf x\rangle + \langle-C^\top\mathbf y + \mathbf b,\mathbf z\rangle]$$

and therefore

$$\min_{\mathbf x \ge 0,\mathbf z \le 0} L(\mathbf x,\mathbf z,\mathbf y) = \left\{\begin{align} \begin{matrix} -\langle\mathbf y, \mathbf d\rangle&\mbox{ if } A^\top\mathbf y + \mathbf a \ge 0 \mbox{ and } \mathbf b - C^\top\mathbf y \le 0 \\ -\infty&\mbox{otherwise} \end{matrix}\end{align} \right.$$

The dual objective function is therefore expressed as

$$\max_{\mathbf y \ge 0} L(\mathbf x,\mathbf z,\mathbf y) = \max [-\langle\mathbf y, \mathbf d\rangle].$$

Dual Problem

$$\begin{align} \text{maximize} \quad & \sum_{j=1}^m -d_j y_j \\\ \text{subject to} \quad & A^\top\mathbf y + \mathbf a \ge 0 \\ \quad & \mathbf b - C^\top\mathbf y \le 0 \\ & y_j \ge 0 \quad \forall j=1,\ldots,m \\ \end{align}$$

Let $\mathbf y'= - \mathbf y$, then we have $$\begin{align} \text{maximize} \quad & \sum_{j=1}^m d_j y'_j \\\ \text{subject to} \quad & A^\top\mathbf y' \le \mathbf a \\ \quad & -C^\top\mathbf y' \ge \mathbf b \\ & y'_j \le 0 \quad \forall j=1,\ldots,m \\ \end{align}$$