---
tags: optimization
---
# Duality and KKT Conditions

## The Lagrange Dual Function

Consider an optimization problem in the standard form:
$$
\begin{aligned}
& \underset{x}{\text{minimize}}
& & f_0(x) \\
& \text{subject to}
& & f_i(x) \leq 0, \; i = 1, \ldots, m \\
& & & h_i(x) = 0, \; i = 1, \ldots, p,
\end{aligned} \tag{1} \label{prob}
$$
with variable $x \in \mathbb R^n$. Assume its domain $\mathcal D = \bigcap_{i=0}^m \operatorname{dom} f_i \cap \bigcap_{i=1}^p \operatorname{dom} h_i$ is nonempty, and denote the optimal value of ($\ref{prob}$) by $p^*$. (We do not assume the problem is convex.)

The basic idea in Lagrangian duality is to take the constraints in ($\ref{prob}$) into account by **augmenting the objective function with a weighted sum of the constraint functions**.

> **Def**
>
> We define the ***Lagrangian*** $L: \mathbb R^n \times \mathbb R^m \times \mathbb R^p \rightarrow \mathbb R$ associated with problem ($\ref{prob}$) as
> $$
> L(x, \lambda, \nu) = f_0 (x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{i=1}^p \nu_i h_i(x),
> $$
> with $\operatorname{dom} L = \mathcal D \times \mathbb R^m \times \mathbb R^p$. We refer to $\lambda_i$ as the ***Lagrange multiplier*** associated with the $i$th inequality constrain $f_i(x) \le 0$; similarly we refer to $\nu_i$ as the Lagrange multiplier associated with the $i$th equality constraint $h_i(x) = 0$. The vectors $\lambda$ and $\nu$ are called the ***dual variables*** or ***Lagrange multiplier vectors*** associated with the problem.

> **Def**
>
> We define the ***Lagrange dual function*** (or just ***dual function***) $g: \mathbb R^m \times \mathbb R^p \rightarrow \mathbb R$ as the minimum value of the Lagrangian over $x$: for $\lambda \in \mathbb R^m, \nu \in \mathbb R^p$,
> $$
> g(\lambda, \nu) = \inf_{x \in \mathcal D} L(x, \lambda, \nu)
> = \inf_{x\in \mathcal D} \left( f_0 (x) + \sum_{i=1=}^m \lambda_i f_i(x) + \sum_{i=1}^p \nu_i h_i(x), \right)
> $$
> (You can conceptually regard $\inf$ as $\min$ if you are not familiar with it.)

Since the dual function is the pointwise infimum of a family of [affine function](https://hackmd.io/oONZgO_USseT-uTCxlJtCQ#Affine-Functions) of $(\lambda, \nu)$, **it is concave** (see [this](https://hackmd.io/oONZgO_USseT-uTCxlJtCQ#Pointwise-Maximum-and-Supremum) for proof), **even when the problem is not convex**.

> **Proposition**
>
> The dual function yields lower bounds on the optimal value $p^*$ of the problem ($\ref{prob}$); that is, for any $\lambda \succeq 0$ and any $\nu$ we have
> $$
> \begin{align}
> g(\lambda, \nu) \le p^* \tag{2} \label{lowerbdd}
> \end{align}
> $$
> *proof*
>
> Suppose $\tilde x$ is a feasible point for the problem ($\ref{prob}$), so we have
> $$
> f_i(\tilde x) \le 0
> $$
> and
> $$
> g_i(\tilde x) = 0
> $$
> Thus, we have
> $$
> g(\lambda, \nu) \le L(\tilde x, \lambda, \nu) = f_0 (\tilde x) + \underbrace{\sum_{i=1=}^m \lambda_i f_i(\tilde x)}_{\le 0} + \underbrace{\sum_{i=1}^p \nu_i h_i(\tilde x)}_{=0} \le f_0 (\tilde x)
> $$
> When $\tilde x$ is a minimizer of the original problem, the desired inequality is obtained.

### Linear Approximaiton Intepretation

The orginal problem ($\ref{prob}$) can be rewrite as an unconstrained problem,
$$
\begin{align}
\text{minimize} && f_0(x) + \sum_{i=1}^m I_- (f_i(x)) + \sum_{i=1}^p I_0(h_i(x)),
\end{align}
$$
where $I_-: \mathbb R \rightarrow \mathbb R$ is the indicator function for the nonpositive reals,
$$
I_- = \begin{cases}
0, & u \le 0 \\
\infty, & u > 0
\end{cases}
$$
and similar, $I_0$ is the indicator function of $\{0\}$. Lagrangian can be intepretated as a "approximation" of the objective function above. Consier the following problem:
$$
\begin{align}
& \text{minimize} && L(x, \lambda, \nu) = f_0 (x) + \sum_{i=1=}^m \lambda_i f_i(x) + \sum_{i=1}^p \nu_i h_i(x), \\
& \text{subject to} && \lambda \succeq 0
\end{align}
$$
If $f_i(x) \ge 0$, which violates the constrain of the original problem, then a penalty $\lambda_i f_i(x)$ would be applied on the objective function. This penalty can be regarded as a lower approximation of $I_-(f_i(x))$. Since $\lambda_i u \le I_-(u)$ and $\nu_i u \le I_0(u)$ for all $u$, we see that the dual function yeilds a lower bound on the optimal value of the original problem, as the previous proposition implies.

## The Lagrange Dual Problem

For each pair $(\lambda, \nu)$, the Lagrange dual function gives us a lower bound on the optimal value $p^*$ of the optimiation problem ($\ref{prob}$). a natural question is: What is the *best* lower bound that can be obtaned from the Lagrange dual function?

This leads to the optimization problem:
$$
\begin{aligned}
& \text{maximize} & g(\lambda, \nu) \\
& \text{subject to} & \lambda \succeq 0
\end{aligned}
\tag{3} \label{dual_prob}
$$
This problem is callede the ***Lagrange dual problem*** associated with the problem associated with the problem ($\ref{prob}$). In this context the original problem ($\ref{prob}$) is sometimes called the ***primal problem***. If a pair $(\lambda, \nu)$ is feasible for the dual problem ($\ref{dual_prob}$), then it's ***dual feasible***. We refer to $(\lambda^*, \nu^*)$ as ***dual optimal*** or ***optimal Lagrange multipliers*** if they are optimal for the problem ($\ref{dual_prob}$).

The Lagrange dual problem ($\ref{dual_prob}$) **is a convex optimization problem**, since the objetive to be maxmized is concave and the constraint is convex. This is the case whether or not the primal problem is convex.

### Weak Duality

> **Theorem**
>
> Let $d^*$ denotes the optimal value of the Lagrange dual problem. Then we have the following inequality:
> $$
> d^* \le p^*.
> $$
> This property is called ***weak duality***.
>
> *proof*
>
> This is a straightforward result from ($\ref{lowerbdd}$).
>
> **Remark**
>
> We refer to the difference $p^* - d^*$ as the ***optimal duality gap*** of the original problem, since it gives the gap between the optimal value of the primal problem and the best lower bound on it that can be obtained from the Lagrange dual function.

Weak duality can sometimes be used to find a lower bound on the optimal value of a problem taht is diffuicult to solve, since the dual problem is always convex and in many cases can be solved efficiently, to find $d^*$.

### Strong Duality and Slater's Constraint Qualification

> **Def**
>
> If the equality
> $$
> d^* = p^*
> $$
> holds, i.e., the optimal duality gap is zero, then we say that ***strong duality*** holds. This means that the best bound that can be obtained from the Lagrange dual function **is tight**.

Strong duality does not, in general, hold. but if the primal problem is convex, i.e., of the form
$$
\begin{aligned}
& \text{minimize} && f_0(x) \\
& \text{subject to} && f_i(x) \le 0, & i = 1,\ldots, m, \\
&&& Ax = b
\end{aligned}
\tag{4} \label{convexprob}
$$
with $f_0,\ldots,f_m$ convex, we **usually** (but not always) have strong duality. There are many results that establish conditions on the problem, beyond convexity, under which strong duality holds. These conditions are called ***constraint qualifications***.

One simple constaint qualification is ***Slater's condition***, described as follows:

> **Theorem**
>
> For the convex primal problem of the form of ($\ref{convexprob}$), if there exists an $x \in \operatorname{relent}\mathcal D$ such that
> $$
> \begin{align}
> f_i(x) < 0, && i = 1,\ldots, m, && Ax = b,
> \end{align}
> $$
> then **strong duality holds**. (Such a point $x$ is called ***strictly feasible***.)

## Optimality Conditions

### Complementary Slackness

Suppose that the primal and dual optimal values are attained and equal (strong duality holds). Let $x^*$ be a primal optimal and $(\lambda^*, \nu^*)$ be a dual optimal point. This means that
$$
\begin{align*}
f_0(x^*)
&= g(\lambda^*, \nu^*) \\
&= \inf_x \left( f_0(x) + \sum_{i=1}^m \lambda_i^* f_i(x) + \sum_{i=1}^p \nu_i^* h_i(x)\right) \\
&\le f_0(x^*) + \sum_{i=1}^m \lambda_i^* f_i(x^*) + \sum_{i=1}^p \nu_i^* h_i(x^*) \\
&\le f_0(x^*)
\end{align*}
$$
The last inequality follows from $\lambda_i^* \ge 0, f_i(x^*) \le 0, i = 1, \ldots, m$, and $h_i(x^*) = 0, i = 1, \ldots, p$. thus, we conclude that the two inequalities in this chain hold with equality.

Some interesting conclusions from the equality:

1. $x^*$ minimize $L(x, \lambda^*, \nu^*)$ over $x$. (The Lagrangian $L(x, \lambda^*, \nu^*)$ can have other minimizers; $x^*$ is simply a minimizer.)

2. Since $h_i(x^*) = 0$ and so does $\sum_{i=1}^p v_i^* h_i(x^*)$, we have
$$
\sum_{i=1}^m \lambda_i^* f_i (x^*) = 0
$$
Since each term in this sum is nonpositive, we conclude that
$$
\begin{align}
\lambda_i^* f_i(x^*) = 0, && i = 1,\ldots, m.
\end{align}
$$
This condition is knwon as ***complementary slackness***; it holds for any primal optimal $x^*$ and any dual optimal $(\lambda^*, \nu^*)$ (when strong duality holds). We can express the complementary slackness condition as
$$
\lambda_i^* > 0 \Longrightarrow f_i(x^*) = 0
$$
or, equivalently,
$$
f_i(x^*) < 0 \Longrightarrow \lambda_i^* = 0
$$

### KKT Optimality Conditions

Now, we assume that the functions $f_0, \ldots, f_m, h_1,\ldots, h_p$ in ($\ref{prob}$) are differentiable (and therefore have open domains), ut we make no assumptions yet about convexityl.

#### KKT conditions for nonconvex problems

Let $x^*$ and $(\lambda^*, \nu^*)$ be any primal and dual optimal point.s with zero duality gap (strong duality holds). Since $x^*$ minimizes $L(x, \lambda^*, \nu^*)$ over $x$, it follows that its gradient must vansih at $x^*$, i.e.,
$$
\nabla f_0(x^*) + \sum_{i=1}^m \lambda_i^* \nabla f_i(x^*) + \sum_{i=1}^p \nu_i^* \nabla h_i(x^*) = 0.
$$
Thus we have
$$
\begin{aligned}
f_{i}\left(x^{\star}\right) & \leq 0, \quad i=1, \ldots, m \\
h_{i}\left(x^{*}\right) &=0, \quad i=1, \ldots, p \\
\lambda_{i}^{\star} & \succeq 0, \quad i=1, \ldots, m \\
\lambda_{i}^{\star} f_{i}\left(x^{\star}\right) &=0, \quad i=1, \ldots, m \\
\nabla f_{0}\left(x^{\star}\right)+\sum_{i=1}^{m} \lambda_{i}^{\star} \nabla f_{i}\left(x^{*}\right)+\sum_{i=1}^{p} \nu_{i}^{\star} \nabla h_{i}\left(x^{\star}\right) &=0,
\end{aligned}
$$
which are called the ***Karush-Kuhn-Tucker*** (KKT) conditions.

To summerize, for **any** optimization problem with differentiable objective and constraint functions for which strong duality obtains, any pair of primal and dual optimal poitns must satisfy the KKT conditions.

#### KKT conditions for convex problems

When the primal problem is convex, the KKT conditions are also **sufficient for the points to be primal and dual optimal**.

> **Theorem**
>
> Assume that the primal problem ($\ref{prob}$) is convex. If $f_i$ are convex and $h_i$ are affine, and $\tilde x, \tilde \lambda, \tilde \nu$ are any points that satisfy the KKT conditions
> $$
> \begin{aligned}
> f_{i}\left(\tilde x\right) & \leq 0, \quad i=1, \ldots, m \\
> h_{i}\left(\tilde x\right) &=0, \quad i=1, \ldots, p \\
> \tilde \lambda & \succeq 0, \quad i=1, \ldots, m \\
> \tilde \lambda f_{i}\left(\tilde x\right) &=0, \quad i=1, \ldots, m \\
> \nabla f_{0}\left(\tilde x\right)+\sum_{i=1}^{m} \tilde\lambda_{i} \nabla f_{i}\left(\tilde x\right)+\sum_{i=1}^{p} \tilde \nu_{i} \nabla h_{i}\left(\tilde x\right) &=0,
> \end{aligned}
> $$
> then $\tilde x$ and $(\tilde \lambda, \tilde \nu)$ are primal and dual optimal, with zero duality gap.
>
> *proof*
>
> The first two conditions state that $\tilde x$ is primal feasible.
>
> Since $f_i$ and $h_i$ are convex, $L(x, \tilde \lambda, \tilde \nu)$ is conevex in $\tilde x$; the last line states that its gradient with respect to $x$ vanishes at $x = \tilde x$, so it follows that $\tilde x$ minimizes $L(x, \tilde \lambda, \tilde \nu)$ over $x$. From this we conclude that
> $$
> \begin{align}
> g(\tilde \lambda, \tilde \nu)
> &= L(\tilde x, \tilde \lambda, \tilde \nu) \\
> &= f_0(\tilde x) + \sum_{i=1}^m \tilde \lambda_i f_i(\tilde x) + \sum_{i=1}^p \tilde v_i h_i(\tilde x)
> \end{align}
> $$
> Since we have $h_i(\tilde x) =0$ and $\tilde \lambda f_i(\tilde x) = 0$, we finally obtain
> $$
> g(\tilde \lambda, \tilde \nu) = f_0(\tilde x)
> $$
> This show`s that $\tilde x$ and $(\tilde \lambda, \tilde \nu)$ have zero duality gap, and therefore are primal and dual optimal.

Bsaed on the proof above, we can conclude that if a convex optimization problem with differntiable objective and constraint functions satisfies Slater's condition, then the KKT conditions **provide necessary and sufficient conditions for optimality**.