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)
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
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)
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
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
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
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
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)
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
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
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
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
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
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
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
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
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
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
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,