In this post we discuss the correspondence between the Lagrangian and the Fenchelian duality frameworks and we trace their common origin to the concept of convex conjugate functions and perturbed optimization problems.

**Duality in mathematics**

In mathematics, the concept of duality allows to study an object by means of some other object called its dual. A linear operator can be studied via its *adjoint* operator . Certain properties of a Banach space can be studied via its *topological dual* . A convex set in can be seen as the intersection of a set of hyperplanes, that is and the latter is often a more convenient representation. These are examples of *dual objects* in mathematics. Likewise, in convex optimization, the dual object which corresponds to a convex function is its *convex conjugate. *When it comes to optimization problems, however, there are several ways in which we may derive dual optimization problems leading to different formulations. This is because we first need to specify what exactly we dualize and how…

**Convex conjugate functions**

*Notation:* In what follows, denote two Hilbert spaces. Their inner product will be denoted by With minor adaptations the results presented here hold for Banach spaces as well. We denote the extended-real line by .

In convex optimization theory, most duality concepts (including the Lagrange and Fenchel duality frameworks) source from the realization that **convex sets** can be represented as the **intersection of a set of hyperplanes**. This extends elegantly to proper, convex, lower semicontinuous functions which can be identified by their epigraphs. Recall that the epigraph of a function is the set .

Let us describe the supporting hyperplanes of the epigraph of a function. Let be an affine function with slope which is majorized by , that is for all .

Provided that is proper, convex and lower semicontinuous, for every slope there is a supporting hyperplane for the form for some . This is

The *convex conjugate* of at is the RHS of this equation which returns a value so that is a supporting hyperplane of the epigraph of .

Provided that is proper, convex and lower semicontinuous, knowing can tell us everything about . In fact, according to the Fenchel-Moreau theorem, , where .

The convex conjugates are the *dual* objects of convex functions and, as you can see, they

**Perturbation Functions**

The framework of perturbation functions is perhaps the most elegant in optimization theory the reveals the essence of dual optimization problems [1], [2]. In fact, every dualization (there is no unique way in which we define a dual optimization problem) is associated with a perturbation function.

Consider the optimization problem

We introduce a convex function which we shall call a *perturbation function, *so that . Then, the optimization problem above can be equivalently written as

For , the following problem, which depends parametrically on , is called a *perturbed optimization problem*

Let be the optimal value of this problem. We are interested in determining . If is sufficiently regular, that is, proper, convex, lower semicontinuous (we shall discuss later when this is the case), then

otherwise .

The **dual problem** consists in finding .

By definition

therefore,

Therefore, the determination of requires the solution of the optimization problem

This is precisely the **Fenchel dual** optimization problem [3].

**Duality and Perturbation Functions**

Let us see how exactly perturbation functions lead naturally to dual formulations. The convex conjugate of is

therefore,

As a result, the dual optimization problem problem can be written as

or, equivalently

Juxtapose this with the primal problem which is

**Lagrangian Duality and Perturbation Functions**

Lagrangian duality is a particular type of duality for optimization problems of the form

where , and is meant in the component-wise sense.

We perturb the problem as follows

where . Define the set . The perturbed problem is written as

where is the indicator function of , that is

In other words, the perturbation function is defined as

Its convex conjugate is

where .

This is exactly the **Lagrangian dual** optimization problem which is the Fenchel dual on a properly chosen perturbation function.

**References**

[1] R.I. Bot, S.M. Grad and G. Wanka, Fenchel-Lagrange Duality Versus Geometric Duality in Convex Optimization, JOTA 129(1):35-54, 2006.

[2] R.T. Rockafellar, R. J.-B. Wets, Variational Analysis, Springer, 2009.

[3] H. H. Bauschke, P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, Springer, 2011.

In the paragraph on Lagrangian Duality and Perturbation Functions shouldn’t the perturbed problem be g(x) – y <=0 for the definition of the set C(x,y) to make sense?

LikeLiked by 1 person

Yes, this was a typo. Thanks for pointing out to it.

LikeLike