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

related reading

• CS261 Lecture 5: Linear Programming | in theorylucatrevisan.wordpress.com
• svm_dual_kernelcs.cmu.edu
• Pen and Paper Exercises in Machine Learningarxiv.org
• The Art of Linear Programmingyoutube.com
• eecs127_reader.pdfeecs127.github.io
• [2410.21265] Modular Duality in Deep Learningarxiv.org
• Mathematical optimization - Wikipediaen.wikipedia.org
• https://www.deeplearningbook.org/contents/linear_algebra.htmldeeplearningbook.org
• 142_Luenberger.pdfsites.science.oregonstate.edu
• prox_algs.pdfweb.stanford.edu
• CS231n Deep Learning for Computer Visioncs231n.github.io
• Universal Complexity Bounds for Universal Gradient Methods in Nonlinear Optimizationarxiv.org