Duality

We firstly take a look at a single-constraint problem:

\[\begin{aligned} \mathbf{x}&=& \arg\min_{\mathbf{x}} f_0(\mathbf{x}) \\ \text{subject to:}&& f_1(\mathbf{x}) = 0 \end{aligned}\]

Lagrange Multiplier Method

If we can turn this problem into an unconstrained optimization problem, we can find the solution by solving a system of equations where the partial derivatives are equal to zero (assuming that solving such a system is feasible).

This was the motivation for the mathematician Lagrange to use the function:

\[\mathcal{L}(\mathbf{x}, \lambda) = f_0(\mathbf{x}) + \lambda f_1(\mathbf{x})\]

Note that, in this function, we have an additional variable $\lambda$, called the Lagrange multiplier. The function $\mathcal{L}(\mathbf{x}, \lambda)$ is known as the auxiliary function, or the Lagrangian. It has been proven that the optimal value of problem $(1)$ satisfies the condition $\nabla_{\mathbf{x}, \lambda} \mathcal{L}(\mathbf{x}, \lambda) = 0$ (the proof of this is omitted here).

This is equivalent to:

\[\begin{aligned} \nabla_{\mathbf{x}}f_0(\mathbf{x}) + \lambda \nabla_{\mathbf{x}} f_1(\mathbf{x}) &=& 0 \label{eq:s2} \\ f_1(\mathbf{x}) & = & 0 \label{eq:s3} \end{aligned}\]

Note that the second condition is equivalent to $\nabla_{\lambda}\mathcal{L}(\mathbf{x}, \lambda) = 0$, which is also the constraint in problem (1).

Solving the system of equations \((2) - (3)\) is, in many cases, simpler than directly finding the optimal value of problem $(1)$.

Consider the following simple examples.

Example 1: Find the maximum and minimum values of the function $f_0(x, y) = x + y$ subject to the condition $f_1(x, y) = x^2 + y^2 = 2$. Note that this is not a convex optimization problem because the feasible set $x^2 + y^2 = 2$ is not a convex set (it is just a circle).

Solution:

The Lagrangian of this problem is: \(\mathcal{L}(x, y, \lambda) = x + y + \lambda(x^2 + y^2 - 2)\) The extremum points of the Lagrange function must satisfy the condition:

\[\nabla_{x, y, \lambda} \mathcal{L}(x, y, \lambda) = 0 \Leftrightarrow \left\{ \begin{matrix} 1 + 2\lambda x &=& 0 \\ 1 + 2\lambda y &=& 0 \\ x^2 + y^2 &=& 2 \end{matrix} \right.\]

We get $x = y = \dfrac{-1}{2\lambda}$ from the above set of equations. Substituting into $x^2+y^2=2$, we have $\lambda^2 = \dfrac{1}{4} \Rightarrow \lambda = \pm \dfrac{1}{2}$. Thus, we have two pairs of solutions $(x, y) \in {(1, 1), (-1, -1)}$. By substituting these values into the objective function, we can find the minimum and maximum values of the function.

Example 2: Cross-entropy. We introduced the loss function in the form of cross-entropy. The cross-entropy function is used to measure the similarity between two probability distributions, where the smaller the value of the function, the closer the distributions are. The minimum value of the cross-entropy is achieved when the two probability distributions are identical. Let’s prove this assertion.

Consider a probability distribution $\mathbf{p} = [p_1, p_2, \dots, p_n]^T$ with $p_i \in [0, 1]$ and $\sum_{i=1}^n p_i = 1$. For an arbitrary probability distribution $\mathbf{q} = [q_1, q_2, \dots, q_n]$, assuming $q_i \neq 0, \forall i$, the cross-entropy function is defined as:

\[f_0(\mathbf{q}) = -\sum_{i=1}^n p_i \log(q_i)\]

We need to find $\mathbf{q}$ such that the cross-entropy is minimized.

In this problem, the constraint is $\sum_{i=1}^n q_i = 1$. The Lagrangian of the problem is:

\[\mathcal{L}(q_1, q_2, \dots, q_n, \lambda) = -\sum_{i=1}^n p_i \log(q_i) + \lambda\left(\sum_{i=1}^n q_i - 1\right)\]

We need to solve the following system of equations:

\[\nabla_{q_1, \dots, q_n, \lambda} \mathcal{L}(q_1, \dots, q_n, \lambda) = 0 \Leftrightarrow \left\{ \begin{matrix} -\dfrac{p_i}{q_i} + \lambda &=& 0, ~~ i = 1, \dots, n \label{eq:svm7} \\ q_1 + q_2 + \dots + q_n &=& 1 \end{matrix} \right.\]

From the above equation, we can conclude $p_i = \lambda q_i$.

Therefore: $1 = \sum_{i=1}^n p_i = \lambda\sum_{i=1}^n q_i = \lambda \Rightarrow \lambda = 1 \Rightarrow q_i = p_i, \forall i$.

This shows why the cross-entropy function is used to force two probability distributions to be close.

The Lagrange Dual Function

Lagrangian

For a general optimization problem:

\[\begin{aligned} \mathbf{x}^* &=& \arg\min_{\mathbf{x}} f_0(\mathbf{x}) \nonumber \\ \text{subject to:} && f_i(\mathbf{x}) \leq 0, \quad i = 1, 2, \dots, m \label{eq:svm9} \\ && h_j(\mathbf{x}) = 0, \quad j = 1, 2, \dots, p \nonumber \end{aligned}\]

with the domain $\mathcal{D} = \left(\cap_{i=0}^m \text{dom}f_i\right) \cap \left(\cap_{j=1}^p \text{dom}h_j\right)$. Note that we are not assuming convexity of the objective function or the constraints here. The only assumption is that $\mathcal{D} \neq \emptyset$ (non-empty set).

The Lagrangian is constructed similarly with a Lagrange multiplier for each (in)equality constraint:

\[\mathcal{L}(\mathbf{x}, \lambda, \nu) = f_0(\mathbf{x}) + \sum_{i=1}^m \lambda_i f_i(\mathbf{x}) + \sum_{j=1}^p \nu_j h_j(\mathbf{x})\]

where $\lambda = [\lambda_1, \lambda_2, \dots, \lambda_m]; \nu = [\nu_1, \nu_2, \dots, \nu_p]$ (note that $\nu$ is the Greek letter nu), are vectors called dual variables or Lagrange multiplier vectors. If the primary variable $\mathbf{x} \in \mathbb{R}^n$, the total number of variables in this function will be $n + m + p$.

(Usually, I use lowercase bold letters to represent vectors; however, I could not bold $\lambda$ and $\nu$ here due to the limitation of writing both in LaTeX and markdown. I note this to avoid confusion for the reader.)

The Lagrange Dual Function

The Lagrange dual function of the optimization problem (or simply the dual function) $\eqref{eq:svm9}$ is a function of the dual variables, defined as the infimum over $\mathbf{x}$ of the Lagrangian:

\[\begin{aligned} g(\lambda, \nu) &=& \inf_{\mathbf{x} \in \mathcal{D}} \mathcal{L}(\mathbf{x}, \lambda, \nu) \nonumber \\ &=& \inf_{\mathbf{x} \in \mathcal{D}}\left( f_0(\mathbf{x}) + \sum_{i=1}^m \lambda_i f_i(\mathbf{x}) + \sum_{j=1}^p \nu_j h_j(\mathbf{x})\right) \nonumber \end{aligned}\]

If the Lagrangian is not bounded below, the dual function at $\lambda, \nu$ will take the value $-\infty$.

Notes:

- The $\inf$ is taken over the domain $\mathbf{x} \in \mathcal{D}$, which is the domain of the problem (the intersection of the domains of all functions in the problem). This domain is different from the feasible set. Usually, the feasible set is a subset of the domain $\mathcal{D}$.

- For each $\mathbf{x}$, the Lagrangian is an affine function of $(\lambda, \nu)$, which is a concave function. Therefore, the dual function is the pointwise infimum of (potentially infinitely many) concave functions, which is a concave function. Thus, the dual function of any optimization problem is concave, regardless of whether the original problem is convex. Recall that the pointwise supremum of convex functions is a convex function, and a function is concave if negating it results in a convex function.

Lower Bound on the Optimal Value

If $p^$ is the *optimal value of problem $\eqref{eq:svm9}$, then for any dual variables $\lambda_i \geq 0, \forall i$, and $\nu$, we have:

\[\begin{aligned} g(\lambda, \nu) \leq p^* \label{eq:svm10} \end{aligned}\]

This property can be easily proven. Suppose $\mathbf{x}_0$ is any feasible point of problem $\eqref{eq:svm9}$, meaning it satisfies the constraints

$f_i(\mathbf{x}_0) \leq 0, \forall i = 1, \dots, m; h_j(\mathbf{x}_0) = 0, \forall j = 1, \dots, p$.

We then have:

\[\sum_{i=1}^m \lambda_i f_i(\mathbf{x}_0) + \sum_{j=1}^p \nu_j h_j(\mathbf{x}_0) \leq 0 \Rightarrow \mathcal{L}(\mathbf{x}_0, \lambda, \nu) \leq f_0(\mathbf{x}_0)\]

Since this is true for all feasible $\mathbf{x}_0$, we have the following important property:

\[g(\lambda, \nu) = \inf_{\mathbf{x} \in \mathcal{D}} \mathcal{L}(\mathbf{x}, \lambda, \nu) \leq \mathcal{L}(\mathbf{x}_0, \lambda, \nu) \leq f_0(\mathbf{x}_0)\]

When $\mathbf{x}_0 = \mathbf{x}^*$, we get inequality $\eqref{eq:svm10}$.\

The Lagrange Dual Problem

For each pair $(\lambda, \nu)$, the Lagrange dual function provides a lower bound for the optimal value \(p^*\) of the original problem $\eqref{eq:svm9}$. The question is: for which pair $(\lambda, \nu)$ do we get the best lower bound for \(p^*\)? In other words, we need to solve the problem:

\[\begin{aligned} \lambda^*, \nu^* &=& \arg \max_{\lambda, \nu} g(\lambda, \nu) \label{eq:svm13} \\ \text{subject to:} && \lambda \succeq 0 \nonumber \end{aligned}\]

One important point: since $g(\lambda, \nu)$ is concave and the constraint functions $f_i(\lambda) = -\lambda_i$ are convex functions, problem $\eqref{eq:svm13}$ is a convex optimization problem. Therefore, in many cases, the solution can be easier to find than for the original problem. Note that the dual problem $\eqref{eq:svm13}$ is convex regardless of whether the original problem $\eqref{eq:svm9}$ is convex.

This problem is called the Lagrange dual problem associated with problem $\eqref{eq:svm9}$. Problem $\eqref{eq:svm9}$ is also referred to as the primal problem. Additionally, there is a concept called dual feasible, which refers to the feasible set of the dual problem, including the condition $\lambda \succeq 0$ and the hidden condition $g(\lambda, \nu) > -\infty$ (since we are looking for the maximum value of the function, $g(\lambda, \nu) = -\infty$ is obviously not interesting).

The solution of problem \(\eqref{eq:svm13}\), denoted by \(\lambda^*, \nu^*\), is called dual optimal or optimal Lagrange multipliers.

Note that the hidden condition $g(\lambda, \nu) > -\infty$ can be explicitly written in many cases. Returning to the example above, the hidden condition can be written as $\mathbf{c}+ \mathbf{A}^T\nu - \lambda = 0$. This is an affine function. Therefore, even with this additional constraint, we still have a convex problem.

Weak Duality

Let the optimal value of the dual problem $\eqref{eq:svm13}$ be denoted by $d^*$. According to $\eqref{eq:svm13}$, we know that:

\[d^* \leq p^*\]

even if the original problem is not convex.

This simple property is called weak duality. Though simple, it is extremely important.

From here we observe two things:

- If the primal problem is not bounded below, i.e., $p^* = -\infty$, then we must have $d^* = -\infty$, meaning the Lagrange dual problem is infeasible (i.e., there is no value that satisfies the constraints).

- If the dual problem is not bounded above, i.e., $d^* = +\infty$, we must have $p^* = +\infty$, meaning the original problem is infeasible.

The value $p^* - d^$ is called the *optimal duality gap. This gap is always non-negative.

Sometimes, there are problems (convex or non-convex) that are very difficult to solve, but at least if we can find \(d^*\), we can determine a lower bound for the original problem. Finding \(d^*\) is often feasible because the dual problem is always convex.

Strong Duality and Slater’s Constraint Qualification

If the equality \(p^* = d^*\) holds, the optimal duality gap is zero, and we say that strong duality occurs. In this case, solving the dual problem allows us to find the exact optimal value of the primal problem.

Unfortunately, strong duality does not always occur in optimization problems. However, if the primal problem is convex, i.e., it has the form:

\[\begin{aligned} \mathbf{x} &=& \arg \min_{\mathbf{x}} f_0(\mathbf{x}) \nonumber \\ \text{subject to:} && f_i(\mathbf{x}) \leq 0, \quad i = 1, 2, \dots, m \label{eq:svm12} \\ && \mathbf{Ax} = \mathbf{b} \nonumber \end{aligned}\]

where $f_0, f_1, \dots, f_m$ are convex functions, we often (but not always) have strong duality. There has been much research establishing conditions beyond convexity for strong duality to occur. These conditions are often called constraint qualifications.

One of the simplest constraint qualifications is Slater’s condition.

Definition: A feasible point of problem $\eqref{eq:svm12}$ is called strictly feasible if:

\[f_i(\mathbf{x}) < 0, \quad i = 1, 2, \dots, m, \quad \mathbf{Ax} = \mathbf{b}\]

Slater’s Theorem: If there exists a strictly feasible point (and the primal problem is convex), then strong duality holds.

This fairly simple condition will be helpful for many subsequent optimization problems.

Note:

• Strong duality does not always occur. For convex problems, it occurs more frequently. There are convex problems for which strong duality does not hold.

• There are non-convex problems for which strong duality still holds, such as the problem in Figure 1 above.

Optimality Conditions

Complementary Slackness

Assume that strong duality holds. Let \(\mathbf{x}^*\) be an optimal point of the primal problem, and let \((\lambda^*, \nu^*)\) be the optimal solution of the dual problem. We have:

\[\begin{aligned} f_0(\mathbf{x}^*) &=& g(\lambda^*, \nu^*) \nonumber \\ &=& \inf_{\mathbf{x}} \left(f_0(\mathbf{x}) + \sum_{i=1}^m \lambda_i^* f_i(\mathbf{x}) + \sum_{j=1}^p \nu_j^* h_j(\mathbf{x})\right) \nonumber \\ &\leq& f_0(\mathbf{x}^*) + \sum_{i=1}^m \lambda_i^* f_i(\mathbf{x}^*) + \sum_{j=1}^p \nu_j^* h_j(\mathbf{x}^*) \nonumber \\ &\leq& f_0(\mathbf{x}^*) \nonumber \end{aligned}\]

From here, we can see that the equality in the third and fourth lines must simultaneously hold. This leads to two additional interesting observations:

Since each term in the above sum is non-positive due to $\lambda_i^* \geq 0, f_i \leq 0$, we conclude that:

\[\lambda_i^* f_i(\mathbf{x}^*) = 0, \quad i = 1, 2, \dots, m\]

This condition is called complementary slackness. From this, we can infer:

\[\begin{aligned} \lambda_i^* > 0 &\Rightarrow& f_i(\mathbf{x}^*) = 0 \\ f_i(\mathbf{x}^*) < 0 &\Rightarrow& \lambda_i^* = 0 \end{aligned}\]

That is, one of the two values must always be zero.

KKT Optimality Conditions

We still assume that the functions under consideration are differentiable, and the optimization problem does not necessarily have to be convex.

KKT Conditions for Non-Convex Problems

Assume that strong duality holds. Let \(\mathbf{x}^*\) and \((\lambda^*, \nu^*)\) be any primal and dual optimal points. Since \(\mathbf{x}^*\) optimizes the differentiable function \(\mathcal{L}(\mathbf{x}, \lambda^*, \nu^*)\), the derivative of the Lagrangian at \(\mathbf{x}^*\) must be zero.

The Karush-Kuhn-Tucker (KKT) conditions state that \(\mathbf{x}^*, \lambda^*, \nu^*\) must satisfy:

\[\begin{aligned} f_i(\mathbf{x}^*) &\leq& 0, \quad i = 1, 2, \dots, m \nonumber \\ h_j(\mathbf{x}^*) &=& 0, \quad j = 1, 2, \dots, p \nonumber \\ \lambda_i^* &\geq& 0, \quad i = 1, 2, \dots, m \nonumber \\ \lambda_i^* f_i(\mathbf{x}^*) &=& 0, \quad i = 1, 2, \dots, m \nonumber \\ \nabla f_0(\mathbf{x}^*) + \sum_{i=1}^m \lambda_i^* \nabla f_i(\mathbf{x}^*) + \sum_{j=1}^p \nu_j^* \nabla h_j(\mathbf{x}^*) &=& 0 \nonumber \end{aligned}\]

These are the necessary conditions for \(\mathbf{x}^*, \lambda^*, \nu^*\) to be solutions of both problems.

KKT Conditions for Convex Problems

For convex problems where strong duality holds, the KKT conditions above are also sufficient conditions. Therefore, for convex problems with differentiable objective and constraint functions, any point that satisfies the KKT conditions is primal and dual optimal for the primal and dual problems.

From this, we can conclude that: For a convex problem with Slater’s condition satisfied (implying strong duality), the KKT conditions are necessary and sufficient for optimality.

The KKT conditions are very important in optimization. In some special cases (as we will see in the upcoming Support Vector Machine lesson), solving the system of (in)equations given by the KKT conditions is feasible. Many optimization algorithms are based on solving the system of KKT conditions.

Example: Equality Constrained Convex Quadratic Minimization

Consider the problem:

\[\begin{aligned} \mathbf{x} &=& \arg \min_{\mathbf{x}} \dfrac{1}{2}\mathbf{x}^T\mathbf{Px} + \mathbf{q}^T\mathbf{x} + r \nonumber \\ \text{subject to:} && \mathbf{Ax} = \mathbf{b} \nonumber \end{aligned}\]

where $\mathbf{P} \in \mathbb{S}_+^n$ (the set of symmetric positive semi-definite matrices).

Lagrangian:

\[\mathcal{L}(\mathbf{x}, \nu) = \dfrac{1}{2}\mathbf{x}^T\mathbf{Px} + \mathbf{q}^T\mathbf{x} + r + \nu^T(\mathbf{Ax} - \mathbf{b})\]

The KKT conditions for this problem are:

\[\begin{aligned} \mathbf{Ax}^* &=& \mathbf{b} \nonumber \\ \mathbf{P}\mathbf{x}^* + \mathbf{q} + \mathbf{A}^T\nu^* &=& 0 \nonumber \end{aligned}\]

The second equation is the equation of the Lagrangian derivative at $\mathbf{x}^*$ being zero.

This system can be rewritten simply as a simple linear equation: \(\begin{bmatrix} \mathbf{P} & \mathbf{A}^T \\ \mathbf{A} & \mathbf{0} \end{bmatrix} \begin{bmatrix} \mathbf{x}^* \\ \nu^* \end{bmatrix} = \begin{bmatrix} -\mathbf{q} \\ \mathbf{b} \end{bmatrix}\)