Convex Optimization: Convex Sets, Epigraphs, Slater Condition, and Interior Point Methods

In mathematical optimization, the great divide is not between linearity and non-linearity, but between Convexity and Non-Convexity. In convex optimization, any local minimum is guaranteed to be a global minimum, allowing polynomial-time numerical solvers to reliably find global optima across problems with millions of variables.

This comprehensive guide details the core theory of convex optimization: Convex Sets and Epigraphs, Jensen's Inequality, Slater's Constraint Qualification, Interior Point Barrier Methods, and the Alternating Direction Method of Multipliers (ADMM).

1. Quick-Reference: Convex Optimization Classes

+-----------------------------------------------------------------------------------------------------------------------+
|                                           CONVEX OPTIMIZATION HIERARCHY                                               |
+-----------------------------------------------------------------------------------------------------------------------+
| Class                  | Objective Function                     | Constraint Set             | Solver Algorithm       |
+------------------------+----------------------------------------+----------------------------+------------------------+
| Linear Program (LP)    | Linear (c^T x)                         | Polyhedron (Ax <= b)       | Simplex / Barrier      |
| Quadratic Program (QP) | Convex Quadratic (x^T Qx)              | Polyhedron (Ax <= b)       | Active-Set / OSQP      |
| Second-Order Cone (SOCP)| Linear (c^T x)                        | Second-Order Cones         | Primal-Dual Interior Pt|
| Semidefinite Prog (SDP)| Linear Matrix Trace                    | Positive Semidefinite Cone | IPM (Mosek / SeDuMi)   |
+-----------------------------------------------------------------------------------------------------------------------+

2. Convex Sets, Functions, and Epigraphs

1. Convex Set: A set C \subseteq R^n is convex if the line segment connecting any two points in C lies entirely within C:

   orall x, y \in C, \; heta \in [0, 1] \implies heta x + (1 - heta)y \in C

2. Convex Function: A function f: C o R is convex if its Epigraph is a convex set:

   f( heta x + (1 - heta)y) \le heta f(x) + (1 - heta)f(y) \quad ( ext{Jensen's Inequality})

                         Convex vs Non-Convex Function
        Convex Function f(x)                      Non-Convex Function g(x)
               \      /                                    /\    /
                \    /                                   /  \  /
                 +---+                                   +----+--+
          (Single Global Min)                     (Trapped in Local Minima!)

3. Slater's Condition and Strong Duality

For convex optimization problems minimizing convex f_0(x) subject to convex f_i(x) \le 0 (i = 1, \dots, m) and affine A x = b:

Slater's Constraint Qualification

If there exists a strictly feasible point x \in ext{relint}(D) such that f_i(x) < 0 for all i = 1, \dots, m and A x = b, then Strong Duality holds (p^* = d^*) and the duality gap is strictly zero, guaranteeing that the dual problem achieves the exact optimal value of the primal problem.

References

1. Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
2. Rockafellar, R. T. (1970). Convex Analysis. Princeton University Press.
3. Boyd, S., et al. (2011). Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers. Foundations and Trends in Machine Learning.