Complementary Slackness
KarushKuhnTucker (KKT) Conditions
KKT Conditions For Convex Problem
Perturbation And Sensitivity Analysis
Global Sensitivity Result
Local Sensitivity
Duality And Problem Reformulations
Introducing New Variables And Equality Constraints
Implicit Constraints
Semidefinite Program
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.”
Introduction  Lecture 1 
Convex Sets  Lecture2 
Convex Functions  Lectures 34 
Convex Optimization Problems  Lectures 57 
Duality  Lectures 87 
Approximation and Fitting  Lecture 10 
Statistical Estimation  Lectures 1112 
Geometric Problems  Lectures 1213 
Numerical Linear Algebra Background  Lectures 1314 
Unconstrained Minimization  Lectures 1516 
Equality Constrained Minimization  Lectures 1617 
Interiorpoint Methods  Lectures 1719 
Conclusions  Lecture 19 
Convex Optimization Examples 
Filter Design and Equalization 
Disciplined Convex Programming and CVX 
Review Session 1  Lectures 12 
Review Session 2  Lectures 34 
Review Session 3  Lectures 56 
Review Session 4  Lectures 78 
Review Session 5  Lectures 910 
Review Session 6  Lectures 1113 
Review Session 7  Lecture 14 
Review Session 8  Lectures 1516 
Review Session 9  Lectures 
Unless otherwise noted, all reading assignments are from the textbook. Copyright in this book is held by Cambridge University Press.
Readings  Due Date 

Chapters 1 and 2  Lecture 4 
Chapters 3 and 4  Lecture 6 
CVX Users' Guide  Lecture 8 
Chapter 5  Lecture 10 
Chapters 6 and 7  Lecture 12 
Chapter 8 and appendix C  Lecture 14 
Chapter 9  Lecture 16 
Chapters 10 and 11  Lecture 18 
All numbered exercises are from the textbook. Copyright in this book is held by Cambridge University Press.
You will sometimes need to download Matlab files, see Software below.
Assignment  Exercises  Solutions  Due Date 

Homework 1  2.1, 2.2, 2.5, 2.7, 2.8, 2.11, 2.12, and 2.15  Solutions  Lecture 4 
Homework 2  2.28, 2.33, 3.2, 3.5, 3.6, 3.15, 3.16(be), 3.18(b), 3.24(fh), 3.36(a,d) Hint for 3.5: For each , is convex in and thus is a convex function of . 
Solutions  Lecture 6 
Homework 3  3.42, 3.54, 3.57, 4.1, 4.4, 4.8(ae), 4.17, and some additional exercises  Solutions  Lecture 8 
Homework 4  4.11, 4.16, 4.29, 4.30, 5.1, and some additional exercises Hint for 4.29: The condition is: There exists a feasible for which 
Solutions  Lecture 10 
Homework 5  4.15, 4.60, 5.13, 6.2, and some additional exercises  Solutions  Lecture 12 
Homework 6  6.9, and some additional exercises. You will also need to download flowgray.png Warning. Early printings of the book contain an error in the formulation of the Aoptimal experiment design problem. See the book errata page 
Solutions  Lecture 14 
Homework 7  8.16, 9.30, 9.31 and some additional exercises (which include some hints for 9.30 and 9.31).  Solutions  Lecture 16 
Homework 8  9.8, 10.1a, 11.13, and some additional exercises  Solutions  Lecture 19 
Watch Online: 
Download:
Right Click, and Save As

Duration:  
Watch Now  Download  1 hr 17 min  
Topics: 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 Elements, Supporting Hyperlane Theorem, Minimum And Minimal Elements Via Dual Inequalities 
Watch Online: 
Download:
Right Click, and Save As

Duration:  
Watch Now  Download  1 hr 17 min  
Topics: Logistics, Convex Functions, Examples, Restriction Of A Convex Function To A Line, FirstOrder Condition, Examples (FOC And SOC), Epigraph And Sublevel Set, Jensen’s Inequality, Operations That Preserve Convexity, Pointwise Maximum, Pointwise Maximum, Composition With Scalar Functions, Vector Composition 
Watch Online: 
Download:
Right Click, and Save As

Duration:  
Watch Now  Download  1 hr 14 min  
Topics: Vector Composition, Perspective, The Conjugate Function, Quasiconvex Functions, Examples, Properties (Of Quasiconvex Functions), LogConcave And LogConvex Functions, Properties (Of LogConcave And LogConvex Functions), Examples (Of LogConcave And LogConvex Functions) 
Watch Online: 
Download:
Right Click, and Save As

Duration:  
Watch Now  Download  1 hr 16 min  
Topics: 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 Program 
Watch Online: 
Download:
Right Click, and Save As

Duration:  
Watch Now  Download  1 hr 9 min  
Topics: (Generalized) LinearFractional Program, Quadratic Program (QP), Quadratically Constrained Quadratic Program (QCQP), SecondOrder Cone Programming, Robust Linear Programming, Geometric Programming, Example (Design Of Cantilever Beam), GP Examples (Minimizing Spectral Radius Of Nonnegative Matrix) 
Watch Online: 
Download:
Right Click, and Save As

Duration:  
Watch Now  Download  1 hr 15 min  
Topics: 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 TradeOff In Portfolio Optimization, Scalarization, Scalarization For Multicriterion Problems 
Watch Online: 
Download:
Right Click, and Save As

Duration:  
Watch Now  Download  1 hr 16 min  
Topics: Lagrangian, Lagrange Dual Function, LeastNorm Solution Of Linear Equations, Standard Form LP, TwoWay Partitioning, Dual Problem, Weak And Strong Duality, Slater’s Constraint Qualification, Inequality Form LP, Quadratic Program, Complementary Slackness 
Watch Online: 
Download:
Right Click, and Save As

Duration:  
Watch Now  Download  1 hr 18 min  
Topics: Applications Section Of The Course, Norm Approximation, Penalty Function Approximation, LeastNorm Problems, Regularized Approximation, Scalarized Problem, Signal Reconstruction, Robust Approximation, Stochastic Robust LS, WorstCase Robust LS 
Watch Online: 
Download:
Right Click, and Save As

Duration:  
Watch Now  Download  1 hr 16 min  
Topics: 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 Discrimination 
Watch Online: 
Download:
Right Click, and Save As

Duration:  
Watch Now  Download  1 hr 15 min  
Topics: Linear Discrimination (Cont.), Robust Linear Discrimination, Approximate Linear Separation Of NonSeparable Sets, Support Vector Classifier, Nonlinear Discrimination, Placement And Facility Location, Numerical Linear Algebra Background, Matrix Structure And Algorithm Complexity, Linear Equations That Are Easy To Solve, The FactorSolve Method For Solving Ax = B, LU Factorization 
Watch Online: 
Download:
Right Click, and Save As

Duration:  
Watch Now  Download  1 hr 10 min  
Topics: LU Factorization (Cont.), Sparse LU Factorization, Cholesky Factorization, Sparse Cholesky Factorization, LDLT Factorization, Equations With Structured SubBlocks, Dominant Terms In Flop Count, Structured Matrix Plus Low Rank Term 
Watch Online: 
Download:
Right Click, and Save As

Duration:  
Watch Now  Download  1 hr 17 min  
Topics: 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 Convergence Analysis, Examples 
Watch Online: 
Download:
Right Click, and Save As

Duration:  
Watch Now  Download  1 hr 14 min  
Topics: Continue On Unconstrained Minimization, SelfConcordance, Convergence Analysis For SelfConcordant Functions, Implementation, Example Of Dense Newton System With Structure, Equality Constrained Minimization, Eliminating Equality Constraints, Newton Step, Newton’s Method With Equality Constraints 
Watch Online: 
Download:
Right Click, and Save As

Duration:  
Watch Now  Download  1 hr 19 min  
Topics: 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 Inequality, InteriorPoint Methods, Logarithmic Barrier 
Watch Online: 
Download:
Right Click, and Save As

Duration:  
Watch Now  Download  1 hr 17 min  
Topics: 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 
Watch Online: 
Download:
Right Click, and Save As

Duration:  
Watch Now  Download  1 hr 15 min  
Topics: InteriorPoint Methods (Cont.), Example, Barrier Method (Review), Complexity Analysis Via SelfConcordance, Total Number Of Newton Iterations, Generalized Inequalities, Logarithmic Barrier And Central Path, Barrier Method, Course Conclusion, Further Topics 