$\def\vect{\boldsymbol}$ Dizemos que o conjunto $C$ é convexo quando dados quaisquer $\vect x, \vect y \in C$, então, para todo $\alpha \in [ 0, 1 ]$, temos $$\large \alpha \vect x + ( 1 - \alpha )\vect y \in C. $$
Provem que
Seja $f : \mathbb R^n \to \mathbb R$, então o epígrafo de $f$ consiste em todos os pontos no gráfico dessa função e os acima destes. Mais precisamente: $$\large\DeclareMathOperator{\epi}{epi} \epi( f ) := \{ ( \vect x, y ) \in \mathbb R^n \times \mathbb R : y \ge f( \vect x ) \}. $$
Dizemos que $f :\mathbb R^n \to \mathbb R$ é convexa quando $\epi( f )$ é um conjunto convexo.
Dizemos que $f :\mathbb R^n \to \mathbb R$ é convexa quando para quaisquer $\vect x, \vect y \in \mathbb R^n$, para todo $\alpha \in [ 0, 1 ]$, temos $$\large f( \alpha \vect x + ( 1 - \alpha )\vect y ) \leq \alpha f( \vect x ) + ( 1 - \alpha )f( \vect y ). $$
Exercício: provar que ambas as definições são equivalentes.
Dizemos que um problema de otimização não-linear da forma $$\large\DeclareMathOperator{\sa}{s.a:} \begin{split} \min & \quad f( \vect x )\\ \sa & \quad \vect x \in \Omega \end{split} $$ é convexo quando $f$ é uma função convexa e $\Omega$ é um conjunto convexo.
Todo minimizador local de um problema de otimização não-linear convexo é um minimizador global.
Prova: suponhamos que exista $\vect y \in \Omega$ que é um minimizador local, mas não é global. Então seja $\vect x \in \Omega$ tal que $f( \vect x ) < f( \vect y )$. Observemos que como $f$ é convexa, temos, para $\alpha \in ( 0, 1 ]$: $$\large f( \alpha \vect x + ( 1 - \alpha )\vect y ) \le \alpha f( \vect x ) + ( 1 - \alpha )f( \vect y ) = f( \vect y ) + \alpha\bigl( f( \vect x ) - f( \vect y ) \bigr) < f( \vect y ). $$
Além disso, como $\Omega$ é convexo, então $\alpha \vect x + ( 1 - \alpha )\vect y \in \Omega$.
Exercício: defina apropriadamente minimizadores (e maximizadores) locais e globais para problemas de otimização não-linear com restrições.
Uma função $f : \mathbb R^n \to \mathbb R$ diferenciável é convexa se e somente se para quaisquer $\vect x, \vect y \in \mathbb R^n$ $$\large f( \vect y ) \geq f( \vect x ) + \nabla f( \vect x )^T( \vect y - \vect x ). $$
Prova:
Primeiro provaremos que se $f$ é convexa e diferenciável, então a desigualdade vale. Primeiro, lembremo-nos que $$\large \begin{split} \lim_{\alpha \to 0} \frac{f( \alpha ( \vect y - \vect x ) + \vect x ) - f( \vect x )}\alpha & {} = \lim_{\alpha \to 0}\frac{f( \alpha \vect y + ( 1 - \alpha ) \vect x ) - f( \vect x )}\alpha\\ & {} \leq \lim_{\alpha \to 0}\frac{\alpha f( \vect y ) + ( 1 - \alpha ) f( \vect x ) - f( \vect x )}\alpha\\ & {} \leq \lim_{\alpha \to 0}\frac{\alpha \bigl( f( \vect y ) - f( \vect x ) \bigr)}\alpha = f( \vect y ) - f( \vect x ) \end{split} $$
Por outro lado: $$\large \begin{split} \lim_{\alpha \to 0} \frac{f( \alpha ( \vect y - \vect x ) + \vect x ) - f( \vect x )}\alpha & {} = \lim_{\alpha \to 0}\frac{f( \vect x ) + \nabla f( \vect x )^T\alpha ( \vect y - \vect x ) + \alpha \| \vect x - \vect y \|E\bigl( \vect x, \alpha( \vect x - \vect y ) \bigr) - f( \vect x )}\alpha\\ & {} = \lim_{\alpha \to 0}\frac{\nabla f( \vect x )^T\alpha ( \vect y - \vect x ) + \alpha \| \vect x - \vect y \|E\bigl( \vect x, \alpha( \vect x - \vect y ) \bigr) }\alpha\\ & {} = \lim_{\alpha \to 0}\nabla f( \vect x )^T( \vect y - \vect x ) + \| \vect x - \vect y \|E\bigl( \vect x, \alpha( \vect x - \vect y ) \bigr) = \nabla f( \vect x )^T( \vect y - \vect x ) \end{split} $$
Agora vamos provar que se a função é diferenciável e a desigualdade vale, então a função é convexa. Seja $\vect z = \alpha \vect x + ( 1 - \alpha )\vect y$, a desigualdade pode ser utilizada duas vezes pra obtermos: $$\large \begin{split} f( \vect y ) &{} \geq f( \vect z ) + \nabla f( \vect z )^T( \vect y - \vect z )\\ f( \vect x ) &{} \geq f( \vect z ) + \nabla f( \vect z )^T( \vect x - \vect z ) \end{split} $$ A primeira dessas desigualdades pode ser simplificada da seguinte forma: $$\large \begin{split} f( \vect y ) &{} \geq f( \vect z ) + \nabla f( \vect z )^T( \vect y - \vect z )\\ &{} = f( \vect z ) + \nabla f( \vect z )^T\bigl( \vect y - \alpha \vect x - ( 1 - \alpha )\vect y \bigr)\\ &{} = f( \vect z ) + \alpha\nabla f( \vect z )^T( \vect y - \vect x ) \end{split} $$
enquanto a segunda fica $$\large \begin{split} f( \vect x ) &{} \geq f( \vect z ) + \nabla f( \vect z )^T( \vect x - \vect z )\\ &{} = f( \vect z ) + \nabla f( \vect z )^T\bigl( \vect x - \alpha \vect x - ( 1 - \alpha )\vect y \bigr)\\ &{} = f( \vect z ) + (1 - \alpha)\nabla f( \vect z )^T( \vect x - \vect y ) \end{split} $$
Para $\alpha \in [0, 1]$, $( 1 - \alpha ) \in [0, 1]$ e podemos multiplicar as desigualdades acima respectivamente por $( 1 - \alpha )$ e $\alpha$ para obter $$\large \begin{split} ( 1 - \alpha )f( \vect y ) &{} \geq ( 1 - \alpha )f( \vect z ) + ( 1 - \alpha )\alpha\nabla f( \vect z )^T( \vect y - \vect x )\\ \alpha f( \vect x ) &{} \geq \alpha f( \vect z ) + \alpha( 1 - \alpha )\nabla f( \vect z )^T( \vect x - \vect y ) \end{split} $$ somando obtemos $$\large ( 1 - \alpha )f( \vect y ) + \alpha f( \vect x ) \ge f( \vect z ) = f( \alpha \vect x + ( 1 - \alpha )\vect y ) $$