CS261 Lecture 6: Duality in Linear Programming | in theory
In which we introduce the theory of duality in linear programming. 1. The Dual of Linear Program Suppose that we have the following linear program in maximization standard form: $latex \displaystyl…
In which we introduce the theory of duality in linear programming. 1. The Dual of Linear Program Suppose that we have the following linear program in maximization standard form: and that an LP-solver has found for us the solution , , , of cost . How can we convince ourselves, or another user, that the solution is indeed optimal, without having to trace the steps of the computation of the algorithm? Observe that if we have two valid inequalities then we can deduce that the inequality (derived by “summing the left hand sides and the right hand sides” of our original inequalities) is
Explore this link on the map →related reading
- CS261 Lecture 5: Linear Programming | in theorylucatrevisan.wordpress.com
- bv_cvxbook.pdfweb.stanford.edu
- Deriving Muonjeremybernste.in
- bv_cvxbook.pdfstanford.edu
- Pen and Paper Exercises in Machine Learningarxiv.org
- [2410.21265] Modular Duality in Deep Learningarxiv.org
- https://www.deeplearningbook.org/contents/linear_algebra.htmldeeplearningbook.org
- prox_algs.pdfweb.stanford.edu
- Mathematical optimization - Wikipediaen.wikipedia.org
- Minimax theorem - Wikipediaen.wikipedia.org
- A Neural Network Framework for Discovering Closed-form Solutions to Quadratic Programs with Linear Constraintsarxiv.org
- Dual graph - Wikipediaen.wikipedia.org