Lagrange duality

总结自 section note 5: Convex Optimization Overview, Part II

0. IntroductionPermalink

In the study of convex optimization, the mathematical optimization problems follow the form below:

where

• $x\in {\mathbb{R}}^n$ is a vector known as the optimization variable
• $f:{\mathbb{R}}^n\to \mathbb{R}$ is a convex function that we want to minimize
• $C\subseteq {\mathbb{R}}^n$ is a convex set describing the set of feasible (capable of being done or carried out) solutions

A necessary and sufficient condition for $x^{\ast }\in {\mathbb{R}}^n$ to be the globally optimal of problem $(\text{1})$ is that ${\mathrm{\nabla }}_{x}f(x^{\ast })=0$.

In the more general setting of convex optimization problem with constraints, however, this simple optimality condition does not work. One primary goal of duality theory is to characterize the optimal points of convex programs in a mathematically rigorous way.

Here we propose a form of generic differentiable convex optimization problems, as:

where

• $x\in {\mathbb{R}}^n$ is the optimization variable
• $f:{\mathbb{R}}^n\to \mathbb{R}$ and $g_i:{\mathbb{R}}^n\to \mathbb{R}$ are differentiable convex functions
• $h_i:{\mathbb{R}}^n\to \mathbb{R}$ are affine functions
  • An affine function is a function of the form $f(x)=a^{T}x+b$ for some $a\in {\mathbb{R}}^n$, $b\in \mathbb{R}$
• $g_i$ is one of the $m$ convex inequality constraints
• $h_i$ is one of the $p$ affine equality constraints

1. The LagrangianPermalink

Given a convex constrained minimization problem of the form $(\text{OPT})$, the (generalized) Lagrangian is a function $L:{\mathbb{R}}^n\times {\mathbb{R}}^m\times {\mathbb{R}}^p\to \mathbb{R}$ defined as

where

• $x\in {\mathbb{R}}^n$ is the primal variables of the Lagrangian
• $\alpha \in {\mathbb{R}}^m$ and $\beta \in {\mathbb{R}}^p$ are the dual variables of the Lagrangian, a.k.a Lagrange multipliers

Intuitively, the Lagrangian can be thought of as a modified version of the objective function to the original convex optimization problem $(\text{OPT})$ which accounts for each of the constraints. The Lagrange multipliers ${\alpha }_i$ and ${\beta }_i$ can be thought of penalties of violating the constraints. The key intuition behind the theory of Lagrange duality is the following:

For any convex optimization problem, there always exist settings of the dual variables such that the unconstrained minimum of the Lagrangian with respect to the primal variables (keeping the dual variables fixed) coincides with the solution of the original constrained minimization problem.

We formalize this intuition when we describe the KKT conditions in Section 6.

2. Primal and dual problemsPermalink

To show the relationship between the Lagrangian and the original convex optimization problem $(\text{OPT})$, we introduce the notions of the “primal” and “dual problems” associated with a Lagrangian:

The primal problemPermalink

The primal objective function ${\theta }_P:{\mathbb{R}}^n\to \mathbb{R}$ is defined as

Then the unconstrained minimization problem

is known as the primal problem.

• Generally, we say that a point $x\in {\mathbb{R}}^n$ is primal feasible if $g_i(x)\le 0$, $i=1,\cdots ,m$ and $h_i(x)=0$, $i=1,\cdots ,p$
• We typically use the vector $x^{\ast }\in {\mathbb{R}}^n$ to denote the solution of $(\text{P})$, and we let $p^{\ast }={\theta }_P(x^{\ast })$ denote the optimal value of the primal objective.

The dual problemPermalink

By switching the order of the minimization and maximization above, we obtain an entirely different optimization problem.

The dual objective function ${\theta }_D:{\mathbb{R}}^m\times {\mathbb{R}}^p\to \mathbb{R}$ is defined as

Then the constrained maximization problem

is known as the dual problem.

• Generally, we say that $(\alpha ,\beta )$ are dual feasible if ${\alpha }_i(x)\ge 0$, $i=1,\cdots ,m$
• We typically use the vector $({\alpha }^{\ast },{\beta }^{\ast })\in {\mathbb{R}}^m\times {\mathbb{R}}^p$ to denote the solution of $(\text{D})$, and we let $d^{\ast }={\theta }_D({\alpha }^{\ast },{\beta }^{\ast })$ denote the optimal value of the dual objective.

3. Interpreting the primal problemPermalink

当 $x$ is primal feasible 时，$g_i(x)\le 0$, $h_i(x)=0$，又因为 ${\alpha }_i\ge 0$，所以 ${\alpha }_i{g}_i(x)$ 最大为 0，${\beta }_i{h}_i(x)$ 恒为 0。 此时 ${\theta }_P(x)=f(x)$。

当 $x$ is not primal feasible 时，${\alpha }_i{g}_i(x)$ 和 ${\beta }_i{h}_i(x)$ 都可以任意大，取 max 直接可以得到 $\mathrm{\infty }$。此时 ${\theta }_P(x)=f(x)+\mathrm{\infty }$。

考虑到我们最原始的问题 $(\text{OPT})$ 是求 $minf(x)$，primal problem $(\text{P})$是求 $min{\theta }_P(x)$。所以我们可以认为：当 $x$ is primal feasible 时，求 $min{\theta }_P(x)$ 等价于求 $minf(x)$。

4. Interpreting the dual problemPermalink

The dual objective, ${\theta }_D(\alpha ,\beta )$, is a concave function of $\alpha$ and $\beta$. To interpret the dual problem, first we make the following observation:

Lemma 1: If $(\alpha ,\beta )$ are dual feasible, then ${\theta }_D(\alpha ,\beta )\le p^{\ast }$.

Proof:

Lemma 2 (Weak Duality): For any pair of primal and dual problems, $d^{\ast }={\theta }_D({\alpha }^{\ast },{\beta }^{\ast })\le p^{\ast }$.

This is obvious following Lemma 1.

Lemma 3 (Strong Duality): For any pair of primal and dual problems which satisfy certain technical conditions called constraint qualifications, then $d^{\ast }=p^{\ast }$.

Slater’s condition: a primal/dual problem pair satisfy Slater’s condition if there exists some feasible primal solution $x$ for which all inequality constraints are strictly satisfied (i.e., $g_i(x)<0$, $i=1,\cdots ,m$).

注意 Slater’s condition 并不能实现 Strong Duality，书上只是拿它举个例子说明啥叫 “technical conditions”。要实现 Strong Duality，还得靠下文的 KTT conditions。

注意，Strong Duality 的意义并不是简单地得到 $d^{\ast }=p^{\ast }$，而是说明了 “只要满足了 constraint qualifications，那么 primal problem 等价于 dual problem”，进一步就有：

• 求 dual problem $(\text{D})$
  • 等价于
• 求 primal problem $(\text{P})$
  • 等价于
• 求最原始的 optimization 问题 $(\text{OPT})$

5. Complementary slacknessPermalink

在我们讲 KTT conditions 之前，我们先来说一下 Complementary slackness。

Lemma 4 (Complementary Slackness): If strong duality holds, then ${\alpha }_i^{\ast }{g}_i(x^{\ast })=0$ for each $i=1,\cdots ,m$.

证明比较简单。之前 Lemma 2 有 $d^{\ast }\le p^{\ast }$，现在 strong duality holds 了有 $d^{\ast }=p^{\ast }$。所以按 Lemma 1 的证明走，所有的 $\le$ 现在都要取 $=$，必然要求 ${\alpha }_i^{\ast }{g}_i(x^{\ast })=0$。

又因为 ${\alpha }_i^{\ast }\ge 0$，所以有：

${\alpha }_i^{\ast }>0\Rightarrow g_i(x^{\ast })=0$

$g_i(x^{\ast })<0\Rightarrow {\alpha }_i^{\ast }=0$

这个 ${\alpha }_i^{\ast }{g}_i(x^{\ast })=0$ 的 constraint 我们又称为 active constraint。在 SVM 中，support vector 其实就是以 active constraint 的形式存在的。

6. The KKT (Karush-Kuhn-Tucker) conditionsPermalink

Theorem 1: Suppose that $x^{\ast }\in {\mathbb{R}}^n$, ${\alpha }^{\ast }\in {\mathbb{R}}^m$ and ${\beta }^{\ast }\in {\mathbb{R}}^p$ satisfy the following conditions:

1. (Primal feasibility) $g_i(x^{\ast })\le 0$, $i=1,\cdots ,m$ and $h_i(x^{\ast })=0$, $i=1,\cdots ,p$,
2. (Dual feasibility) ${\alpha }_i^{\ast }\ge 0$, $i=1,\cdots ,m$,
3. (Complementary slackness) ${\alpha }_i^{\ast }{g}_i(x^{\ast })=0$, $i=1,\cdots ,m$, and
4. (Lagrangian stationarity) ${\mathrm{\nabla }}_{x}L(x^{\ast },{\alpha }^{\ast },{\beta }^{\ast })=0$.

Then $x^{\ast }$ is primal optimal and $({\alpha }^{\ast },{\beta }^{\ast })$ are dual optimal. Furthermore, if strong duality holds, then any primal optimal $x^{\ast }$ and dual optimal $({\alpha }^{\ast },{\beta }^{\ast })$ must satisfy the conditions 1 through 4.

These conditions are known as the Karush-Kuhn-Tucker (KKT) conditions.