Convex Optimization

The following plan is tentative and is meant to serve as a navigational chart. The actual topics covered will be filled in after each lecture as the quarter progresses.

ADMM and proximal algorithms (Dec. 10)

Dual ascent. Method of multipliers (MM). Alternating direction method of multipliers (ADMM). Example patterns for the x or z argmin problems: proximal operator, projection on a set, soft thresholding operator. How to cast a generic convex problem in ADMM form. Example: lasso via ADMM.

First order algorithms (part of Dec. 03, Dec. 08)

Gradient descent, Polyak's heavy ball, Nesterov's accelerated gradient descent, projected gradient descent, mirror descent.

**[Lecture 18: intro to gradient descent] [Lecture 19]**

Geometric [Chap. 8] and machine learning problems (Dec. 01, part of Dec. 03)

Projection on a set with respect to a distance: examples. Classification/discrimination problems: necessary and sufficient condition for linear classifiability, robust linear classifier, approximate linear classifier: support vector machine (SVM), robust approximate linear classifier, nonlinear classification with higher degree polynomials, cvx numerical examples.

**[Lecture 17] [Lecture 18: approximate linear and exact nonlinear classification]**

Approximation [Chap. 6] and statistical estimation **[Chap. 7]** problems (Nov. 19, Nov. 24)

Two statements on KKT condition. SDP duality. Regression/approximation problems: ordinary and constrained least squares (QP), ell_1 and ell_infty regressions (LP). Statistical estimation: maximum likelihood estimation (MLE), maximum a posteriori (MAP) estimation. Maximum entropy problems.

Duality [Chap. 5] (Nov. 10, Nov. 12, Nov. 17)

More examples of convex optimization problems. Lagrangian, Lagrange dual function, and Lagrange dual problem. Weak and strong duality. Slater's condition. Examples. Complimentary slackness. Derving Lagrange dual via convex conjugate. KKT condition.

**[Lecture 12] [Lecture 13] [Lecture 14]**

**Why is negative log det convex over the positive definite cone?**

**What is the relative interior of a set?**

Convex optimization problems [Chap. 4] (Oct. 29, Nov. 03, Nov. 05)

Friends of convex/concave functions: strongly convex/concave, quasi convex/concave, log convex/concave. Definition of convex optimization problem. Types of convex optimization problems and their relations: LP, QP, QCQP, SOCP, SDP. Examples. GP.

**[Lecture 9] [Lecture 10] [Lecture 11]**

Convex functions [Chap. 3] (Oct. 22, Oct. 27)

Supporting hyperplanes, spectrahedron, convex and concave functions: zeroth, first and second order characterizations, strcit convexity/concavity, sublevel and superlevel sets: showing set convexity via function convexity, epigraphs and hypographs: showing function convexity by set convexity, operations preserving function convexity, Legendre-Fenchel conjugate.

**Notes on the calculus of convex conjugates**

Convex sets [Chap. 2] (Oct. 13, Oct. 15, Oct. 20)

Background on matrix differential calculus. Affine, convex and conic sets, some important examples of convex sets, operations that preserve set convexity, generalized inequalities, dual and polar cones, separating hyperplanes.

**[Lecture 4] [Lecture 5] [Lecture 6]**

Introduction and background (Oct. 01, Oct. 06, Oct. 08)

Course logistics, subject overwiew, usage of parser software (CVX in MATLAB, CVXPY in Python, Convex.jl in Julia), structure and classification of optimization problems, review of vectors, matrices and functions of them, common types of matrices encountered across science and engineering.