# 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.