Finding the dual problem of a minimum problem

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}

\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?

• You do not need to write the original problem into canonical form to write its dual. See page 98 web.stanford.edu/~ashishg/msande111/notes/chapter4.pdf Apr 30 at 11:45
• I think both answers are equivalent, as maximizing $-y$ with $y\ge 0$ is equivalent to maximizing $y \le 0$. Apr 30 at 11:47
• @PrameshKumar I see, I was just thinking it would be easier to convert a canonical form problem. Apr 30 at 11:50
• In your dual problem, I think the right hand term of the second constraint should be $-b$ though. Apr 30 at 12:03
• After correcting the $b$ to $-b$ in the dual, performing a change of variable $y$ to $-y$ (like you did for $z$) will yield the final form you are trying to match. Apr 30 at 12:36

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}