Find dual from primal optimization problem

Question

I need to find the dual to the following optimization problem:

$\text{max} \{c x: A x \leq b, C y \geq d, x+y \geq 0\}$,

where $A$ and $C$ are matrices and $c$, $b$, $x$ and $y$ are vectors.

In order to so, I want to find a matrix $A'$ and a vector $b'$ to reduce this problem to the standard form

$\text{max} \{c x: A' x \leq b'\}$.

I know how to do this for problems containing additional constraints on the vector $x$, but I do not know how to combine the constraints $C y \geq d$ and $x+y \geq 0$ into one useful constraint on $x$.

Answer 1

The trick is to combine your variables into a single vector $z = [x\ y]$, and write everything in terms of that. For example, you create the vector $c_x = [c\ 0]$ (i.e. it's just c padded out with zeros to multiply against the values of y) for your objective function, and you turn your three sets of constraints into a big single matrix multiplication where you build a block matrix out of A, C and a 1 vector with appropriate zero padding.

Answer 2

Consider the linear optimization problem

\begin{equation}\label{eq:original_problem} \text{max}\{ c x: A x \leq b, C y \geq d, x + y \geq 0 \} = \text{max}\{ c x: A x \leq b, -C y \leq -d, -x - y \leq 0 \} . \end{equation}

One may introduce the composite column vectors

\begin{align*} z &:= \begin{bmatrix} x \\ y \end{bmatrix}, \\ b' &:= \begin{bmatrix} b \\ -d \\ 0 \end{bmatrix}, \end{align*}

the composite row vector

\begin{equation*} c' := \begin{bmatrix} c & 0 \end{bmatrix}, \end{equation*}

and the composite matrix

\begin{equation*} A' := \begin{bmatrix} A & 0 \\ 0 & -C \\ -1 & -1 \end{bmatrix}. \end{equation*}

In this way, the linear optimization problem (\ref{eq:original_problem}) is written as

\begin{equation}\label{eq:matrix_form} \text{max}\{ c' z: A' z \leq b' \}. \end{equation}

Applying the strong duality theorem to (\ref{eq:matrix_form}), gives

\begin{equation}\label{eq:dual_matrix_form} \text{max}\{ c' z: A' z \leq b' \} = \text{min}\{ u b': u A'= c', u \geq 0 \}. \end{equation}

Here $u$ is the composite row vector with elements

\begin{equation*} u = \begin{bmatrix} \alpha & \beta & \gamma \end{bmatrix}, \end{equation*}

where $\alpha$, $\beta$ and $\gamma$ are row vectors.

By expanding the composite column vector $b'$, the composite row vectors $u$ and $c'$, and the composite matrix $A'$, (\ref{eq:dual_matrix_form}) is written as

\begin{equation}\label{eq:dual_algebra_form} \text{min}\{ \alpha b - \beta d: \alpha A - \gamma = c, -\beta C - \gamma = 0, \alpha \geq 0, \beta \geq 0, \gamma \geq 0 \}. \end{equation}

The objective function does not include the variable $\gamma$, and the constraint $\gamma \geq 0$ is incorporated into the other constraints in (\ref{eq:dual_algebra_form}), giving the final answer

\begin{equation}\label{eq:dual_final} \text{min}\{ \alpha b - \beta d: \alpha A \geq c, \beta C \leq 0, \alpha A - c = -\beta C, \alpha \geq 0, \beta \geq 0 \}. \end{equation}

Answer 3

Here is another approach that just computes the formal dual:

The primal problem is $\sup_{x,y} \inf_{\alpha \ge 0, \beta \ge 0, \gamma \ge 0} c x + \alpha^T (b-Ax) + \beta^T (Cy-d) + \gamma^T x + \gamma^T y$.

The formal dual is $\inf_{\alpha \ge 0, \beta \ge 0, \gamma \ge 0} \sup_{x,y} c x + \alpha^T (b-Ax) + \beta^T (Cy-d) + \gamma^T x + \gamma^T y$.

To simplify, note that we must have $c-\alpha^T A +\gamma^T = 0$ and $\beta^T C + \gamma^T = 0$, otherwise the inside term is $\infty$.

Hence we have the formal dual $\inf_{\alpha \ge 0, \beta \ge 0, c-\alpha^T A=\beta^TC, \beta^T C \ge 0} \alpha^T b - \beta^T d$.