Convex Objective Function

If we can draw a straight line between two points in an Epigraph, then every local minimum is also a global minimum. This make stuff more simple.

More formally; for any two points $x,y\in S$, we have $\alpha x+(1-\alpha )y\in S$ for all $\alpha \in [0,1]$. The function $f$ is a convex function if its domain $S$ is a convex set and if for any two points $x$ and $y$ in $S$, the following property is satisified

$$f(\alpha x+(1-\alpha )y)\le \alpha f(x)+(1-\alpha )f(y),\forall \alpha \in [0,1]$$

If the inequality is strict, we say that it is strictly convex.

---

Typically has “guaranteed complexity”, aka we know how long it will take to solve it.