Duality

Duality lets us associate to any constrained optimization problem, a concave maximization problem whose solutions lower bound the optimal value of the original problem. What is interesting is there are cases, when one can solve the primal problem by first solving the dual one. Now, consider general constrained optimization problem:

We’ll build $g(y)$, that preserves uniform bound:

As a consequence:

We’ll consider one (of the many) possible way to construct $g(y)$ in case, when we have general mathematical programming problem with functional constraints:

And the Lagrangian, associated with this problem:

Now, we notice, that the original problem is equivalent to the following unconstraint problem:

Because $\lambda$ don’t affect the equality entries (since they all are equal to zero), while $\mu$ is positive and decreases Lagrangian (since all inequality entries are non - positive). Moreover, it can be seen, that:

Now, we denote the inner optimization as follows:

Summary

  Primal Dual
Function
Variables
Constraints
Problem
Optimal

Useful features

  • Construction of lower bound on solution of the direct problem.

    It could be very complicated to solve the initial problem. But if we have the dual problem, we can take an arbitrary $y \in \Omega$ and substitute it in $g(y)$ - we’ll immediately obtain some lower bound.

  • Checking for the problem’s solvability and attainability of the solution.

    From the inequality $\max\limits_{y \in \Omega} g(y) \leq \min\limits_{x \in S} f(x) $ follows: if $\min\limits_{x \in S} f(x) = -\infty$, then $\Omega = \varnothing$ and vice versa.

  • Sometimes it is easier to solve a dual problem than a primal one.

    In this case, if the strong duality holds: $g(y^∗) = f(x^∗)$ we lose nothing.

  • Obtaining a lower bound on the function’s residual.

    $f(x) - f^∗ \leq f(x) - g(y)$ for an arbitrary $y \in \Omega$

  • Dual function is always concave

    As a pointwise minimume of affine functions.

Weak duality

It is common to name this relation between optimals of primal and dual problems as weak duality. For problem, we have

While the difference between them is often called duality gap:

Note, that we always have weak duality, if we’ve formulated primal and dual problem. It means, that if we were managed to solve dual problem (which is always convex, no matter the initial problem was or not), than we have some lower bound. Surprisingly, there are some notable cases, when these solutions are equal.

Strong duality

Strong duality if duality gap is zero:

Notice: both and may be .

  • Several sufficient conditions known!
  • “Easy” necessary and sufficient conditions: unknown.

Slater’s sufficient condition

Theorem Let the primal problem be the Convex optimization problem. If there is a feasible point such that is strictly feasible for the non-affine constraints (and merely feasible for affine, linear ones), then strong duality holds. Moreover, in this case, the dual optimal is attained (i.e., ).

Slater’s condition: There exists s.t. , i.e. there is a strictly feasible point.

Counterexample

Only feasible line is , therefore we know optimal value of the primal problem . Let’s construct the Lagrangian:

Then, dual function is:

Dual problem is formulating the following way:

Here, we clearly see unit dual gap: and lack of strictly feasible solutions.

Examples

Least squares

Problem

Lagrangian

Dual function

Setting gradient to zero to find minimum 🤔:

Here we see lower bound property:

Let’s solve the dual problem:

Calculate the primal optimal and check whether this problem has strong duality or not.

Fenchel - Rockafellar problem

Problem

Let and — function, defined on the sets and in Euclidian Spaces and respectively. Let be the conjugate functions to the and respectively. Let — linear mapping. We call Fenchel - Rockafellar problem the following minimization task:

where — preimage of . We’ll build the dual problem using variable separation. Let’s introduce new variable . The the problem could be rewritten:

Lagrangian

Dual function

Now, we need to remember the definition of the Conjugate function:

So, we have

which allows us to formulate one of the most important theorems, that connects dual problems and conjugate functions:

Fenchel - Rockafellar theorem Let and — function, defined on the sets and in Euclidian Spaces and respectively. Let be the conjugate functions to the and respectively. Let — linear mapping. Let - optimal values of primal and dual problems:

Then we have weak duality: . Furthermore, if the functions and are convex and , then we have strong duality: . While points and are optimal values for primal and dual problem if and only if

Convex case is especially important since if we have Fenchel - Rockafellar problem with parameters , than the dual problem has the form

Logistic regression

Problem

where . Let and be the following functions

And let be some linear map:

Then, we can introduce Fenchel - Rockafellar problem:

Entropy maximization

Problem

Lagrangian

References