Convex Optimization

This page is a summarization of the convex optimization topic. If not pointed out, all pages and propositions can be found in Bertsekas (2009).

Convex Functions

  • operations that preserves convexity/closeness:

    • page 12, prop 1.1.4:

      \(F(\mathbf{x}) = f(\mathbf{A}\mathbf{x})\), then \(f\) is convex/closed => \(F\) is convex/closed

    • page 13, prop 1.1.5:

      \(F(\mathbf{x}) = \sum_{i=1}^m \gamma_i f_i(\mathbf{x})\), then \(f_i\) are convex/closed and \(\gamma_i\) are positive => \(F\) is convex/closed

    • page 13, prop 1.1.6: \(F(\mathbf{x}) = \sup_{i \in I} f_i(\mathbf{x})\), then \(f_i\) are convex/closed => \(F\) is convex/closed

  • for differentiable \(f\), assuming \(C \sube \mathbb{R}^n\) is a nonempty convex set:

    • page 14, prop 1.1.7:

      • \(f\) is convex over \(C\) <=> \(f(\mathbf{z}) \geq \nabla f(\mathbf{x})^{\top} (\mathbf{z}-\mathbf{x}), \quad\forall \mathbf{x},\mathbf{z} \in C\).
      • \(f\) is strictly convex over \(C\) <=> the above inequality is strict whenever \(\mathbf{x} \neq \mathbf{z}\).
    • page 17, prop 1.1.8:

      \(x^* \in C\) minimizes \(f\) over \(C\) <=> \(\nabla f(\mathbf{x}^*)^{\top} (\mathbf{z}-\mathbf{x}^*) \geq 0, \quad \forall \mathbf{z} \in C\).

  • page 17, prop 1.1.9: projection theorem

    • there exists a unique \(\mathbf{z} \in \mathbb{R}^n\) that minimizes \(\|\mathbf{z}-\mathbf{x}\|\) over \(\mathbf{x} \in C\).
    • \(\mathbf{x}^*\) is the projection of \(\mathbf{z}\) on C <=> \((\mathbf{z}-\mathbf{x}^*)^{\top}(\mathbf{x}-\mathbf{x}^*) \leq 0, \quad \forall \mathbf{x}\in C\).
  • for twice differentiable \(f\), assuming \(C \sube \mathbb{R}^n\) is a nonempty convex set

    • \(\nabla^2 f(x)\) positive semidefinite for all \(x \in C\) => \(f\) is convex over \(C\).
    • \(\nabla^2 f(x)\) positive definite for all \(x \in C\) => \(f\) is strictly convex over \(C\).
    • \(C\) is open, and \(f\) is convex over \(C\) => \(\nabla^2 f(x)\) positive semidefinite for all \(x \in C\).

References

Bertsekas, Dimitri P. 2009. Convex Optimization Theory. Optimization and Computation Series 1. Belmont, Massachusetts: Athena Scientific.