Convex Optimization
Consider the general constrained optimization problem (P) shown below, where we have not assumed anything regarding the functions $f$, $h$, $l$ (like convexity).
\[\begin{array}{ll} &\text{(P)}\\ \min\limits_{x} &f(x) \\ \text{subject to} & h_i(x) \leq 0, \quad i = 1, \ldots, m \\ & l_j(x) = 0, \quad j = 1, \ldots, r \end{array}\]Langrangian
Define the Lagrangian
\[L(x, u, v) = f(x) + \sum_{i=1}^{m} u_i h_i(x) + \sum_{j=1}^{r} v_j l_j(x).\]where $u\in\RR^m$, $v\in\RR^r$, and $u\geq 0$.
Then we have
\[L(x, u, v)\leq f(x),\]i.e. the Lagrangian $L(x, u, v)$ is always a lower bound for the primal criterion $f(x)$ for any dual feasible $u,v$.
And so, we have that if $f^*$ is the primal optimal value and $C$ is the primal feasible set, then
\[f^*\geq \min_{x\in C} L(x,u,v)\geq \min_x L(x,u,v):=g(u,v),\]where the function
\[g(u, v) = \min_{x} L(x, u, v)\]is called the Lagrange dual function, and it provides a lower bound on the optimal value $f^*$ for any dual feasible $u,v$.
Dual Problem
We define $G$ as the dual of $P$ by maximizing $g(u,v)$ over all dual feasible $u, v$.
\[\begin{array}{ll} &\text{(G)} \\ \max\limits_{u,v} &g(u,v) \\ \text{subject to} & u \geq 0 \end{array}\]A very interesting property is that the dual problem is a convex optimization problem (even if the primal problem is non-convex) problem in $u, v$, as $g(u, v)$ can be expressed as the negative of pointwise maximum of convex functions in $(u, v)$.
Weak Duality
If the dual optimal value is $g^*$, then
\[f^*\geq g^*.\]This always holds (even if the primal problem is nonconvex) and is called the weak duality property.
Slater’s Condition
In some problems, we have $f^* = g^*$, known as strong duality. For example, if Slater’s condition holds, then we have strong duality.
Slater’s condition:
- The primal is a convex problem, i.e. $f$ is convex, $h_i$ is convex, and $l_j$ is affine.
- There exists at least one strictly feasible $x\in\RR^n$, i.e. $h_i(x)<0$ for every $i$.
- An extension maintains that strict inequalities only need to hold over $h_i (x)$ that are not affine.
Duality Gap
The duality gap for $x,u,v$ is $f (x) − g (u, v)$. It satisfies
\[0\leq f(x)-f^*\leq f(x)-g(u,v).\]This implies that a zero duality gap indicates an optimal value for both the primal and the dual.
KKT Conditions
We first state the KKT conditions associated with problem $P$, they are:
- Stationarity Condition: for the given dual variable pair $u, v$, the point $x$ minimizes the lagrangian $L(x, u, v)$
- Complementary Slackness
- Primal feasibility
- Dual Feasibility
KKT conditions on $x, u, v$ are in a very broad sense equivalent to having an optimal primal solution $x$ and optimal dual solution $u, v$ at the same time.
Necessity
First we show that if $x^* , u^* , v^* $ are the primal and dual solutions respectively with zero duality gap, then they satisfy the KKT conditions.
\[\begin{align*} f(x^*)&=g(u^*,v^*)\\ &=\min_x f(x)+\sum_{i=1}^{m} u_i^* h_i(x) + \sum_{j=1}^{r} v_j^* l_j(x)\\ &\leq f(x^*)+\sum_{i=1}^{m} u_i^* h_i(x^*) + \sum_{j=1}^{r} v_j^* l_j(x^*)\\ &\leq f(x^*) \end{align*}\]which means that all inequalities can be replaced by equalities, yielding the KKT conditions.
Sufficiency
Next we show that if there exists $x^* , u^* , v^* $ that satisfy KKT conditions, then $x^* , u^* , v^* $ are primal and dual optimal.
\[\begin{align*} g(u^*,v^*)&=f(x^*)+\sum_{i=1}^{m} u_i^* h_i(x^*) + \sum_{j=1}^{r} v_j^* l_j(x^*)\\ &=f(x^*) \end{align*}\]which indicates zero duality gap.