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
The framework of perturbation functions is perhaps the most elegant in optimization theory the reveals the essence of dual optimization problems , . 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
The dual problem consists in finding .
Therefore, the determination of requires the solution of the optimization problem
This is precisely the Fenchel dual optimization problem .
Duality and Perturbation Functions
Let us see how exactly perturbation functions lead naturally to dual formulations. The convex conjugate of is
As a result, the dual optimization problem problem can be written as
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
This is exactly the Lagrangian dual optimization problem which is the Fenchel dual on a properly chosen perturbation function.
 R.I. Bot, S.M. Grad and G. Wanka, Fenchel-Lagrange Duality Versus Geometric Duality in Convex Optimization, JOTA 129(1):35-54, 2006.
 R.T. Rockafellar, R. J.-B. Wets, Variational Analysis, Springer, 2009.
 H. H. Bauschke, P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, Springer, 2011.