{"id":2145,"date":"2010-02-01T23:37:48","date_gmt":"2010-02-02T07:37:48","guid":{"rendered":"http:\/\/algnotes.info\/b\/?p=2145"},"modified":"2026-09-30T09:14:25","modified_gmt":"2026-09-30T17:14:25","slug":"lagrangian-relaxation-discussion","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/background\/lagrangian-relaxation-discussion\/","title":{"rendered":"Lagrangian relaxation \/ discussion"},"content":{"rendered":"<div class=\"latex-file\">\n<div class=\"latex-document\">\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<blockquote class=\"quote\"><p><center><em>A brief yet long-winded discussion of Lagrangian-relaxation algorithms.<\/em><\/center><\/p><\/blockquote>\n<p> \u00a0<!--more--><\/p>\n<p><div style=\"margin:0pt;padding:0pt;margin-bottom:12px\"><\/div>\n<\/p>\n<hr \/>\n<div class=\"expandable\" id=\"a0000000002\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for background material\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for background material\u2026<\/summary>\n<div class=\"collapseomatic_content\">\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/lagrangian-relaxation-example\">An example Lagrangian-relaxation algorithm<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/obliv\">Using randomized rounding to derive Lagrangian-relaxation algorithms<\/a> <\/p>\n<\/li>\n<\/ul>\n<\/div>\n<\/details>\n<\/div>\n<hr \/>\n<\/p>\n<\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000003\">Lagrangian relaxation<\/h1>\n<p>Lagrangian relaxation is a sophisticated generalization of the greedy approach: to approximately solve a given \u201chard\u201d optimization problem, one solves a sequence of carefully chosen \u201ceasier\u201d problems, then aggregates the solutions of the easier problems, typically by taking a weighted combination of them. <\/p>\n<p>The easy problems are obtained from the original problem by relaxing some of the more difficult constraints, replacing them by a single <em>surrogate constraint<\/em>. Typically, the surrogate constraint is a weighted combination of the constraints it replaces, and the weights come from the gradient of a smooth potential function that somehow proxies the replaced constraints. To prove the algorithm\u2019s quality of approximation, one proves some invariant involving this potential function. <\/p>\n<p>Historically, Lagrangian-relaxation algorithms have been used (i) for problem formulations involving huge numbers of variables (as a practical alternative to ellipsoid methods \u2014 similarly to column generation; the Held-Karp lower bound for the traveling salesman problem is one famous example), and (ii) for problems that are composed of many subproblems that are loosely coupled by side constraints (multicommodity flow is a canonical example). The last few decades have seen improved bounds on convergence rates \u2014 that is, bounds on the number of subproblem solutions needed to approximate the original problem to the desired extent. Similarly to greedy algorithms, the form that these algorithms take makes them useful in many contexts (for example, distributed, parallel, and online settings). <\/p>\n<p>The basic observation \u2014 that a \u201chard\u201d problem can be approximately solved by a weighted combination of \u201ceasy\u201d problems \u2014 can also be used to prove some nice combinatorial theorems. This is roughly because, if the easy-problem solutions have some nice combinatorial property, the property may carry over to their weighted combination, and thus to some approximate solution to the hard problem. <\/p>\n<p>The basic observation is also directly related to the learning-theory concept of <em>boosting<\/em> (the problem of strongly learning a concept reduces to the problem of weakly learning it). Relatedly, some Lagrangian-relaxation algorithms can be viewed as learning-theory algorithms for <em>following expert advice<\/em> (such as multiplicative-weights-update algorithms). <\/p>\n<\/div><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000004\">Replacing many constraints by a single surrogate<\/h1>\n<p> A typical optimization problem is of the form <em>find a vector <script type=\"math\/tex;\">x\\in {\\mathbb R}^n<\/script> meeting some constraints, possibly while maximizing or minimizing some objective function<\/em>. <\/p>\n<p>We will write the constraints in the form <script type=\"math\/tex;\">x\\in {\\cal P},\\,  Ax \\le \\mathbf1<\/script>. That is, we partition the constraints into two sets: the first set we write abstractly as \u201c<script type=\"math\/tex;\">x\\in {\\cal P}<\/script>\u201d, where <script type=\"math\/tex;\">{\\cal P}<\/script> can be an arbitrary set, but is typically some polytope (these are the constraints we want to leave \u201cin place\u201d); the second set \u201c<script type=\"math\/tex;\">Ax \\le \\mathbf1<\/script>\u201d we call <em>side<\/em> constraints. (Technically, we require that <script type=\"math\/tex;\">Ax\\ge \\mathbf0<\/script> for all <script type=\"math\/tex;\">x\\in {\\cal P}<\/script>, that is, the side constraints are packing or covering constraints.) <\/p>\n<p>The algorithm will replace the side constraints by a single \u201csurrogate\u201d constraint. Somehow, the algorithm will compute a coefficient vector <script type=\"math\/tex;\">\\alpha \\in {\\mathbb R}_+^m<\/script>, such that <script type=\"math\/tex;\">\\sum _i \\alpha _i = 1<\/script>. The surrogate constraint will be the single linear constraint that is their <script type=\"math\/tex;\">\\alpha <\/script>-weighted average: <\/p>\n<div id=\"eq:1\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{equation}  ({\\textstyle \\sum _i \\alpha _i A_i}) \\cdot x \\le 1\\label{eq:1}, ~ \\mbox{ in other words, }~  (\\alpha ^{\\scriptscriptstyle \\sf T}A) x \\le 1. \\end{equation}<\/script><\/div>\n<p> (Here <script type=\"math\/tex;\">A_i<\/script> is the <script type=\"math\/tex;\">i<\/script>th row of <script type=\"math\/tex;\">A<\/script>, so the <script type=\"math\/tex;\">i<\/script>th side constraint is <script type=\"math\/tex;\">A_i\\cdot x \\le 1<\/script>.) <\/p>\n<p>The resulting surrogate problem (for this <script type=\"math\/tex;\">\\alpha <\/script>) is <em>find <script type=\"math\/tex;\">x\\in {\\cal P}<\/script> such that the single linear constraint\u00a0\\eqref{eq:1} holds (while maximizing or minimizing the objective function, if present)<\/em>. Clearly, the surrogate problem is a relaxation of the original problem. That is, any feasible solution to the original problem is also feasible for the surrogate problem. <\/p>\n<div class=\"latex-paragraph\">\n<div class=\"latex-paragraph-heading\"> <b>The algorithm takes a weighted average of surrogate solutions.<\/b> <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> The Lagrangian-relaxation algorithms that we discuss here all work as follows. In each iteration, the algorithm computes a particular vector <script type=\"math\/tex;\">\\alpha \\in {\\mathbb R}_+^m<\/script> of constraint multipliers, then solves the surrogate problem for that particular <script type=\"math\/tex;\">\\alpha <\/script>. Finally, it returns a weighted average <script type=\"math\/tex;\">\\overline x<\/script> of the solutions to the surrogate problems. <\/p>\n<\/div><\/div>\n<div class=\"latex-paragraph\">\n<div class=\"latex-paragraph-heading\"> <b>Example.<\/b> <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> A main point is that the surrogate problem is easier to solve than the original problem. As a simple example, suppose we start with the packing problem <script type=\"math\/tex;\">\\max \\{  |x|_1 \\, :\\, Ax \\le \\mathbf1, x\\in {\\mathbb R}_+^n\\} <\/script>, where the polytope <script type=\"math\/tex;\">{\\cal P}<\/script> is simply the positive quadrant. Then the surrogate problem for a given <script type=\"math\/tex;\">\\alpha \\in {\\mathbb R}_+^m<\/script> will be of the form <\/p>\n<div id=\"a0000000005\" class=\"equation\"><script type=\"math\/tex; mode=display\"> \\max \\{  |x|_1 \\, :\\, \\beta \\cdot x \\le 1,\\,  x\\in {\\mathbb R}_+^n\\} , <\/script><\/div>\n<p> where <script type=\"math\/tex;\">\\beta = \\alpha ^{\\scriptscriptstyle \\sf T}A<\/script>. The surrogate problem has just one constraint, so is solved by taking just one index <script type=\"math\/tex;\">j<\/script> and taking that <script type=\"math\/tex;\">x_j<\/script> as large as possible (<script type=\"math\/tex;\">x_j = 1\/\\beta _j<\/script>). The index <script type=\"math\/tex;\">j<\/script> should be chosen to maximize the resulting cost, <script type=\"math\/tex;\">1\/\\beta _j<\/script>. <\/p>\n<\/div><\/div>\n<\/div><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000006\">The surrogate problems are feasible, and they bound OPT<\/h1>\n<p> Each surrogate problem is a relaxation of the original problem (including its objective), so, for each surrogate problem, the solution to the surrogate problem will meet the constraint <script type=\"math\/tex;\">x\\in {\\cal P}<\/script> and will have cost at most (or, for maximization, at least) the optimal cost of the original problem. Hence the weighted average <script type=\"math\/tex;\">\\overline x<\/script> will also be in <script type=\"math\/tex;\">{\\cal P}<\/script> and will have cost at most (or at least) the optimal cost of the original problem. If the algorithm chooses the surrogate problems well, then the weighted average <script type=\"math\/tex;\">\\overline x<\/script> should also (approximately) meet all side constraints. <\/p>\n<div class=\"latex-paragraph\">\n<div class=\"latex-paragraph-heading\"> <b>Solving the surrogate problems approximately.<\/b> <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Each surrogate problem doesn\u2019t have to be solved exactly. If each surrogate problem\u2019s solution is, say, a <script type=\"math\/tex;\">\\lambda <\/script>-approximate solution for its problem, it is also a <script type=\"math\/tex;\">\\lambda <\/script>-approximate solution for the original problem (minus the side constraints). The weighted combination <script type=\"math\/tex;\">\\overline x<\/script> of such solutions will necessarily also be a <script type=\"math\/tex;\">\\lambda <\/script>-approximate solution to the original problem (minus the side constraints). <\/p>\n<div id=\"a0000000007\" class=\"my-theorem latex-paragraph latex-exercise\">\n<div class=\"latex-paragraph-heading\">   <b>Exercise <\/b> (using an approximate subroutine).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Modify the correctness proof in <a href=\"http:\/\/algnotes.info\/on\/lagrangian-relaxation-example\">the multicommodity flow example<\/a> to show that, if in each iteration the algorithm chooses a path <script type=\"math\/tex;\">p'<\/script> such that <script type=\"math\/tex;\">\\sum _{e\\in p'} \\alpha _e\/c_e \\le \\lambda \\,  \\min _{p\\in P} \\sum _{e\\in p}\\alpha _e\/c_e<\/script>, then the final flow <script type=\"math\/tex;\">f<\/script> will have value at least <script type=\"math\/tex;\">(1-O(\\varepsilon ))|f^*|\/\\lambda <\/script>. <\/p>\n<\/div><\/div>\n<\/div><\/div>\n<\/div><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000008\">Choosing the constraint multipliers<\/h1>\n<p> Typically, the algorithm will maintain a current solution <script type=\"math\/tex;\">x<\/script> of some kind, and will be guided by a real-valued potential function <script type=\"math\/tex;\">\\phi (x)<\/script> that somehow smoothly proxies all of the side constraints. (For example, for the side constraints <script type=\"math\/tex;\">Ax\\le \\mathbf1<\/script>, one might use the potential function <script type=\"math\/tex;\">\\Phi (x) = \\ln \\sum _{i} \\exp (A_i x)<\/script>.) The constraint multiplier vector <script type=\"math\/tex;\">\\alpha <\/script> will typically be the gradient <script type=\"math\/tex;\">\\alpha = \\nabla \\Phi (x)<\/script> of the potential function with respect to <script type=\"math\/tex;\">x<\/script>. <\/p>\n<p>The algorithms are not typically pure gradient-descent algorithms, though. For example, in each iteration, the algorithm might choose just one coordinate <script type=\"math\/tex;\">x_j<\/script> of the current solution <script type=\"math\/tex;\">x<\/script>, and then increase only that coordinate. It might choose the <script type=\"math\/tex;\">x_j<\/script> so as to maximize <script type=\"math\/tex;\">c_j\/(\\delta \\Phi \/\\delta x_j)<\/script> \u2014 the rate of increase in the cost divided by the rate of increase in the potential function. <\/p>\n<\/div>\n<div class=\"latex-section\">\n<h1 id=\"a0000000009\">Potential-function invariant for the side constraints<\/h1>\n<p> In this way, the algorithm will maintain some potential-function invariant on the current solution <script type=\"math\/tex;\">x<\/script>. For example, the invariant might be <script type=\"math\/tex;\">\\Phi (x) \\le (c\\cdot x)\/{\\textsc{opt}}+ \\ln m<\/script>. At termination (once <script type=\"math\/tex;\">c\\cdot x<\/script> is large enough) the invariant will imply that the side constraints are approximately met. <\/p>\n<\/div><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000010\">Step size and trust regions<\/h1>\n<p> The potential functions, which are typically not linear, are generally smooth. That is, at any point <script type=\"math\/tex;\">\\tilde x<\/script>, they are well-approximated by their first-order approximation: for any \u201csmall\u201d <script type=\"math\/tex;\">d<\/script>, <\/p>\n<div id=\"a0000000011\" class=\"equation\"><script type=\"math\/tex; mode=display\"> \\Phi (\\tilde x+d) \\approx \\Phi (\\tilde x) + \\nabla \\Phi (\\tilde x) \\cdot d. <\/script><\/div>\n<p> With each surrogate subproblem, the algorithm will typically take the current overall solution <script type=\"math\/tex;\">\\tilde x<\/script>, and then move it in the direction of the solution to the surrogate subproblem: <script type=\"math\/tex;\">\\tilde x \\leftarrow \\tilde x + \\lambda x<\/script>, where <script type=\"math\/tex;\">x<\/script> is the solution to the surrogate subproblem. <\/p>\n<p>The algorithm will typically choose the step size <script type=\"math\/tex;\">\\lambda <\/script> so that the increase in the potential function is <script type=\"math\/tex;\">(1+O(\\varepsilon ))<\/script>-approximated by its first-order approximation <script type=\"math\/tex;\">\\lambda \\nabla \\Phi (\\tilde x) \\cdot \\tilde x<\/script>. That is, it will move <script type=\"math\/tex;\">\\tilde x<\/script> to a new point that is within the <em>trust region<\/em> around the current point. <\/p>\n<p>This will suffice to maintain the desired invariant. (A tolerance for this <script type=\"math\/tex;\">(1+O(\\varepsilon ))<\/script>-approximation of the change will be built into the potential function or the invariant.) <\/p>\n<\/div><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000012\">Convergence<\/h1>\n<p> There is a large literature on Lagrangian-relaxation algorithms in Computer Science. Some of the more well-known papers are by Plotkin, Shmoys, and Tardos (e.g.\u00a0<span class=\"cite\">[<a href=\"#Plotkin95Fast\">12<\/a>]<\/span>), and by Grigoriadis and Khachiyan (e.g.\u00a0<span class=\"cite\">[<a href=\"#Grigoriadis01Approximate\">6<\/a>]<\/span>). <\/p>\n<p>With current algorithms (e.g.\u00a0<span class=\"cite\">[<a href=\"#garg2007faster\">4<\/a>]<\/span>), the number of iterations needed in the worst case to converge to a <script type=\"math\/tex;\">(1\\pm \\varepsilon )<\/script>-approximate solution is typically <script type=\"math\/tex;\">O(\\min (m,\\omega )\\log (m)\/\\epsilon ^2)<\/script>, where <script type=\"math\/tex;\">m<\/script> is the number of constraints, and <script type=\"math\/tex;\">\\omega <\/script> is the so-called <em>width<\/em> of the problem (here, the maximum value of <script type=\"math\/tex;\">A_i\\cdot x<\/script> for any <script type=\"math\/tex;\">x\\in {\\cal P}<\/script> and matrix row <script type=\"math\/tex;\">A_i<\/script>). <\/p>\n<p>The time to solve the subproblem in each iteration depends on the subproblem. For explicitly given pure packing or pure covering problems (where <script type=\"math\/tex;\">{\\cal P}<\/script> is the just <script type=\"math\/tex;\">\\{ x~ |~  x\\ge 0\\} <\/script>), the time can (roughly) be reduced to <script type=\"math\/tex;\">O(1)<\/script> per iteration\u00a0<span class=\"cite\">[<a href=\"#Kouf07Beating\">9<\/a>]<\/span>. <\/p>\n<\/div><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000013\">Surrogate duality<\/h1>\n<p> The surrogate relaxation described above is a form of partial linear-programming duality: for any constraint-multiplier vector <script type=\"math\/tex;\">\\alpha <\/script>, the optimal solution to the surrogate relaxation of the problem gives a bound on <span class=\"scshape\" style=\"font-variant:small-caps;text-transform:lowercase\">opt<\/span>. This is a kind of duality called <em>surrogate duality<\/em>. <\/p>\n<p>It often translates directly into standard LP dual solutions. The vector <script type=\"math\/tex;\">\\alpha <\/script> corresponds to a dual solution (for some reformulation of the original LP). For example, recall the surrogate problem for the simple packing problem <script type=\"math\/tex;\">\\max \\{ |x|_1 \\, :\\, Ax \\le \\mathbf1, x\\in {\\mathbb R}_+^n\\} <\/script>. The surrogate is <script type=\"math\/tex;\">\\max \\{ |x|_1 \\, :\\, \\beta \\cdot x \\ge 1, x\\in {\\mathbb R}_+^n\\} ,<\/script> where <script type=\"math\/tex;\">\\beta = \\alpha ^{\\scriptscriptstyle \\sf T}A<\/script>. The surrogate problem is solved by finding the index <script type=\"math\/tex;\">j<\/script> that maximizes <script type=\"math\/tex;\">1\/\\beta _j<\/script>, taking that <script type=\"math\/tex;\">x_j<\/script> to be <script type=\"math\/tex;\">1\/\\beta _j<\/script>, and leaving all other coordinates zero. Since this is the optimal solution for the surrogate problem, which is in turn a relaxation of the original problem, the cost achieved by this <script type=\"math\/tex;\">x<\/script> is an upper bound on <span class=\"scshape\" style=\"font-variant:small-caps;text-transform:lowercase\">opt<\/span>: <\/p>\n<div id=\"a0000000014\" class=\"equation\"><script type=\"math\/tex; mode=display\"> {\\textsc{opt}}~ \\le ~  1\/\\min _j \\beta _j ~ =~  1\/\\min _j \\alpha \\cdot A^{\\scriptscriptstyle \\sf T}_j. <\/script><\/div>\n<p> (Here <script type=\"math\/tex;\">A^{\\scriptscriptstyle \\sf T}_j<\/script> is the <script type=\"math\/tex;\">j<\/script>th column of <script type=\"math\/tex;\">A<\/script>.) <\/p>\n<p>The standard LP dual of the original problem is <script type=\"math\/tex;\">\\min \\{ |y|_1 \\, :\\, A^{\\scriptscriptstyle \\sf T}y \\ge 1, x\\in {\\mathbb R}_+^n\\} <\/script>. We leave it as an exercise to show that scaling the constraint-multiplier vector <script type=\"math\/tex;\">\\alpha <\/script> gives a dual solution <script type=\"math\/tex;\">y<\/script> whose cost (by weak duality) gives the same upper bound on <span class=\"scshape\" style=\"font-variant:small-caps;text-transform:lowercase\">opt<\/span>. (Recall that <script type=\"math\/tex;\">|\\alpha |_1=1<\/script>.) <\/p>\n<\/div><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000015\">Problems having many variables<\/h1>\n<p> Lagrangian-relaxation algorithms can be used for problems with many variables, as long as the surrogate problem can be solved. For example, consider a simple multicommodity-flow problem in feasibility form: <\/p>\n<div id=\"primal\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{equation} \\label{primal}\\textstyle \\mbox{find } f\\in {\\mathbb R}^P \\text{ such that } |f| = 1 \\mbox{ and } \\forall e\\in E.\\,  f(e) \\le \\,  c. \\end{equation}<\/script><\/div>\n<p> There is a, implicitly, a variable for every path <script type=\"math\/tex;\">p\\in P<\/script>. There can be exponentially many, but, applying Lagrangian-relaxation with the capacity constraints as side constraints, the surrogate problem that arises is this: for a given <script type=\"math\/tex;\">\\alpha <\/script> (with <script type=\"math\/tex;\">|\\alpha |_1=1<\/script>), <\/p>\n<div id=\"surrogate\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{equation} \\label{surrogate}\\textstyle \\mbox{find } f\\in {\\mathbb R}^P \\text{ such that } |f| = 1 \\mbox{ and } \\sum _{e\\in E} \\alpha _e f(e)\\,  \\le \\,  c. \\end{equation}<\/script><\/div>\n<p> The solution (if it exists) will be to send <script type=\"math\/tex;\">1<\/script> unit of flow along a path <script type=\"math\/tex;\">p\\in P<\/script> such that <script type=\"math\/tex;\">\\sum _{e\\in P} \\alpha _e \\le c<\/script>. That is,\u00a0\\eqref{surrogate} is equivalent to <\/p>\n<div id=\"surrogate2\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{equation} \\label{surrogate2}\\textstyle \\mbox{find } p\\in P \\text{ such that } \\sum _{e\\in p} \\alpha _e \\,  \\le \\,  c. \\end{equation}<\/script><\/div>\n<p> Such a path can be found quickly, if it exists, using a shortest-path algorithm. In this way, Lagrangian-relaxation can reduce the multicommodity-flow problem to a (poly-length) sequence of shortest-path problems. <\/p>\n<div class=\"latex-paragraph\">\n<div class=\"latex-paragraph-heading\"> <b>Similarity to column generation.<\/b> <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Column generation is a practical technique with a similar spirit. The idea is that if a problem formulation has many more variables than constraints, one may run the Simplex algorithm, but only explicitly write down columns (variables) that have been brought into the current solution with non-zero values. To do the pivot step at each iteration requires checking whether a new variable (column) should be brought in. <a href=\"http:\/\/en.wikipedia.org\/wiki\/Dantzig-Wolfe_decomposition\">Dantzig-Wolfe decomposition<\/a> explicitly combines this idea with Lagrangian relaxation. <a href=\"http:\/\/en.wikipedia.org\/wiki\/Benders&#x27;_decomposition\">Benders\u2019 decomposition<\/a> brings in rows as needed, instead of columns. <\/p>\n<\/div><\/div>\n<\/div><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000016\">Relation to dual Ellipsoid method<\/h1>\n<p> Recall that the Ellipsoid method uses a \u201cseparation oracle\u201d framework: to try find a feasible point in a convex body <script type=\"math\/tex;\">{\\cal B}<\/script>, the Ellipsoid method supplies a candidate point <script type=\"math\/tex;\">\\tilde\\alpha <\/script> to the separation oracle for <script type=\"math\/tex;\">{\\cal B}<\/script>. The oracle must either determine that <script type=\"math\/tex;\">\\tilde\\alpha <\/script> is in <script type=\"math\/tex;\">{\\cal B}<\/script> (and we are done), or must return a linear constraint that is valid for <script type=\"math\/tex;\">{\\cal B}<\/script> but not for <script type=\"math\/tex;\">\\tilde\\alpha <\/script> (a proof that <script type=\"math\/tex;\">\\tilde\\alpha <\/script> is not in <script type=\"math\/tex;\">{\\cal B}<\/script>), in which case the algorithm continues. Crucially for many applications, the convex body <script type=\"math\/tex;\">{\\cal B}<\/script> may be defined (implicitly) as the intersection of exponentially many constraints. As long as the oracle can find a constraint violated by a given <script type=\"math\/tex;\">\\tilde\\alpha <\/script> (if there is one) in polynomial time, the Ellipsoid method will finish in polynomial time. <\/p>\n<p>Consider applying the separation-oracle framework to the <em>dual<\/em> of the problem\u00a0\\eqref{primal} above. One dual formulation (after appropriate scaling) is <\/p>\n<div id=\"dual\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{equation} \\label{dual}\\textstyle \\mbox{find } \\alpha \\in {\\mathbb R}^m \\text{ such that } |\\alpha |_1 = 1 \\mbox{ and } \\forall p\\in P.\\,  \\sum _{e\\in p} \\alpha _e \\gt c. \\end{equation}<\/script><\/div>\n<p> (Note that the last inequality is strict.) This dual is feasible iff the primal is infeasible. <\/p>\n<p>Take the polytope <script type=\"math\/tex;\">{\\cal B}<\/script> to be the set of <script type=\"math\/tex;\">\\alpha <\/script>\u2019s meeting the constraints in\u00a0\\eqref{dual}, then apply Ellipsoid. For this polytope, Ellipsoid will give the separation oracle a candidate <script type=\"math\/tex;\">\\alpha <\/script>. To determine whether <script type=\"math\/tex;\">\\alpha <\/script> is feasible for <script type=\"math\/tex;\">{\\cal B}<\/script>, the separation oracle can check directly that <script type=\"math\/tex;\">|\\alpha |_1=1<\/script>. Determining whether the remaining constraints are feasible is equivalent to solving the surrogate problem\u00a0\\eqref{surrogate2}. <\/p>\n<p>Generally, whenever one can apply Ellipsoid to solve a given packing or covering problem using a particular separation oracle, then it is also possible to solve the problem by applying Lagrangian relaxation to the dual: the surrogate problem that arises will be the one solved by the separation oracle. The converse is also true. <\/p>\n<\/div><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000017\">Machine learning<\/h1>\n<p> Some types of Lagrangian-relaxation algorithms are closely related to <em>multiplicative-weights update algorithms<\/em> from machine learning, which play a role in <em>boosting<\/em> and <em>following expert advice<\/em> with low regret. Boosting reduces the problem of strongly learning a concept to a sequence of problems of weakly learning the concept against some distribution <script type=\"math\/tex;\">\\alpha <\/script>. Technically, this reduction corresponds to the reduction done by Lagrangian-relaxation algorithms, reducing a hard problem to a sequence of surrogate problem. See\u00a0<span class=\"cite\">[<a href=\"#Freund99Adaptive\">3<\/a>]<\/span> for more details. <\/p>\n<p>Lagrangian-relaxation algorithms can also be interpreted as <em>fictitious-play algorithms<\/em> for two-player zero-sum games with non-negative payoffs. <\/p>\n<\/div>\n<div class=\"latex-section\">\n<h1 id=\"a0000000018\">Differential equations and Lyapunov functions<\/h1>\n<p> Lagrangian-relaxation algorithms may be thought of as gradient-descent algorithms, at least in that each step is chosen to augment the current solution in a direction parallel to some coordinate axis, and along which the potential-function change is suitably bounded. <\/p>\n<p>Making the step size <script type=\"math\/tex;\">\\varepsilon <\/script> infinitesmal gives a continuous-time algorithm. The resulting system avoids the discrete step, so is easier to study than a discrete algorithm: it can be modeled as a system of differential equations, where the potential function of the algorithm becomes a Lyapunov function for the system. Such systems are deeply studied in <a href=\"http:\/\/www.cds.caltech.edu\/~murray\/amwiki\/\">control theory<\/a>\u00a0<span class=\"cite\">[<a href=\"#astrom2008feedback\">2<\/a>]<\/span>, and are used to analyze congestion-control mechanisms <span class=\"cite\">[<a href=\"#low2002internet\">11<\/a>, <a href=\"#kelly2001mathematical\">7<\/a>, <a href=\"#garg2002line\">5<\/a>]<\/span>. <\/p>\n<\/div><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000019\">Oblivious randomized rounding<\/h1>\n<p> Many of the notes here explore the following connection between greedy\/Lagrangian-relaxation algorithms and randomized rounding: Lagrangian-relaxation algorithms can be understood as randomized-rounding algorithms, and can be systematically derived using the method of conditional expectations. In this view, the algorithms and their underlying potential functions are derived using standard probabilistic tools. The potential functions are \u201cgiven meaning\u201d as conditional expectations or pessimistic estimators. <\/p>\n<\/div>\n<div class=\"latex-section\">\n<h1 id=\"a0000000020\">Related<\/h1>\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/greedy-example\">The greedy set-cover algorithm<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/obliv\">Using randomized rounding to derive greedy and Lagrangian-relaxation algorithms<\/a> <\/p>\n<\/li>\n<\/ul>\n<p>Lagrangian-relaxation algorithms have a long history. They were analyzed as early as the 1950s (e.g., by von Neumann <span class=\"cite\">[<a href=\"#vonNeumann63Review\">10<\/a>]<\/span>). Their main historical use has been to reduce a hard problem (such as multicommodity flow) to a sequence of simpler problems (such as shortest paths). For a brief summary of their history within computer science, see\u00a0<span class=\"cite\">[<a href=\"#Klein99Number\">8<\/a>]<\/span>. See also the technical survey\u00a0<span class=\"cite\">[<a href=\"#arora2005mwu\">1<\/a>]<\/span>. For an operations-research perspective, see\u00a0<span class=\"cite\">[<a href=\"#todd2002mfl\">13<\/a>]<\/span>. <\/p>\n<div class=\"latex-subsubsection\">\n<h3 id=\"a0000000021\">On Wikipedia<\/h3>\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Lagrangian_relaxation\">Lagrangian relaxation<\/a>, <a href=\"http:\/\/en.wikipedia.org\/wiki\/Lagrange_multiplier\">Lagrange multiplier<\/a>, <a href=\"http:\/\/en.wikipedia.org\/wiki\/Trust_region\">Trust region<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Column_generation\">Column generation<\/a>, <a href=\"http:\/\/en.wikipedia.org\/wiki\/Dantzig-Wolfe_decomposition\">Dantzig-Wolfe decomposition<\/a>, <a href=\"http:\/\/en.wikipedia.org\/wiki\/Benders%27_decomposition\">Benders\u2019 decomposition<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Ellipsoid_method\">Ellipsoid method<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Winnow_algorithm\">the Winnow algorithm<\/a> and <a href=\"http:\/\/en.wikipedia.org\/wiki\/AdaBoost\">AdaBoost<\/a> (multiplicative-weights algorithms in machine learning) <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Fictitious_play\">Fictitious play<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Lyapunov_function\">Lyapunov function<\/a>, <a href=\"http:\/\/en.wikipedia.org\/wiki\/Network_congestion#Congestion_control\">Congestion control<\/a>, <a href=\"http:\/\/www.cds.caltech.edu\/~murray\/amwiki\/\">control theory (Caltech)<\/a> <\/p>\n<\/li>\n<\/ul>\n<\/div>\n<\/div><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div>\n<h1 id=\"bibliography\">Bibliography<\/h1>\n<table class=\"bibliography\" cellspacing=\"0\" cellpadding=\"2\">\n<tr>\n<td valign=\"top\">[<a name=\"arora2005mwu\">1<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;S+Arora&quot;+author:&quot;+E+Hazan&quot;+author:&quot;+&quot;+author:&quot;+S+Kale&quot;+intitle:&quot;+The+multiplicative+weights+update+method:+a+meta-algorithm+and+applications&quot;\">S.\u00a0Arora, E.\u00a0Hazan, and S.\u00a0Kale. The multiplicative weights update method: a meta-algorithm and applications. <em>Theory of Computing<\/em>, 8(1):121\u2013164, 2012. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"astrom2008feedback\">2<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;K+strom+&quot;+author:&quot;+R+Murray&quot;+intitle:&quot;+Feedback+systems:+an+introduction+for+scientists+and+engineers&quot;\">K.\u00a0str\u00f6m and R.\u00a0Murray. <em>Feedback systems: an introduction for scientists and engineers<\/em>. Princeton University Press, 2008. Online at <a href=\"http:\/\/www.cds.caltech.edu\/~murray\/amwiki\">http:\/\/www.cds.caltech.edu\/<script type=\"math\/tex;\">\\sim <\/script>murray\/amwiki<\/a>. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"Freund99Adaptive\">3<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;Y+Freund+&quot;+author:&quot;+R+E++Schapire&quot;+intitle:&quot;+Adaptive+game+playing+using+multiplicative+weights&quot;\">Y.\u00a0Freund and R.\u00a0E. Schapire. Adaptive game playing using multiplicative weights. <em>Games and Economic Behavior<\/em>, 29:79\u2013103, 1999. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"garg2007faster\">4<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;N+Garg+&quot;+author:&quot;+J+Konemann&quot;+intitle:&quot;+Faster+and+simpler+algorithms+for+multicommodity+flow+and+other+fractional+packing+problems&quot;\">N.\u00a0Garg and J.\u00a0K\u00f6nemann. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. <em>SIAM Journal on Computing<\/em>, 37:630, 2007. Preliminary version in FOCS\u201998 (pp.\u00a0300\u2013309). <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"garg2002line\">5<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;N+Garg+&quot;+author:&quot;+N+Young&quot;+intitle:&quot;+On-line+end-to-end+congestion+control&quot;\">N.\u00a0Garg and N.\u00a0Young. On-line end-to-end congestion control. In <em>Foundations of Computer Science, 2002. Proceedings. The 43rd Annual IEEE Symposium on<\/em>, pages 303\u2013310. IEEE, 2002. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"Grigoriadis01Approximate\">6<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;M+D++Grigoriadis&quot;+author:&quot;+L+G++Khachiyan&quot;+author:&quot;+L+Porkolab&quot;+author:&quot;+&quot;+author:&quot;+J+Villavicencio&quot;+intitle:&quot;+Approximate+max-min+resource+sharing+for+structured+concave+optimization&quot;\">M.\u00a0D. Grigoriadis, L.\u00a0G. Khachiyan, L.\u00a0Porkolab, and J.\u00a0Villavicencio. Approximate max-min resource sharing for structured concave optimization. <em>SIAM Journal on Optimization<\/em>, 11:1081\u20131091, 2001. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"kelly2001mathematical\">7<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;F+Kelly&quot;+intitle:&quot;+Mathematical+modelling+of+the+internet&quot;\">F.\u00a0Kelly. Mathematical modelling of the internet. <em>Mathematics Unlimited-2001 and Beyond<\/em>, pages 685\u2013702, 2001. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"Klein99Number\">8<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;P+Klein+&quot;+author:&quot;+N+E++Young&quot;+intitle:&quot;+On+the+number+of+iterations+for+Dantzig-Wolfe+optimization+and+packing-covering+approximation+algorithms&quot;\">P.\u00a0Klein and N.\u00a0E. Young. On the number of iterations for Dantzig-Wolfe optimization and packing-covering approximation algorithms. <em>Lecture Notes in Computer Science<\/em>, 1610:320\u2013327, 1999. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"Kouf07Beating\">9<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;C+Koufogiannakis+&quot;+author:&quot;+N+E++Young&quot;+intitle:&quot;+Beating+simplex+for+fractional+packing+and+covering+linear+programs&quot;\">C.\u00a0Koufogiannakis and N.\u00a0E. Young. Beating simplex for fractional packing and covering linear programs. In <em>Forty Eighth Annual Symposium on Foundations of Computer Science<\/em>, Providence, Rhode Island, 21\u201323\u00a0Oct. 2007. IEEE. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"vonNeumann63Review\">10<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;H+W++Kuhn+&quot;+author:&quot;+A+W++Tucker&quot;+intitle:&quot;+Review+of+A+numerical+method+for+determination+of+the+value+and+the+best+strategies+of+a+zero-sum+two-person+game+with+large+numbers+of+strategies,+by+John+von+Neumann&quot;\">H.\u00a0W. Kuhn and A.\u00a0W. Tucker. Review of \u2018A numerical method for determination of the value and the best strategies of a zero-sum two-person game with large numbers of strategies\u2019, by John von Neumann. In <em>John von Neumann: Collected Works<\/em>, volume\u00a0VI, pages 96\u201397. Pergamon Press, 1963. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"low2002internet\">11<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;S+Low&quot;+author:&quot;+F+Paganini&quot;+author:&quot;+&quot;+author:&quot;+J+Doyle&quot;+intitle:&quot;+Internet+congestion+control&quot;\">S.\u00a0Low, F.\u00a0Paganini, and J.\u00a0Doyle. Internet congestion control. <em>Control Systems Magazine, IEEE<\/em>, 22(1):28\u201343, 2002. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"Plotkin95Fast\">12<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;S+A++Plotkin&quot;+author:&quot;+D+B++Shmoys&quot;+author:&quot;+&quot;+author:&quot;+E+Tardos&quot;+intitle:&quot;+Fast+approximation+algorithms+for+fractional+packing+and+covering+problems&quot;\">S.\u00a0A. Plotkin, D.\u00a0B. Shmoys, and E.\u00a0Tardos. Fast approximation algorithms for fractional packing and covering problems. <em>Math. Operations Research<\/em>, 20(2):257\u2013301, 1995. Preliminary version in FOCS\u201991. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"todd2002mfl\">13<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;M+J++Todd&quot;+intitle:&quot;+The+many+facets+of+linear+programming&quot;\">M.\u00a0J. Todd. The many facets of linear programming. <em>Mathematical Programming<\/em>, 91(3):417\u2013436, 2002. <\/a><\/td>\n<\/tr>\n<\/table><\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>A brief yet long-winded discussion of Lagrangian-relaxation algorithms. \u00a0<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":8676,"menu_order":8,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-2145","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/2145","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/comments?post=2145"}],"version-history":[{"count":0,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/2145\/revisions"}],"up":[{"embeddable":true,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8676"}],"wp:attachment":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/media?parent=2145"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}