\chapter{Programaci\'o no lineal sense restriccions}

\begin{teo*}[Condicions necess\`aries d'optimalitat]
    Sigui $f \colon \real^n \to \real$ un problema d'optimitzaci\'o no lineal $\min_{x\in\real^n} f\left( x \right)$. Si $x^*$ \'es un m\'inim local de $f$ i $f \in \C^2$ en un entorn de $x^*$, llavors:
    \begin{enumerate}[i)]
        \item $\nabla f\left( x^* \right) = 0$. (Condici\'o de 1r ordre)
        \item $\nabla^2 f\left( x^* \right) \geq 0$. (Condici\'o de 2n ordre)
    \end{enumerate}
\end{teo*}
\begin{teo*}[Condicions suficients d'optimalitat]
    Si $f \in \C^2$ en un entorn obert de $x^*$, $\nabla f\left( x^* \right) = 0$ i $\nabla^2 f\left( x^* \right)$ \'es definida positiva, llavors $x^*$ \'es m\'inim local estricte de $f$.
\end{teo*}
\begin{teo*}[Condicions d'optimalitat en problemes convexos]
    Si $f$ \'es convexa i diferenciable, llavors $\nabla f\left( x^* \right) = 0 \iff x^*$ \'es m\'inim global de $f$.
\end{teo*}
\begin{met}[Mètode del Gradient]
    $x^{k+1} = x^k + \alpha^kd^k$, \quad $d^k = -\nabla f\left( x^k \right)$. \\
    $\alpha^k$ ha de complir les condicions d'Armijo-Wolfe.
\end{met}
\begin{met}[Mètode de Newton]
    $x^{k+1} = x^k + \alpha^kd^k$, \quad $d^k = -\left( \nabla^2 f\left( x^k \right) \right)^{-1} \nabla f\left( x^k \right)$. \\
    $\alpha^k$ ha de complir les condicions d'Armijo-Wolfe, normalment $\alpha^k = 1$.
\end{met}
\begin{prop}[Condicions d'Armijo-Wolfe]
    \begin{enumerate}[i)]
        \item[]
        \item Condici\'o de descens suficient (AW-1): \\
            $g\left( \alpha \right) \leq g\left( 0 \right) + \alpha c_1g'\left( 0 \right),\, c_1 \in (0,1).$ \\
            $f\left( x^k + \alpha d^k \right) \leq f\left( x^k \right) + \alpha c_1 \nabla f\left( x^k \right)^t d^k,\, c_1 \in (0,1).$
        \item Condici\'o de corbatura (AW-2): \\
            $g'\left( \alpha \right) \geq c_2 g'\left( 0 \right),\, 0 < c_1 < c_2 < 1.$ \\
            $\nabla f\left( x^k + \alpha d^k \right)^td^k \geq c_2 \nabla f\left( x^k \right)d^k,\, 0 < c_1 < c_2 < 1$.
    \end{enumerate}
\end{prop}