2
$\begingroup$

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?

$\endgroup$
6
  • 1
    $\begingroup$ 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 $\endgroup$ Apr 30 at 11:45
  • 1
    $\begingroup$ I think both answers are equivalent, as maximizing $-y$ with $y\ge 0$ is equivalent to maximizing $y \le 0$. $\endgroup$
    – Kuifje
    Apr 30 at 11:47
  • $\begingroup$ @PrameshKumar I see, I was just thinking it would be easier to convert a canonical form problem. $\endgroup$
    – bm1125
    Apr 30 at 11:50
  • 3
    $\begingroup$ In your dual problem, I think the right hand term of the second constraint should be $-b$ though. $\endgroup$
    – Kuifje
    Apr 30 at 12:03
  • 2
    $\begingroup$ 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. $\endgroup$
    – RobPratt
    Apr 30 at 12:36
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.