Lagrangean duality: Difference between revisions

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search
(Updated the History section to include more info and match our Google docs latest.)
Line 7: Line 7:


== '''History''' ==
== '''History''' ==
The Lagrangian duality is a component of the mathematical optimization theory called the duality principle. Origins of Duality has been documented as being part of an intellectual debate and observation amongst Mathematicians, and colleagues, John von Neumann and George Dantzig. While George was sharing his own theory on linear programming, and his simplex method, John von Neumann quickly surmised that Dantzig's Linear Programming shared an equivalence with his Game Theory and Expanding Economy model.
The Lagrangian duality is a component of the mathematical optimization theory called the duality principle. Origins of Duality has been documented as being part of an intellectual debate and observation amongst Mathematicians, and colleagues, John von Neumann and George Dantzig. During World War II the allied forces were employing the greatest minds in the field mathematics and logistics to provide a strategic edge over the Axis forces. During this timeframe, Neumann and Dantzig, two renowned experts in the fields of linear programming and game theory had a chance encounter and meeting of the minds.
 
During their interaction they began to speak and provide lectures on their life’s work. While Dantzig was sharing his own theory on linear programming, and his simplex method, Neumann quickly surmised that Dantzig's Linear Programming shared an equivalence with his Game Theory and Expanding Economy model. Neumann then began conceptualizing the theory of using an alternate perspective, the dual problem. In which, solving for either the primal or dual would yield an optimal solution. Later that year in 1947 Neumann would formally publish his theory of Duality. This principle would then see several formulations and implementations such as Fenchel, Wolfe, and Lagrangian.


== '''Algorithm''' ==
== '''Algorithm''' ==

Revision as of 11:41, 27 November 2021

Authors: Sonam Tharkay (st849), Jerome Terrell (jet258), Ashley Turke (ajt238), Mariet Kurtz (msk328), Daniel Yeung (djy27) (SYSEN5800 Fall 2021)

(NOTE: THIS PAGE IS STILL IN DEVELOPMENT.)

Introduction

A common approach to solving optimization problems is by constructing the Lagrangian dual of the problem and solving the dual problem instead of the primal problem. This approach is called Lagrangian relaxation. The advantage of performing Lagrangian relaxation is that in many situations it is easier to solve the dual than the primal problem. For example, in general non-convex problems are more difficult to solve than convex problems. Even if the primal optimization problem is non-convex, the Lagrangian dual could be convex. [1]

History

The Lagrangian duality is a component of the mathematical optimization theory called the duality principle. Origins of Duality has been documented as being part of an intellectual debate and observation amongst Mathematicians, and colleagues, John von Neumann and George Dantzig. During World War II the allied forces were employing the greatest minds in the field mathematics and logistics to provide a strategic edge over the Axis forces. During this timeframe, Neumann and Dantzig, two renowned experts in the fields of linear programming and game theory had a chance encounter and meeting of the minds.

During their interaction they began to speak and provide lectures on their life’s work. While Dantzig was sharing his own theory on linear programming, and his simplex method, Neumann quickly surmised that Dantzig's Linear Programming shared an equivalence with his Game Theory and Expanding Economy model. Neumann then began conceptualizing the theory of using an alternate perspective, the dual problem. In which, solving for either the primal or dual would yield an optimal solution. Later that year in 1947 Neumann would formally publish his theory of Duality. This principle would then see several formulations and implementations such as Fenchel, Wolfe, and Lagrangian.

Algorithm

Generalization of a typical optimization problem:

Optimization Problem (in Standard Form):

minimize   

subject to  

The Lagrangian for the optimization problem above takes the form:

where λ and v are the Lagrange Multipliers (dual variables).

Source of this section: [3]

The Lagrangian takes all of the constraints and combines it with the objective function into one larger formula.

Process

Constructing the Lagrangian dual can be done in four easy steps:

Step 1: Construct the Lagrangian.

Step 2: Take the partial derivatives (gradient) of the Lagrangian with respect to x, set each equal to zero, and solve for x*.

Step 3: Substitute x* terms into the Lagrangian to create the dual function (𝜙), which is only a function of the dual variables (λ, v).

Step 4: Construct the dual with the dual function (𝜙) and the  new constraints. If the original problem is for minimization, the dual is for maximization, and vice versa. The dual variables are non-negative.

Weak and Strong Duality

The strong duality is a concept in mathematical optimization that states the primal optimal objective and the dual optimal objective value are equal. Whereas, in the weak duality, the optimal value from the primal objective is greater than or equal to the dual objective. Thus, in the weak duality, the duality gap is greater than or equal to zero [11].

Illustration of the weak and strong duality [9].

The verification of gaps is a convenient tool to check for optimality solutions. The illustration shows that the weak duality has the gap whereas the strong duality does not. Thus, the strong duality only holds true if the duality gap is equal to 0.

Complementary Slackness

Complementary Slackness implies a relationship between the slackness in primal constraints and the slackness on the dual variable. The Complementary Slackness Theorem can be used to develop a test of optimality for a solution. Slack in corresponding inequalities must be complementary in the sense that it cannot occur simultaneously in both of them thus if the primal is unbounded then the dual is infeasible and vice versa [12]. Complementary Slackness is also used as a tool to find the optimal dual solution when only the optimal primal solution is known [11].

Numerical Examples

In this section, we will apply the process to solve an example problem.


Construct the Lagrangian dual for the following optimization problem:

minimize  

subject to 


Step 1: Construct the Lagrangian.



Step 2: Take the partial derivatives of the Lagrangian with respect to x, set each equal to zero, and solve for x*.





Step 3: Substitute x* terms into the Lagrangian to create the dual function (𝜙), which is only a function of the dual variables (λ, v).

Step 4: Construct the dual with the dual function (𝜙) and the  new constraints. If the original problem is for minimization, the dual is for maximization, and vice versa. The dual variables are non-negative.


maximize


subject to

Applications

The optimal solution to a dual problem is a vector of Karush-Kuhn-Tucker (KKT) multipliers (also known as Lagrange Multipliers or Dual Multipliers), thus the multipliers can be used for nonlinear programming problems to ensure the solution is indeed optimal. Since the Lagrange Multipliers can be used to ensure the optimal solution, Lagrangian duals can be applied to achieve many practical outcomes in optimization, such as determining the lower bounds for non-convex problems, simplifying the solutions of some convex problems meeting the conditions for strong duality, and determining the feasibility of a system of equations or inequalities [3].

One application where the Lagrangian dual may be applied to find bounds for a complex problem is the symmetric Traveling Salesman Problem. This problem is analytically difficult, but its Lagrangian dual is a convex problem whose optimal solution provides a lower bound on solutions to the primal problem. While the solution to the dual problem may not be feasible in the primal problem, it is possible to use heuristic methods to find a primal solution based on the optimal dual solution [4].

Lagrangian duals have also proven useful in deep learning problems where the objective is to learn optimization problems constrained by hard physical laws. By incorporating duality during the training cycle, researchers can achieve improved results on a variety of problems, including optimizing power flows; optimizing gas compressor usage in natural gas pipelines; transprecision computing, in which the bit width of variables may be reduced to reduce power usage in embedded systems at the cost of increased error; and devising classifiers which are “fair” with respect to a defined protected characteristic [7].

The convex relaxation provided by the Lagrangian dual is also useful in the domains of machine learning [5]; combinatorial optimization, where it generalizes two well-known relaxation techniques in the field, max-stable and max-cut [6]; and 3D registration of geometric data in computer vision, where primal techniques often fail to escape local optima [8].

In some real-world applications, the dual formulation of a problem has a specific real-world meaning. The following are examples of real-world applications for Lagrangian Duality [2]:

In an electrical network, if the primal problem describes current flows, the dual problem describes voltage differences.

In an economic model, if the primal problem describes production and consumption levels, the dual problem describes the prices of goods and services.

In a structural design model, if the primal problem describes the tension of various beams, the dual problem describes nodal displacements.

In a resource allocation model, if the primal problem describes supply as seen by the production manager, the dual problem describes the demand as seen by the supplier. Applying the duality theorem towards both linear programming problems, the production levels and the prices can be set to establish a balance and equilibrium.

Conclusion

Overall, Lagrangian duality is a very useful way to solve complex optimization problems. Whenever there is difficulty solving a problem, it is oftentimes an effective strategy to find and solve the dual of the problem using the Lagrangian. Lagrangian duality is used in a variety of applications, including the traveling sales problem, deep learning models, and computer vision.

References

S. Boyd, L. Vandenberghe, Convex Optimization, Cambridge University Press, 2009, https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf

R. M. Freund, Applied Lagrange Duality for Constrained Optimization, Massachusetts Institute of Technology, 2004,  https://ocw.mit.edu/courses/sloan-school-of-management/15-094j-systems-optimization-models-and-computation-sma-5223-spring-2004/lecture-notes/duality_article.pdf

S. Wolf, S. M. Günther, An Introduction to Duality in Convex Optimization, Technische Universität München, 2011, https://www.net.in.tum.de/fileadmin/TUM/NET/NET-2011-07-2/NET-2011-07-2_20.pdf

S. Timsj, An Application of Lagrangian Relaxation to the Traveling Salesman Problem, https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.31.843&rep=rep1&type=pdf

J. Hui, Machine Learning - Lagrange multiplier & Dual decomposition, https://jonathan-hui.medium.com/machine-learning-lagrange-multiplier-dual-decomposition-4afe66158c9

C. Lemarechal, F. Oustry, Semidefinite Relaxations and Lagrangian Duality with Application to Combinatorial Optimization, https://hal.inria.fr/inria-00072958/document

F. Fioretto, P. Van Hentenryck, T. W. K. Mak, C. Tran, F. Baldo, M. Lombardi, Lagrangian Duality for Constrained Deep Learning, https://web.ecs.syr.edu/~ffiorett/files/papers/ecml2020_arxiv.pdf

J. Briales, J. Gonzalez-Jimenez, Convex Global 3D Registration with Lagrangian Duality, https://openaccess.thecvf.com/content_cvpr_2017/papers/Briales_Convex_Global_3D_CVPR_2017_paper.pdf

B. Ghojogh, Illustration of weak duality and strong duality, ResearchGate, https://www.researchgate.net/figure/Illustration-of-weak-duality-and-strong-duality_fig6_355093246

A. Majumdar, Duality: The unsung hero of optimization explained through an example, https://towardsdatascience.com/duality-the-unsung-hero-of-optimization-explained-through-an-example-f53f3fb191d9

R.J. Vanderbei, Linear Programming: Foundations and Extensions. Springer, 2008.  (PDF at http://link.springer.com/book/10.1007/978-0-387-74388-2)

J. Birge, F. Louveaux, Introduction to Stochastic Programming, Springer, 2011. (PDF at http://link.springer.com/book/10.1007/978-1-4614-0237-4)

  1. S. Boyd, L. Vandenberghe, Convex Optimization, Cambridge University Press, 2009, https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf