Week

Topics

Text Reference

Assignments

1/09

Introduction; Motivating Example: Data Fitting.

Basic Concepts: Vector Space, Norm, Vector Calculus, Linear Algebra.

Chapter 1

Appendix A

1/16

Gradient and Hessian of functions. Functions of matrices.

Convex Sets.

Chapter 2

HW #1, data

Due Jan 30

1/23

Convex functions. First-order and Second-order conditions for differentiable convex functions. Properties of Convex Functions.

Chapter 3

1/30

Convex optimization problems. Local and global optimal solutions of convex optimization problems.

Chapter 4

2/6

Linear Programming. Quadratic programming. Quadratically constrained quadratic programming. Second-order cone programming. Robust linear programming.

Chapter 4

HW #2, data

Due Feb 27

2/13

(class held during the reading week instead)

2/20

Least-square problems. Optimal control problem. Geometric programming. Semi-definite programming. SDP relaxation.

Chapter 4

2/27

Theory: Lagrangian. Dual optimization problem. Duality gap. Slater’s condition. Sensitivity analysis.

Chapter 5, Rockafellar:
Sec. 33

3/6

Duals of LP. Economics and Pricing Interpretation. Saddle points. Game theory. Duality theory for minimax optimization.

Chapter 5, Rockafellar:
Sec. 33

HW #3

Due March 27

3/13

Duals of QP. Controllability-observability duality. Dual of $l_p$ optimization. Duality theory for optimization problem with generalized inequality. SDP relaxation.

Chapter 5

3/20

Complementary slackness condition. Karush-Kuhn-Tucker (KKT) Conditions. Interpretation of the KKT condition. Regularity condition for local optimality. Generalized inequalities.

Bertsekas
Ch. 3

3/27

Algorithms: Descent methods. Newton's method. Equality Constrained Minimization. Infeasible-start Newton's Method. Interior-point method for constrained optimization.

Chapter 9, Chapter 10

Chapter 11

HW #4, data

Due April 10

4/3

Interpretation of Interior-point method via KKT condition. Primal-Dual Interior-Point Method. Generalized Inequality. Analytic Centering. Ellipsoid method. Subgradient method for non-differentiable functions. Dual Decomposition.

Chapter 11

References:
1, 2, 3

4/10

Sequential quadratic programming. Coordinate descent. Integer programming problems. Sparse optimization.

4/10

Project Presentation in class.

Project Report

Due April 13

Final Exam: TBD

TA office hour: Monday 11am-12pm BA2179; Thursday 2-3pm BA4164