Duality and Lagrange Multipliers in General Optimization

Nicholas Ruozzi from the University of Texas at Dallas discusses duality and Lagrange multipliers in general optimization problems. The lecture covers the minimization of a function subject to constraints and introduces the Lagrangian as a key concept. By formulating the Lagrangian, optimal solutions can be found using the method of Lagrange multipliers to optimize functions with constraints, transforming the original problem into an unconstrained one.

• General Optimization
• Lagrange Multipliers
• Constraints
• University of Texas

brandon Follow

Uploaded on Jul 16, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Lecture 6: Duality and Lagrange Multipliers Nicholas Ruozzi University of Texas at Dallas

2. General Optimization min ? ??0(?) subject to: ??? 0, ?? = 0, ? = 1, ,? ? = 1, ,? 2

3. Lagrangian ? ? ? ?,?,? = ?0? + ????? + ?? ?(?) ?=1 ?=1 Incorporate constraints into a new objective function ? 0 and ? are vectors of Lagrange multipliers The Lagrange multipliers can be thought of as enforcing soft constraints 3

4. Example max ?,? ?? subject to: ? + ? = 1 4

5. Example max ?,? ?? subject to: ? + ? = 1 ? ?,?,?1 = ?? + ?1 1 ? ? 5

6. Example max ?,? ?? subject to: ? + ? = 1 ? ?,?,?1 = ?? + ?1 1 ? ? ?? ?= ? ?1= 0 ?? ?= ? ?1= 0 ?? ?1 = 1 ? ? = 0 6

7. Example max ?,? ?? subject to: ? + ? = 1 ? ?,?,?1 = ?? + ?1 1 ? ? ? = ? ? + ? = 1 7

8. Example max ?,? ?? subject to: ? + ? = 1 ? ?,?,?1 = ?? + ?1 1 ? ? ? = ? ? + ? = 1 ? = ? = .5 is the only critical point of ? 8

9. Necessary Conditions min ? ??0(?) subject to: ?? = 0, ? = 1, ,? Theorem: if ? is a local minimum of the constrained optimization problem and 1? , , ?(? ) are linearly independent, then there exists a ? ? such that ? ? ,? = 0 9

10. Duality Construct a dual function by minimizing the Lagrangian over the primal variables ? ?,? = inf ??(?,?,?) ? ?,? = whenever the Lagrangian is not bounded from below for a fixed ? and ? 10

11. Example: Projection Projection of the point ? ?onto box constraints 1 2 subject to: 2 min ? ? ? ?2 ? ? ? ? 11

12. Example: Projection Projection of the point ? ?onto box constraints 1 2 subject to: 2 min ? ? ? ?2 ? ? ? ? ? ?,?,? 1 2 2+ = ?? ?? ?? ?? ?? + ?? ?? ?? ? ? ? 12

13. Example: Projection Projection of the point ? ?onto box constraints 1 2 subject to: 2 min ? ? ? ?2 ? ? ? ? ? ?,?,? 1 2 2+ = ?? ?? ?? ?? ?? + ?? ?? ?? ? ? ? ?? ?? = ?? ?? ??+ ??= 0 13

14. Example: Projection Projection of the point ? ?onto box constraints 1 2 subject to: 2 min ? ? ? ?2 ? ? ? ? ? ?,? 1 2 2+ = ?? ?? ?? ?? ?? ??+ ?? ? ? + ?? ??+ ?? ?? ?? ? 14

15. Example: Projection Projection of the point ? ?onto box constraints 1 2 subject to: 2 min ? ? ? ?2 ? ? ? ? ? ?,? 1 2 2+ ?? 2 = ?? + ?? ?? ?? + ?? ?? ?? ? ? ? 15

16. The Primal Problem min ? ??0(?) subject to: ??? 0, ?? = 0, ? = 1, ,? ? = 1, ,? Equivalently, inf ? sup ? 0,??(?,?,?) Why are these equivalent? 16

17. The Primal Problem min ? ??0(?) subject to: ??? 0, ?? = 0, ? = 1, ,? ? = 1, ,? Equivalently, inf ? sup ? 0,??(?,?,?) ? ? sup ? 0,? ?0? + ????? + ?? ?(?) = ?=1 ?=1 whenever ? violates the constraints 17

18. The Dual Problem sup ? 0,??(?,?) Equivalently, sup ? 0,?inf ??(?,?,?) The dual problem is always concave, even if the primal problem is not convex For each ?, ?(?,?,?) is a linear function in ? and ? Minimum (or infimum) of concave functions is concave! (equivalent to sup of convex functions convex) 18

19. Primal vs. Dual Dual bounded from above by Primal sup ? 0,?inf ??(?,?,?) inf sup ? 0,??(?,?,?) ? Proof: ? ?,? = inf ? ?(? ,?,?) ?(?,?,?) for all ? 19

20. Primal vs. Dual Dual bounded from above by Primal sup ? 0,?inf ??(?,?,?) inf sup ? 0,??(?,?,?) ? Proof: ? ?,? = inf ? ?(? ,?,?) ?(?,?,?) for all ? ? ? ,?,? ?0(? ) for any feasible ? , ? 0 ? ? ? ?,?,? = ?0? + ????? + ?? ?(?) ?=1 ?=1 20

21. Primal vs. Dual Dual bounded from above by Primal sup ? 0,?inf ??(?,?,?) inf sup ? 0,??(?,?,?) ? Proof: ? ?,? = inf ? ?(? ,?,?) ?(?,?,?) for all ? ? ? ,?,? ?0(? ) for any feasible ? , ? 0 0 0 ? ? ? ?,?,? = ?0? + ????? + ?? ?(?) ?=1 ?=1 21

22. Primal vs. Dual Dual bounded from above by Primal sup ? 0,?inf ??(?,?,?) inf sup ? 0,??(?,?,?) ? Proof: ? ?,? = inf ? ?(? ,?,?) ?(?,?,?) for all ? ? ? ,?,? ?0(? ) for any feasible ? , ? 0 Let ? be the optimal solution to the primal problem and ? 0 ? ?,? ? ? ,?,? ?0? 22

23. Example: Projection Projection of the point ? ?onto box constraints 1 2 subject to: 2 min ? ? ? ?2 ? ? ? ? ? ?,? 1 2 2+ ?? 2 = ?? + ?? ?? ?? + ?? ?? ?? ? ? ? 23

24. Example: Projection Projection of the point ? ?onto box constraints 1 2 subject to: 2 min ? ? ? ?2 ? ? ? ? ? ?,? 1 2 2+ ?? 2 = ?? + ?? ?? ?? + ?? ?? ?? ? ? ? ?? ?? ?? = ??+ ?? ??= 0 ?? ?? ?? ??= 0 24

25. Example: Projection Projection of the point ? ?onto box constraints 1 2 subject to: 2 min ? ? ? ?2 ? ? ? ? ? ?,? 1 2 2+ ?? 2 = ?? + ?? ?? ?? + ?? ?? ?? ? ? ? ?? ?? ?? = ??+ ?? ??= 0 ?? ?? ?? ??= 0 25

26. Example: Projection Projection of the point ? ?onto box constraints 1 2 subject to: 2 min ? ? ? ?2 ? ? ? ? ? ?,? 1 2 2+ ?? 2 = ?? + ?? ?? ?? + ?? ?? ?? ? ? ? 0,if ?? ?? ?? ??,if ??< ?? 0,if ?? ?? ?? ??,if ??> ?? ??= ??= 26

27. Example: Projection Projection of the point ? ?onto box constraints 1 2 subject to: 2 min ? ? ? ?2 ?? ?? ? ? ? ? = ?? ?? ??+ ??= 0 ? ?,?,? 1 2 2+ = ?? ?? ?? ?? ?? + ?? ?? ?? ? ? ? ??,if ?? ?? ?? ??,if ??< ?? ??,if ??> ?? ??= 27

28. Example: LP Duality ? ???? max subject to: ?? ? ? 0 28

29. ????? max subject to: ?? ? ? 0 29

30. ????? max subject to: ?? ? ? 0 30

31. Example: Project on a Line Projection of the point ? ?onto ?(?) = ? + ?? 1 2 subject to: ? = ? + ?? 2 min ? ?2 ? ?,? 31

32. Projection of the point ? ?onto ?(?) = ? + ?? 1 2 2 min ? ?2 ? ?,? subject to: ? = ? + ?? 32

33. Projection of the point ? ?onto ?(?) = ? + ?? 1 2 2 min ? ?2 ? ?,? subject to: ? = ? + ?? 33

34. Quick Recap Primal: Primal: min ? ??0(?) inf ? sup ? 0,??(?,?,?) subject to: ??? 0, ?? = 0, ? = 1, ,? ? = 1, ,? Lagrangian Lagrangian: : ? ? ? ?,?,? = ?0? + ????? + ?? ?(?) ?=1 ?=1 Dual: ? ?,? = inf ? ?(?,?,?) , ? 0 Weak Duality: sup ? 0,?inf ? ? ?,?,? inf sup ? 0,??(?,?,?) ? 34

35. Strong Duality Under certain conditions, the two optimization problems are equivalent sup ? 0,?inf ??(?,?,?) = inf sup ? 0,??(?,?,?) ? This is called strong duality Conditions on the constraint that guarantee this are called constraint qualifications If the inequality is strict, then we say that there is a duality gap Size of gap measured by the difference between the two sides of the inequality 35

36. Slaters Condition For any optimization problem of the form min ? ??0(?) subject to: ??? 0, ? = 1, ,? ?? = ? where ?0, ,??are convex functions, strong duality holds if there exists an ? such that ??? < 0, ? = 1, ,? ?? = ? 36

37. Complementary Slackness Suppose that there is zero duality gap Let ? be an optimum of the primal and (? ,? ) be an optimum of the dual ?0? = ? ? ,? ? ? ??? + ?(?) = inf ?0? + ?? ?? ? ?=1 ?=1 ? ? ??? + ?? ?0? + ?? ?? ?=1 ? ?=1 ??? = ?0? + ?? ?=1 ?0? 37

38. Complementary Slackness ? ??? = 0 ?? ?=1 As ? 0 and ???? ?? 0, this can only happen if ??? = 0 for all ? If ??? < 0, then ?? = 0 If ?? > 0, then ??(? ) = 0 ONLY applies when there is no duality gap 38

39. Example: Projection Projection of the point ? ?onto box constraints 1 2 subject to: 2 min ? ? ? ?2 ? ? ? ? ? ?,?,? 1 2 2+ = ?? ?? ?? ?? ?? + ?? ?? ?? ? ? ? Comp. Slack.: ??< ?? ??= 0 ??> ?? ??= 0 ??> 0 ??= ?? ??> 0 ??= ?? 39

40. Example: Slack Variables ?,??2+ ?2 min subject to: ? + ? 1 40

41. Example: Slack Variables ?,?,??2+ ?2 min subject to: ? + ? = 1 ? ? 0 41

42. ?,?,??2+ ?2 min subject to: ? + ? = 1 ? ? 0 42

43. Example: Comp. Slack. Utility ? ,? ?? min subject to: ? ? ? 0 43

44. Other Duality Notes Strong duality always holds for linear programming problems (with finite solutions)! Max-flow is dual to minimum cut (from algorithms) Bipartite matching is dual to bipartite vertex cover (Konig s Theorem) 44

45. Karush-Kuhn-Tucker Conditions If there is zero duality gap, then the following are necessary and sufficient conditions for ? and ? ,? to be solutions of the primal and dual problems ??(? ,? ,? ) = 0 critical point of Lagrangian For all ?,??? 0 primal feasibility For all ?, ?? = 0 0 For all ?, ?? dual feasibility ??? = 0 For all ?, ?? complementary slackness 45

46. Karush-Kuhn-Tucker Conditions If there is zero duality gap, then the following are necessary and sufficient conditions for ? and ? ,? to be solutions of the primal and dual problems ??(? ,? ,? ) = 0 can be replaced with the requirement that zero be an element of the subgradient for nondifferentiable functions For all ?,??? 0 For all ?, ?? = 0 0 For all ?, ?? ??? = 0 For all ?, ?? 46

47. Example: Quadratic Minimization 1 2???? + ??? min ? ? subject to: ?? = ? Convex and strong duality as long as there exists a feasible point and ?is positive semidefinite (from Slater s condition) 47

48. Example: Quadratic Minimization 1 2???? + ??? min ? ? subject to: ?? = ? Convex and strong duality as long as there exists a feasible point and ?is positive semidefinite (from Slater s condition) KKT conditions imply: ? ? = ? ? ?? 0 ? ? Only need to solve a linear system! 48

49. What Can Go Wrong? Dual can be degenerate Dual function is equal to Could be a (large) duality gap Solving the dual problem does not yield a solution to the primal Small duality gaps can sometimes can be turned into approximation schemes 49

50. Example: Degenerate Dual ?,? ?2 ?2 min subject to: 1 ? 1 1 ? 1 50

Load More ...