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
Subgradient Methods
Step Size Rules
Assumptions
Convergence Results
Aside: Example: Applying Subgradient Method To Abs(X)
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.”
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 |
Notes on relaxation and randomized methods for nonconvex QCQP |
Notes on convex-concave games and minimax |
Numerical linear algebra software |
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 may require Matlab files, see Software below.
Assignment | Solutions | Due 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 |
Convex Optimization II requires an extensive project. Here are the project guidelines. Here are the project deadlines:
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 |
Matlab files for homework problems: |
---|
bicommodity_data.m |
ex_blockprecond.m |
l1_heuristic_portfolio_data.m |
quad2_min.m |
sp_bayesnet_data.m |
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 |
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 |
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 |
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 |
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 |
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) |
Watch Online: |
Download:
Right Click, and Save As
|
Duration: | |
Watch Now | 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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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, |