Condições de otimalidade KKT

\[ \newcommand{\I}[0]{\mathcal{I}} \newcommand{\E}[0]{\mathcal{E}} \newcommand{\R}[0]{\mathbb{R}} \renewcommand{\L}[0]{\mathcal{L}} \newcommand{\eq}[2]{\begin{equation} #1 \label{#2} \end{equation}} \]
Técnicas de otimização são usadas em diversos contextos para encontrar a melhor solução de um problema, que pode ou não envolver diversas restrições nas soluções aceitas. A qualidade de uma solução é medida por uma função objetivo \(f(x)\) e toda solução deve obedecer uma série de restrições \(c_i(x)\). Neste texto apresentamos alguns resultados que levam às Condições de Otimalidade de primeira ordem, também conhecidas como condições KKT Formalmente, um problema de otimização pode ser expresso, de forma geral, como
\[ \begin{equation} \begin{cases} \textrm{minimize }f(x) \\ \textrm{ s.t.}\\ c_j(x) = 0, j \in \E \\ c_i(x) \geq 0, i \in \I \end{cases} \label{eq:formulation} \end{equation} \]
Primeiramente, estamos interessados somente nos pontos que satisfazem todas as restrições. O conjunto de pontos $\Omega$ que satisfaz todas as restrições é chamado conjunto viável.
\[\eq{ \omega = \{x \in \R^n : c_i(x) = 0, i \in \I ; c_j(x) \geq 0, j \in \E \} }{eq:viable-set} \]
Encontrar o mínimo global de \(f(x)\) é difícil mesmo quando não existem restrições. Portanto, estudamos o conjunto de soluções locais \(f(x)\). Sob certas condições (como no caso de Programação Linear ), mínimos locais também podem ser mínimos globais de \(f(x)\).

Uma solução \(x^* \in \omega\) é uma solução local se existe uma vizinhança \(\mathcal{N}\) de \(x^*\) tal que\(f(x^*)\geq f(x)\) para todo \(x \in \omega \cap \mathcal{N}\).
Uma solução \(x^* \in \omega\) é uma solução local isolada se existe uma vizinhança \(\mathcal{N}\) de \(x^*\) tal que \(x^*\) é a única solução local. Isso implica \(f(x) > f(x^*), x \in \mathcal{N} \cap \omega\).

O conjunto ativo \(\mathcal{A}(x) = \{ i : c_i(x) = 0, i \in \I \cup \E \}\) contém todas as restrições satisfeitas com igualdade.

A suavidade de \(f(x)\) e das restrições \(c_i(x)\) fornece uma maneira de percorrer o conjunto viável \(\Omega\). Dada uma solução \(x \in \Omega\), suavidade garante que podemos buscar na vizinhança de \(x\) por uma solução \(x + \epsilon d\) que melhore a função objetivo e seja viável. A partir de agora tanto \(f(x)\) quanto as restrições \(c_i(x), i \in \I \cup \E\) são suaves e diferenciáveis uma vez.

Aproximação de mínimos locais

Dada uma solução \(x \in \R^n\) e um pequeno "passo" \(s \in \R^n\), iremos analisar a vizinhança de x para obter intuições de como navegar de solução em solução de modo a sempre diminuir o valor da função objetivo \(f(x)\). Esta análise serve como motivação para as condições KKT.
Primeiramente, como queremos minimizar \(f(x)\), precisamos que \(f(x + s) - f(x) < 0\). Aproximando \(f(x+s)\) à primeira ordem temos
\[ f(x + s) = f(x) + s^T\nabla f(X) < f(x) \Rightarrow s^T\nabla f(x) < 0. \]
Como todas as restrições de igualdade devem ser mantidas, também queremos que \(c_j(x + s) = 0\). Fazendo novamente uma aproximação de primeira ordem, temos que
\[ 0 = c_j(x + s) = c_j(x) + s^T\nabla c_j(x) \Leftarrow s^T \nabla c_j(x) = 0. \]
Também é necessário manter viabilidade nas inequações (i.e. \(c_i(x) \geq 0, i \in \I\)), o que significa \(c_i(x+s) \geq 0\). Aproximando à primeira ordem,
\[ c_i(x + s) = c_i(x) + s^T \nabla c_i(x) \geq 0. \]
Caso I: A restrição não está ativa e \(c_i(x) > 0\). Então qualquer passo\(s\)pequeno o suficiente satisfaz a equação acima.
Case II:A restrição está ativa e \(c_i(x) = 0\). Então as equações se tornam
\[ s^T \nabla c_i(x) \geq 0 \textrm{ and } s^T\nabla f(x) < 0. \]
Como buscamos por um mínimo local, queremos que a interseção de ambas as condições seja vazia. Isto é alcançado quando \(\nabla c_i(x)\) e \(\nabla f(x)\) possuem a mesma direção, (\(\nabla f(x) = \lambda_i \nabla c_i(x), \lambda_i > 0\)).
Estas duas condições podem ser sumarizadas usando a função Lagrangiano definida abaixo:
\[ \L(x, \lambda) = f(x) - \sum_j^\E \lambda_j c_j(x) - \sum_i^\I \lambda_i c_i(x) \]
Em um mínimo local, é necessário que \[ \nabla \L_x(x^*, \lambda^*) = \nabla f(x) - \sum_j^\E \lambda_j c_j(x) - \sum_i^\I \lambda_i c_i(x) = 0 , \textrm{ for some } \lambda^* \geq 0 \] e \[ \lambda^*_i c_i(x) = 0, i \in \I. \]
Esta última condição é uma condição de complementaridade: para todas inequações ativas precisamos que \(\lambda^*_i > 0\). Para as outras, ao definir seus \(\lambda^*_i = 0\) correspondentes os eliminamos do Lagrangiano e \(\nabla \L(x^*, \lambda^*) = f(x^*)\). Estas condições são compiladas nas Condições de primeira ordem KKT.

Condições de otimalidade KKT

As condições KKT sumarizam as condições necessárias de primeira ordem para que um ponto \(x^*\) seja um mínimo local. Estas condições estão associadas com os gradientes de \(f(x)\) e \(c_i(x)\). As condições são necessárias, mas não suficientes
Dado um mínimo local \(x^*\) (tal que os gradientes de suas restrições ativas seja LI), existe \(\lambda^* \geq 0\) tal que:
\[ \begin{equation} \label{eq:kkt1} \nabla_x \L(x^*, \lambda^*) = 0, \end{equation} \] \[ \begin{equation} c_i(x) = 0, i \in \E, \end{equation} \] \[ \begin{equation} c_i(x) \geq 0, i \in \I, \end{equation} \] \[ \begin{equation} \lambda_i^* \geq 0, i \in \I, \end{equation} \] \[ \begin{equation} \lambda^*_i c_i(x) = 0, i \in \E \cup \I. \end{equation} \]

Referências:

Jorge Nocedal, Stephen J Wright, "Numerical Optimization", Springer-Verlag New York, 2006.

---

Made with Pweave and Pandoc.