Decomposition Applications
Rate Control Setup
Rate Control Problem
Rate Control Lagrangian
Aside: Utility Functions
Rate Control Dual
Dual Decomposition Rate Control Algorithm
Dual Decomposition Rate Control Algorithm
Generating Feasible Flows
Example
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
Dual Decomposition Network Flow Algorithm
Electrical Network Analogy
Example: Minimum Queueing Delay
A Specific Example
Optimal Flow
Convergence Of Dual Function
Convergence Of Primal Residual
Convergence Of Dual Variables
Aside: More Complicated Problems
Announcement
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 Cuttingplane Methods  Lecture Slides  Lecture Notes  
Analytic Center Cuttingplane 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  
Conjugategradient Method  Lecture Slides  Matlab Files  
Truncated Newton Methods  Lecture Slides  Matlab Files  
Methods for Convexcardinality Problems  Lecture Slides  Matlab Files  
Methods for Convexcardinality Problems, Part II  Lecture Slides  Matlab Files  
Model Predictive Control  Lecture Slides  Matlab Files  
Stochastic Model Predictive Control  Lecture Slides  
BranchandBound Methods  Lecture Slides  Lecture Notes  Python Files 
Notes on relaxation and randomized methods for nonconvex QCQP 
Notes on convexconcave 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 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) 
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_1Norm 
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, OnLine Learning And Adaptive Signal Processing, Example: MeanAbsolute Error Minimization, Localization And CuttingPlane Methods, CuttingPlane Oracle, Neutral And Deep Cuts, Unconstrained Minimization, Deep Cut For Unconstrained Minimization, Feasibility Problem, Inequality Constrained Problem, Localization Algorithm, Example: Bisection On R, Specific CuttingPlane Methods, Center Of Gravity Algorithm, Convergence Of CG CuttingPlane Method 
Watch Online: 
Download:
Right Click, and Save As

Duration:  
Watch Now  Download  1 hr 12 min  
Topics: Addendum: HitAndRun CG Algorithm, Maximum Volume Ellipsoid Method, Chebyshev Center Method, Analytic Center CuttingPlane Method, Extensions (Of CuttingPlane Methods), Dropping Constraints, Epigraph CuttingPlane Method, PWL Lower Bound On Convex Function, Lower Bound, Analytic Center CuttingPlane Method, ACCPM Algorithm, Constructing CuttingPlanes, 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 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, QuasiLinearization, 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, ConvexConcave 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, CayleyHamilton 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 MatrixVector 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 InteriorPoint Methods, Network Rate Control, Dual Rate Control Problem, PrimalDual Search Direction (BV Section 11.7), Truncated Netwon PrimalDual Algorithm, Primal And Dual Objective Evolution, Relative Duality Gap Evolution, Relative Duality Gap Evolution (N = 10^6), L_1Norm Methods For ConvexCardinality Problems, L_1Norm Heuristics For Cardinality Problems, Cardinality, General ConvexCardinality Problems, Solving ConvexCardinality Problems, Boolean LP As ConvexCardinality 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_1Norm 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_1Norm Methods For ConvexCardinality 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_1Norm Methods 
Watch Online: 
Download:
Right Click, and Save As

Duration:  
Watch Now  Download  1 hr 19 min  
Topics: Model Predictive Control, Linear TimeInvariant 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 StateFeedback 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 BooleanConvex Problem, Solution Methods, Lower Bound Via Convex Relaxation, Upper Bounds, Branching, New Bounds From Subproblems, Branch And Bound Algorithm (Mixed BooleanConvex Problem), Minimum Cardinality Example, Bounding X, Relaxation Problem, Algorithm Progress, Global Lower And Upper Bounds, Portion Of NonPruned Sparsity Patterns, Number Of Active Leaves In Tree, Global Lower And Upper Bounds, 