This article is a result of an investigation I conducted over the optimization literature. As a researcher in networking I rely often on optimization techniques and I need to understand them in depth. So far, I have not found any textbook or article which I fully like so I decided to write one myself. This text represents what I wanted to read when I started studying optimization and it is intended to constitute a reminder for the future.
The Problem (a.k.a. primal)
The formulation of an optimization problem can be given, without loss of generality, as:
To ease the notation, where not specified, . We assume that , i.e., they are linear and continuously differentiable over our dominion. We also assume that are convex functions. This is a quite strong assumption but without this convexity property (which grants there are not local minima) solution gets way more complex. We need convexity on for the reason explained in the Lagrangian relaxation section.
NOTE: If are linear and all your original constraints were equalities (but for the range ), you may think to solve it using the simplex method. Simplex method does not provide all the optimal solutions (in general) but it works with standard algebraic solvers.
The previous problem optimization is quite powerful from the representation point of views; in fact we can transform:
- a maximization problem: ;
- an inequality constraint: ;
- an equality constraint: ;
- variable dominion constraints, such as can be interpreted as .
Textbooks usually keep the distinction between equalities and inequalities for a reason will be presented in the the special case of equalities section.
The Lagrangian Relaxation
This section presents the idea behind the Lagrangian relaxation: get rid of the constraints (or at least of some of them). Solving primal problem most of the time is hard exactly for the presence of the constraints. However, consider this one-constrain toy example:
We have that, for any scalar that is large enough,
In fact, the value of impacts on the minimization problem, privileging the values of which makes . The role of is amplifying this effect.
We call the Lagrangian function: . In general, we have .
It is worth noticing, if are convex (as anticipated in the problem section) then is convex.
The special case of equalities
Suppose your original problem is
which you port to our standard form of:
Now the Lagrange function is: with If we now define we can than rewrite it as: But now and it is not anymore constrained to positive values.
Optimum lower bound (a.k.a. dual)
Starting from the Lagrangian relaxation we can go further and there is an equivalence result stating:
Dual of a linear problem
It is worth noticing that it can be possible to represent through some constraints and remove it from the objective function; e.g.:
has . But minimizing would have not lower bound if .
So we can introduce this constraint and our problem becomes:
Which is obviously equal to:
And, since and picking a new variable :
NOTE: If you have a linear problem with variables and constraints, it is computationally convenient to solve the dual problem (with the dual-simplex), as it will have variables and constraints.
The Lagrangian and KKT Theorems
The nice thing about a Lagrangian relaxation is that the minimization objective becomes finding the minimum of a function (no constraints anymore). In the introductory courses of analysis, they teach to use derivates to find the extrema of a given function. In our case we use the gradient but it is quite similar.
Theorem (Lagrange): The Langrange theorem states that if is a optimum for , all the constraints are expressed with equalities and it holds the Linearly Independence Constraint Qualification (LICQ) (i.e., rank), then it exists :
We can use this theorem to solve analytically with only equality constraints:
Theorem (KKT): The KKT theorem states that, given a problem in the form of primal for which it holds the LICQ; let be the index sets of the equality and inequality constraints respectively, if is a minimum then:
The main difference between Lagrange theorem and the KKT theorem is that the latter has to carefully handle the inequalities constraints; in particular it requires that, if a constraint is active, than . Otherwise, we would have
Both Lagrange and KKT theorems provide necessary conditions for optimality, hence once got a set of critical points candidate to be optima we have to test them against the primal objective function and constraints.
Bonus: Solving a linear dual with the subgradient method
In general we can solve it via a cutting plane or tangential approximation approaches to recover both primal and dual solution.
However, if our problem is linear (i.e., and are linear) we can use the subgradient method. The subgradient algorithm is a method to maximize (minimize) a function using only very few assumptions. Suppose you want to maximize , then chosen an particular sequence , you iterate over :
- if then and return to step 1
where is the subgradient of computed in . If then .
It is important to choose carefully so that the method converges. Several alternatives have been published, among others these properties grant the convergence:
A practical choice can be for some .
Hence, solving a dual problem in the form of the dual, becomes:
- Choose , set
- if then and return to step 2 Sherali et al. proved that in our context, final result is distorted but we can reconstruct it:
Recall that the constraint imposed by step 3 is needed if and only if is associated to an inequality constraint.