14. Duality

Introduction

• A baker with two types of cakes: simple and fancy

• Both types require some basic ingredients; the fancy type requires fancier ingredients and more labor but generates more profit.

• Popular bakery: No upper limit on the quantity that can be sold

• Baker’s problem: How many simple and fancy cakes to produce?

$$\max 24x_1 + 14x_2$$

$\text{subject to}$

$$3x_1 + 2x_2 \le 120 \\ 4x_1 + x_2 \le 100 \\ 2x_1 + x_2 \le 70 \\ x_1, x_2\ge 0$$

Optimum : $x_1^* = 16, x_2^* = 36$

→ Total revenue : 888

Suppose I would like to take over the baker’s business. How much should I pay to get this deal? Consider unit price I pay for the baker’s asset as the variables

$$\min 120y_1 + 100 y_2 + 70y_3$$

$\text{subject to}$

$$3y_1 + 4y_2 + 2y_3 \ge 24\\2y_1 + y_2 + y_3 \ge 14 \\ y_1, y_2, y_3 \ge 0$$

Dual linear program

The dual of a given linear program (LP) is another LP that is derived from the original (the primal) LP in the following schematic way:

https://en.wikipedia.org/wiki/Dual_linear_program

Duality (optimization)

In mathematical optimization theory, duality or the duality principle is the principle that optimization problems may be viewed from either of two perspectives, the primal problem or the dual problem. If the primal is a minimization problem then the dual is a maximization problem (and vice versa). Any feasible solution to the primal (minimization) problem is at least as large as any feasible solution to the dual (maximization) problem. Therefore, the solution to the primal is an upper bound to the solution of the dual, and the solution of the dual is a lower bound to the solution of the primal.[1] This fact is called weak duality.

https://en.wikipedia.org/wiki/Duality_(optimization)

Dual LP

For any LP, there is a dual LP

• min $\leftrightarrow$ max

• objective function $\leftrightarrow$ Right-hand side

• Transposed constraint matrix

• variable sign depends on the type of inequality

The original LP is called the primal

1. Primal

$$\min c^Tx$$

$\text{subject to}$

$$Ax \ge b \\ x \ge 0$$

2. Dual

$$\max b^Ty$$

$\text{subject to}$

$$A^Ty \le c \\ y \ge 0$$

Derivation

We already see that primal problem and dual problem related to the order of the optimization.

We can express the primal problem by using Lagrangian as follows

$$\min_{x\ge0}\max_{\lambda\ge 0} c^Tx - \lambda^T(Ax - b)$$

If we swap the order of optimization i.e.

$$\max_{\lambda\ge 0}\min_{x\ge0} c^Tx - \lambda^T(Ax - b)$$

we call it dual problem.

Note that

$$\max_{\lambda\ge 0}\min_{x\ge0} c^Tx - \lambda^T(Ax - b)\\ = \max_{\lambda\ge 0}\min_{x\ge0} \sum_ic_ix_i - \lambda_i(A_ix_i - b_i) \\ =\max_{\lambda\ge0}\min_{x\ge0}\sum_i(c_i - \lambda_iA_i)x_i + \lambda_ib_i$$

where $A_i$ is $i$’th row of $A$.

Since $x_i \ge 0,\forall i$, it satisfy the condition as a constraint

💡

We can simply understand this concept as a constant in penalty function.

Therefore, above equation can be expressed

$$\max b^T\lambda$$

$\text{subject to}$

$$c_i \ge \lambda_iA_i, \forall i \\ \lambda \ge 0$$

💡

$\lambda \ge 0$ is related to the dual feasibility or a constant in penalty function.

or we can expressed as follows

$$\max b^T\lambda$$

$\text{subject to}$

$$A^T\lambda \le c \\ \lambda\ge 0$$

Duality Table

Weak Duality

Assuming minimization in primal LP

• Any feasible solution of the primal gives an upper bound for the dual

• Any feasible solution of the dual gives a lower bound for the primal

Proof

Suppose take $x$ such that

$$Ax \ge b, x\ge 0$$

and take $y$ such that

$$A^Ty \le c, y\ge 0$$

This is equivalent to

$$y^TA \le c^T, y\ge 0$$

Now, we compare the value of each objective funcitons.

$$c^Tx \ge y^TAx \ge y^Tb = b^Ty$$

Since $x$ and $y$ are arbitrary, this holds.

Suppose the primal has unbounded optimum, can we say something about the dual?

→ Dual have no feasible area

💡

즉 한쪽이 unbounded이면 다른쪽의 solution이 unfeasible하다.

Example of using Weak Duality

$$\min 120y_1 + 100 y_2 + 70y_3$$

$\text{subject to}$

$$3y_1 + 4y_2 + 2y_3 \ge 24\\2y_1 + y_2 + y_3 \ge 14 \\ y_1, y_2, y_3 \ge 0$$

Consider a solution in $y$ such that

$$y_1 = y_3 = 0, y_2 = 14$$

The value of its objective function is 1400. That means the maximum in the primal is at most 1400.

Strong Duality

If one of the two problems has an optimal solution, so does the other one and that the bounds given by the weak duality theorem are tight, i.e.

$$\min_x c^Tx = \max_y b^Ty$$

Complementary Slackness and LP Optimality

Theorem (Complementary Slackness)

Consider a pair of primal and dual programs with the primal problem in standard form. If $x^*$ is optimal for the primal and $y^*$ is optimal for the dual, then

$$[x^*]^T(c - A^Ty^*) = 0$$

If $x$ is feasible for the primal, $y$ is feasible for the dual, and $x^T(c - A^Ty) = 0$, then $x$ and $y$ are optimal for their respective problems.

Proof

Note that

$$c^Tx \ge y^TAx$$

for all $x, y\in S$, since $x\ge0$ and $c^T \ge y^TA$

Similarly,

$$y^TAx \ge y^Tb$$

for all $x, y \in S$, since $y\ge 0$ and $Ax \ge b$

Let $x^*$ and $y^*$ are optimal for primal and dual respectively. Then

$$c^Tx^* \ge [y^*]^TAx^* \ge [y^*]^Tb$$

By strong duality,

$$c^Tx^* = [y^*]^TAx^* = [y^*]^Tb$$

Therefore,

$$[x^*]^T(c - A^Ty^*) = 0$$

Since $x^T(c-A^Ty) = 0$, it satisfy the KKT condition for dual problem. Therefore, $y$ is a optimal for dual problem. Moreover, by strong duality, we can sure that $x$ and $y$ are optimal for their respective problems.

💡

Notice that this condition is related to the complementary slackness condition in KKT condition. We will prove this relation exactly at the next section.

Optimality and the Lagrangian Function

We can view this problem as

$$\min c^Tx$$

$\text{subject to}$

$$Ax \ge b \quad (\lambda) \\ Ix \ge 0 \quad (\pi)$$

Define

$$\mathcal L(x, \lambda, \pi) = c^Tx - \lambda^T(Ax-b) - \pi^T(Ix)$$

Check KKT conditions

1. Stationary condition

   $$\nabla_x \mathcal L(x, \lambda, \pi) = c - A^T\lambda - \pi = 0$$

2. Dual feasibility

   $$\lambda \ge0 \\ \pi \ge 0$$

3. Primal feasibility

   $$Ax\ge b \\ Ix\ge 0$$

4. Complementary slackness

   $$\lambda^T(Ax - b) = 0 \\ \pi^T(Ix) = 0$$

By stationary condition,

$$\pi = c - A^T\lambda$$

Since $\pi x = 0$,

$$\pi x = 0 = cx - A^T\lambda x \\ \Rightarrow (c-A^T\lambda)x = 0$$

It is related to the complementary slackness

💡

Basically related to the optimal condition

Moreover, since $\pi \ge 0$,

$$c- A^T\lambda \ge 0 \\ \Rightarrow A^T\lambda \le c$$

It is related to constraints in dual problem