The course covers optimizing over nonnegative polynomials, shape-constrained regression, Difference of Convex (DC) programming, Monotone regression, NP-hardness, SOS relaxation, Convex-Concave Procedure (CCP), and numerical experiments. The teaching method includes theoretical explanations, problem-solving demonstrations, and numerical experiments. The course is intended for individuals interested in nonconvex polynomial optimization, learning applications, and matrix-analytic techniques.
Nonnegative Polynomials, Nonconvex Polynomial Optimization, and Applications to Learning
Overview
Syllabus
Intro
Optimizing over nonnegative polynomials
1. Shape-constrained regression
2. Difference of Convex (DC) programming Problems of the form min fo (x)
Monotone regression: problem definition
NP-hardness and SOS relaxation
Approximation theorem
Numerical experiments (1/2) • Low noise environment
Difference of Convex (dc) decomposition
Existence of dc decomposition (2/3)
Convex-Concave Procedure (CCP)
Picking the "best" decomposition for CCP
Undominated decompositions (1/2)
Comparing different decompositions (1/2)
Main messages • Optimization over nonnegative polynomials has many applications Powerful SDP/SOS-based relaxations available.
Uniqueness of dc decomposition
Taught by
Simons Institute
