모두를 위한 컨벡스 최적화 (Convex Optimization For All) 00 Preface 00-01 Author 00-02 Revision 00-03 Table of contents 01 Introduction 01-01 Optimization problems? 01-02 Convex optimization problem 01-03 Goals and Topics 01-04 Brief history of convex optimization 02 Convex Sets 02-01 Affine and convex sets 02-01-01 Line, line segment, ray 02-01-02 Affine set 02-01-03 Convex set 02-01-04 Cone 02-02 Some important examples 02-02-01 Convex set examples 02-02-02 Convex Cone examples 02-03 Operations that preserve convexity 02-04 Generalized inequalities 02-05 Separating and supporting hyperplanes 02-06 Dual cones and generalized inequalities 02-06-01 Dual cones 02-06-02 Dual generalized inequalities 03 Convex functions 03-01 Basic properties and examples 03-01-01 Definition 03-01-02 Examples of convex functions 03-01-03 Key properties of convex functions 03-02 Operations that preserve convexity 03-03 The conjugate function 03-04 Quasiconvex functions 03-04-01 Definition and examples 03-04-02 Basic properties 03-04-03 Differentiable quasiconvex functions 03-04-04 Operations that preserve quasiconvexity 03-05 Log-concave and log-convex functions 03-06 Convexity with respect to generalized inequalities 04 Convex optimization basics 04-01 Basic terminology 04-02 Convex solution sets 04-03 First order optimality condition 04-04 Partial optimization 04-05 Transformations and change of variables 04-06 Eliminating equality constraints 04-07 Slack variables 04-08 Relaxation 05 Canonical Problems 05-01 Linear Programming (LP) 05-02 Quadratic Programming (QP) 05-03 Quadratically Constrained Quadratic Programming (QCQP) 05-04 Second-Order Cone Programming (SOCP) 05-05 Semidefinite Programming (SDP) 05-06 Conic Programming (CP) 06 Gradient Descent 06-01 Gradient Descent 06-02 How to choose step sizes 06-02-01 Fixed step size 06-02-02 Backtracking line search 06-02-03 Exact line search 06-03 Convergence analysis 06-03-01 Convergence analysis & Proof 06-03-02 Convex function quardratic upper bound 06-03-03 Convergence analysis for backtracking 06-03-04 Convergence analysis under strong convexity 06-03-05 A look at the conditions & Practicalities 06-03-06 Can we do better? 06-04 Gradient boosting 06-05 Stochastic gradient descent 07 Subgradient 07-01 Subgradient 07-02 Subdifferentials 07-02-01 Connection to a Convexity Geometry 07-02-02 Subgradient Calculus 07-03 Subgradient Optimality Condition 07-03-01 Subgradient Optimality Condition 07-03-02 Derivation of First-Order Optimality Condition 07-03-03 Example: Lasso Optimality Condition 07-03-04 Example: Soft-Thresholding 07-03-05 Example: Distance to a Convex Set 08 Subgradient Method 08-01 Subgradient Method 08-01-01 Step size choices 08-01-02 Basic Inequality 08-01-03 Convergence analysis 08-01-04 Convergence rate 08-01-05 Example: Regularized Logistic Regression 08-01-06 Polyak step sizes 08-01-07 Example: Intersection of sets 08-01-08 Projected Subgradient Method 08-02 Stochastic Subgradient Method 08-02-01 Stochastic Subgradient Method 08-02-02 Convergence of Stochastic Methods 08-02-03 Convergence Rate of Stochastic Method 08-02-04 Batch vs Stochastic Methods 08-03 Improving on the Subgradient Method 09 Proximal Gradient Descent and Acceleration 09-01 Proximal gradient descent 09-02 Convergence analysis 09-03 Example: matrix completion 09-04 Special cases 09-05 Acceleration 09-05-01 Accelerated proximal gradient method 09-05-02 Convergence analysis 09-05-03 Example : FISTA 09-05-04 Is acceleration always useful? 10 Duality in Linear Programs 10-01 Lower Bounds in Linear Programs 10-02 Duality in general LPs 10-03 Max flow and min cut 10-04 Another Perspective on LP duality 10-05 Matrix Games 11 Duality in General Programs 11-1 Lagrangian 11-2 Lagrange dual function 11-3 Lagrange dual problem 11-4 Strong duality 11-5 Duality gap 12 KKT conditions 12-01 Karush-Kuhn-Tucker conditions 12-02 Example: quadratic with equality constraints 12-03 Example: water-filling 12-04 Example: support vector machines 12-05 Constrained and Lagrange forms 12-06 Uniqueness in L1 penalized problems 13 Duality uses and correspondences 13-01 Uses of duality 13-02 Solving the primal via the dual 13-03 Dual norms 13-04 Conjugate function 13-04-01 Example: lasso dual 13-04-02 Conjugates and dual problems 13-04-03 Shifting linear transformations 13-05 Dual cones 13-06 Dual subtleties & Double dual 14 Newton's Method 14-01 Newton's method 14-01-01 Newton's method interpretation 14-02 Interpretation & Properties 14-02-01 Root finding 14-02-02 Affine invariance of Newton's method 14-02-03 Local convergence analyisis 14-03 Newton decrement 14-04 Backtracking line search 14-05 Convergence analysis 14-06 Self concordance 14-06-01 Definition of self-concordant functions 14-06-02 Convergence analysis for self-concordant functions 14-07 Comparison to first-order method 14-08 Special cases 14-09 Quasi-Newton methods 15 Barrier Method 15-01 Barrier method and log barrier function 15-01-01 Inequality constrained minimization problems 15-01-02 Log barrier function & barrier method 15-01-03 Log barrier calculus 15-02 Central path 15-03 Properties and interpretation 15-03-01 Perturbed KKT conditions 15-03-02 Suboptimality gap 15-04 Barrier method v.0 and v.1 15-05 Convergence analysis 15-06 Barrier method v.2 15-07 Feasibility methods 15-08 Formal barrier method 16 Duality Revisited 16-01 Lagrangian duality revisited 16-02 Optimality conditions 16-03 Fenchel duality 17 Primal-Dual Interior-Point Methods 17-01 Barrier method & duality & optimality revisited 17-02 Primal-dual interior-point method 17-02-01 Central path equations and Newton step 17-02-02 Surrogate duality gap, residuals 17-02-03 Primal-Dual Algorithm 17-03 Some history 17-04 Special case: linear programming 17-05 Optimality conditions for semidefinite programming 18 Quasi-Newton methods 18-01 Secant Equation and Curvature Condition 18-02 Symmetric Rank-One Update (SR1) 18-03 Davidon-Fletcher-Powell (DFP) Update 18-04 Broyden-Fletcher-Goldfarb-Shanno (BFGS) update 18-05 The Broyden Class 18-06 Superlinear convergence 18-07 Limited Memory BFGS (LBFGS) 19 Proximal Newton Method 19-01 Proximal Newton method 19-01-01 Reminder: proximal gradient descent 19-01-02 Proximal Newton method 19-01-03 Scaled proximal map 19-02 Backtracking line search 19-03 When would we use proximal Newton? 19-04 Convergence analysis 19-05 Notable examples 19-06 Proximal quasi-Newton methods 19-07 Projected Newton method 20 Dual Methods 20-01 Dual (sub)gradient methods 20-01-01 Convergence Analysis 20-02 Dual Decomposition 20-02-01 Dual Decomposition with Equality Constraint 20-02-02 Dual Decomposition with Inequality Constraint 20-03 Augmented Lagrangians 20-04 A peak at ADMM 20-04-01 ADMM 20-04-02 Converegence Guarantee 20-04-03 ADMM in Scaled Form 20-04-04 Example: Alternating Projection 20-05 References 21 Alternating Direction Method of Multipliers 21-01 Last time : Dual method, Augmented Lagrangian method, ADMM, ADMM in scaled form 21-02 Connection to proximal operators 21-03 Example : Lasso regression and group lasso Regression 21-04 Example : Sparse subspace estimation and sparse plus low rank decomposition 21-05 Consensus ADMM 21-06 Faster convergence with subprogram parametrization : example of the 2d fused lasso problem 22 Conditional Gradient (Frank-Wolfe) Method 22-01 Last time: ADMM 22-02 Conditional gradient method 22-03 Convergence analysis 22-04 Properties and variants 23 Coordinate Descent 23-01 Coordinate Descent 23-02 Example: linear regression 23-03 Example: lasso regression 23-04 Example: Pathwise coordinate descent for lasso 24 Mixed Integer Programming (part I) 24-01 Definition 24-02 Examples of integer programs 24-03 Solving integer programs 24-04 Relaxations 24-05 Branch and bound algorithm (B&B) 25 Mixed Integer Programming (part II) 25-01 Cutting Planes 25-01-01 Convexification 25-01-02 Cutting plane algorithm 25-01-03 Gomory cuts (1958) 25-01-04 Branch and cut algorithm 25-02 Two extended examples 25-02-01 Best subset selection 25-02-02 Least mean squares References