Schedule for AMS 553.465/665: Introduction to Convexity, Fall 2018.
Here is the schedule of lectures :
PART I: Structure and properties of convex sets
Lecture 1, dated 9/4/2018 (Sections 1 and 2.1 from lecture notes): Norms, basic real analysis and topology; Definition of convex set, Examples: halfspaces, hyperplanes; Operations that preserve convexity;
Lecture 2, dated 9/6/2018 (Sections 2.1 and 2.2 from lecture notes): Convex combinations, convex hull; Convex cones, affine sets, linear sets.
Lecture 3, dated 9/11/2018 (Sections 2.2 and 2.3 from lecture notes): Conical hull, affine hull, linear hull/span; Fundamental Theorem of Linear Algebra; Affine independence, characterizations of affine independence, characterizations of affine sets; Dimension of convex sets. Separating hyperplane theorem; Every closed convex set is the intersection of some family of halfspaces.
Lecture 4, dated 9/13/2018 (Section 2.3.1 from lecture notes): Reviewing the separating hyperplane theorem; definition of polyhedra, Supporting hyperplane theorem, Farkas' Lemma, Polarity.
Lecture 5, dated 9/18/2018 (Section 2.3.2 from lecture notes): Finishing with polarity; Separation oracles for representing general convex sets. Towards an intrinsic description of convex sets: Definitions - Faces, extreme points, relative interior, relative boundary, dimension of proper faces.
Lecture 6, dated 9/20/2018 (Section 2.3.2 from lecture notes): Exposed faces, supporting hyperplane that does not contain the convex set entirely; Relative boundary and proper faces, Krein-Milman theorem. Recession directions, recession cone.
Lecture 7, dated 9/25/2018 (Section 2.3.2 from lecture notes): Convex set is compact if and only if recession cone is the zero vector; Definitions of lineality space, pointed closed convex sets; Writing pointed, closed convex sets as the Minkowski sum of the convex hull of extreme points and the recession cone; Characterization of pointed, closed, convex cones.
Lecture 8, dated 9/27/2018 (Section 2.3.2 from lecture notes): Finishing up with characterization of pointed, closed, convex cones; Bases of closed, convex, pointed cones; Writing a closed, convex, pointed cone as the conical hull of its extreme rays, Writing closed, convex sets that are pointed as convex combination of extreme points and conical hull of the extreme rays of its recession cone, Dealing with the lineality space: interect with orthogonal complement to get pointed set, Final decomposition of closed, convex sets into lineality space, and extreme points and extreme rays of the "effective" set after factoring out the lineality space. Discussion of instrinsic and extrinsic descriptions of closed, convex sets.
Lecture 9, dated 10/2/2018 (Section 2.4 from lecture notes): Radon's Theorem, discussion of VC theory and VC dimension of halfspaces, Helly's Theorem; Application of Helly's theorem to centerpoints.
Lecture 10, dated 10/4/2018 (Section 2.4 and Section 2.5.1 from lecture notes): Caratheodory's Theorem (cone and convex version); application to show that convex hull of compact set is compact; Polyhedra: characterization of extreme points in terms of rank of tight constraints (statement).
Lecture 11, dated 10/09/2019 : Canceled. Instructor away for conference.
Lecture 12, dated 10/11/2018 (Section 2.4 and Section 2.5.1 from lecture notes): Characterization of extreme points in terms of rank of tight constraints, finiteness of extreme points, characterization of extreme rays of recession cone in terms of rank of constraint matrix, finiteness of extreme rays, Minkowski-Weyl Theorem, Part I showing that any polyhedron can be expressed as a Minkowski sum conv(V) + cone(R) for some finite sets V, R, Part II of Minkowski-Weyl using polars.
Lecture 13, dated 10/16/2018 (Sections 2.5.2 and 2.5.3 from lecture notes): Characterization of valid inequalities, emptiness of polyhedra, Faces of polyhedra: equivalence of face and exposed face, and an "analytical" expression in terms of equalities, Consequences: finitely many faces, each face is a polyhedron.
Lecture 14, dated 10/18/2018 (Section 2.5.4 from lecture notes): Dimension of polyhedra, characterization of affine hull in terms of implicit equalities, Redundant and irredundant inequalities, Facet characterization, Uniqueness of system for full-dimensional polyhedra.
PART II: Structure and properties of convex functions
Lecture 15, dated 10/23/2018 (Sections 3.1 and 3.2 from lecture notes): Definition of convex function, epigraphs, characterization of convex functions in terms of epigraphs, Examples: Indicator, Linear/Affine functions, Maximum of affine functions, Jensen's inequality, Operations that preserve convexity, More examples: supremum of affine functions, sum of top k eigenvalues of a symmetric matrix, Affine support, Characterization of convexity in terms of affine support.
Lecture 16, dated 10/25/2018 (Sections 3.1, 3.2 and 3.3 from lecture notes): Compteing the proof of affine support characterization of convex functions, Definition of subgradient and subdifferential from affine supports, convexity of subdifferential. Continuity properties of convex functions. Reidemeister's theorem: convex functions are differentiable almost everywhere. Slope property of one-dimensional convex functions, Differentiability properties of one-dimensional functions.
Lecture 17, dated 10/30/2018 (Sections 3.3, 3.4 and 3.5 from lecture notes): Convexity characterization of differentiable functions in terms of gradient, Convexity characterization of twice differentiable functions in terms of Hessians; Sublinear functions: definitions, characterizations in terms of convexity/positive homogeneity, Characterization of sublinear functions in terms of epigraphs, norms as symmetric sublinear functions, correspondence with compact, convex, symmetric bodies, Gauges: definitions, basic properties.
Lecture 18, dated 11/1/2018 (Section 3.5 from lecture notes): Characterization of sublinear functions in terms of epigraphs, Gauges: definitions, basic properties, obtain the set, its relative interior and its recession cone from sublevel sets of the gauge, compactness characterization in terms of positivity of gauge, Uniqueness of gauge as a representation of compact convex sets containing the origin in their interior, Fundamental one-to-one correspondence between norms and centrally symmetric, compact convex sets, Computations: Formula for gauge of a halfspace, Gauge function of intersection as supremum of gauge functions, Formula for gauge function of a polyhedron, example in 2D showing non-uniqueness of representations for unbounded closed, convex sets.
Lecture 19, dated 11/6/2018: Canceled. Instructor away for conference.
Lecture 20, dated 11/8/2018: Canceled. Instructor away for conference.
Lecture 21, dated 11/13/2018 (Sections 3.5 and 3.6 from lecture notes): Support functions: definitions, sublinearity, duality between gauge of a set and support function of the polar; Fundamental one-to-one correspondence between closed, convex sets and closed, sublinear functions. Putting all the following into one picture: a sublinear function's epigraph, the associated convex set with the function, the polar of the epigraph, the polar of the associated convex set, the gauge function of the polar. Directional derivatives, directional derivative function is sublinear, Subdifferential's support function is the directional derivative function.
PART III: Convexity and optimization
Lecture 22, dated 11/15/2018 (Section 3.6 and Section 4 from lecture notes): Characterization of differentiability of a convex function in terms of directional derivative function being linear and uniqueness of subgradient, Subdifferential calculus; Optimization of convex function over convex set; Local minimum = Global minimum for convex optimization; Feasible direction cone, Tangent cone, Normal cone; polarity relationship between normal cone and tangent cone, Characterization of minima in terms of directional derivatives, tangent cone, and normal cone+subdifferential.
Lecture 23, dated 11/27/2018 (Section 4 from lecture notes): Algorithmic basis for optimization: first order oracles: function values and subgradient oracles for convex functions, separation oracles for closed, convex sets; Subgradient Algorithm with oracle for projection to the constraint set, Rate of convergence.
Lecture 24, dated 11/29/2018 (Sections 4.2 and 4.3 from lecture notes): Generalized inequalities: characterization in terms of closed, convex, pointed cones; Examples: nonnegative orthant, second order cone constraint/Lorentz cone, semidefinite cone constraint. K-convex mappings, Examples of K-convex mappings, Convex optimization with generalized inequalities, Examples: Linear Programs/Convex quadratic programs/semidefinite programs/explicit convex programs; Development of the Lagrangian dual problem.
Lecture 25, dated 12/4/2018 (Section 4.3 from lecture notes): Detailed investigation of the Lagrangian dual problem, Weak duality/strong duality/zero duality gap, Concavity of the Lagrangian function, computing subgradients of the Lagrangian function by solving an unconstrained convex optimization problem. Solving the Lagrangian dual problem given an oracle to project onto the dual cone. Deriving special form of the Lagrangian dual problem for conic optimization problems (linear programs as special cases). Complementary slackness, Saddle-point interpretation of Lagrangian duality.
Lecture 26, dated 12/6/2018 : Canceled. Instructor out of town.