Convex Optimization Duality

cse203b convex optimization chapter 5 duality n.w
1 / 37
Embed
Share

Explore the concept of duality in convex optimization with discussions on primal and dual problems, Lagrangian functions, sensitivity analysis, and examples in linear programming. Understand the primal-dual conversion procedure, KKT conditions, and shadow-price interpretation within the realm of generalized inequalities.

  • Optimization
  • Duality
  • Convex
  • Programming
  • Sensitivity
rayaanacharya
kwill Follow

Uploaded on | 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. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download 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.

E N D

Presentation Transcript

  1. CSE203B Convex Optimization: Chapter 5 Duality CK Cheng Dept. of Computer Science and Engineering University of California, San Diego 1

  2. Chapter 5 Duality Primal and Dual Problem (Mechanism) Primal Problem Lagrangian Function Lagrange Dual Problem Examples (Primal Dual Conversion Procedure) Linear Programming Quadratic Programming Conjugate Functions (Duality) Entropy Maximization Interpretation (Duality) (Theory) Saddle-Point Interpretation Geometric Interpretation Slater s Condition Shadow-Price Interpretation KKT Conditions (Optimality Conditions) Sensitivity (Shadow-Price) (Perturbation) Generalized Inequalities 2

  3. Duality Primal Problem (Solution ? is feasible) min ?0(?)? ?? ?.?. ??? 0 ? = 1, ,? ?? = 0 ? = 1, ,? Notation: Opt: ? ,? = ?0? ?????? ? = ??? ?0 ? ??? ?? ???? ? Lagrangian: ?:?? ?? ?? ? ? ?,?,? = ?0? + ?=1 ??,??:???????? ??????????,??, ?+,?? ?. ? ?????(?) + ?=1 ?? ?(?) Lagrange dual function (Solution ? may not be feasible) g ?,? = inf ? ?? ?,?,? Dual Problem ?,? ?? ????,? ? ?,? ?.?.? ?+ 3

  4. Duality Dual Problem (Solution ? may not be feasible) ????,? ? ?,? ?.?.? 0 1. ? ?,? ?? ??????? 2. ? ?,? ? an optimal value where ? 0 Proof 1: By definition of ? ?,? and the convexity of pointwise max operation on convex functions. Proof 2: For any feasible ? and ? 0 ?0 ? ? ?,?,? (Because ???? ? + ?? ?( ?) 0) ? ?,?,? ?(?,?) by definition of ?(?,?) Thus ? = ?0? ?(?,?) 4

  5. Example: Linear Programming Prime: ??? ??? ??????? ?? ?? ? ?? ? 0 ? 0 ? 0 Lagrangian ? ?,? = ??? + ?? ? ? = inf ??? ? ??? ?? + ???? ???+ ???, ??,??? 0 ??(?,?) ????+ ? 0 (???? ???+ ? = 0) ?? ?????? (???? ???+ ? 0) ?? = ?? ? ? = ????, , Dual: max ???? (??? ????) ??????? ?? ????+ ? 0 ?? 0 5

  6. Example: Linear Programming ?1 ?2 3 0 Prime: min 1 1 ?1 ?2 1 1 3 subject to 2 ?1 ?2 Dual: m?? 3 2 ?1 ?2 1 3 1 0 0 + 1 subject to 0 1 ?1,?2 0 Results: ?1 ?2= ?1 ?2= 1/3 2 1/3, ? = 7 3 2/3, ? = 7 3 6

  7. Example: Linear Programming ??? ??? ??????? ?? ?? = ?, ? 0, (?? ? 0) Lagrangian: ? ?,?,? = ??? + ?? ? + ???? ? = ??? + ? + ??? ??? Lagrange Dual: ? ?,? = inf ??(?,?,?) 1. If ??? ? + ? = 0 ? ?,? = ??? 2. Else ? ?,? = Properties: 1. ? is linear on affine domain ?,? ??? ? + ? = 0 , hence concave. 2. If ? 0 ??? + ? 0 ? ??? ?? ??? + ? 0 max ??? ??? + ? 0 max ??? ??? ? or 7

  8. Example: Quadratic Programming ??? ??? ??????? ?? ?? = ? Lagrangian: ? ?,? = ??? + ???? ? To minimize ? over ?, we set ??? ?,? = 2? + ??? = 0 ? = 1 Lagrange Dual Function: ? ? = ? ? = 1 2??? (1) 2???,? = 1 4?????? ??? A concave function of ? Lower Bound Property: To maximize ? ? ,we set? = 2 ??? 1? Thus,we have ? ? = 1 ? 1 4?????? ???, ? 4?????? ??? = ????? 1? (2) ? = ????? 1? ? = ? ?? = ????? 1? (3) (3) From From (1) (1) and and (2) (2), we have , we have 8

  9. Example: Quadratic Program Quadratic Program ??? ???? ?.?. ?? ? Lagrange Dual Function: g ? = min = 1 Dual Problem: max 1 ?.?. ? 0 ? ? ?++ ???? + ??(?? ?) ? 4???? 1??? ??? 4???? 1??? ??? 9

  10. Example: Quadratic Program (nonconvex prob.) ??? ???? + 2??? ?.?. ??? 1 Dual Function: g ? = min Unbounded below if ? + ?? 0 or if ? + ?? 0 & ? ?(? + ??) Minimized by ? = A + ??+? Otherwise g ? = ??? + ??+? ? Dual Problem: ? ??,? 0 ??? + ?? ? + 2??? ? ? ??? ??? + ??+? ? ?.?. ? + ?? ? ? ?(? + ??) ??? ? ? ? + ?? ? ? ?.?. ? ? ? ?? ? ? ? ? + ??+? ? ? + ?? ?? ? ? ? ? ? + ??+? ? + ?? ? ? ??? + ??+? + ? ? 10

  11. Example: Discrete Problem Two-Way Partitioning Problem Primal: ??? ???? ?.?. ?? ?.?. ?? 1,1 , ???? = ????????? Not a convex opt problem (Partitioning is an NP complete problem) We can assume that ? ?? (???? =1 Lagrangian: ? ?,? = ???? + ?=1 ??(?2 Lagrange dual function: ???? + ???? ? ? ??? = ???, ? ??,??? ? ? = 1, ,? 2= 1 2???? +1 2????? =1 2??? + ???) ? 2 1) = ??? + ???? ? ? ??? ? + ???? ? 0 ?? ?????? ? ? = inf , 11

  12. Example: Discrete Problem Dual: ??? ? ? = ??? ?.?. ? + ???? ? 0 Solution ? = ????? 1 ? ? = 1?? = ?????? 12

  13. Examples: Conjugate Function min?0(?) ?.?. ?? ? ?? = ? Dual function ? ?,? = inf ? ????0(?0? + ???? ? + ???? ? ) inf ? ????0(?0? + ??? + ????? b? ???) = ?0 ??? ??? ??? ??? Where ?0 ? = max = Conjugate function ? ??????? ?0(?) ??? ??? ?.?. ?? = ? ? ? ??? ??? ?.?. ?? ? ??? ??? ?.?. ??? + ? = ? ? ? ??? ??? ?.?. ??? + ? ? 13

  14. Examples: Entropy Maximization ? ? min?0? = ?=1 ???????, ? ?++ ?.?. ?? ? 1T? = 1 ? Since ?0 ? = ?=1 Thus, the dual function is ? ?,? = ??? ? ?=1 = ??? ? ? ? 1 ?=1 To maximize ? ?,? , we set ? = ??? ?=1 ??? 1,?? ? ?? ? 1 ? ? ?? ??, ai: the ithcolumn of A. ? ? ?? ? ? ?? ?? 1 Dual Problem max ??? log( ?=1 ?.?. ? 0 ??) ? ? ?? 14

  15. Examples: Minimum Volume Covering Ellipsoid ? min?0? = logdet? 1, ? ?++ ?.?. ?? Lagrangian ? ?,? = ??????? 1+ ?=1 ???? 1,? = 1, ,? ????? ???? 1??, ? ?+ ? Lagrange dual function ? ? ? = min ? ?,? ,? ?+ ? Dual Problem max ?????? ?=1?????? ?.?. ?=1?????? ? 1?? + ? ? ? 0,? ?+ 15

  16. Interpretation: Saddle-point max ? ?min ? W ? ?,? min ? ?max ? ??(?,?) max ? ??(?) ? ? = min ?(?,?) 1 2 3 1 2 3 1 2 1 3 ? Example : ? ?,? ? = 1 2 ? = 1, 2, 3 min ? ?? ?,1 = 1 min ? ?? ?,2 = 1 min ? ?? ?,3 = 2 I. z decides first max ? ?min ? ?? ?,? = 1 m?? ? ?? 1,? = 3 m?? ? ?? 2,? = 2 m?? ? ?? 3,? = 3 II. w decides first m?? ? ?max ? ?? ?,? = 2 16

  17. Interpretation: Saddle-point Claim : Result of II > Result of I Given an arbitrary pair ?, ? ? min ? ?? ?, ? ? ?, ? m?? min ? ?? ?, ? m?? Thus m?? ? ?min ? ?? ?,? ?, ? ? ? ?? ?,? ? ?? ?,? min ? ?m?? ? ?? ?,? 17

  18. Interpretation: Saddle-point 1 2 3 1 2 3 1 2 3 1 2 3 Example : ? ?,? ? = ? = 1, 2, 3 min ? ?? ?,1 = 1 min ? ?? ?,2 = 1 min ? ?? ?,3 = 1 max ? ?min m?? ? ?? 1,? = 1 m?? ? ?? 2,? = 2 m?? ? ?? 3,? = 3 m?? ? ?max ? ?? ?,? = 1 ? ?? ?,? = 1 18

  19. Interpretation: Saddle-point 1 2 3 1 2 3 3 1 2 2 3 1 Example : ? ?,? ? = ? = 1, 2, 3 min ? ?? ?,1 = 1 min ? ?? ?,2 = 1 min ? ?? ?,3 = 1 max ? ?min m?? ? ?? 1,? = 3 m?? ? ?? 2,? = 3 m?? ? ?? 3,? = 3 m?? ? ?max ? ?? ?,? = 1 ? ?? ?,? = 3 19

  20. Interpretation: Saddle-point 1 2 3 4 2 3 6 3 5 3 1 2 Example : ? ?,? ? = ? = 1, 2, 3 20

  21. Geometric Interpretation ?????? ?.?.?1? 0 (? 0) ? ? = min ?,? ? ? + ?? ? ? = {(?1? ,??? )|? ?} ? ? = ?? + ? supporting hyperplane to ? that intersects t axis at ? = ?(?) ? 21

  22. Geometric Interpretation ?????? ?.?.?1? 0 (? 0) ? ? = min ?,? ? ? + ?? ? = {(?1? ,??? )|? ?} ? ? ? = ?? + ? supporting hyperplane to ? that intersects t axis at ? = ?(?) ? 22

  23. Geometric Interpretation ?????? ?.?.?1? 0 (? 0) ? ? = min ?,? ? ? + ?? ? = {(?1? ,??? )|? ?} ? ? ? = ?? + ? supporting hyperplane to ? that intersects t axis at ? = ?(?) 23

  24. Geometric Interpretation ?????? ?.?.?1? 0 (? 0) ? ? = min ?,? ? ? + ?? ? = {(?1? ,??? )|? ?} ? ? ? = ?? + ? supporting hyperplane to ? that intersects t axis at ? = ?(?) 24

  25. Duality via Separating Hyperplane Set ? = { ?1? , ,??? , 1? , , ?? ,??? ? ?? ?? ?,? = inf{?| ?,?,? ?,? 0,? = 0} x ? , ? ?????+ ?=1 Lagrangian ? = ?,?,1??,?,? = ?=1 Dual Problem ? ?,? = inf{ ?,?,1?(?,?,?)| ?,?,? ?} ????+ ? Separating hyperplane: Example {(?,?)|??? ?,?1? ?, ? ?} ??,?,? ?, ??,?,? ?, ?, ?, ? ?, ?, ? ?,?,? ? ?,?,? ? ? ?, ? ?,1) Since ? 0, we can have ?,?,1 = ( ? = {(?,?,?)| ? ?,??? ??,? = 1, ,?, ?? = ??,? = 1, ,?,??? ?} 25

  26. Lagrange dual problem ????(?,?) ?.?. ? 0 Properties This is a convex problem. The opt. solution is denoted as ? ? ? = ??? 0 If ??? > 0, it is a weak duality. If ??? = 0, it is a strong duality. relint: relative interior of set D Slater s condition Given that the primal problem is convex, If ??? < 0,? = 1, ,?, ? ?????? ? Then strong duality holds. ?????? ? = ? ? ? ?,? ??? ? ? ??? ???? ? > 0 ? ?,? = {?| ? ? ?} 26 any norm

  27. Shadow Price Interpretation: Food vs. Vitamin Flour protein powder Veg. vitamins A,B,D,E,K Fruits minerals Primal ?????? ?.?. ?? ? ? 0 min?1?1+ ?2?2+ ?3?3 ?11 ?12 ?21 ?22 ?31 ?32 ?13 ?23 ?33 ?1 ?2 ?3 ?????? ?.?. ?? + ? 0 ? 0 ?1 ?2 ?3 ,?i 0, ? m?? ?1?1+ ?2?2+ ?3?3 ?11 ?21 ?12 ?22 ?13 ?23 ?????? ?.?. ??? ? ? 0 Dual ?31 ?32 ?33 ?1 ?2 ?3 ?1 ?2 ?3 ? ?? + ? + ?2 ? ? ?2 ?? + ?2 ? ? ?? + ?1 ?, ?? ???1 ? ? ?,? = ??? + ?1 = ??+ ?1 ??= ?1 Lagrangian ?? 27

  28. Shadow Price Interpretation: Spring Energy & Force ??????1,?2 =1 ?? : potential energy ??> 0 : stiffness constant of spring i ?/2 ?1 0 ? + ?1 ?2 0 ?/2 ? + ?2 0 ???1 2(?1?1 ?1 ?/2 ?1 0 ?2 ? + ?1 ?2 0 ?3 ?/2 ? + ?2 0 ?1?/2 ?1 = 0,?2? ?2+ ?1 = 0,?3?/2 ? + ?2 = 0 zero gradient condition ?1?1 ?2(?2 ?1) ?2?2 ?1 ?3(? ?2)+ ?1 ??: contact forces between the walls & blocks 2+1 2+1 2 2?1?1 2?2?2 ?1 2?3? ?2 2+ ?2?2 ?1 2+ ?3? ?2 2) 1 0 1 0 1=0 1+?3 + ?2 28

  29. KKT (Karush-Kuhn-Tucker) Conditions ??? ,? = 1, ,?, ?? , ? = 1, ,? ??? ?????????????? 1. Primal constraints : ??? 0,? = 1, ,?. ?? = 0,? = 1, ,?. 2. Dual constraints : ? 0 3. Complementary slackness : ????? = 0,? = 1, ,?. 4. Gradient of Lagrangian with respect to x variables ???? + ?=1 ? ??? ???? + ?=1 ?? ? ?(?) = 0 29

  30. KKT (Karush-Kuhn-Tucker) Conditions 1. Primal, Lagrangian, and Dual max ?,?min = max ?,??(?,?) ?: ?,?,? ?????(?) ?? 0 ?= 0 ? ?,?,? ? ? = ??? + ????(?) + ?? ? ? ,?? 0 ?=1 (????) ?=1 m?? ? m?? ?,? m?? ?,? min ? 1. Feasibility ?,?,? 2. ? ?,?,? = ??? ?? ??> 0, ??= 0 ??= 0, ?? ??< 0 ?(?,?,?) = ??(?) 3. ? ?,? = min ? Necessary condition for local optimality Sufficient when the problem is convex & satisfy regularity conditions (Slater condition) 30

  31. Sensitivity Perturbed Problem ?????(?) ?.?. ?? ?? ?(?) = ?? ??? ? = ? ?,? ??? ??? ?.?. ? 0 ? ?,? = max Unperturbed Problem ??= ??= 0 max? ?,? ?.?. ? 0 ? 0,0 ,? ,? ?,?? ?,? ??? ??? ? ?,? ? ? ,? ??? ??? = ? 0,0 uT? ??? = ??? Proof : ?? 0,0 ??? ? 0 ? ?? 0,0 ??? ? 0 ? hence, equality ?? ?,? ?? ?,? ??? = ?,? = (0,0), ?? ?? ?,? = (0,0) ? ???,0 ? (0,0) = lim ?? ? ???,0 ? (0,0) = lim ?? 31

  32. Generalized Inequalities Primal ?????(?) ?? ??0,? = 1, ,? ?= 0,? = 1, ,? Lagrangian ? ? ???(?) + ? ?,?,? = ??? + ?? ?? ? ? , ?=1 ?=1 0,? = 1, ,?, ?? ??? ?? ?? Lagrange Dual ?(?,?)= inf ??(?,?,?) 32

  33. Generalized Inequality: KKT Conditions ?????(?) ?.? ?? ??0,? = 1, ,? ?= 0,? = 1, ,? ??? ,? = 1, ,?, ?? , ? = 1, ,? are differentiable 1. Primal constraints : ??? ??0,? = 1, ,?. ?? = 0,? = 1, ,?. 2. Dual constraints : ? ?? 0 ???? = 0,? = 1, ,?. 3. Complementary slackness : ?? 4. Gradient of Lagrangian with respect to x variables ???? + ?=1 ? ??? ? ???? + ?=1 ?? ? ?(?) = 0 33

  34. Generalized Inequalities: SOCP ?????? ??? + ?? Primal ?? + ?,? = 1, ,? 2 ?? ?+ ?? ) ??, ? = 1, ,? i.e. (??? + ??,?? Lagrangian ???? + ?? + ???? ?? + ??) ? ?,?,? = ??? (?? , ? = 1, ,? (??,??) ?? Lagrange Dual ???+ ????) max ?(?? ?? ??, ? = 1, ,? ???+ ????= ? ??? 34

  35. Generalized Inequalities: Semidefinite Program Primal ?????? ?1?1+ + ????+ ? 0,where ?1, ,??,? ?? Lagrangian ?(??? + ?? (?1?1+ + ????+ ? ?)), ? ?+ ? ?,?,? = inf ? Lagrange Dual ?(?,?)= inf ??(?,?,?) Dual max ? ??(??) ?? ??? + ??= 0,? = 1, ,? ? 0 35

  36. Chapter 5 Summary Primal and Dual Problem Primal Problem Lagrangian Function Lagrange Dual Problem Examples (Primal Dual Conversion Procedure) Linear Programming Quadratic Programming Conjugate Functions (Duality) Entropy Maximization Interpretation (Duality) Saddle-Point Interpretation Geometric Interpretation Slater s Condition Shadow-Price Interpretation KKT Conditions (Optimality Conditions) Sensitivity (Shadow-Price) Generalized Inequalities 36

  37. Chapter 5 Summary Duality provides a lower bound of the problem even the primal may not be convex. KKT conditions convert the minimization problem into equations. Lagrange multipliers provide the sensitivity of the constraints. Generalized inequality broadens the scope of convex optimization. 37

Related


Investment and Challenges in Economic Development Workshop

Investment and Challenges in Economic Development Workshop

abdullahi
Heisenberg's Uncertainty Principle in Elementary Quantum Mechanics

Heisenberg's Uncertainty Principle in Elementary Quantum Mechanics

alia
Boolean Algebra: Duality Theorem, De-Morgan's Law, and Don't Care Conditions

Boolean Algebra: Duality Theorem, De-Morgan's Law, and Don't Care Conditions

islarose
Reflections on Slavery: Frederick Douglass's Inner Turmoil

Reflections on Slavery: Frederick Douglass's Inner Turmoil

ruby
Duality and Lagrange Multipliers in General Optimization

Duality and Lagrange Multipliers in General Optimization

brandon
Linear Programming Models for Product-Mix Problems and LP Problem Solutions

Linear Programming Models for Product-Mix Problems and LP Problem Solutions

aodh
Analyzing Power in William Blake's Poem

Analyzing Power in William Blake's Poem "The Tyger

colter
Exploring

Exploring "The Tyger" by William Blake: An Insight into the Poet's Vision

annabell
Exploring the Themes and Symbolism in Dr. Jekyll and Mr. Hyde

Exploring the Themes and Symbolism in Dr. Jekyll and Mr. Hyde

ianis
Unraveling the Enigmatic World of Quantum Mechanics

Unraveling the Enigmatic World of Quantum Mechanics

tianna
Exploring Wave-Particle Duality in Electron Diffraction Experiment

Exploring Wave-Particle Duality in Electron Diffraction Experiment

wisteria
Journey Through Optics: From Ancient Discoveries to Modern Applications

Journey Through Optics: From Ancient Discoveries to Modern Applications

harris
Sensitivity Analysis and LP Duality in Optimization Methods

Sensitivity Analysis and LP Duality in Optimization Methods

sultan
Dual Identities: A Reflection on Duality in Dr. Jekyll and Mr. Hyde

Dual Identities: A Reflection on Duality in Dr. Jekyll and Mr. Hyde

beatriz
Dp-branes, NS5-branes, U-duality, and M-Theory Overview

Dp-branes, NS5-branes, U-duality, and M-Theory Overview

kalani
Nuclear Interactions through Holography and Gauge/Gravity Duality

Nuclear Interactions through Holography and Gauge/Gravity Duality

eaan477
Additive Combinatorics Approach to Log-Rank Conjecture in Communication Complexity

Additive Combinatorics Approach to Log-Rank Conjecture in Communication Complexity

mah_for
Themes of Contrast and Curiosity in

Themes of Contrast and Curiosity in "Dr. Jekyll and Mr. Hyde

tyey205
Sensitivity Analysis and Duality in Linear Programming

Sensitivity Analysis and Duality in Linear Programming

fin_tie
Three-Form Matter and Supergravity in String Compactifications

Three-Form Matter and Supergravity in String Compactifications

adey769
Duality in Aesthetic Appreciation of Nature: Triviality and Seriousness

Duality in Aesthetic Appreciation of Nature: Triviality and Seriousness

wandu
State-Channel Duality in Quantum Physics for High-Energy Colliders

State-Channel Duality in Quantum Physics for High-Energy Colliders

verhulst_r

More Related Content