3 - duality & robust optimization

Duality

All the aforementioned is true for duality in linear programming as well:

We recall the standard form of an LP in both:

Standard Form

Primal Form

Dual Form

> Dual Form

Summary

Dual Variable =

Notations

Primal & Dual Form

It is worth noting that we derived the dual from a primal LP in standard form (which we can always obtain and then derive the dual),

but there is a “highway to the dual” even for a primal LP in non-standard form:

Geometric Look at Duality 1

Geometric Look at Duality 2

Economic Look at Duality

We can think of the primal LP as representing a problem where

We can think of the primal LP as representing a problem where a manufacturer wants to maximize profit by producing n products using m limited resources.

In the dual, we take the perspective of someone who wants

Different Forms of Duality

Weak Duality

Different Forms of Duality

Strong Duality

Complementary Slackness

We have seen that the close relationship between the primal and the dual LP allows us to

We have seen that the close relationship between the primal and the dual LP allows us to gain insights for one from the other.

This is often exploited in practical applications, e. g., to make problems easier tractable / solvable.

Robust Linear Optimization Video

Robust Linear Optimization

Polyhedral Uncertainty Set

Polyhedral Uncertainty Set

Duality

Robust Linear Optimization

With U_i filled in

Common Forms of Polyhedral Uncertainty Sets

Uncertainty in the Objective Function