CO 769 Syllabus (Winter 2023)
Convex Relaxations of Numerically Hard Problems; Efficient Numerical Solutions

There will be four assignments with the last due on Fri. Apr. 14.
50% for the final take-home assignment/exam; and 50% for 3 assignments during the semester.
The course will be self-contained. The required theory will generally be covered when it arises. We will cover (time permitting) elements from the following:

syllabus

1. Motivation
   1. Role of cone optimization (LP/SDP/DNN) in solving hard numerical problems.
   2. Examples of hard problems in discrete, combinatorial, engineering optimization.
2. Background
   1. convex analysis
   2. semidefinite programming, SDP
   3. numerical linear algebra
   4. linear and nonlinear programming optimality conditions
3. Interior point methods, implementations, applications
   1. facial reduction and robustness
   2. sparsity, chordal completions
4. First order methods, splitting methods
   1. projections, fractional objectives
5. Applications and Implementations
   1. low rank matrix completions, Euclidean distance matrix completion
   2. clustering, graph partitioning, quadratic assignment, max-cut, quadratic knapsack,
   3. molecular conformation, protein folding,

CO 769 webpage

References:

1. Syllabus for Topics course in 2016
2. Survey Paper/book on Facial Reduction (D. Drusvyatskiy and H. Wolkowicz) ( book at Amazon)
3. Semidefinite Optimization and Convex Algebraic Geometry (online), MOS-SIAM Series on Optimization, 2013, Editors: Grigoriy Blekherman , Pablo A. Parrilo and Rekha R. Thomas
4. Handbook on Semidefinite, Conic and Polynomial Optimization ( electronic from library), 2012 (Springer) Editors: Anjos, Miguel F., Lasserre, Jean B.
5. Handbook of Semidefinite Programming: Theory, Algorithms, and Applications, 2000 (Kluwer), Editors: Henry Wolkowicz, Romesh Saigal, Lieven Vandenberghe