Convex Optimization Interior-Point Methods Summary
Explore Chapter 11 of Convex Optimization covering interior-point methods, barrier formulations, and generalized inequality problems. Dive into logarithmic barrier formulation, central path analysis, and the barrier method algorithm for solving optimization problems.
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.
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
CSE203B Convex Optimization Chapter 11 Interior Point Methods CK Cheng Dept. of Computer Science and Engineering University of California, San Diego 1
Chapter 11: Interior-Point Methods Formulation Inequality constrained optimization Barrier Method Generalized Inequalities Problems Primal Dual Interior Point Methods Summary 2
Formulation: The problem Problem: min?0(?) Subject to ?? 0, ? = 1, ,? ?? = ? Function ??s are convex, twice continuously differentiable We assume that rank ? = ?,? ?? ?. Issues: 1. ? can be exponential. 2. When to put ??= 0 (active)? There are 2m combination. 3
Formulation: logarithmic barrier Problem: ? min?0(?) + ???(?) ?=1 ?.?. ?? = ? When ??= 0 if ? 0,??= . Otherwise, ????0(?) + 1 ? i=1 ?.?. ?? = ? m log( ??(?)) Remark: 1. Convert inequality constraints to barrier functions. 2. Incorporate barrier functions in objective function. 3. Increase ? to improve accuracy. 4
Formulation: logarithmic barrier Let us set m ? ? = ??? ??? , ??? ? = {?|??? < 0} i=1 ? ? is convex and twice differentiable m ??? ?2? ? = i=1 Central Path is {? (?)|? > 0} 1 ?? ? = ???(?) i=1 m 1 1 ???2???? ????? ?2??? ??? ??? ??0? + ?(?) ?.?. ?? = ? 5
Formulation: logarithmic barrier Ex: Problem: ??? ??? ?? ??, ?.?. ?? ? = ?, ,? Log barrier formulation: ? ??) min???? log(?? ?? ?=1 Hyperplane ??? = ??? ? is tangent to real curve ? through ? ? . Solution ? ? balance the force between ???0(?) and i=1 1 m ??????(?). 6
Formulation: logarithmic barrier Ex: Problem: ??? ??? ?.?. ?? ???0? = ?? ?? ?? ? = ?, ,? m m 1 1 ???(?) = ???? ??? ?? ?? i=1 i=1 1 1 ?? = ??} Note that min ???? ????, ??= {?|?? ???? 2= ?? ?? 7
Barrier Method: Algorithm Given strictly feasible ?, ? = ?0> 0,? > 1,? > 0 Repeat 1. Centering step to find solution ? (?) Problem: ??? ??0? + ?(?) ?.?. ?? = ? 2. Update ? = ? ? 3. Stopping criterion: exit if ? (10-20) (Newton s method) ?< ? 4. Increase ? = ?? ? log( ??(0)) ???? Complexity: # Repeats (Outer iterations) = Plus the initial centering step ? ?(0) 8
Barrier Method: Newtons Step for Modified KKT ??2??? + ?2?(?) ? ? ?? 0 ? ? = ????? + ??(?) 0 ? 1 ? log ??? = ???(?) ??? ?=1 ?=1 ? ?2 log ??? ?=1 1 1 ?[ ????2??? + ???2???? ????? = ?=1 9
Barrier Method: Central Path Min ?0(?)+ 1 ?.?. ?? = ? Lagrangian: ? ?,? = ?0(?)+ 1 For an optimal solution, we have (? ? , ? ? ) ?0? + 1/(???? ) ??? + ?? ? = 0 We can view the dual points from central path: ?? Original Lagrangian: ? ?,?,? = ?0? + ????? + ???? ? Replace with (? (?),? (?), ?(?)): ? ? ,? , ? = ?0? + ?? mlog( ??(?)) ? i=1 mlog( ??(?)) + ??(?? ?) ? i=1 ? = 1/(???? ) ,? = 1, ,? ??? + ???? ? = ?0? ? ? Thus, we have ?0? ? ? ?/? 10
Barrier Method: Feasible Solution Search Search 1: min? ?.?.??? ?,? = 1, ,? ?? = ?,? ? Search 2: min1??, ?.?.??? ??,? = 1, ,? ?? = ? ? ? ?+ 11
Barrier Method: complexity analysis #Repeats (outer iterations) =Ceiling(log(?/(??0))/????) #Newton steps per outer iteration (self-concordance) =? ? 1 ???? ? + log2log21/???, where ? = ?? 1 2?2/(20 8?) 12
Generalized Inequalities Problems Problem: min?0(?) Subject to ??(?) ??0, ? = 1, ,?,where ??(?) ??? ?? = ? The KKT conditions: ?? = ? ??? ??0, ?? ?0? + ???? ??? ?? Note that ???? ??? ? ? = 1, ,? ?? 0, ? = 1, ,? + ??? = 0 ???? = 0,? = 1, ,?. 13
Generalized Inequalities Problems: log barrier Problem: min?0(?) Subject to ??(?) ??0, ? = 1, ,?,where ??(?) ??? ?? = ? Given a proper cone ? ??, a generalized logarithm for ?,?:?? ? has the following two criteria: 1. Function ?: concave, closed, twice continuously differentiable, dom ? = ??? ?, and 2? ? 0, for ? ??? ? 2. Equality: ? ?? = ? ? + ?????,for all y 0,? > 0, where there exists a constant (degree of ?) ? > 0 We can derive two properties 1. If ? ?0, then ? ? ? 0 (Proof?) 2. ?? ? ? = ? (from criterion 2) 14
Generalized Inequalities Problems: log barrier ? Example 1: Cone ? = ?+ Function ? ? = ??????,? 0 is a generalized logarithm 1. Concavity: 2? ? = ???? 1 2 0 ?? 2. Log behavior: ? ?? = ??????= ?????+ ?????, where ? > 0. Two properties: 1. If ? ? = ?+ ? ? = ?1, , ?? 2. ?? ? ? = ?. ?, then 1 1 ? 0 15
Generalized Inequalities Problems: log barrier 21/2 ??+1 Example 2: Cone ? = ? ??+1 ??? Function ? ? = log(??+1 1. Concavity: (exercise) 2. Log behavior: ? ?? = ? ? + 2???? Two properties 1. ??(?) ??? ??+1 ?? ??(?) ???+1 ??+1 ?? ? ? ??? ? 2. ?? ? ? = 2. 2), 2 ??? 2?? = 2,? = 1, ,? 2 2??+1 = 2, 2 16
Generalized Inequalities Problems: log barrier ? Example 3: Cone ? ?+ Function ? ? = logdet?, 1. Concavity: (exercise) 2. Log behavior: ? ?? = ? ? + ????? Two properties: 1. ??????(??)=?????? ? + ? ???? ? ? = ? 1 0 2. ?? ? ? ? = ?? ?? 1= ?. 17
Primal-Dual Interior-Point Method min??(?) ?.?.??? 0,? = 1, ,? ?? = ? Lagrangian ? ?,?,? = ??? + ?=1 KKT Conditions ??? ?,?,? = ???? + ?=1 ?? = ? ??? 0,? = 1, ,? ?? 0 ????? = 0 ????? =1 (??= ?????? + ???? ? ??????? + ??? = 0 ?,? = 1, ,? 1 ????) 18
Primal-Dual Interior-Point Method ?????= ???? + ?????(?) + ??? ???????????= ???? ? ? ? 1/? 1 ( ????? 1/?) ???????= ?? ? ??1?? ????? ??? + ?,? + ?,? + ? = ???,?,? + ????? ? 1.?????? + ?,? + ?,? + ? ??????,?,? + ??????? +??????? ???????= ?2??? + ?=1 ???????= ?? ?? ???????= ?? 2. ?????.? + ?,? + ?,? + ? ?????.?,?,? + ???????. +???????. ???????.= ???? ? ??(?) ???????.=????(? ? ) ????? ????? ???? ? ? ? ?? ? = , ??= , ? = ? ? ? = 0 ? ? ? + ??????? ????2??(?) ? ? ? ? = 0 19
Primal-Dual Interior-Point Method ?????= ???? + ?????(?) + ??? ???????????= ???? ? ? ? 1/? 1 ( ????? 1/?) ???????= ?? ? ? ???2??(?) ????? ?????. ????. ?2??? + ?? ?? ?? (1) (2) (3) ? ? ? ?=1 = ???? ? ??(?) ? ??1?? ????(? ? ) 0 ????? ????? ???? 0 0 ? ? ? ?? ? = , ??= , ? = ????? ??? + ?,? + ?,? + ? = ???,?,? + ????? ? 20
Primal Dual Interior Point Method: the surrogate duality gap ? ?,? = ? ??? ??? < 0,? 0 When ??????= 0,??? ?????= 0 21
Primal-Dual Interior-Point Method: comparison with barrier method Primal-dual interior-point method: ? ????? ?????. ????. ?2??? + ???2??(?) ?? ?? ?? (1) (2) (3) ? ? ? ?=1 = ???? ? ??(?) ? ????(? ? ) 0 1 ? ????. 0 0 1 ??? ?0? + ??? ?? 0 ??? ? ? = ? + ? ? where ???= 2?0? + ?? 2??? + (??/??? ) ??? ???? Barrier Method: 1 ??? t ?0? + ??? ?? 0 ? ? ???? ? = ? ????. where ????= ? 2?0? + ( 1/??? ) 2??? + (1/???2) ??? ???? 22
Primal-Dual Interior-Point Method: algorithm Input ??< 0,? > 0,? > 1,?????> 0,? > 0 Repeat 1. Determine ?, set ? ??/ ? 2. Compute ( ?, ?, ?) 3. Line Search and update ? ? ? ? = ? + ? ? ( ? = ) Until ???? Remark 1. Parameter ? is automatically adjusted. 2. The process proceeds even ?? ?,??(?,?,?) 0. 3. The search directions are similar to but not quite the same as the search directions of the barrier method. 4. The method is often more efficient than the barrier method. 2 ?????, ????? 2 ?????,??? ? ? 23
Summary Interior point methods convert inequality constraints into costs of objective function. The barrier method starts with strictly feasible solution. The primal dual interior methods have become popular due to its efficiency and generalization. 24
