Learn · Convex Optimization II

Lecture 11 of 18Lecture 111 h 16 min

Sequential Convex Programming, Methods For Nonconvex Optimization Problems, Sequential Convex Programming (SCP), Basic Idea Of SCP, Trust Region, Affine And Convex Approximations Via Taylor Expansions, Particle Method, Fitting Affine Or…

Stephen Boyd · Stanford University

At Stanford Engineering Everywhere Transcript

Credits and licence

From
Convex Optimization II, 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. Course Logistics, Course Organization, Course Topics, Subgradients, Basic Inequality, Subgradient Of A Function, Subdifferential, Subgradient Calculus, Some Basic Rules (For Subgradient Calculus), Pointwise Supremum, Weak Rule For… 1 h 2 min · Video
  2. Recap: Subgradients, Subgradients And Sublevel Sets, Quasigradients, Optimality Conditions – Unconstrained, Example: Piecewise Linear Minimization, Optimality Conditions – Constrained, Directional Derivative And Subdifferential, Descent… 1 h 7 min · Video
  3. Convergence Proof, Stopping Criterion, Example: Piecewise Linear Minimization, Optimal Step Size When F* Is Known, Finding A Point In The Intersection Of Convex Sets, Alternating Projections, Example: Positive Semidefinite Matrix… 1 h 15 min · Video
  4. Project Subgradient For Dual Problem, Subgradient Of Negative Dual Function, Example (Strictly Convex Quadratic Function Over Unit Box), Subgradient Method For Constrained Optimization, Convergence, Example: Inequality Form LP, Stochastic… 1 h 19 min · Video
  5. Stochastic Programming, Variations (Of Stochastic Programming), Expected Value Of A Convex Function, Example: Expected Value Of Piecewise Linear Function, On-Line Learning And Adaptive Signal Processing, Example: Mean-Absolute Error… 1 h 16 min · Video
  6. Addendum: Hit-And-Run CG Algorithm, Maximum Volume Ellipsoid Method, Chebyshev Center Method, Analytic Center Cutting-Plane Method, Extensions (Of Cutting-Plane Methods), Dropping Constraints, Epigraph Cutting-Plane Method, PWL Lower… 1 h 12 min · Video
  7. Example: Piecewise Linear Minimization, ACCPM With Constraint Dropping, Epigraph ACCPM, Motivation (For Ellipsoid Method), Ellipsoid Algorithm For Minimizing Convex Function, Properties Of Ellipsoid Method, Example (Using Ellipsoid… 1 h 14 min · Video
  8. Recap: Ellipsoid Method, Improvements (To Ellipsoid Method), Proof Of Convergence, Interpretation Of Complexity, Deep Cut Ellipsoid Method, Ellipsoid Method With Deep Objective Cuts, Inequality Constrained Problems, Stopping Criterion,… 1 h 11 min · Video
  9. Comments: Latex Typesetting Style, Recap: Primal Decomposition, Dual Decomposition, Dual Decomposition Algorithm, Finding Feasible Iterates, Interpretation, Decomposition With Constraints, Primal Decomposition (With Constraints)… 1 h 10 min · Video
  10. Decomposition Applications, Rate Control Setup, Rate Control Problem, Rate Control Lagrangian, Aside: Utility Functions, Rate Control Dual, Dual Decomposition Rate Control Algorithm, Generating Feasible Flows, Convergence Of Primal And… 1 h 17 min · Video
  11. Sequential Convex Programming, Methods For Nonconvex Optimization Problems, Sequential Convex Programming (SCP), Basic Idea Of SCP, Trust Region, Affine And Convex Approximations Via Taylor Expansions, Particle Method, Fitting Affine Or… 1 h 16 min · Video
  12. Recap: 'Difference Of Convex' Programming, Alternating Convex Optimization, Nonnegative Matrix Factorization, Comment: Nonconvex Methods, Conjugate Gradient Method, Three Classes Of Methods For Linear Equations, Symmetric Positive… 1 h 13 min · Video
  13. Recap: Conjugate Gradient Method, Recap: Krylov Subspace, Spectral Analysis Of Krylov Sequence, A Bound On Convergence Rate, Convergence, Residual Convergence, CG Algorithm, Efficient Matrix-Vector Multiply, Shifting, Preconditioned… 1 h 15 min · Video
  14. Methods (Truncated Newton Method), Convergence Versus Iterations, Convergence Versus Cumulative CG Steps, Truncated PCG Newton Method, Truncated Newton Interior-Point Methods, Network Rate Control, Dual Rate Control Problem, Primal-Dual… 1 h 13 min · Video
  15. Recap: Example: Minimum Cardinality Problem, Interpretation As Convex Relaxation, Interpretation Via Convex Envelope, Weighted And Asymmetric L_1 Heuristics, Regressor Selection, Sparse Signal Reconstruction, L_1-Norm Methods For… 1 h 3 min · Video
  16. Model Predictive Control, Linear Time-Invariant Convex Optimal Control, Greedy Control, 'Solution' Via Dynamic Programming, Linear Quadratic Regulator, Finite Horizon Approximation, Cost Versus Horizon, Trajectories, Model Predictive… 1 h 19 min · Video
  17. Stochastic Model Predictive Control, Causal State-Feedback Control, Stochastic Finite Horizon Control, 'Solution' Via Dynamic Programming, Independent Process Noise, Linear Quadratic Stochastic Control, Certainty Equivalent Model… 1 h 17 min · Video
  18. Announcements, Recap: Branch And Bound Methods, Basic Idea, Unconstrained, Nonconvex Minimization, Lower And Upper Bound Functions, Branch And Bound Algorithm, Comment: Picture Of Branch And Bound Algorithm In R^2, Comment: Binary Tree,… 1 h 19 min · Video