Lecture 8 - Recap: Ellipsoid Method

Expand/Collapse Video

Course Details

Show All

Course Description

Continuation of Convex Optimization I. Subgradient, cutting-plane, and ellipsoid methods. Decentralized convex optimization via primal and dual decomposition. Alternating projections. Exploiting problem structure in implementation. Convex relaxations of hard problems, and global optimization via branch & bound. Robust optimization. Selected applications in areas such as control, circuit design, signal processing, and communications. Course requirements include a substantial project.

Prerequisites: Convex Optimization I


Instructor

FPO

Boyd, Stephen

Stephen P. Boyd is the Samsung Professor of Engineering, and Professor of Electrical Engineering in the Information Systems Laboratory at Stanford University. His current research focus is on convex optimization applications in control, signal processing, and circuit design.

Professor Boyd received an AB degree in Mathematics, summa cum laude, from Harvard University in 1980, and a PhD in EECS from U. C. Berkeley in 1985. In 1985 he joined the faculty of Stanford’s Electrical Engineering Department. He has held visiting Professor positions at Katholieke University (Leuven), McGill University (Montreal), Ecole Polytechnique Federale (Lausanne), Qinghua University (Beijing), Universite Paul Sabatier (Toulouse), Royal Institute of Technology (Stockholm), Kyoto University, and Harbin Institute of Technology. He holds an honorary doctorate from Royal Institute of Technology (KTH), Stockholm.

Professor Boyd is the author of many research articles and three books: Linear Controller Design: Limits of Performance (with Craig Barratt, 1991), Linear Matrix Inequalities in System and Control Theory (with L. El Ghaoui, E. Feron, and V. Balakrishnan, 1994), and Convex Optimization (with Lieven Vandenberghe, 2004).

Professor Boyd has received many awards and honors for his research in control systems engineering and optimization, including an ONR Young Investigator Award, a Presidential Young Investigator Award, and an IBM faculty development award. In 1992 he received the AACC Donald P. Eckman Award, which is given annually for the greatest contribution to the field of control engineering by someone under the age of 35. In 1993 he was elected Distinguished Lecturer of the IEEE Control Systems Society, and in 1999, he was elected Fellow of the IEEE, with citation: “For contributions to the design and analysis of control systems using convex optimization based CAD tools.” He has been invited to deliver more than 30 plenary and keynote lectures at major conferences in both control and optimization.

In addition to teaching large graduate courses on Linear Dynamical Systems, Nonlinear Feedback Systems, and Convex Optimization, Professor Boyd has regularly taught introductory undergraduate Electrical Engineering courses on Circuits, Signals and Systems, Digital Signal Processing, and Automatic Control. In 1994 he received the Perrin Award for Outstanding Undergraduate Teaching in the School of Engineering, and in 1991, an ASSU Graduate Teaching Award. In 2003, he received the AACC Ragazzini Education award, for contributions to control education, with citation: “For excellence in classroom teaching, textbook and monograph preparation, and undergraduate and graduate mentoring of students in the area of systems, control, and optimization.”

Handouts

Lecture Materials

Subgradients Lecture Slides Lecture Notes  
Subgradient Methods Lecture Slides Lecture Notes Matlab Files
Subgradient Methods for Constrained Problems Lecture Slides    
Stochastic Subgradient Method Lecture Slides Lecture Notes Matlab Files
Localization and Cutting-plane Methods Lecture Slides Lecture Notes  
Analytic Center Cutting-plane Method Lecture Slides Lecture Notes Matlab Files
Ellipsoid Method Lecture Slides Matlab Files  
Ellipsoid Method Part II Lecture Slides Matlab Files  
Primal and Dual Decomposition Lecture Slides Lecture Notes Matlab Files
Decomposition Applications Lecture Slides    
Sequential Convex Programming Lecture Slides Matlab Files  
Conjugate-gradient Method Lecture Slides Matlab Files  
Truncated Newton Methods Lecture Slides Matlab Files  
Methods for Convex-cardinality Problems Lecture Slides Matlab Files  
Methods for Convex-cardinality Problems, Part II Lecture Slides Matlab Files  
Model Predictive Control Lecture Slides Matlab Files  
Stochastic Model Predictive Control Lecture Slides    
Branch-and-Bound Methods Lecture Slides Lecture Notes Python Files

Additional Lecture Notes

Notes on relaxation and randomized methods for nonconvex QCQP
Notes on convex-concave games and minimax
Numerical linear algebra software

Resources

This page contains links to various interesting and useful sites that relate in some way to convex optimization. It goes without saying that you’ll be periodically checking things using google and wikipedia. The wikipedia entry on convex optimization (and related topics) could be improved or extended.

Stephen Boyd’s research page. There’s a lot of material there, and you don’t have to know every detail in every paper, but you should certainly take an hour or more to browse through these papers.
EE364a web page. We expect you to know what’s in these pages.
The Convex Optimization book. You’re expected to know pretty well the material in this book. Unless you have a really good memory, you should be browsing through this.
Lieven Vandenberghe’s ee236a and ee236b course pages.
Athena Scientific books on optimization. You can also check the MIT courses that use some of these books.
CVX. Be sure to check out the every extensive library of examples. (Indeed, feel free to add to it.)
CVXOPT, which also includes an extensive library of examples, and CVXMOD
YALMIP, a Matlab toolbox for optimization modeling.
SOSTOOLS, a toolbox for formulating and solving sums of squares (SOS) optimization problems.

Assignments

Homework Assignments

Assignments may require Matlab files, see Software below.

AssignmentSolutionsDue Date
Assignment 1 Solutions Lecture 4
Assignment 2 Solutions Lecture 5
Assignment 3 Solutions Lecture 7
Assignment 4 Solutions Lecture 11
Assignment 5 Solutions Lecture 14
Assignment 6 Solutions Lecture 17
Assignment 7 Solutions Lecture 18

Final Project

Convex Optimization II requires an extensive project. Here are the project guidelines.

Here are the project deadlines:

  • Initial proposal, due Lecture 7
  • Revised proposal, due Lecture 12
  • Midterm progress report, due Lecture 14
  • Final report, due Lecture 18

Here is some example Latex code you can use for a template. Project proposals, reports, and posters must use Latex, with either our template or a good alternative.

Matlab files for homework problems:
camera_data.m
flowgray.png
illum_data.m
log_normcdf.m
log_opt_invest.m
nonlin_meas_data.m
ps_data.m
pwl_fit_data.m
sep3way_data.m
sp_ln_sp_data.m
team_data.m
thrusters_data.m
tv_img_interp.m

Software

Course Sessions (18):

Show All

Lecture 1

Watch Online: Download:
Right Click, and Save As
Duration:
Watch Now Download 1 hr 2 min
Topics: 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 Pointwise Supremum, Expectation, Minimization, Composition, Subgradients And Sublevel Sets, Quasigradients

Transcripts

Lecture 2

Watch Online: Download:
Right Click, and Save As
Duration:
Watch Now Download 1 hr 7 min
Topics: Recap: Subgradients, Subgradients And Sublevel Sets, Quasigradients, Optimality Conditions – Unconstrained, Example: Piecewise Linear Minimization, Optimality Conditions – Constrained, Directional Derivative And Subdifferential, Descent Directions, Subgradients And Distance To Sublevel Sets, Descent Directions And Optimality, Subgradient Method, Step Size Rules, Assumptions, Convergence Results, Aside: Example: Applying Subgradient Method To Abs(X)

Transcripts

Lecture 3

Watch Online: Download:
Right Click, and Save As
Duration:
Watch Now Download 1 hr 15 min
Topics: 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 Completion, Speeding Up Subgradient Methods, A Couple Of Speedup Algorithms, Subgradient Methods For Constrained Problems, Projected Subgradient Method, Linear Equality Constraints, Example: Least L_1-Norm

Transcripts

Lecture 4

Watch Online: Download:
Right Click, and Save As
Duration:
Watch Now Download 1 hr 19 min
Topics: 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 Subgradient Method, Noisy Unbiased Subgradient, Stochastic Subgradient Method, Assumptions, Convergence Results, Convergence Proof, Stochastic Programming

Transcripts

Lecture 5

Watch Online: Download:
Right Click, and Save As
Duration:
Watch Now Download 1 hr 16 min
Topics: 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 Minimization, Localization And Cutting-Plane Methods, Cutting-Plane Oracle, Neutral And Deep Cuts, Unconstrained Minimization, Deep Cut For Unconstrained Minimization, Feasibility Problem, Inequality Constrained Problem, Localization Algorithm, Example: Bisection On R, Specific Cutting-Plane Methods, Center Of Gravity Algorithm, Convergence Of CG Cutting-Plane Method

Transcripts

Lecture 6

Watch Online: Download:
Right Click, and Save As
Duration:
Watch Now Download 1 hr 12 min
Topics: 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 Bound On Convex Function, Lower Bound, Analytic Center Cutting-Plane Method, ACCPM Algorithm, Constructing Cutting-Planes, Computing The Analytic Center, Infeasible Start Newton Method Algorithm, Properties (Of Infeasible Start Newton Method Algorithm), Pruning Constraints, PWL Lower Bound On Convex Function, Lower Bound In ACCPM, Stopping Criterion, Example: Piecewise Linear Minimization

Transcripts

Lecture 7

Watch Online: Download:
Right Click, and Save As
Duration:
Watch Now Download 1 hr 14 min
Topics: 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 Method), Updating The Ellipsoid, Simple Stopping Criterion, Basic Ellipsoid Algorithm, Interpretation (Of Basic Ellipsoid Algorithm), Example (Of Ellipsoid Method)

Transcripts

Lecture 8

Watch Online: Download:
Right Click, and Save As
Duration:
Now Playing Download 1 hr 11 min
Topics: 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, Epigraph Ellipsoid Method, Epigraph Ellipsoid Example, Summary: Methods For Handling, Nondifferentiable Convex Optimization Problems Directly, Decomposition Methods, Separable Problem, Complicating Variable, Primal Decomposition, Primal Decomposition Algorithm, Example (Using Primal Decomposition), Aside: Newton's Method With A Complicating Variable, Dual Decomposition, Dual Decomposition Algorithm

Transcripts

Lecture 9

Watch Online: Download:
Right Click, and Save As
Duration:
Watch Now Download 1 hr 10 min
Topics: Comments: Latex Typesetting Style, Recap: Primal Decomposition, Dual Decomposition, Dual Decomposition Algorithm, Finding Feasible Iterates, Interpretation, Decomposition With Constraints, Primal Decomposition (With Constraints) Algorithm, Example (Primal Decomposition With Constraints), Dual Decomposition (With Constraints), Dual Decomposition (With Constraints) Algorithm, General Decomposition Structures, General Form, Primal Decomposition (General Structures), Dual Decomposition (General Structures), A More Complex Example, Aside: Pictorial Representation Of Primal And Dual Decomposition

Transcripts

Lecture 10

Watch Online: Download:
Right Click, and Save As
Duration:
Watch Now Download 1 hr 17 min
Topics: 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 Dual Objectives, Maximum Capacity Violation, Single Commodity Network Flow Setup, Network Flow Problem, Network Flow Lagrangian, Network Flow Dual, Recovering Primal From Dual, Dual Decomposition Network Flow Algorithm, Electrical Network Analogy, Example: Minimum Queueing Delay, Optimal Flow, Convergence Of Dual Function, Convergence Of Primal Residual, Convergence Of Dual Variables, Aside: More Complicated Problems

Transcripts

Lecture 11

Watch Online: Download:
Right Click, and Save As
Duration:
Watch Now Download 1 hr 16 min
Topics: 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 Quadratic Functions To Data, Quasi-Linearization, Example (Nonconvex QP), Lower Bound Via Lagrange Dual, Exact Penalty Formulation, Trust Region Update, Nonlinear Optimal Control, Discretization, SCP Progress, Convergence Of J And Torque Residuals, Predicted And Actual Decreases In Phi, Trajectory Plan, 'Difference Of Convex' Programming, Convex-Concave Procedure

Transcripts

Lecture 12

Watch Online: Download:
Right Click, and Save As
Duration:
Watch Now Download 1 hr 13 min
Topics: 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 Definite Linear Systems, CG Overview, Solution And Error, Residual, Krylov Subspace, Properties Of Krylov Sequence, Cayley-Hamilton Theorem, Spectral Analysis Of Krylov Sequence

Transcripts

Lecture 13

Watch Online: Download:
Right Click, and Save As
Duration:
Watch Now Download 1 hr 15 min
Topics: 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 Conjugate Gradient Algorithm, Choice Of Preconditioner, CG Summary, Truncated Newton Method, Approximate Or Inexact Newton Methods, CG Initialization, Hessian And Gradient, Methods, Convergence Versus Iterations, Convergence Versus Cumulative CG Steps, Truncated PCG Newton Method, Extensions

Transcripts

Lecture 14

Watch Online: Download:
Right Click, and Save As
Duration:
Watch Now Download 1 hr 13 min
Topics: 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 Search Direction (BV Section 11.7), Truncated Netwon Primal-Dual Algorithm, Primal And Dual Objective Evolution, Relative Duality Gap Evolution, Relative Duality Gap Evolution (N = 10^6), L_1-Norm Methods For Convex-Cardinality Problems, L_1-Norm Heuristics For Cardinality Problems, Cardinality, General Convex-Cardinality Problems, Solving Convex-Cardinality Problems, Boolean LP As Convex-Cardinality Problem, Sparse Design, Sparse Modeling / Regressor Selection, Estimation With Outliers, Minimum Number Of Violations, Linear Classifier With Fewest Errors, Smallest Set Of Mutually Infeasible Inequalities, Portfolio Investment With Linear And Fixed Costs, Piecewise Constant Fitting, Piecewise Linear Fitting, L_1-Norm Heuristic, Example: Minimum Cardinality Problem, Polishing, Regressor Selection

Transcripts

Lecture 15

Watch Online: Download:
Right Click, and Save As
Duration:
Watch Now Download 1 hr 3 min
Topics: 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 Convex-Cardinality Problems Part II, Total Variation Reconstruction, Total Variation Reconstruction, TV Reconstruction, L_2 Reconstruction, Iterated Weighted L_1 Heuristic, Sparse Solution Of Linear Inequalities, Detecting Changes In Time Series Model, Time Series And True Coefficients, TV Heuristic And Iterated TV Heuristic, Extension To Matrices, Factor Modeling, Trace Approximation Results, Summary: L_1-Norm Methods

Transcripts

Lecture 16

Watch Online: Download:
Right Click, and Save As
Duration:
Watch Now Download 1 hr 19 min
Topics: 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 Control (MPC), MPC Performance Versus Horizon, MPC Trajectories, Variations On MPC, Explicit MPC, MPC Problem Structure, Fast MPC, Supply Chain Management, Constraints And Objective, MPC And Optimal Trajectories, Variations On Optimal Control Problem

Transcripts

Lecture 17

Watch Online: Download:
Right Click, and Save As
Duration:
Watch Now Download 1 hr 17 min
Topics: 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 Predictive Control, Stochastic MPC: Sample Trajectory, Cost Histogram, Simple Lower Bound For Quadratic Stochastic Control, Branch And Bound Methods, Methods For Nonconvex Optimization Problems, Branch And Bound Algorithms, Comment: Example Problem

Transcripts

Lecture 18

Watch Online: Download:
Right Click, and Save As
Duration:
Watch Now Download 1 hr 19 min
Topics: 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, Example, Pruning, Convergence Analysis, Bounding Condition Number, Small Volume Implies Small Size, Mixed Boolean-Convex Problem, Solution Methods, Lower Bound Via Convex Relaxation, Upper Bounds, Branching, New Bounds From Subproblems, Branch And Bound Algorithm (Mixed Boolean-Convex Problem), Minimum Cardinality Example, Bounding X, Relaxation Problem, Algorithm Progress, Global Lower And Upper Bounds, Portion Of Non-Pruned Sparsity Patterns, Number Of Active Leaves In Tree, Global Lower And Upper Bounds,

Transcripts