Convex Optimization: Interior Point Methods Formulation

This chapter on interior point methods in convex optimization explores the formulation of inequality-constrained optimization problems using barrier methods and generalized inequalities. It covers primal-dual interior point methods and discusses issues such as exponential complexity and determining active constraints. The logarithmic barrier formulation converts inequality constraints into barrier functions and incorporates them into the objective function to improve accuracy. The algorithm for the barrier method involves a centering step to find the solution, updating parameters iteratively, and using a stopping criterion based on Newton's method.

• Convex Optimization
• Interior Point Methods
• Barrier Method
• Inequality Constraints
• Primal-Dual

mjer Follow

Uploaded on Sep 13, 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. CSE203B Convex Optimization Chapter 11 Interior Point Methods CK Cheng Dept. of Computer Science and Engineering University of California, San Diego 1

2. Chapter 11: Interior-Point Methods Formulation Inequality constrained optimization Barrier Method Generalized Inequalities Problems Primal Dual Interior Point Methods Summary 2

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

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

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

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

7. Formulation: logarithmic barrier Ex: Problem: ??? ??? ?.?. ?? ???0? = ?? ?? ?? ? = ?, ,? m m 1 1 ???(?) = ???? ??? ?? ?? i=1 i=1 1 1 ?? = ??} Note that min ???? ????, ??= {?|?? ???? 2= ?? ?? 7

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

9. Barrier Method: Newtons Step for Modified KKT ??2??? + ?2?(?) ? ? ?? 0 ? ? = ????? + ??(?) 0 ? 1 ? log ??? = ???(?) ??? ?=1 ?=1 ? ?2 log ??? ?=1 1 1 ?[ ????2??? + ???2???? ????? = ?=1 9

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

11. Barrier Method: Feasible Solution Search Search 1: min? ?.?.??? ?,? = 1, ,? ?? = ?,? ? Search 2: min1??, ?.?.??? ??,? = 1, ,? ?? = ? ? ? ?+ 11

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

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

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

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

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

17. Generalized Inequalities Problems: log barrier ? Example 3: Cone ? ?+ Function ? ? = logdet?, 1. Concavity: (exercise) 2. Log behavior: ? ?? = ? ? + ????? Two properties: 1. ??????(??)=?????? ? + ? ???? ? ? = ? 1 0 2. ?? ? ? ? = ?? ?? 1= ?. 17

18. Primal-Dual Interior-Point Method min??(?) ?.?.??? 0,? = 1, ,? ?? = ? Lagrangian ? ?,?,? = ??? + ?=1 KKT Conditions ??? ?,?,? = ???? + ?=1 ?? = ? ??? 0,? = 1, ,? ?? 0 ????? = 0 ????? =1 (??= ?????? + ???? ? ??????? + ??? = 0 ?,? = 1, ,? 1 ????) 18

19. Primal-Dual Interior-Point Method ?????= ???? + ?????(?) + ??? ???????????= ???? ? ? ? 1/? 1 ( ????? 1/?) ???????= ?? ? ??1?? ????? ??? + ?,? + ?,? + ? = ???,?,? + ????? ? 1.?????? + ?,? + ?,? + ? ??????,?,? + ??????? +??????? ???????= ?2??? + ?=1 ???????= ?? ?? ???????= ?? 2. ?????.? + ?,? + ?,? + ? ?????.?,?,? + ???????. +???????. ???????.= ???? ? ??(?) ???????.=????(? ? ) ????? ????? ???? ? ? ? ?? ? = , ??= , ? = ? ? ? = 0 ? ? ? + ??????? ????2??(?) ? ? ? ? = 0 19

20. Primal-Dual Interior-Point Method ?????= ???? + ?????(?) + ??? ???????????= ???? ? ? ? 1/? 1 ( ????? 1/?) ???????= ?? ? ? ???2??(?) ????? ?????. ????. ?2??? + ?? ?? ?? (1) (2) (3) ? ? ? ?=1 = ???? ? ??(?) ? ??1?? ????(? ? ) 0 ????? ????? ???? 0 0 ? ? ? ?? ? = , ??= , ? = ????? ??? + ?,? + ?,? + ? = ???,?,? + ????? ? 20

21. Primal Dual Interior Point Method: the surrogate duality gap ? ?,? = ? ??? ??? < 0,? 0 When ??????= 0,??? ?????= 0 21

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

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

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