Learn · Convex Optimization I

Lecture 17 of 19Lecture 171 h 19 min

Newton's Method (Cont.), Newton Step At Infeasible Points, Solving KKT Systems, Equality Constrained Analytic Centering, Complexity Per Iteration Of Three Methods Is Identical, Network Flow Optimization, Analytic Center Of Linear Matrix…

Stephen Boyd · Stanford University

At Stanford Engineering Everywhere Transcript

Credits and licence

From
Convex Optimization I, Stanford University (at Stanford Engineering Everywhere)
Licence
CC BY-NC-SA 4.0, as Stanford Engineering Everywhere states it. Non-commercial use only.
Attribution
Stanford Engineering Everywhere, Stanford University. Licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License, unless otherwise expressly indicated.
Who can watch
Tweens profiles and older. How courses are placed

All the lectures

  1. Introduction, Examples, Solving Optimization Problems, Least-Squares, Linear Programming, Convex Optimizations, How To Solve?, Course Goals 1 h 21 min · Video
  2. Guest Lecturer: Jacob Mattingley, Logistics, Agenda, Convex Set, Convex Cone, Polyhedra, Positive Semidefinite Cone, Operations That Preserve Convexity, Intersection, Affine Function, Generalized Inequalities, Minimum And Minimal… 1 h 17 min · Video
  3. Logistics, Convex Functions, Examples, Restriction Of A Convex Function To A Line, First-Order Condition, Examples (FOC And SOC), Epigraph And Sublevel Set, Jensen’s Inequality, Operations That Preserve Convexity, Pointwise Maximum,… 1 h 17 min · Video
  4. Vector Composition, Perspective, The Conjugate Function, Quasiconvex Functions, Examples, Properties (Of Quasiconvex Functions), Log-Concave And Log-Convex Functions, Properties (Of Log-Concave And Log-Convex Functions), Examples (Of… 1 h 14 min · Video
  5. Optimal And Locally Optimal Points, Feasibility Problem, Convex Optimization Problem, Local And Global Optima, Optimality Criterion For Differentiable F0, Equivalent Convex Problems, Quasiconvex Optimization, Problem Families, Linear… 1 h 16 min · Video
  6. (Generalized) Linear-Fractional Program, Quadratic Program (QP), Quadratically Constrained Quadratic Program (QCQP), Second-Order Cone Programming, Robust Linear Programming, Geometric Programming, Example (Design Of Cantilever Beam), GP… 1 h 9 min · Video
  7. Generalized Inequality Constraints, Semidefinite Program (SDP), LP And SOCP As SDP, Eigenvalue Minimization, Matrix Norm Minimization, Vector Optimization, Optimal And Pareto Optimal Points, Multicriterion Optimization, Risk Return… 1 h 15 min · Video
  8. Lagrangian, Lagrange Dual Function, Least-Norm Solution Of Linear Equations, Standard Form LP, Two-Way Partitioning, Dual Problem, Weak And Strong Duality, Slater’s Constraint Qualification, Inequality Form LP, Quadratic Program,… 1 h 16 min · Video
  9. Complementary Slackness, Karush-Kuhn-Tucker (KKT) Conditions, KKT Conditions For Convex Problem, Perturbation And Sensitivity Analysis, Global Sensitivity Result, Local Sensitivity, Duality And Problem Reformulations, Introducing New… 1 h 17 min · Video
  10. Applications Section Of The Course, Norm Approximation, Penalty Function Approximation, Least-Norm Problems, Regularized Approximation, Scalarized Problem, Signal Reconstruction, Robust Approximation, Stochastic Robust LS, Worst-Case… 1 h 18 min · Video
  11. Statistical Estimation, Maximum Likelihood Estimation, Examples, Logistic Regression, (Binary) Hypothesis Testing, Scalarization, Experiment Design, D-Optimal Design 1 h 17 min · Video
  12. Continue On Experiment Design, Geometric Problems, Minimum Volume Ellipsoid Around A Set, Maximum Volume Inscribed Ellipsoid, Efficiency Of Ellipsoidal Approximations, Centering, Analytic Center Of A Set Of Inequalities, Linear… 1 h 16 min · Video
  13. Linear Discrimination (Cont.), Robust Linear Discrimination, Approximate Linear Separation Of Non-Separable Sets, Support Vector Classifier, Nonlinear Discrimination, Placement And Facility Location, Numerical Linear Algebra Background,… 1 h 15 min · Video
  14. LU Factorization (Cont.), Sparse LU Factorization, Cholesky Factorization, Sparse Cholesky Factorization, LDLT Factorization, Equations With Structured Sub-Blocks, Dominant Terms In Flop Count, Structured Matrix Plus Low Rank Term 1 h 10 min · Video
  15. Algorithm Section Of The Course, Unconstrained Minimization, Initial Point And Sublevel Set, Strong Convexity And Implications, Descent Methods, Gradient Descent Method, Steepest Descent Method, Newton Step, Newton’s Method, Classical… 1 h 17 min · Video
  16. Continue On Unconstrained Minimization, Self-Concordance, Convergence Analysis For Self-Concordant Functions, Implementation, Example Of Dense Newton System With Structure, Equality Constrained Minimization, Eliminating Equality… 1 h 14 min · Video
  17. Newton's Method (Cont.), Newton Step At Infeasible Points, Solving KKT Systems, Equality Constrained Analytic Centering, Complexity Per Iteration Of Three Methods Is Identical, Network Flow Optimization, Analytic Center Of Linear Matrix… 1 h 19 min · Video
  18. Logarithmic Barrier, Central Path, Dual Points On Central Path, Interpretation Via KKT Conditions, Force Field Interpretation, Barrier Method, Convergence Analysis, Examples, Feasibility And Phase I Methods 1 h 17 min · Video
  19. Interior-Point Methods (Cont.), Example, Barrier Method (Review), Complexity Analysis Via Self-Concordance, Total Number Of Newton Iterations, Generalized Inequalities, Logarithmic Barrier And Central Path, Barrier Method, Course… 1 h 15 min · Video