# Otimização/Imprimir

* Esta é a versão para impressão de Otimização
* Se você for imprimir esta página, escolha "Visualizar impressão" no seu navegador, ou clique em Versão para impressão, você irá ver esta página sem esse aviso, sem os elementos de navegação a esquerda ou acima, e sem as TOC's de cada página.
* Atualize esta página para ter certeza de que está imprimindo a versão mais atual.
* Para maiores informações sobre a versão para impressão, incluindo como fazer arquivos PDF realmente adequados para a impressão, veja Wikilivros:Versões para impressão.

# Introdução

Este material está sendo elaborado com base nas notas de aula da disciplina Otimização II, do curso de Matemática Industrial oferecido pela UFPR, ministrada pelo professor Wilfredo, no segundo semestre letivo do ano de 2008.
O conteúdo do livro não precisa (nem deve) se limitar àquele que consta atualmente no índice. Sendo assim, a qualquer momento o livro pode ser revisto e ampliado.
Sinta-se a vontade para ler este ou quaisquer outros livros do projeto, melhorando-os conforme lhe for possível. Com isso estará ajudando a aumentar a quantidade e a qualidade dos textos didáticos disponíveis em língua portuguesa, ao mesmo tempo em que colaborará com o crescimento projeto Wikilivros como um todo.
Se tiver dúvidas ou sugestões sobre páginas específicas, utilize as páginas de discussão correspondentes para deixar um comentário a respeito.
Ainda há muito por fazer, mas cada um daqueles que contribuem acredita estar fazendo o possível para oferecer o melhor a todos.

# Método de gradientes conjugados
## Algumas considerações históricas

* Este método foi originalmente proposto por Hestenes e Stiefel, em 1952.
* Seu objetivo inicial foi a resolução de problemas quadráticos sem restrições, mas logo o mesmo foi estendido para casos mais gerais.

## O método

Este método pode ser considerado sob dois pontos de vista:
* Como um método de descida, com busca linear exata;
* Como um método de resolução de sistema linear, baseado em um processo de ortogonalização.

### Definição

Um conjunto não vazio $D\subset \mathbb {R} ^{n}$ é dito convexo quando $\forall x,y\in D$ e $t\in \left[0,1\right]$ vale
    $tx+(1-t)y\in D$

### Exemplos de conjuntos convexos e côncavos

* Este é um conjunto convexo, pois todo segmento com extremidades no conjunto está totalmente contido no conjunto.
* Este é um conjunto côncavo, pois existe um segmento com extremidades no conjunto que não está totalmente contido no conjunto.

#### Definição

Uma função $f:D\mapsto \mathbb {R}$ é dita convexa quando $D\subset \mathbb {R} ^{n}$ é convexo e $\forall x,y\in D$ e $\forall t\in \left[0,1\right]$ vale
    $f(tx+(1-t)y)\leq tf(x)+(1-t)f(y)$

#### Definição

Dado um conjunto convexo $D\subset \mathbb {R} ^{n}$, uma função $f:D\mapsto \mathbb {R}$ é dita fortemente convexa quando existe uma constante $a>0$ tal que $f(x)-a\|x\|^{2}$ é convexa.

#### Exercício

Verifique que uma função quadrática $f:\mathbb {R} ^{n}\mapsto \mathbb {R}$ é fortemente convexa se existe uma matriz simétrica definida positiva $A$, um vetor $a\in \mathbb {R} ^{n}$ e um escalar $\alpha \in \mathbb {R} \$ de modo que $f(x)={\frac {1}{2}}x^{\top }Ax+a^{\top }x+\alpha$.
Nota: Uma matriz é definida positiva se, e somente se, todos os seus autovalores são positivos.
Tem-se:
    $\nabla f:\mathbb {R} ^{n}\mapsto \mathbb {R}$
    $\nabla ^{2}f:\mathbb {R} ^{n}\mapsto (\mathbb {R} ^{n})^{2}$
Sendo $f(x)={\frac {1}{2}}x^{\top }Ax+a^{\top }x+\alpha$, segue em particular que $\nabla f=Ax+a$ e $\nabla ^{2}f=A=P^{\top }\Lambda P$, onde $\Lambda$ é uma matriz diagonal cujos elementos da diagonal são os autovalores de $A$ e $P$ é uma matriz onde as colunas são os autovetores correspondentes aos autovalores.
Note que $A$ é uma matriz simétrica, pois é a matriz Hessiana de uma função com segundas derivadas parciais contínuas, e consequentemente vale ${\frac {\partial ^{2}f}{\partial x\partial y}}={\frac {\partial ^{2}f}{\partial y\partial x}}$.
Para introduzir o método de direções conjugadas, serão consideradas somente funções quadráticas.
Uma condição necessária de primeira ordem para que $x$ seja um ponto de mínimo para a função $f$ é que $\nabla f(x)=0$. Para o presente caso, a função $f$ é convexa, então, a condição necessária $\nabla f(x)=0$ também é suficiente.

#### Exercício

Prove que se $A$ é uma matriz simétrica definida positiva, então $f:\mathbb {R} ^{n}\mapsto \mathbb {R}$ dada por $f(x)=x^{\top }Ax+a^{\top }x+\alpha$ possui um único ponto de mínimo.
No caso de uma função quadrática, tem-se $\nabla f(x)=0\Leftrightarrow Ax+a=0$, ou seja, $x$ é solução do sistema linear $Ax=-a$.
A resolução de um sistema linear nem sempre pode ser feita numericamente de forma eficiente. Por exemplo, se a matriz do sistema é:
    $A={\begin{bmatrix}10^{-20}&1\\1&10^{20}+1\end{bmatrix}}$
A solução do sistema linear corresponde à interseção entre duas retas quase paralelas, e os erros de truncamento podem causar imprecisão na solução obtida computacionalmente.
Analiticamente, o sistema $Ax=-a$ tem $x=-A^{-1}a$ como solução. Então alguém poderia se perguntar: qual o problema em resolver esse sistema linear, se basta calcular a inversa da matriz $A$ e multiplicar pelo vetor $-a$? A resposta é que o calculo da inversa de uma matriz em geral é impraticável computacionalmente, por ter custo muito alto. Por isso, nas situações práticas, onde as matrizes tem ordem bem maior do que 2 (digamos 1000), o cálculo de matrizes inversas não é uma opção.
Assim, com o intuito de desenvolver um método computacional para o cálculo de minimizadores, é preciso utilizar outras técnicas. Considere o seguinte:
Em um método de descida tem-se sempre uma sequencia $\{x_{k},t_{k},d_{k}\}\in \mathbb {N}$, com $x_{k+1}=x_{k}+t_{k}d_{k}$ e $t_{k}$ é um minimizador de ${f(x_{k}+td_{k}):t\in \mathbb {R} }$
    $\nabla f(x)=Ax+a$
e
    $0=\nabla f(x_{k+1})=Ax_{k+1}+a=A(x_{k}+t_{k}d_{k})+a=Ax_{k}+t_{k}Ad_{k}+a$
Logo, $t_{k}Ad_{k}=-(Ax_{k}+a)$ e multiplicando por $d_{k}^{\top }$ obtem-se $t_{k}d_{k}^{\top }Ad_{k}=-(d_{k}^{\top }Ax_{k}+d_{k}^{\top }a)$. Consequentemente, o valor de $t_{k}$ é dado por
    $t_{k}={\frac {-(d_{k}^{\top }Ax_{k}+a^{\top }d_{k})}{d_{k}^{\top }Ad_{k}}}$
Deste modo, o método consistirá de escolher em cada etapa $k$ uma direção $d_{k}$, e calcular o coeficiente $t_{k}$ pela fórmula anterior, para gerar o próximo ponto $x_{k+1}$. Mas como escolher a direção $d_{k}$?
Dado $x_{k}$ e escolhido $d_{k}$, defina $\theta :R\mapsto \mathbb {R}$ como $\theta (t)=f(x_{k}+td_{k})$, ou seja, $\theta$ é a restrição da função $f$ à reta que passa pelo ponto $x_{k}$ e que tem direção $d_{k}$. Logo, derivando a expressão de $\theta$ em relação a $t$, obtem-se
    $\theta ^{\prime }(t)=\nabla f(x_{k}+td_{k})^{\top }d_{k}$
Então, no ponto de mínimo, $x_{k+1}$, tem-se
    $0=\nabla f(x_{k+1})^{\top }d_{k}$
Ou seja, a direção $d_{k}$ a ser seguida a partir do ponto $x_{k}$ é ortogonal ao gradiente da função $f$, no ponto $x_{k+1}$.

## Esquema do método de descida

    $x_{k+1}=x_{k}+t_{k}d_{k}=(x_{k-1}+t_{k-1}d_{k-1})+t_{k}d_{k}=\ldots =x_{1}+t_{1}d_{1}+\ldots +t_{k}d_{k}=x_{1}+\sum _{i=1}^{k}t_{i}d_{i}$
Seja ${\bar {x}}$ o minimizador da função $f$. Tem-se
    $x_{k+1}-{\bar {x}}=x_{1}-{\bar {x}}+\sum _{i=1}^{k}t_{i}d_{i}$
Mas $0=\nabla f({\bar {x}})=A{\bar {x}}+a$ implica que $a=-A{\bar {x}}$, logo
    $\nabla f(x)=Ax+a=Ax-A{\bar {x}}=A(x-{\bar {x}})$
e consequentemente
    $A(x_{k+1}-{\bar {x}})=A(x_{1}-{\bar {x}})+\sum _{i=1}^{k}t_{i}Ad_{i}$
Donde $\nabla f(x_{k+1})=\nabla f(x_{1})+\sum _{i=1}^{k}t_{i}Ad_{i}$. Portanto $0=\nabla f(x_{k+1})^{\top }d_{k}=\nabla f(x_{1})^{\top }d_{k}+\sum _{i=1}^{k}t_{i}d_{i}^{\top }Ad_{k}$.

### Exercício

Provar que se $A$ é uma matriz simétrica, definida positiva, então existe uma matriz simétrica $B$, de modo que $A=B^{2}$
Usando o resultado desse exercício, tem-se ainda que $0=\nabla f(x_{k+1})^{\top }d_{k}=\nabla f(x_{1})^{\top }d_{k}+\sum _{i=1}^{k}t_{i}(Bd_{i})^{\top }(Bd_{k})$
Fazendo $\delta =Bd$, o método do gradiente conjugado escolhe as direções de descida tais que $\delta _{i}^{\top }d_{j}=0,\forall i\not =j$. Mas quando $i\not =j$, tem-se na expressão apresentada anteriormente apenas $0=\nabla f(x_{1})^{\top }d_{k}+t_{k}(Bd_{k})^{\top }(Bd_{k})=\nabla f(x_{1})^{\top }d_{k}+t_{k}d_{k}Ad_{k}$
Finalmente, tem-se o algoritmo para este método.

## Algoritmo de Hestenes-Stiefel

Pode-se verificar facilmente que $d_{k+1}\perp d_{k}$. De fato, como $d_{k+1}=-\nabla f(x_{k+1})+{\frac {\nabla f(x_{k+1})^{\top }Ad_{k}}{d_{k}^{\top }Ad_{k}}}d_{k}$, tem-se $Ad_{k+1}=-A\nabla f(x_{k+1})+{\frac {\nabla f(x_{k+1})^{\top }Ad_{k}}{d_{k}^{\top }Ad_{k}}}Ad_{k}$. Logo, $d_{k}^{\top }Ad_{k+1}=-\nabla f(x_{k+1})^{\top }Ad_{k}+{\frac {\nabla f(x_{k+1})^{\top }Ad_{k}}{d_{k}^{\top }Ad_{k}}}d_{k}^{\top }Ad_{k}=-\nabla f(x_{k+1})^{\top }Ad_{k}+\nabla f(x_{k+1})^{\top }Ad_{k}=0$.

### Exercício

Provar que se $y=Bx$ então $\|y_{1}-{\bar {y}}\|^{2}=\|y_{k+1}-{\bar {y}}\|^{2}+\sum _{i=1}^{k}t_{i}^{2}\|\delta _{i}\|^{2}$.

### Exemplos

Considere $f:\mathbb {R} ^{2}\mapsto \mathbb {R}$ definida por $f(x,y)={\frac {1}{2}}(x^{2}+y^{2})={\frac {1}{2}}{\begin{bmatrix}x&y\end{bmatrix}}{\begin{bmatrix}1&0\\0&1\end{bmatrix}}{\begin{bmatrix}x\\y\end{bmatrix}}$. Em outros termos, tomando $u={\begin{bmatrix}x\\y\end{bmatrix}}$, tem-se $f(u)={\frac {1}{2}}u^{\top }Au$, onde $A={\begin{bmatrix}1&0\\0&1\end{bmatrix}}=I_{2\times 2}$.
Pode-se aplicar o método de direções conjugadas ao seguinte problema
    $(P)\left\{{\begin{matrix}minf(u)\\u\in \mathbb {R} ^{2}\end{matrix}}\right.$
Note, desde já, que o conjunto solução é $S=\{{\begin{bmatrix}0\\0\end{bmatrix}}\}$.

#### Inicio

* Toma-se $x_{0}$ arbitrário, por exemplo, $x_{0}={\begin{bmatrix}2\\1\end{bmatrix}}$.
* Avalia-se o gradiente da função $f$ neste ponto inicial: $\nabla f(x_{0})=Ax_{0}=I_{2\times 2}x_{0}=x_{0}$

#### Iteração 1

* $d_{0}=-\nabla f(x_{0})={\begin{bmatrix}-2\\-1\end{bmatrix}}$
* $t_{0}={\frac {\|\nabla f(x_{0})\|^{2}}{d_{0}^{\top }Ad_{0}}}={\frac {5}{5}}=1$
* $x_{1}=x_{0}+t_{0}d_{0}={\begin{bmatrix}2\\1\end{bmatrix}}+1{\begin{bmatrix}-2\\-1\end{bmatrix}}={\begin{bmatrix}0\\0\end{bmatrix}}$
A seguir, verifica-se se o gradiente se anula no novo ponto $x_{1}$:
* $\nabla f(x_{1})=A{\begin{bmatrix}0\\0\end{bmatrix}}={\begin{bmatrix}0\\0\end{bmatrix}}$
Como o gradiente já é nulo, não é preciso fazer a segunda iteração, e o ponto $x_{1}$ é o (único) minimizador global de $f$.
Em um caso mais geral, considerando $f:\mathbb {R} ^{2}\mapsto \mathbb {R}$ definida por $f(x,y)={\frac {\lambda }{2}}(x^{2}+y^{2})={\frac {1}{2}}{\begin{bmatrix}x&y\end{bmatrix}}{\begin{bmatrix}\lambda &0\\0&\lambda \end{bmatrix}}{\begin{bmatrix}x\\y\end{bmatrix}}$, tem-se cálculos muito parecidos em cada passo.
O conjunto solução continua sendo $S=\{{\begin{bmatrix}0\\0\end{bmatrix}}\}$.

#### Inicio

* Considere $x_{0}$ como no primeiro exemplo, ou seja, $x_{0}={\begin{bmatrix}2\\1\end{bmatrix}}$.
* Avalia-se o gradiente da função $f$ neste ponto inicial: $\nabla f(x_{0})=Ax_{0}=\lambda x_{0}$

#### Iteração 1

* $d_{0}=-\nabla f(x_{0})=\lambda {\begin{bmatrix}-2\\-1\end{bmatrix}}$
* $t_{0}={\frac {\|\nabla f(x_{0})\|^{2}}{d_{0}^{\top }Ad_{0}}}={\frac {5\lambda ^{2}}{5\lambda ^{3}}}={\frac {1}{\lambda }}$
* $x_{1}=x_{0}+{\frac {1}{\lambda }}\lambda d_{0}={\begin{bmatrix}2\lambda \\\lambda \end{bmatrix}}+1{\begin{bmatrix}-2\lambda \\-\lambda \end{bmatrix}}={\begin{bmatrix}0\\0\end{bmatrix}}$
A seguir, verifica-se se o gradiente se anula no novo ponto $x_{1}$:
* $\nabla f(x_{1})=A{\begin{bmatrix}0\\0\end{bmatrix}}=\lambda {\begin{bmatrix}0\\0\end{bmatrix}}={\begin{bmatrix}0\\0\end{bmatrix}}$
Novamente, o gradiente se anula já na primeira iteração, de modo que $x_{1}$ é o minimizador global de $f$.

#### Exercício

Seja $A\in \mathbb {R} ^{n\times n}$ uma matriz simétrica definida positiva, cujos autovalores são todos iguais. Então começando de qualquer ponto $x_{0}\not =0$, o método fornece $x_{n-1}$ como solução.
Um terceiro exemplo pode ser dado tomando $A={\begin{bmatrix}2&-1\\-1&2\end{bmatrix}}$ e $f:\mathbb {R} ^{2}\mapsto \mathbb {R}$ definida por $f(u)={\frac {1}{2}}u^{\top }Au$. Observe que tal matriz é simétrica e definida positiva:
    $\det(A-\lambda I)=(2-\lambda )(3-\lambda )-1=\lambda ^{2}-4\lambda -3=(\lambda -3)(\lambda -1)$
Logo, os autovalores de $A$ são $\lambda =1$ e $\lambda =3$. Isso também implica que a função é fortemente convexa.
Aplicando o método:

#### Início

* Toma-se um ponto arbitrário no plano, por exemplo $x_{0}={\begin{bmatrix}10\\20\end{bmatrix}}$;
* Verifica-se se tal ponto é o minimizador global, avaliando nele o gradiente da função:
    $\nabla f(x_{0})={\begin{bmatrix}2&-1\\-1&2\end{bmatrix}}{\begin{bmatrix}10\\20\end{bmatrix}}={\begin{bmatrix}0\\30\end{bmatrix}}\not ={\begin{bmatrix}0\\0\end{bmatrix}}$.
* Já que o gradiente não se anulou no chute inicial, é preciso escolher uma direção e um comprimento de passo para determinar a próxima aproximação:

#### Iteração 1

    $d_{0}=-\nabla f(x_{0})={\begin{bmatrix}0\\-30\end{bmatrix}}$
    $t_{0}={\frac {\|{\begin{bmatrix}0&30\end{bmatrix}}\|^{2}}{{\begin{bmatrix}0&-30\end{bmatrix}}{\begin{bmatrix}2&-1\\-1&2\end{bmatrix}}{\begin{bmatrix}0\\-30\end{bmatrix}}}}={\frac {900}{{\begin{bmatrix}0&-30\end{bmatrix}}{\begin{bmatrix}-30\\-60\end{bmatrix}}}}={\frac {900}{1800}}={\frac {1}{2}}$
Feitos esses cálculos, o próximo ponto é dado por
    $x_{1}=x_{0}+t_{0}d_{0}={\begin{bmatrix}10\\20\end{bmatrix}}+{\frac {1}{2}}{\begin{bmatrix}0\\-30\end{bmatrix}}={\begin{bmatrix}10\\20\end{bmatrix}}+{\begin{bmatrix}0\\-15\end{bmatrix}}={\begin{bmatrix}10\\5\end{bmatrix}}$
Para saber se será necessária uma nova iteração, ou se o minimizador foi encontrado, calcula-se o gradiente da função no ponto:
    $\nabla f(x_{1})={\begin{bmatrix}2&-1\\-1&2\end{bmatrix}}{\begin{bmatrix}10\\5\end{bmatrix}}={\begin{bmatrix}15\\0\end{bmatrix}}\not ={\begin{bmatrix}0\\0\end{bmatrix}}$.
Novamente, será preciso calcular uma nova direção e um novo comprimento de passo:

#### Iteração 2

    $d_{0}={\begin{bmatrix}-15\\0\end{bmatrix}}+\beta {\begin{bmatrix}0\\-30\end{bmatrix}}={\begin{bmatrix}-15\\-30\beta \end{bmatrix}}$
onde $\beta$, no algoritmo de Hestenes é dado por:
    $\beta ={\frac {{\begin{bmatrix}15&0\end{bmatrix}}{\begin{bmatrix}2&-1\\-1&2\end{bmatrix}}{\begin{bmatrix}0\\-30\end{bmatrix}}}{{\begin{bmatrix}0&-30\end{bmatrix}}{\begin{bmatrix}2&-1\\-1&2\end{bmatrix}}{\begin{bmatrix}0\\-30\end{bmatrix}}}}={\frac {{\begin{bmatrix}15&0\end{bmatrix}}{\begin{bmatrix}30\\-60\end{bmatrix}}}{{\begin{bmatrix}0&-30\end{bmatrix}}{\begin{bmatrix}30\\-60\end{bmatrix}}}}={\frac {15\times 30}{(-30)\times (-60)}}={\frac {1}{4}}$
Portanto
    $d_{0}=-15{\begin{bmatrix}1\\1/2\end{bmatrix}}$
Além disso, o tamanho do passo é dado por
    $t_{1}={\frac {\|\nabla f(x_{1})\|^{2}}{d_{0}^{\top }Ad_{0}}}={\frac {15^{2}}{15^{2}{\begin{bmatrix}1&1/2\end{bmatrix}}{\begin{bmatrix}2&-1\\-1&2\end{bmatrix}}{\begin{bmatrix}1\\1/2\end{bmatrix}}}}={\frac {1}{{\begin{bmatrix}1&1/2\end{bmatrix}}{\begin{bmatrix}3/2\\0\end{bmatrix}}}}={\frac {1}{3/2}}={\frac {2}{3}}$
Portanto
    $x_{2}=x_{1}+t_{1}d_{1}={\begin{bmatrix}10\\5\end{bmatrix}}-15{\frac {2}{3}}{\begin{bmatrix}1\\1/2\end{bmatrix}}={\begin{bmatrix}10\\5\end{bmatrix}}-10{\begin{bmatrix}1\\1/2\end{bmatrix}}={\begin{bmatrix}0\\0\end{bmatrix}}$
Obviamente, este é o minimizador procurado (pois o método tem a propriedade de convergência quadrática, ou seja utiliza no máximo $n$ iterações para chegar a solução quando aplicado a funções quadráticas definidas em $\mathbb {R} ^{n}$)

#### Exercício

Implementar o algoritmo de Hestenes-Stiefel em alguma linguagem de programação, por exemplo em Scilab, ou Matlab.

#### Exercício

Seja $f$ um função quadrática fortemente convexa. Verifique as seguintes igualdades:
* ${\frac {-\nabla f(x_{k})^{\top }d_{k}}{d_{k}^{\top }Ad_{k}}}={\frac {\|\nabla f(x_{k})\|^{2}}{d_{k}^{\top }Ad_{k}}}$
* ${\frac {\nabla f(x_{k})^{\top }Ad_{k-1}}{d_{k-1}^{\top }Ad_{k-1}}}={\frac {\|\nabla f(x_{k})\|^{2}}{\|\nabla f(x_{k-1})\|^{2}}}$
* ${\frac {\nabla f(x_{k})^{\top }Ad_{k}}{d_{k-1}^{\top }Ad_{k-1}}}={\frac {\nabla f(x_{k})^{\top }(\nabla f(x_{k})-\nabla f(x_{k-1}))}{\|\nabla f(x_{k-1})\|^{2}}}$

### Implementação em Scilab

Abaixo é apresentada uma implementação deste algoritmo na linguagem de programação utilizada pelo Scilab.
Para facilitar a compreensão do método, pode ser útil exibir as curvas de nível da função. Uma forma de implementar uma função com esse propósito é a seguinte:

## Algoritmo de Fletcher-Reeves

Esta versão é na verdade uma extensão do algoritmo anterior, permitindo a aplicação no caso de funções que não são quadráticas.

## Algoritmo de Polak-Ribière

Uma outra versão é a seguinte:

### Exercício

Verificar que, no caso de uma função $f$ quadrática e fortemente convexa, os algoritmos de Hestenes-Stiefel, de Fletcher-Reeves e de Polak-Ribière são os mesmos.

### Exercício

Seja $f(x)=e^{-x}+e^{x}$. Implemente o método de gradientes conjugados, e utilize o algoritmo para determinar o ponto de mínimo da função $f$. Note que o espaço é unidimensional, então o método de gradientes conjugados reduz-se ao método dos gradientes, com primeira direção $-\nabla f(x_{0})$. Observe ainda que $f$ é uma função coerciva fortemente convexa.

## Algoritmo auxiliar

Para o caso de funções não quadráticas, é preciso usar algum método de busca linear para a implementação do método dos gradientes conjugados, seja a versão de Fletcher-Reeves ou a de Polak-Ribière. Uma possibilidade é a busca de linear de Armijo (ver Izmailov & Solodov (2007), vol 2, pag. 65), cujo algoritmo é esboçado a seguir:
com:
* $pred=-t\theta$
* $\theta (t)=f(x+td)$
* $\theta '(t)=\nabla f(x+td)^{\top }d$

# Métodos de penalidades

Os métodos que recebem este nome fazem parte de uma família de métodos baseados em:
* Simplicidade conceitual;
* Eficiência prática;
Algumas das primeiras funções de penalidade foram desenvolvidas por:
* Courant (1943)
* Ablate Brighham (1955) (qual o artigo?)
* AV Fiacco, GP McCormick (1968) (qual o artigo?)
Para compreender este tipo de método, será considerado o seguinte problema:
$(P)\left\{{\begin{matrix}minf(x)\\g_{i}(x)\leq 0\forall i=1,\ldots ,p\\h_{j}(x)=0\forall j=1,\ldots ,q\end{matrix}}\right.$
Adicionalmente, se for considerado o conjunto de pontos $C=\{x\in \mathbb {R} ^{n}:g_{i}(x)\leq 0,\forall i=1,\ldots ,p;h_{j}(x)=0,\forall j=1,\ldots ,q\}$, o problema (P) se escreve ainda como
$(P)\left\{{\begin{matrix}minf(x)\\x\in C\end{matrix}}\right.$
Uma primeira idéia para a resolução desse tipo de problema é fazer uso de funções indicadoras, conforme é definido a seguir:

## Definição

Dado um conjunto não vazio $C\subset \mathbb {R} ^{n}$, define-se a função indicadora $I_{C}:\mathbb {R} ^{n}\mapsto \mathbb {R} \cup \{\infty \}$ por:
    $I_{C}(x)={\begin{cases}0,&{\mbox{se }}x\in C\\\infty ,&{\mbox{se }}x\not \in C\end{cases}}$
Notas: A função indicadora $I_{C}$ é às vezes denotada por $\chi _{C}$.
Para transformar um conjunto (P) em um problema sem restrições, pode-se proceder da seguinte maneira: Considerar o problema (PD), dado por:
$(PD)\left\{{\begin{matrix}minf(x)+I_{C}(x)\\x\in \mathbb {R} ^{n}\end{matrix}}\right.$
Considerando $i_{C}:\mathbb {R} \mapsto \mathbb {R} \cup \{\infty \}$ definida por:
    $i_{C}(t)={\begin{cases}0,&{\mbox{se }}t\leq 0\\\infty ,&{\mbox{se }}t>0\end{cases}}$
Tem-se ainda o problema (PP), dado por:
$(PP)\left\{{\begin{matrix}minf(x)+\sum _{i=1}^{p}i(g_{i}(x))+\sum _{j=1}^{p}i(h_{j}(x))\\x\in \mathbb {R} ^{n}\end{matrix}}\right.$
Comentários:
* A grande vantagem desta idéia é que ela transforma um problema com restrições em um problema irrestrito.
* A principal desvantagem é que a função $\phi$ definida a seguir é descontínua em cada ponto $x\in \partial C$:
    $\phi :\mathbb {R} ^{n}\mapsto \mathbb {R} \cup \{\infty \}$
    $\phi (x)=f(x)+\sum _{i=1}^{p}i(g_{i}(x))+\sum _{j=1}^{p}i(h_{j}(x))$

## Método de penalidade exterior

Para contornar a desvantagem da descontinuidade da função apresentada anteriormente, surgem outras funções, como por exemplo:
    $H:\mathbb {R} \mapsto \mathbb {R}$
    $H(t)={\begin{cases}0,&{\mbox{se }}t\leq 0\\t^{2},&{\mbox{se }}t>0\end{cases}}$

### Definição

Dada uma função $g:A\mapsto \mathbb {R}$, definida em um conjunto arbitrário $A$, define-se a parte positiva de $g$, como:
    $g^{+}(x)=max\{0,g(x)\}$

### Exercício

Verifique que para cada $x\in \mathbb {R} ^{n}$ tem-se, para cada $i$, a igualdade $H(g_{i}(x))=\left(g_{i}^{+}(x)\right)^{2}$, onde $g_{i}^{+}$ é a parte positiva de $g_{i}$ e $H$ é a função definida no exemplo anterior.

### Exercício

Verifique que para cada $x\in \mathbb {R} ^{n}$ tem-se, para cada $j$, a igualdade $H\left(h_{j}(x)^{2}\right)=\left(h_{j}(x)\right)^{2}$.
A idéia de aplicar penalizações aos pontos que não pertencem ao conjunto viável é formalizada na seguinte definição:

### Definição

Seja $H:\mathbb {R} ^{n}\mapsto \mathbb {R}$. A função $H$ é chamada de função de penalidade exterior se possui as seguintes propriedades:
* $H(x)\geq 0,\forall x\in \mathbb {R} ^{n}$
* $H(x)=0,\Leftrightarrow x\in C$
* $H$ é contínua
Nota: Lembre-se que $C=\{x\in \mathbb {R} ^{n}:g_{i}(x)\leq 0,\forall i=1,\ldots ,p;h_{j}(x)=0,\forall j=1,\ldots ,q\}$ é o conjunto viável do problema (P).
Em particular, as funções $H\circ g_{i}$ são funções de penalidade exterior.

### Definição

Seja $\theta :\mathbb {R} ^{n}\mapsto \mathbb {R}$. A função $\theta$ é dita coerciva se $\lim _{\|x\|\to \infty }\theta (x)=+\infty$
Nota: Conforme o Wikcionário, o termo coercivo significa: que coage; que reprime; que impõe pena; coercitivo. Nesse sentido, esse é um termo adequado ao tratar do conceito anterior, no contexto dos métodos de penalidade.

### Exercício

Verifique que $\theta$ é uma função coerciva se, e somente se, $L_{\theta }(\lambda )=\{x\in \mathbb {R} ^{n}:\theta (x)\leq \lambda \}$ é limitado para todo $\lambda \in \mathbb {R}$.

### Exercício

Verifique que $H:\mathbb {R} ^{n}\mapsto \mathbb {R}$ definida por $H(x)=\sum _{i=1}^{p}\left(g_{i}^{+}(x)\right)^{2}+\sum _{j=1}^{q}\left(h_{j}(x)\right)^{2}$ é uma função de penalidade exterior, onde conforme anteriormente, $g_{i}^{+}$ é a parte positiva de $g_{i}$.

### Exercício

Verifique que se $g:\mathbb {R} ^{n}\mapsto \mathbb {R}$ é uma função contínua coerciva, então existe ${\bar {x}}\in \mathbb {R} ^{n}$ tal que $g({\bar {x}})\leq g(x),\forall x\in \mathbb {R} ^{n}$.

### Alguns conceitos da topologia

Em algumas situações, é interessante ter em mente que certos conceitos definidos no contexto da Otimização são, na verdade, instanciações de conceitos mais gerais, muitos deles provenientes da topologia. Alguns exemplos são apresentados a seguir.

#### Definição

Dado um conjunto $X$, uma coleção $\Gamma \subset {\mathcal {P}}$ de subconjuntos de $X$ é chamada de topologia se:
* $\emptyset ,X\in \Gamma$
* $\left\{A_{i}\right\}_{i\in I}\subset \Gamma \Rightarrow \cup _{i\in I}A_{i}\in \Gamma$
* $\left\{B_{i}\right\}_{i=1}^{p}\subset \Gamma \Rightarrow \cap _{i=1}^{p}B_{i}\in \Gamma$

#### Exemplos

* Topologia euclidiana:
    $X=R$
    $\Gamma =\Gamma _{1}=\{\emptyset \}\cup \{X\}\cup \left\{A\subset \mathbb {R} :\forall x\in A,\exists \epsilon _{x}>0,\left(x-\epsilon _{x},x+\epsilon _{x}\right)\subset A\right\}$
Em outras palavras, a topologia euclideana é a coleção de todos os conjuntos abertos contidos em $\mathbb {R}$. Pode-se verificar com facilidade que de fato são satizfeitas as três propriedades que definem uma topologia.
Outro exemplo muito comum é o seguinte:
* Topologia euclideana estendida:
    $X=R\cup \{\infty \}$
    $\Gamma =\Gamma _{1}\cup \left\{A\subset \mathbb {R} \cup \{\infty \}:\exists a\in \mathbb {R} ,A=\left]a,\infty \right]\right\}$
Em geral, a noção de limite seria caracterizada topologicamente da seguinte forma:

#### Definição

$\lim _{n\to \infty }x_{n}=a\Leftrightarrow \forall I\ni x,\exists n_{0}\in \mathbb {N} ,\forall n\geq n_{0}\Rightarrow x_{n}\in I$

### De volta ao método

Uma vez apresentados os conceitos iniciais, pode-se provar o seguinte teorema:

#### Teorema

Considere:
* $H:\mathbb {R} ^{n}\mapsto \mathbb {R}$ uma função de penalidade exterior;
* $f:\mathbb {R} \mapsto \mathbb {R}$ uma função contínua;
* $C=\{x\in \mathbb {R} ^{n}:g_{i}(x)\leq 0,\forall i=1,\ldots ,p;h_{j}(x)=0,\forall j=1,\ldots ,q\}$ um conjunto fechado;
* $\left\{r_{k}\right\}$ uma sequência de termos positivos tal que $\lim _{k\to \infty }r_{k}=0$.
Suponha que é válida uma das seguintes propriedades:
* $f$ é coerciva.
* $C$ é limitado e $H$ é coerciva.
Se, para cada $k$, for escolhido ${\bar {x}}(r_{k})\in \arg \min\{f(x)+{\frac {1}{r_{k}}}H(x)\}$,então:
* $\left\{{\bar {x}}(r_{k})\right\}$ possui algum ponto de acumulação;
* Todo ponto de acumulação de $\left\{{\bar {x}}(r_{k})\right\}$ é solução do problema (P);
* $\lim _{k\to \infty }H({\bar {x}}(r_{k}))=0$.

#### Exercício

Dado o problema (P), considere $m=\inf \left\{f(x):g_{i}(x)\leq 0,\forall i\ {\text{e}}\ h_{j}=0,\forall j\right\}$ (isso não quer dizer que o problema tenha solução). suponha-se que $f,g$ e $h$ são funções contínuas e que $C=\left\{x:g_{i}(x)\leq 0,\forall i;h_{j}(x)=0,\forall j\right\}$ seja não vazio, ou seja, que $C$ é factível. Tome $H:\mathbb {R} ^{n}\mapsto \mathbb {R}$ como $H(x)=\sum _{i=1}^{p}[g_{i}^{+}(x)]^{2}+\sum _{j=1}^{q}[h_{j}(x)]^{2}$, onde $g_{i}^{+}$ denota a parte positiva de $g_{i}$, como de costume. Considere ainda $\varphi :\mathbb {R} ^{n}\times \mathbb {R} ^{+}\mapsto \mathbb {R}$ dada por $\varphi (x,r)=f(x)+{\frac {1}{r}}H(x)$ e, para cada $r>0$, seja $m(r)=\inf _{x\in \mathbb {R} ^{n}}\varphi (x,r)$
Nessas condições, provar que:
* $H$ é uma função de penalidade exterior
* $m>-\infty$
* $\varphi (x,r)=f(x),\forall x\in C,\forall r>0$
* Se $0<r<s$ então $m(s)<m(r)$
* Se $f,g_{i},h_{j}$ são covexas, então $\varphi$ é convexa.
* Se $f,g_{i},h_{j}$ são diferenciáveis, então $\varphi$ é diferenciável em $x$, e $\nabla _{x}\varphi (x,r)=\nabla f(x)+\sum _{i=1}^{p}g_{i}^{+}(x)\nabla g_{i}(x)+\sum _{j=1}^{q}h_{j}(x)\nabla h_{j}(x)$
* Se $0<r_{k+1}<r_{k}$ e $\lim _{k\to \infty }r_{k}=0$ e se $\{x_{k}\}$ é uma sequência tal que $\varphi (x_{k},r_{k})=m(r_{k})$ e $\lim _{k\to \infty }x_{k}={\bar {x}}$ então ${\bar {x}}$ é solução de (P).

### Algoritmo de penalidade exterior

Nota: Neste algoritmo, $H$ é uma função de penalidade exterior.

#### Exercício

Sejam $f(x,y)=x^{2}+y^{2}$ e $C=\{(x,y)\in \mathbb {R} ^{2}:-x\leq 0;-y\leq 0;x+y-1\leq 0\}$. Considere o problema: $(P)\left\{{\begin{matrix}\min f(x,y)\\(x,y)\in \mathbb {R} ^{n}\end{matrix}}\right.$
Utilize o método de penalidade exterior para determinar o ponto de mínimo da função $f$ sobre o conjunto $C$.

### Implementação do algoritmo de penalidade exterior em SciLab

Considerando o problema
    $(P)\left\{{\begin{matrix}minf(x)\\g_{i}(x)\leq 0\forall i=1,\ldots ,p\\h_{j}(x)=0\forall j=1,\ldots ,q\end{matrix}}\right.$
com $f$ uma função quadrática, $A$ simétrica positiva definida, $g_{i},h_{j}$ lineares, e a função de penalidade, $H$, dada por:
    $H(x)=\sum _{i=1}^{p}(g_{i}^{+}(x,y))^{2}+\sum _{j=1}^{q}(h_{j}(x,y))^{2}$
Pode-se usar o método dos gradientes conjugados para resolver o seguinte problema:
    $(P)\left\{{\begin{matrix}minf(x)+H(x)\\x\in \mathbb {R} ^{n}\end{matrix}}\right.$
onde $f+H$ terá sua matriz Hessiana definida positiva.

## Método de penalidade interior

Este método também é conhecido como método de barreira. Ele consiste em trabalhar com funções de penalidade tais que $\forall x\in \partial C$ e qualquer que seja a sequência $\{x_{n}\}\subset C=\{x:g_{i}(x)<0\}$ para a qual $x_{n}\to x$, se tem que a função de penalidade tende a $+\infty$.
Mas como conseguir esse tipo de função?

### Exemplos

Considere o caso em que $g_{i}(x)=a_{i}^{\top }x-b_{i}$. Lembrando que a função logarítmica tem a propriedade:
    $\lim _{x\to 0^{+}}-\ln(x)=+\infty$
pode-se tomar $H_{1}(x)=-\sum _{i=1}^{p}\ln(b_{i}-a_{i}^{\top }x)$, pois
    $\lim _{a_{i}^{\top }x\to b_{i}}-\ln(b_{i}-a_{i}^{\top }x)=+\infty$
implica que
    $\lim _{x\to \partial C}H_{1}(x)=+\infty$
Analogamente, tem-se
    $\lim _{x\to 0^{+}}{\frac {1}{x}}=+\infty$
então, uma outra função com a propriedade desejada é $H_{2}(x)=\sum _{i=1}^{p}{\frac {1}{b_{i}-a_{i}^{\top }x}}$.
O problema a ser resolvido quando se quer aplicar o método de barreira é o seguinte:
    $(P)\left\{{\begin{matrix}\min f(x)\\g_{i}(x)\leq 0;i=1,\ldots ,p\end{matrix}}\right.$
onde $C=\{x:g_{i}(x)\leq 0,\forall i\}$ é tal que $C^{0}=\{x:g_{i}(x)<0,\forall i\}\not =\emptyset$
Observação: $C^{0}$ não é necessariamente igual ao interior do conjunto $C$. Por exemplo:

#### Definição

Se diz que uma função $B:C^{0}\mapsto \mathbb {R}$ é uma função de barreira se ela possui as seguintes propriedades:
* $B$ é limitada inferiormente em $C$.
* Para qualquer sequência $\{x_{n}\}\subset C^{0}$ tal que $\lim _{n\to \infty }x_{n}=x\in \partial C$ vale $\lim _{n\to \infty }B(x_{n})=+\infty$
* $B$ é contínua

### Algoritmo de barreira

Observação: Neste método os termos da sequência $\{x_{n}\}$ estão sempre em $C^{0}$.

### Implementação do algoritmo de barreira em SciLab

Considerando o problema
    $\left\{{\begin{matrix}minf(x)\\g_{i}(x)\leq 0\forall i=1,\ldots ,p\\\end{matrix}}\right.$
pode-se usar o método de barreira no conjunto:
    $C=\{x\in \mathbb {R} ^{n}:g_{i}(x)\leq 0\}$
Pode-se usar qualquer das funções de penalidade interior apresentadas, por exemplo:
    $B(x)=\sum _{i=1}^{p}{\frac {1}{g_{i}(x)}}$
ou ainda
    $B(x)=\sum _{i=1}^{p}-\ln(-g_{i}(x))$
Como $C^{0}=\{x\in \mathbb {R} ^{n}:g_{i}(x)<0\}$, o problema passa a ser:
    $\left\{{\begin{matrix}minf(x)+B(x)\\x\in C^{0}\end{matrix}}\right.$
Observação: Note que é necessário conhecer um ponto inicial $x_{0}\in C^{0}$, para servir de primeira aproximação, ou ponto de partida para o algoritmo.

# Métodos de região de confiança

Considere o seguinte problema de programação diferenciável não linear sem restrições:
    $(P)\left\{{\begin{matrix}\min f(x)\\x\in \mathbb {R} ^{n}\end{matrix}}\right.$
onde $f:\mathbb {R} ^{n}\mapsto \mathbb {R}$ é de classe $C^{2}(\mathbb {R} ^{n})$.
Observação: Como $f$ não é necessariamente convexa, a matriz $\nabla ^{2}f(x)$ pode não ser definida positiva, apesar de ser simétrica. Neste caso, o método de Newton ou suas variantes (direções conjugadas, quase Newton, etc) não servem.
O primeiro método de região de confiança (em inglês, Trust region method), foi introduzido por Powel em 1970 (qual artigo?) mas oficialmente introduzido por Dennis em 1978 (artigo?). Ele consiste no seguinte:
    A cada iteração, se constrói um modelo quadrático e uma região de confiança
este princípio pode ser considerado como uma extensão da busca de Armijo unidimensional.

## Breve revisão da busca de Armijo

Para entender a geometria do método de região de confiança, é bom lembrar a geometria da busca de Armijo unidimensional.
Seja $d$ uma direção de descida de uma função $f$ a partir do ponto $x$. Então $\nabla f(x)^{\top }d<0$. Agora, considerando $\theta :\mathbb {R} \mapsto \mathbb {R}$, definida por $\theta (t)=f(x+td)$, tem-se:
    $\theta '(t)=\nabla f(x+td)^{\top }d$. Assim, $\theta '(0)=\nabla f(x)^{\top }d<0$. Se $\alpha \in (0,1)$, então $\theta '(0)<\alpha \theta '(0)<0$.

### Exercício

Mostrar que sempre existe $t>0$ tal que ${\frac {f(x+td)-f(x)}{t}}={\frac {\theta (t)-\theta (0)}{t-0}}\leq \alpha \theta '(0)$.
A busca de Armijo consiste em tomar $t>0$.
Se ${\frac {f(x+td)-f(x)}{t}}>\alpha \theta '(0)>\theta '(0)$
Mas como $\theta '(0)=\lim _{t\to 0}{\frac {f(x+td)-f(x)}{t}}$, então existe algum $t>0$ tal que vale ${\frac {f(x+td)-f(x)}{t}}\leq \alpha \theta '(0)$. A tal ponto, chama-se ponto de Armijo.
Introduzindo as seguinte notação
    $m(x+h)=f(x)+\nabla f(x)^{\top }h$ (modelo linear para a função $f$) $pred=m(x)-m(x+td)=-t\theta '(0)$ (redução predita por este modelo) $ared=f(x)-f(x+td)$ (redução real no valor da função)
a pergunta é:
    Quando um ponto $t$ vai ser ponto de Armijo com essa notação?
Tem-se:
    $\alpha \cdot pred=-\alpha t\theta '(0)\leq f(x)-f(x+td)=ared$
Logo, se $\alpha \cdot pred\leq ared$ segue que $t$ é um ponto de Armijo.
Observações: Note que a essência da busca linear de Armijo é construir um modelo linear e um intervalo compacto $[0,t]$, sendo $t>0$ e o ponto inicial da busca e logo procurar o ponto de Armijo em $[0,t]$.

## De volta ao método

O método de região de confiança será uma generalização da busca de Armijo, consistindo da construção de um modelo quadrático e uma região $R$, chamada de região de confiança, e nessa região calcular o novo iterando.

### Algoritmo da região de confiança

Comentários: No algoritmo anterior, quando se tem um passo falho, a região de confiança sempre diminui. Seria bom incluir casos bons, onde a região deve crescer.

### Algoritmo da região de confiança melhorado
## O subproblema quadrático

Conforme foi explicado, o método das regiões de confiança constrói um modelo quadrático da forma:
    $m(h)=g^{\top }h+{\frac {1}{2}}h^{\top }Hh$
onde, no método, $g=\nabla f(x_{k})$ e $H=H_{k}$. Em tal modelo, tem-se
* $g$ um vetor não nulo;
* $h$ uma matriz simétrica (que pode não ser definida positiva)
O problema quadrático é
    $(PQ)\left\{{\begin{matrix}\min m(h)\\\|h\|\leq r\end{matrix}}\right.$
com $r>0$.
Este é o problema que será tratado a seguir.

### Exercício

Provar que $(PQ)$ sempre tem solução.
O exercício anterior garante que o método está bem definido, quer dizer, todas as etapas podem ser realizadas.

# O problema de mínimos quadrados

Este tipo de problema é muito frequente em ciências experimentais. Para ter um exemplo em mente durante a discussão que será feita mais adiante, considere as seguintes informações:
Segundo dados disponibilizados pelo IBGE, o Produto Interno Bruto per capita na cidade de São Paulo, no período de 2002 a 2005, foi (em reais): 17734, 19669, 20943 e 24083, respectivamente.
Com base nessas informações, como poderia ser feita uma previsão do valor correspondente ao ano seguinte (2006)?
Uma escolha possível seria supor que a cada ano o PIB aumenta uma aproximadamente constante, ou seja, usar um modelo linear para obter tal estimativa (que possivelmente será bem grosseira). Intuitivamente, bastaria analisar os dados disponíveis e a partir deles deduzir qual é o aumento que ocorre a cada ano. Depois, a previsão para 2006 seria aproximadamente igual à de 2005 somada com aquele aumento anual.
Esta idéia poderia até funcionar para o caso deste exemplo, mas o que fazer se a quantidade de dados disponíveis sobre algum fenômeno (ou alguma situação) for significativamente maior?
A melhor escolha, sem dúvida, é fazer uso de um computador para obter o modelo que melhor descreve o "comportamento" dos dados experimentais.
Em geral, os problemas de mínimos quadrados consistem em identificar os valores de determinados parâmetros, de modo que se satisfaçam certas equações $h_{i}(x)=0,\,i=1,\ldots ,p$. No contexto do exemplo anterior, se procura um modelo linear para os dados, ou seja, uma função $y=mx+n$ que os descreva da melhor forma possível. Assim, os parâmetros a considerar são $m$ e $n$. Os valores ideais para essas variáveis seriam aqueles que verificassem as seguintes equações:
    $\left\{{\begin{matrix}2002m+n&=&17734\\2003m+n&=&19669\\2004m+n&=&20943\\2005m+n&=&24083\end{matrix}}\right.$
Note que a partir dessas equações poderiam ser definidas as funções $h_{i}$ como:
    $h_{1}(m,n)=2002m+n-17734$
    $h_{2}(m,n)=2003m+n-19669$
    $h_{3}(m,n)=2004m+n-20943$
    $h_{4}(m,n)=2005m+n-24083$
É de se esperar que o sistema de equações obtido a pouco não admitirá uma solução exata, pois se tem mais equações do que variáveis.
Isso geralmente acontece, pois é comum haver uma quantidade $p$ de equações bem maior que o número $n$ de parâmetros a identificar. Em particular, quando todas as equações $h_{i}$ são lineares em suas $n$ variáveis, dificilmente existirá uma solução exata para o sistema linear resultante, pois este terá mais equações do que incógnitas (como no exemplo). Em geral, não é possível encontrar parâmetros que satisfaçam exatamente todas as equações. Por isso, costuma-se tentar identificar os parâmetros que "melhor se aproximam" de uma solução exata, em algum sentido.
Uma forma de obter uma solução aproximada (uma "quase-solução") resulta da seguinte observação: o valor de cada função $h_{i}$ em uma solução exata $x$ deveria ser zero. Se tal exigência é restritiva demais, e com ela não é possível encontrar qualquer solução, uma possibilidade seria exigir um pouco menos. Por exemplo, poderia ser exigido apenas que o valor de $h_{i}$, para $i=1,\ldots ,p$ seja, em geral, pequeno. Uma das formas de capturar essa idéia em termos mais precisos é dizer que se pretende minimizar a soma dos quadrados dos valores de cada $h_{i}$. Em símbolos, o problema passaria a ser:
    $\min _{x\in \mathbb {R} ^{n}}\sum _{i=1}^{p}\left[h_{i}(x)\right]^{2}$

## O caso linear

Neste caso, para cada índice $i=1,\ldots ,p$, a função $h_{i}$ é afim linear, ou seja:
    $h_{i}:\mathbb {R} ^{n}\mapsto \mathbb {R}$
    $h_{i}(x)=a_{i}^{\top }x+b_{i}$
onde $a_{i}\in \mathbb {R} ^{n}$ e $b_{i}\in \mathbb {R}$ para cada $i=1,\ldots ,p$. Deste modo, pode-se definir uma função $H$ como
    $H:\mathbb {R} ^{n}\mapsto \mathbb {R} ^{p}$ de modo que
    $H(x)={\begin{bmatrix}h_{1}(x)\\\vdots \\h_{p}(x)\end{bmatrix}}={\begin{bmatrix}a_{1}^{\top }x+b_{1}\\\vdots \\a_{p}^{\top }x+b_{p}\end{bmatrix}}={\begin{bmatrix}a_{1}^{\top }\\\vdots \\a_{p}^{\top }\end{bmatrix}}x+{\begin{bmatrix}b_{1}\\\vdots \\b_{p}\end{bmatrix}}$
Motivando a introdução da seguinte notação:
    $A={\begin{bmatrix}a_{1}^{\top }\\\vdots \\a_{p}^{\top }\end{bmatrix}},\quad b={\begin{bmatrix}b_{1}\\\vdots \\b_{p}\end{bmatrix}}$
Assim,
    $H(x)=Ax+b$
Logo, buscar uma solução exata é o mesmo que procurar uma solução para o seguinte sistema linear:
    $Ax=-b$
E uma solução aproximada poderia ser buscada a partir do seguinte problema de minimização:
    $\min _{x\in \mathbb {R} ^{n}}{\frac {1}{2}}\|Ax+b\|^{2}$

### Exercício

Verifique que se houver uma solução exata, ela também será um minimizador de $\sum _{i=1}^{p}\left[h_{i}(x)\right]^{2}$. A recíproca é verdadeira?
Analisando a função objetivo do problema de minimização anterior, tem-se:
    $f(x)={\frac {1}{2}}\|Ax+b\|^{2}={\frac {1}{2}}\langle Ax+b,Ax+b\rangle ={\frac {1}{2}}x^{\top }A^{\top }Ax+b^{\top }Ax+{\frac {1}{2}}b^{\top }b$
Logo, como $B=A^{\top }A$ é simétrica e semi-definida positiva, tem-se $f$ convexa. Isso implica que a condição necessária de primeira ordem é também suficiente. Assim, qualquer ponto $x\in \mathbb {R} ^{n}$ tal que $\nabla f(x)=0$ é solução do problema aproximado.
Calculando o gradiente da função objetivo tem-se:
    $0=\nabla f(x)=A^{\top }Ax+A^{\top }b$
Deste modo, a solução do problema é obtida resolvendo o sistema
    $A^{\top }Ax=-A^{\top }b$
Observe também que isso implica $A^{\top }(Ax+b)=0$, ou seja, $Ax+b\in \ker(A^{\top })$.

### Exemplo de aplicação

Considere dado um conjunto de pontos do plano $\mathbb {R} ^{2}$, por exemplo $\{(x_{i},y_{i})\}_{i=1}^{p}$, representando dados obtidos experimentalmente.
Perguntas:
    1. Qual é a função afim linear que melhor se aproxima dos dados experimentais?
    2. Qual é a função quadrática que melhor se aproxima dos dados experimentais?

#### Exercício

Explorar o exemplo anterior com dados concretos, implementando um dos três métodos de gradientes conjugados.

#### Observações

Conforme se aumenta o grau do polinômio que faz a aproximação dos dados, as colunas de $A$ têm elementos elevados a potências cada vez maiores, fazendo com que os autovalores de $A^{\top }A$ sejam cada vez mais dispersos. Com isso, $A^{\top }A$ torna-se mal condicionada.

#### Exercício

É possível, usando o problema de mínimos quadrados, verificar o postulado de Euclides que diz que "por dois pontos distintos passa uma única reta"?

#### Exercício

Usando o problema de mínimos quadrados, é possível inferir que "por três pontos distintos passa uma única curva quadrática"?

## O caso não linear

Para esse tipo de problemas, há dois métodos:
* Gauss-Newton
* Levemberg-Marquardt
Ambos são métodos do tipo Newton. Então, para entender cada um deles é preciso entender o Método de Newton.

### O método de Newton

Para entender a essência do método de Newton, primeiro considere que o problema a ser resolvido é
    $(P)\left\{{\begin{matrix}\min f(x)\\x\in \mathbb {R} ^{n}\end{matrix}}\right.$
sendo $h_{j}:\mathbb {R} ^{n}\rightarrow \mathbb {R}$, e portanto $f={\frac {1}{2}}\sum _{j=1}^{p}[h_{j}]^{2}$ de classe ${\mathcal {C}}^{2}\left(\mathbb {R} ^{n}\right)$. A idéia de Newton é usar o desenvolvimento até segunda ordem da série de Taylor da função $f$ em cada ponto iterado. Isto é, se o iterado é ${\bar {x}}$, então:
    $Q(x)=f({\bar {x}})+\nabla f({\bar {x}})^{\top }(x-{\bar {x}})+{\frac {1}{2}}(x-{\bar {x}})\nabla ^{2}f({\bar {x}})(x-{\bar {x}})$
Então a condição de Newton é que em cada iteração a Hessiana $\nabla ^{2}f$ deve ser definida positiva.
Calculando o gradiente da função $Q$, segue:
    $\nabla Q(x)=\nabla f({\bar {x}})+\nabla ^{2}f({\bar {x}})(x-{\bar {x}})$
Se $x^{*}$ é o (único) minimizador de $Q$, então
    $0=\nabla Q(x^{*})=\nabla f({\bar {x}})+\nabla ^{2}f({\bar {x}})(x^{*}-{\bar {x}})$
donde
    $\nabla ^{2}f({\bar {x}})(x^{*}-{\bar {x}})=-\nabla f({\bar {x}})$
Sendo $\nabla ^{2}f$ definida positiva, tal matriz é também inversível. Portanto:
    $x^{*}={\bar {x}}-\left[\nabla ^{2}f({\bar {x}})\right]^{-1}\nabla f({\bar {x}})$
Assim, pode-se usar a seguinte iteração:
    $x_{k+1}=x_{k}-\left[\nabla ^{2}f(x_{k})\right]^{-1}\nabla f(x_{k})$

#### Algoritmo de Newton (puro)

Voltando ao problema original, de mínimos quadrados, se tinha:
    $f(x)={\frac {1}{2}}\sum _{i=1}^{p}\left[h_{i}(x)\right]^{2}$
Calculando o gradiente desta função, resulta:
    $\nabla f(x)=\sum _{i=1}^{p}h_{i}(x)\nabla h_{i}(x)$
Considera-se $H:\mathbb {R} ^{n}\mapsto \mathbb {R} ^{p}$ definida por
    $H(x)={\begin{bmatrix}h_{1}(x)\\\vdots \\h_{p}(x)\end{bmatrix}}$
Deste modo, a Jacobiana de $H$ verifica:
    $\nabla f(x)=\left[J_{H}(x)\right]H(x)$
pois o produto de uma matriz por um vetor tem como resultado um vetor que é a combinação linear das colunas da matriz, com coeficientes que são as coordenadas do vetor.
Além disso, tem-se
    $\nabla ^{2}f(x)=\sum _{i=1}^{p}h_{i}(x)\nabla ^{2}h_{i}(x)+\sum _{i=1}^{p}\nabla h_{i}(x)\nabla h_{i}(x)^{\top }$
Seja
    $B(x)=\sum _{i=1}^{p}\nabla h_{i}(x)\nabla h_{i}(x)^{\top }=J_{H}(x)J_{H}(x)^{\top }$
Sabe-se que uma matriz $D$ é definida positiva se $x^{t}Dx>0$ para qualquer $x\not =0$. Fazendo $D=\nabla h_{i}(x)\nabla h_{i}(x)^{\top }$, tem-se:
    $x^{\top }\nabla h_{i}(x)\nabla h_{i}(x)^{\top }x=\left[\nabla h_{i}(x)^{\top }x\right]^{2}\geq 0$
Para que $D$ seja definida positiva, é necessário que $S_{P}\left(\nabla h_{i}(x)\right)=\mathbb {R} ^{n}$ ( deve gerar todo o espaço), neste caso, se diz que $J_{H}(x)$ é de posto máximo.

### Algoritmo de Levemberg-Marquardt

A idéia de Levemberg-Marquardt foi perturbar a matriz $B(x)$, considerando $B(x)+\rho I$, para algum $\rho >0$ pequeno.

#### Exercício

Enumere as diferenças que existem nos seguintes algoritmos:
* Newton
* Gauss-Newton
* Levenberg-Marquardt

# KKT

Neste capítulo o objetivo é desenvolver algumas ideias e provar o teorema de Karush–Kuhn–Tucker (também chamado simplesmente de teorema KKT) que será utilizado no capítulo seguinte para explorar os métodos duais. O teorema KKT é bem útil para resolver problemas do tipo
    $(P)\left\{{\begin{matrix}\min f(x)\\g_{i}(x)\leq 0;i=1,\ldots ,p\\h_{j}(x)=0;j=1,\ldots ,q\end{matrix}}\right.$

## Cones
### Definição

Um conjunto $C\in \mathbb {R} ^{n}$ é um cone quando
    $d\in C\Rightarrow td\in C,\forall t\in \mathbb {R} _{+}$
Em outras palavras, a propriedade que caracteriza um cone é que este tipo de conjunto contém todos os múltiplos não nulos de qualquer de seus elementos.

### Definição

Dado um subconjunto $C\subset \mathbb {R} ^{n}$, o cone polar de $C$ é o conjunto definido por
    $C^{*}=\{p\in \mathbb {R} ^{n}:p^{\top }x\leq 0,\ \forall x\in C\}$.
Observações:
* $C^{*}$ é um cone: Se $d\in C^{*}$ tem-se que $d^{\top }x\leq 0,\ \forall x\in C$. Logo, para qualquer $t\in \mathbb {R} _{+}$, vale $(td)^{\top }x=td^{\top }x\leq 0,\ \forall x\in C$. Disto segue que $td\in C^{*}$, mostrando que $C^{*}$ é um cone.
* Sempre se tem que $C\subseteq (C^{*})^{*}$ (Verifique).
Na segunda propriedade a igualdade pode não ocorrer (exemplo?). Para o objetivo deste texto, o ideal seria que a igualdade valesse. Mas será que isso ocorre para algum conjunto? A resposta é sim e, conforme o próximo lema, basta que $C$ seja um cone convexo fechado.

### Lema (Farkas)

Se $C\subset \mathbb {R} ^{n}$ um cone convexo fechado, então $C=(C^{*})^{*}$.

### Definição

Dado $x\in C$, se diz que $d\in \mathbb {R} ^{n}$ é uma direção viável em $x$, com respeito a $C$, quando existe $\epsilon >0$ tal que
       $x+td\in C,\ \forall t\in [0,\epsilon ]$.
    O conjunto de todas as direções viáveis em $x$, com respeito ao conjunto $C$, será denotado por $V_{C}(x)$.
Esse conjunto $V_{C}(x)$ é o cone das direções viáveis em $x$, com respeito a $C$.

### Definição

Uma direção $d\in \mathbb {R} ^{n}$ é uma direção de descida da função $f$ em $x$, se existe $\epsilon >0$ tal que
       $f(x+td)<f(x),\ \forall t\in (0,\epsilon ]$.
    O conjunto das direções de descida será denotado por $D(x)$.

## Caracterização das direções de descida
### Lema

Seja $f:\mathbb {R} ^{n}\rightarrow \mathbb {R}$ uma função diferenciável em $x\in \mathbb {R} ^{n}$. Então
* $\nabla f(x)^{\top }d\leq 0,\ \forall d\in D(x)$.
* $d\in \mathbb {R} ^{n}$ satisfaz $\nabla f(x)^{\top }d<0\ \Rightarrow d\in D(x)$.

## O cone viável linearizado
### Definição

Dado $x\in C=\{x\in \mathbb {R} ^{n};g_{i}(x)\leq 0{\text{ e }}h_{j}(x)=0\}$, a desigualdade $g_{i}(x)\leq 0$ é uma restrição ativa em $x$ se $g_{i}(x)=0$.

### Observações

* O conjunto formado pelos índices das restrições de desigualdade ativas é denotado por $I(x)$. Assim,
    $I(x)=\{i:g_{i}(x)=0\}$

### Definição

Dado um ponto $x\in C$ e o conjunto $I(x)$, se define o cone viável linearizado de $C$ a partir de $x$ como
    $L(x,C)=\{d\in \mathbb {R} ^{n}:\nabla g_{j}(x)^{\top }d\leq 0,\ \forall j\in I(x)\ {\text{e}}\ \nabla h_{i}(x)^{\top }d=0,\ \forall i=1,\dots ,q\}$.
$L(x,C)$ é um cone não-vazio convexo e fechado pois, $0\in L(x,C)$. E se $y,w\in L(x,C)$, tem-se
    $\nabla h_{i}(x)^{\top }(\alpha y+(1-\alpha )w)=\alpha \nabla h_{i}(x)^{\top }y+(1-\alpha )\nabla h_{i}(x)^{\top }w=\alpha 0+(1-\alpha )0=0$ e
    $\nabla g_{j}(x)^{\top }(\alpha y+(1-\alpha )w)=\alpha \nabla g_{j}(x)^{\top }y+(1-\alpha )\nabla g_{j}(x)^{\top }w\leq \alpha 0+(1-\alpha )0\leq 0$.
Portanto $\alpha y+(1-\alpha )w\in L(x,C)$ mostrando que $L(x,C)$ é convexo.
Para mostrar que $L(x,C)$ é fechado, pode-se pegar uma sequência convergente $(d^{k})\in L(x,C)$ e mostrar que o ponto de acumulação dela esta em $L(x,C)$.
Tem-se que $\nabla h_{i}(x)^{\top }d^{k}=0\ {\text{e}}\ \nabla g_{j}(x)^{\top }d^{k}\leq 0,\ \forall k\in \mathbb {N}$.
Passando o limite com $k\rightarrow \infty$, obtem-se
    $0=\lim _{k\rightarrow \infty }{\nabla h_{i}(x)^{\top }d^{k}}=\nabla h_{i}(x)^{\top }\lim _{k\rightarrow \infty }{d^{k}}=\nabla h_{i}(x)^{\top }d$ e
    $0\geq \lim _{k\rightarrow \infty }{\nabla g_{j}(x)^{\top }d^{k}}=\nabla g_{j}(x)^{\top }\lim _{k\rightarrow \infty }{d^{k}}=\nabla g_{j}(x)^{\top }d$.
Isso mostra que $L(x,C)$ é fechado.

### Lema (Caratheodory)

Sejam $y_{1},\dots ,y_{m},w_{1},\dots ,w_{p}\in \mathbb {R} ^{n}$. Seja $x\in \mathbb {R} ^{n}$ com $x\neq 0$ e $\alpha _{1},\dots ,\alpha _{m},\beta _{1},\dots ,\beta _{p}$ escalares tais que$\beta _{j}\geq 0\ \forall j=1,\dots ,p$ e
    $x=\sum _{i=1}^{m}\alpha _{i}y_{i}+\sum _{j=1}^{p}\beta _{j}w_{j}$.
Então existem subconjuntos $I\subset \{1,\dots ,m\}{\text{, }}J\subset \{1,\dots ,p\}$ e escalares $\alpha _{i}^{*}$ com $i\in I$e $\beta _{j}^{*}\ \forall j\in J$ tais que
    $x=\sum _{i\in I}\alpha _{i}^{*}y_{i}+\sum _{j\in J}\beta _{j}^{*}w_{j}$ e os vetores $\{y_{i}\}_{i\in I}\cup \{w_{j}\}_{j\in J}$ são linearmente independentes.

### Definição

Dado um ponto $x\in C$, se define o cone $G(x)$ por
       $G(x)=\{\sum _{i=1}^{q}\alpha _{i}\nabla h_{i}(x)+\sum _{j\in I(x)}\beta _{j}\nabla g_{j}(x):\beta _{j}\geq 0,\ \forall j\in I(x)\}$.
A seguir, serão mostradas algumas propriedades deste cone.

### Lema

Para qualquer $x\in C$, $G(x)$ é um cone convexo e fechado.

### Lema

Para qualquer $x\in C$, $G(x)=L(x,C)^{*}$.

## O cone tangente
### Definição

Um vetor $d\in \mathbb {R} ^{n}$ é chamado direção tangente em $C$ a partir de $x\in C$ quando ou $d=0$ ou $\exists (x^{k})\subset C$ tal que
    $x^{k}\rightarrow x$ e ${\frac {x^{k}-x}{\|x^{k}-x\|}}\rightarrow {\frac {d}{\|d\|}}$.

### Observações

* O conjunto de todas as direções tangentes no ponto $x\in C$, é denominado cone tangente, e denotado por $T(x,C)$.
* Se $a\in C$, então $T(a,C)$ também pode ser descrito como
    $T(a,C)=\left\{d\in ;\exists \{d_{k}\}{\text{ com }}d_{k}\to d;\quad \exists \{t_{k}\}{\text{ com }}t_{k}\to 0{\text{ tais que }}x=a+t_{k}d_{k}\in C,\,\forall k\right\}$

### Exercício

Verifique que $T(a,C)$ é de fato um cone (e portanto merece ser chamado de "cone tangente").

#### Exemplo de cone tangente

Determinar o cone tangente ao ponto $a=(0,0)$ do quadrado unitário com vértices $(0,0)$, $(0,1)$, $(-1,1)$ e $(-1,0)$.

#### Propriedades do cone tangente

O cone tangente definido anteriormente tem as seguintes propriedades:
* $T(a,C)$ é fechado e $0\in T(a,C)$
* Se $C\subset D$ então $T(a,C)\subset T(a,D)$
* Se $V$ é uma vizinhança de $a$, então $T(a,C)=T(a,V\cap C)$

##### Observação

A terceira propriedade indica que o cone tangente só depende do que ocorre bem perto de $a$, no conjunto $C$.

##### Lema

Para qualquer $x\in C$, $T(x,C)$ é fechado.

##### Exercício

Verificar que:
* $T(a,C)\subset L(a,C)$.
* Se $C=\{(x,y)\in \mathbb {R} ^{2};x^{2}+y\leq 0;\quad x^{2}-y\leq 0\}$ e $a=(0,0)$, então $T(a,C)\not =L(a,C)$.
Demonstração :

##### Lema

Se $a\in C$ é um mínimo local do problema (P), então $\nabla f(a)^{\top }d\geq 0,\ \forall d\in T(a,C)$.

## Teorema KKT
### Teorema (Condições de KKT)

Seja $C=\{x\in \mathbb {R} ^{n};g_{i}(x)\leq 0{\text{ e }}h_{j}(x)=0\}$ e considere $a\in C$ um minimizador local do problema
    $(P)\left\{{\begin{matrix}\min f(x)\\x\in C\end{matrix}}\right.$
Se $T(a,C)^{*}=L(a,C)^{*}$, então existem $u\in \mathbb {R} ^{p}$ e $v\in \mathbb {R} ^{q}$ tais que:
* $-\nabla f(a)=\sum _{i=1}^{p}u_{i}\nabla g_{i}(a)+\sum _{j=1}^{q}v_{j}\nabla h_{j}(a)$
* $u_{i}\geq 0,\ \forall i=1,\dots ,p$
* $u_{i}g_{i}(a)=0,\ \forall i=1,\dots ,p$.

# Métodos duais
## Lagrangiana

O conceito de lagrangiana está sempre relacionado ao seguinte problema:
    $(P)\left\{{\begin{matrix}\min f(x)\\g_{i}(x)\leq 0;i=1,\ldots ,p\\h_{j}(x)=0;j=1,\ldots ,q\end{matrix}}\right.$

### Definição

A função lagrangiana associada ao problema $(P)$ é
    $l:\mathbb {R} ^{n}\times \mathbb {R} ^{p}\times \mathbb {R} ^{q}\mapsto \mathbb {R}$ definida por
    $l(x,u,v)=f(x)+\sum _{i=1}^{p}u_{i}g_{i}(x)+\sum _{j=1}^{q}v_{j}h_{j}(x)$.
Em alguns livros é usada a seguinte notação:
    $G:\mathbb {R} ^{n}\mapsto \mathbb {R} ^{p}$ definida por
    $G(x)={\begin{bmatrix}g_{1}(x)\\\vdots \\g_{p}(x)\end{bmatrix}}$
e
    $H:\mathbb {R} ^{n}\mapsto \mathbb {R} ^{q}$ definida por
    $H(x)={\begin{bmatrix}h_{1}(x)\\\vdots \\h_{q}(x)\end{bmatrix}}$
Deste modo, a lagrangiana fica expressa por
    $l(x,u,v)=f(x)+u^{\top }G(x)+v^{\top }H(x)$
que é uma representação bem mais compacta.

## Condições de otimalidade

Para permitir a compreensão da importância da função lagrangiana em otimização, é preciso ter em mente os principais resultados que garantem a otimalidade de uma solução para o problema $(P)$. Nas próximas seções será apresentado um breve resumo das condições de otimalidade, dividindo-as em dois casos:
* Caso particular: quando $C=\{x\in \mathbb {R} ^{n};g_{i}(x)\leq 0{\text{ e }}h_{j}(x)=0\}$ é convexo e fechado.
* Caso geral: quando $C$ é arbitrário.

### Caso particular
#### Proposição

Seja $f$ função de classe ${\mathcal {C}}^{1}$ no conjunto $C$. Se ${\bar {x}}$ é um minimizador local de $f$ no conjunto convexo e fechado $C$, então:
    $\langle \nabla f(x),x-{\bar {x}}\rangle \geq 0,\,\forall x\in C$

#### Observação

A condição $\langle u,v\rangle \geq 0$ significa que os vetores $u$ e $v$ formam um ângulo reto ou agudo (menor ou igual a 90 graus), conforme indicado na figura a seguir:
No caso específico, com $u=\nabla f$ e $v=x-{\bar {x}}$, $\langle u,v\rangle$ é a derivada direcional de $f$ na direção $x-{\bar {x}}$. Quando tal número é não negativo, intuitivamente a função cresce naquela direção.
Quando $C$ é um conjunto convexo e fechado, a existência de uma solução para o problema $(P)$ é garantida pela seguinte proposição:

#### Proposição

Se ${\bar {x}}\in C$, $f$ é convexa e
    $\langle \nabla f(x),x-{\bar {x}}\rangle \geq 0,\,\forall x\in C$
${\bar {x}}$
$f$
$C$
${\bar {x}}$
$(P)$
Até aqui, não é exigido que qualquer das funções $g_{i}$ ou $h_{j}$ sejam diferenciáveis. Isto será utilizado mais adiante, nos algoritmos.
A próxima proposição fornece uma caracterização dos minimizadores, em termos do conceito de projeção.
Lembre-se que a projeção de um ponto ${\bar {y}}$ sobre o conjunto $C$, denotada por ${\bar {P}}=P_{C}({\bar {y}})$, satisfaz $\langle {\bar {P}}-{\bar {y}},x-{\bar {P}}\rangle \geq 0,\,\forall x\in C$. Na verdade, vale:
    ${\bar {P}}=P_{C}({\bar {y}})\Leftrightarrow \langle {\bar {P}}-{\bar {y}},x-{\bar {P}}\rangle \geq 0,\,\forall x\in C$

#### Proposição

Seja $\alpha >0$ um número real fixado.
* Se ${\bar {x}}$ é um minimizador local de $f$ em $C$, então ${\bar {x}}=P_{C}({\bar {x}}-\alpha \nabla f({\bar {x}}))$
* Se $f$ é convexa e ${\bar {x}}=P_{C}({\bar {x}}-\alpha \nabla f({\bar {x}}))$, então ${\bar {x}}$ é um minimizador global de $f$ em $C$.

### Caso geral

Para tratar este caso, é preciso utilizar o conceito de cone tangente. O conjunto contínua o mesmo, ou seja, $C=\{x\in \mathbb {R} ^{n};g_{i}(x)\leq 0{\text{ e }}h_{j}(x)=0\}$, embora não seja mais suposto que ele é convexo. Mesmo assim, $C$ ainda será fechado, pois as funções $g_{i}$ e $h_{j}$ que o definem são contínuas.

#### Teorema

* Se ${\bar {x}}$ é um minimizador local de $f$ em $C$, então $\langle \nabla f({\bar {x}}),d\rangle \geq 0,\,\forall d\in T({\bar {x}},C)$.
* Se $C$ é convexo, $f$ é convexa e $\langle \nabla f({\bar {x}}),d\rangle \geq 0,\,\forall d\in T({\bar {x}},C)$, então ${\bar {x}}$ é minimizador global de $f$ em $C$.
Este teorema pode ser demonstrado de forma análoga a que foi feita anteriormente.
Seja ${\tilde {C}}$ definido como:
    ${\tilde {C}}={\tilde {C}}_{a}=\left\{x\in \mathbb {R} ^{n};g_{i}(x)\leq 0,\,\forall i\in I(a);\quad h_{j}(x)=0\right\}$.
Pela segunda propriedade do cone tangente, tem-se:
    $T(a,V\cap {\tilde {C}})=T(a,C)=T(a,V\cap {\tilde {C}})$. Logo,
    $T(a,C)=T(a,{\tilde {C}})$
Em outras palavras, se é dado um conjunto ${\tilde {C}}$ e depois se restringe tal conjunto para $C$, através do acréscimo de restrições inativas em um ponto $a$, os cones tangentes aos dois conjuntos (no ponto $a$) coincidem.

#### Definição

Toda condição que implica que $T(a,C)=L(a,C)$ é chamada de condição de qualificação das restrições.
Observação: Também se pode dizer condições de regularidade das restrições (do inglês, Regularity conditions).

#### Exemplos de condições de qualificação das restrições

(1) Se $g_{i}$ e $h_{i}$ são funções afim-lineares, então para qualquer $x\in C$, tem-se $T(x,C)=L(x,C)$. Prova-se isso trivialmente
(2) Condições de Slater: Se as funções $g_{i}$ são convexas e as $h_{i}$ são afim lineares e, além disso, existe ${\hat {x}}\in C$ tal que $g_{i}({\hat {x}})<0$ para todo $i$, $h_{j}({\hat {x}})=0$, então para qualquer $x\in C$, tem-se $T(x,C)=L(x,C)$.
(3) Condições de Mangasarian-Fromowitz: Se $\{\nabla h_{j}(x)\}$ é linearmente independente e existe ${\tilde {d}}$ tal que $\langle \nabla h_{j}(x),{\tilde {d}}\rangle =0$ para tpdp $j$ e $\langle \nabla g_{i}(x),{\tilde {d}}\rangle <0$.

##### Teorema (Karush–Kuhn–Tucker)

Suponha que $f$, $g_{i}$ e $h_{j}$ são funções de classe ${\mathcal {C}}^{1}$ em uma vizinhança do ponto ${\bar {x}}$ e que $T({\bar {x}},C)=L({\bar {x}},C)$. Se ${\bar {x}}$ é um minimizador local de $f$ em $C$, então existem $u\in \mathbb {R} ^{p}$ e $v\in \mathbb {R} ^{q}$ tais que:
* $\nabla f({\bar {x}})+\sum _{i=1}^{p}u_{i}\nabla g_{i}({\bar {x}})+\sum _{j=1}^{q}v_{j}\nabla h_{j}({\bar {x}})=0$
* $u_{i}\geq 0,\,\forall i=1,\ldots ,p$
* $u_{i}g_{i}({\bar {x}})=0,\,\forall i=1,\ldots ,q$
Note que aqui aparece a lagrangiana, pois a primeira condição é equivalente a:
    $\nabla _{x}l(x,u,v)=0$
O essencial para a existência de $l(u,v)$ é que $T({\bar {x}},C)=L({\bar {x}},C)$.

##### Teorema

Suponha-se que $f$, $g_{i}$ e $h_{j}$ são funções de classe ${\mathcal {C}}^{1}$ em uma vizinhança de ${\bar {x}}$, que $f$ e $g_{i}$ são convexas e que $h_{j}$ são afim-lineares. são funções de classe ${\mathcal {C}}^{1}$. Se existem $u\in \mathbb {R} ^{p}$ e $v\in \mathbb {R} ^{q}$ tais que:
* $\nabla f({\bar {x}})+\sum _{i=1}^{p}u_{i}\nabla g_{i}({\bar {x}})+\sum _{j=1}^{q}v_{i}\nabla h_{j}({\bar {x}})=0$
* $u_{i}\geq 0,\,\forall i=1,\ldots ,p$
* $u_{i}g_{i}({\bar {x}})=0,\,\forall i=1,\ldots ,p$
* $g_{i}({\bar {x}})\leq 0,\,\forall i=1,\ldots ,p$
* $h_{j}({\bar {x}})=0,\,\forall j=1,\ldots ,q$
A partir deste teorema são construídos alguns algoritmos.
Considere o seguinte problema:
    $\left\{{\begin{matrix}\min f(x)\\g_{i}(x)\leq 0;i=1,\ldots ,p\\h_{j}(x)=0;j=1,\ldots ,q\end{matrix}}\right.$
Sabe-se que $l:\mathbb {R} ^{n}\times \mathbb {R} ^{p}\times \mathbb {R} ^{q}\mapsto \mathbb {R}$ dada por
    $l(x,u,v)=f(x)+\sum _{i=1}^{p}u_{i}g_{i}(x)+\sum _{j=1}^{q}v_{j}h_{j}(x)$.
Agora, tem-se as KKT:

##### Teorema

Supondo que $f,g_{i}$ e $h_{j}$ são de classe ${\mathcal {C}}^{1}$ em uma vizinhança de ${\bar {x}}\in C$ e que $T({\bar {x}},C)=L({\bar {x}},C)$, se ${\bar {x}}$ é um minimizador local de $f$ em $C$, então $\exists {\bar {u}}\in \mathbb {R} ^{p}$ tal que $\exists {\bar {v}}\in \mathbb {R} ^{q}$ de modo que:
* $\nabla _{x}l({\bar {x}},{\bar {u}},{\bar {v}})=0$
* ${\bar {u}}\geq 0$
* $\nabla _{u}l({\bar {x}},{\bar {u}},{\bar {v}})\leq 0$
* ${\bar {u}}^{\top }\nabla _{u}l({\bar {x}},{\bar {u}},{\bar {v}})=0$
* $\nabla _{v}l({\bar {x}},{\bar {u}},{\bar {v}})=0$

## Uma inequação sobre ínfimos e supremos
### Teorema

Sejam $X\subset \mathbb {R} ^{n}$ e $Y\subset \mathbb {R} ^{m}$ dois subconjuntos arbitrários e considere uma aplicação
$K:X\times Y\mapsto \mathbb {R}$. Então
    $-\infty \leq \sup _{y\in Y}\inf _{x\in X}K(x,y)\leq \inf _{x\in X}\sup _{y\in Y}K(x,y)\leq +\infty$

### Exercício

Verifique que:
    $-\infty \leq \sup _{\begin{smallmatrix}u\geq 0\\v\in \mathbb {R} ^{q}\end{smallmatrix}}\inf _{x\in \mathbb {R} ^{n}}l(x,u,v)\leq \inf _{x\in \mathbb {R} ^{n}}\sup _{\begin{smallmatrix}u\geq 0\\v\in \mathbb {R} ^{q}\end{smallmatrix}}l(x,u,v)\leq +\infty$
Defina-se a função:
    $\alpha :\mathbb {R} ^{n}\mapsto \mathbb {R} \cup \{+\infty \}$, dada por
    $\alpha (x)=\sup _{\begin{smallmatrix}u\geq 0\\v\in \mathbb {R} ^{q}\end{smallmatrix}}l(x,u,v)$
e também
    $\beta :[0,+\infty )^{p}\times \mathbb {R} ^{q}\mapsto \mathbb {R} \cup \{-\infty \}$, dada por
    $\beta (u,v)=\inf _{x\in \mathbb {R} ^{n}}l(x,u,v)$
Conforme o exercício anterior, tem-se então
    $-\infty \leq \sup _{\begin{smallmatrix}u\geq 0\\v\in \mathbb {R} ^{q}\end{smallmatrix}}\beta (u,v)\leq \inf _{x\in \mathbb {R} ^{n}}\alpha (x)\leq +\infty$
Observando a relação entre essas funções, é natural considerar dois problemas de otimização:
    $(Pr)\left\{{\begin{matrix}\min \alpha (x)\\x\in \mathbb {R} ^{n}\end{matrix}}\right.$
e
    $(D)\left\{{\begin{matrix}\max \beta (u,v)\\u\geq 0\\v\in \mathbb {R} ^{q}\end{matrix}}\right.$

### Comentários

* As funções $\alpha$ e $\beta$ são conhecidas na literatura como funções em dualidade (ou mais frequentemente, funções duais);
* O problema $(Pr)$ é conhecido como problema primal, enquanto $(D)$ é chamado de problema dual;
* Fazendo ${\bar {\alpha }}=\inf _{x\in \mathbb {R} ^{n}}\alpha (x)$ e ${\bar {\beta }}=\sup _{\begin{smallmatrix}u\geq 0\\v\in \mathbb {R} ^{q}\end{smallmatrix}}\beta (u,v)$, segue-se do exercício anterior que ${\bar {\beta }}\leq {\bar {\alpha }}$;
* A diferença ${\bar {\alpha }}-{\bar {\beta }}$ é chamada de brecha de dualidade, ou salto de dualidade (do inglês, skip duality);

### Exercício

Verifique que: $\alpha (x)=\left\{{\begin{matrix}f(x)&,{\text{ se }}x\in C\\+\infty &,{\text{ se }}x\not \in C\end{matrix}}\right.$

### Exercício

Verifique que $(D)$ consiste de maximizar uma função côncava em um poliedro. Lembre-se:
   * Uma função $f$ é côncava quando $-f$ for convexa.
   * Um poliedro é qualquer intersecção finita de semiespaços fechados.

### Exemplo numérico: problema primal e seu dual

Considere o problema
    $(P)\left\{{\begin{matrix}\min x^{2}\\1\leq x\leq 2\end{matrix}}\right.$

## Ponto de sela

Este é um conceito muito importante relacionado à lagrangiana.

### Definição

Dado o problema $(P)$ e a lagrangiana $l$ associada a esse problema, se diz que $({\bar {x}},{\bar {u}},{\bar {v}})$ é um ponto de sela de $l$ se ${\bar {u}}\geq 0$ e:
    $l({\bar {x}},u,v)\leq l({\bar {x}},{\bar {u}},{\bar {v}})\leq l(x,{\bar {u}},{\bar {v}}),\forall x\in \mathbb {R} ^{n},\forall u\geq 0,\forall v\in \mathbb {R} ^{q}$.

### Teorema

O ponto $({\bar {x}},{\bar {u}},{\bar {v}})$ é um ponto de sela de $l$ se, e somente se:
* ${\bar {x}}$ é solução de $(Pr)$;
* $({\bar {u}},{\bar {v}})$ é solução de $(D)$;
* ${\bar {\alpha }}={\bar {\beta }}$.

### Exemplos

Considere novamente o problema de otimização dado por:
    $\left\{{\begin{matrix}\min x^{2}\\1\leq x\leq 2\end{matrix}}\right.$
Verificar se a lagrangiana associada à $(P)$ tem ponto de sela.

### Análise do problema

Considerando $(P)$, $(Pr)$, $(D)$ e $l$, se $({\bar {u}},{\bar {v}})$ é uma solução do problema dual, considere o seguinte problema:
    $(P_{{\bar {u}},{\bar {v}}})\left\{{\begin{matrix}\min l(x,{\bar {u}},{\bar {v}})\\x\in \mathbb {R} \end{matrix}}\right.$
que no caso do exemplo reduz-se a
    $(P_{{\bar {u}},{\bar {v}}})\left\{{\begin{matrix}\min x^{2}+2(1-x)\\x\in \mathbb {R} \end{matrix}}\right.$
A solução deste problema é obtida resolvendo $2x-2=0$, sendo portanto $x=1$. Note que esta é a solução do problema primal $(Pr)$ (e consequentemente do problema original $(P)$).
Será apenas uma coincidência? Ou ainda, em que situações a solução deste último problema será também solução do problema original?
A resposta será dada pelo próximo teorema. Acompanhe.

#### Teorema (dualidade lagrangiana convexa)

Suponha-se que $f,g_{i}:\mathbb {R} ^{n}\mapsto \mathbb {R}$ são de classe ${\mathcal {C}}^{1}$ e convexas, e que as funções $h_{j}$ são afim lineares e $T(x,C)=L(x,C),\forall x\in C$. Nestas condições:
* Se o problema $(P)$ tem solução, então ${\bar {\alpha }}={\bar {\beta }}$ e os problemas $(Pr)$ e $(D)$ têm solução.
* Se $(P)$ tem solução, e $({\bar {u}},{\bar {v}})$ é solução de $(D)$, então as soluções de $(Pr)$ são as soluções de $(P_{{\bar {u}},{\bar {v}}})$, onde
    $(P_{{\bar {u}},{\bar {v}}})\left\{{\begin{matrix}\min l(x,{\bar {u}},{\bar {v}})\\x\in \mathbb {R} \end{matrix}}\right.$
$(P)$
Antes da demonstração, vale a pena imaginar a seguinte aplicação da segunda parte do teorema: Se por alguma razão não se sabe resolver o problema original $(P)$, pode-se optar por resolver $(D)$ (um problema concavo em um poliedro), e depois resolver $(P_{{\bar {u}},{\bar {v}}})$ (que é um problema convexo sem restrições). Em outras palavras, é possível trocar um problema difícil por dois problemas mais fáceis, $(D)$ e $(P_{{\bar {u}},{\bar {v}}})$.
Agora a demonstração do teorema:

#### Exercício

Verificar se existe salto de dualidade nos problemas em dualidade para o seguinte problema de minimização:
    $(P_{1})\left\{{\begin{matrix}\min x-y^{2}\\x^{2}+y^{2}\leq 1\\x+y\leq 1\end{matrix}}\right.$

#### Exercício

Juntamente com o problema $(P_{1})$ do exercício anterior, considere o seguinte problema:
    $(P_{2})\left\{{\begin{matrix}\min x-y^{2}\\x\geq 0\\y\geq 0\\x+y\leq 1\end{matrix}}\right.$
Os problemas são equivalentes? (no sentido de que têm as mesmas funções objetivo e o mesmo conjunto de restrições) O que acontece com relação às condições de KKT?
$f(x,y)=x-y^{2}$

#### Exercício

Experimente escolher $x\in \mathbb {R} ^{5}$ e uma transformação linear, e um poliedro (intersecção finita de semi-espaços). É difícil de resolver o problema primal. Tente resolver o dual, usando os métodos conhecidos.
A seguir será apresentada uma proposição que responde a uma pergunta deixada anteriormente:

#### Proposição

Considere o problema $(P)$ a lagrangiana $l$ e os problemas em dualidade $(Pr)$ e $(D)$ e $({\bar {u}},{\bar {v}})$ soluções de $(D)$.
Se ${\bar {x}}$ é solução do problema
    $(P_{{\bar {u}},{\bar {v}}})\left\{{\begin{matrix}\min l(x,{\bar {u}},{\bar {v}})\\x\in \mathbb {R} \end{matrix}}\right.,$
${\bar {x}}\in C$
$g_{i}({\bar {x}}){\bar {u}}_{i}=0,\forall i$
${\bar {x}}$
$(P)$
Tal proposição fornece um roteiro para quem precisa resolver o problema $(P)$ relativamente difícil:
* Primeiramente, resolve-se $(D)$;
* Depois, constrói-se o problema $(P_{{\bar {u}},{\bar {v}}})$ e encontra-se uma solução ${\bar {x}}$ para o mesmo;
* Finalmente, se ${\bar {x}}$ satisfaz as últimas condições da proposição, ele é também uma solução de $(P)$.

## Resumo do esquema de dualidade

Neste ponto, pode-se sintetizar a estratégia geral para a resolução de problemas de otimização utilizando esquemas de dualidade.
Considere o problema
    $\left\{{\begin{matrix}\min f(x)\\g_{i}(x)\leq 0;i=1,\ldots ,p\\h_{j}(x)=0;j=1,\ldots ,q\end{matrix}}\right.$
onde $f,g_{i},h_{j}:\mathbb {R} ^{n}\mapsto \mathbb {R}$ são funções de classe ${\mathcal {C}}^{1}(\mathbb {R} ^{n})$, e seja a lagrangiana $l:\mathbb {R} ^{n}\times \mathbb {R} ^{p}\times \mathbb {R} ^{q}\mapsto \mathbb {R}$ definido por
    $l(x,u,v)=f(x)+\sum _{i=1}^{p}u_{i}g_{i}(x)+\sum _{j=1}^{q}v_{j}h_{j}(x)$.
Convenciona-se que:
* $x$ é a variável primal;
* $(u,v)$ é a variável dual;
Nesse sentido, "o $\mathbb {R} ^{p}\times \mathbb {R} ^{q}$ é o dual de $\mathbb {R} ^{n}$" (não confundir com o significado que essa expressão teria na análise funcional. Ver nota sobre a terminologia), ou seja:
* $\mathbb {R} ^{n}$ é onde "mora" a variável primal $x$;
* $\mathbb {R} ^{p}\times \mathbb {R} ^{q}$ é onde "mora" a variável dual $(u,v)$;
Definem-se então as funções $\alpha$ e $\beta$ da seguinte maneira:
    $\alpha :\mathbb {R} ^{n}\mapsto \mathbb {R} \cup \{+\infty \}$, dada por
    $\alpha (x)=\sup _{\begin{smallmatrix}u\geq 0\\v\in \mathbb {R} ^{q}\end{smallmatrix}}l(x,u,v)$
e
    $\beta :\mathbb {R} ^{p}\times \mathbb {R} ^{q}\mapsto \mathbb {R} \cup \{-\infty \}$, dada por
    $\beta (u,v)=\inf _{x\in \mathbb {R} ^{n}}l(x,u,v)$
A partir destas duas funções, formulam-se os seguintes problemas duais:
    $(Pr)\left\{{\begin{matrix}\min \alpha (x)\\x\in \mathbb {R} ^{n}\end{matrix}}\right.$
e
    $(D)\left\{{\begin{matrix}\max \beta (u,v)\\u\geq 0\\v\in \mathbb {R} ^{q}\end{matrix}}\right.$
É possível verificar que $(Pr)$ equivale ao problema original $(P)$ e que $(D)$ consiste da maximização de uma função côncava em um poliedro (convexo).
Logo, o dual de $(P)$ é $(D)$.

### Conclusões

Dado qualquer problema $(P)$, seu dual $(D)$ é um problema côncavo (isto é, a função objetivo é côncava), tal que os pontos satisfazendo o conjunto de restrições formam um poliedro convexo.
Apesar da controvérsia filosófica existente acerca do nome destes conceitos (coisa que poderia muito bem vir a ser alterada no futuro), a moral da história é que "transforma-se um problema geralmente difícil (sem estrutura) em um problema mais fácil (cheio de estrutura)".

## Uma nota sobre a terminologia

Na subárea da matemática denominada Análise Funcional, quando se tem um espaço topológico $X$, costuma-se chamar de dual topológico ao conjunto $X^{*}=\{t:X\mapsto \mathbb {R} ;t{\text{ é linear e continua}}\}$.
Aparentemente, os conceitos de dual da otimização e da análise funcional não tem relação um com o outro.
Um dos primeiros a falar de dualidade (espaços duais) foi o francês Fenchel, mas foi fortemente criticado por Urruty e Lemaréchal, pois os dois conceitos de dualidade não estão relacionados. Também o francês Brezis concordou que há um problema a ser resolvido com a nomenclatura, e um dos conceitos deveria deixar de ser chamado assim.

# Aplicações dos métodos duais
## Aplicação à programação linear

Considere um problema típico da programação linear como:
    $\left\{{\begin{matrix}\min a^{\top }x+b^{\top }y\\Mx+Ny\geq c\\Px+Qy=d\\x\geq 0;\,y\in \mathbb {R} ^{n}\end{matrix}}\right.$
onde são dados $a\in \mathbb {R} ^{n}$, $b\in \mathbb {R} ^{m}$, $M_{p\times n}$, $N_{p\times m}$, $P_{q\times n}$, $Q_{q\times m}$, $d\in \mathbb {R} ^{p}$ e $c\in \mathbb {R} ^{q}$. Por simplicidade, pode-se ainda adotar a seguinte notação:
    $C=\left\{{\begin{bmatrix}x\\y\end{bmatrix}};Mx+Ny\geq c,\,Px+Qy=d,\,x\geq 0{\text{ e }}y\in \mathbb {R} ^{n}\right\}$
Nesta seção será mostrado como a "bonita teoria dos métodos duais" se aplica a esse tipo de problema.
Primeiramente, calcula-se a lagrangiana:
    ${\begin{aligned}l(x,y,u,v,w)&=[a^{\top }x+b^{\top }y]+u^{\top }[c-Mx-Ny]+v^{\top }[d-Px-Qy]+w^{\top }[-x]\\&=[a-M^{\top }u-P^{\top }v-w]^{\top }x+[b-N^{\top }u-Q^{\top }v]^{\top }y+[c^{\top }u+d^{\top }v]\\\end{aligned}}$
Note que:
* As variáveis primais são $x$ e $y$;
* As variáveis duais são $u$, $v$ e $w$;
Agora é preciso identificar as funções $\alpha$ e $\beta$ correspondentes a este problema. Conforme anteriormente, tem-se:
    $\alpha :\mathbb {R} ^{n}\mapsto \mathbb {R} \cup \{+\infty \}$, dada por
    $\alpha (x)=\sup _{\begin{smallmatrix}u\geq 0\\v\in \mathbb {R} ^{q}\\w\geq 0\end{smallmatrix}}l(x,y,u,v,w)=\left\{{\begin{array}{rcl}a^{\top }x+b^{\top }y&,&{\text{ se }}{\begin{bmatrix}x\\y\end{bmatrix}}\in C\\+\infty &,&{\text{ em outros casos}}\end{array}}\right.$
e
    $\beta :\mathbb {R} ^{p}\times \mathbb {R} ^{q}\mapsto \mathbb {R} \cup \{-\infty \}$, dada por
    ${\begin{aligned}\beta (u,v)&=\inf _{\begin{smallmatrix}x\in \mathbb {R} ^{n}\\y\in \mathbb {R} ^{m}\end{smallmatrix}}l(x,y,u,v,w)\\&=\inf _{\begin{smallmatrix}x\in \mathbb {R} ^{n}\\y\in \mathbb {R} ^{m}\end{smallmatrix}}[a-M^{\top }u-P^{\top }v-w]^{\top }x+[b-N^{\top }u-Q^{\top }v]^{\top }y+[c^{\top }u+d^{\top }v]\\&=[c^{\top }u+d^{\top }v]+\inf _{x\in \mathbb {R} ^{n}}[a-M^{\top }u-P^{\top }v-w]^{\top }x+\inf _{y\in \mathbb {R} ^{m}}[b-N^{\top }u-Q^{\top }v]^{\top }y\\&=\left\{{\begin{array}{rcl}c^{\top }u+d^{\top }v&,&{\text{ se }}\left\{{\begin{array}{rcl}a-M^{\top }u-P^{\top }v-w&=&0\\b-N^{\top }u-Q^{\top }v&=&0\\u\geq 0;\,w\geq 0&&\end{array}}\right.\\-\infty &,&{\text{ em outros casos}}\end{array}}\right.\end{aligned}}$
Logo, considerando que $a-M^{\top }u-P^{\top }v=w\geq 0$, o problema dual consiste no seguinte:
    $\left\{{\begin{matrix}\max c^{\top }u+d^{\top }v\\M^{\top }u+P^{\top }v\leq a\\N^{\top }u+Q^{\top }v=b\\u\geq 0\end{matrix}}\right.$

### Exercício

Verificar que ${\bar {x}}$ é uma solução de
    $(P)\left\{{\begin{matrix}\min f(x)\\x\in C\end{matrix}}\right.$
se, e somente se, ${\bar {x}}$ é uma solução de
    $({\bar {P}})\left\{{\begin{matrix}\max(-f(x))\\x\in C\end{matrix}}\right.$

### Exercício

Verificar que:
    $\inf _{x\in C}f(x)=-\sup _{x\in C}[-f(x)]$

### Exemplificando com um problema de programação linear

O seguinte problema é chamado de problema standard (padrão) de programação linear:
    $(PL)\left\{{\begin{matrix}\min c^{\top }x\\Ax=b\\x\geq 0\\\end{matrix}}\right.$
onde são dados $A_{m\times n}$, $b\in \mathbb {R} ^{m}$ e $c\in \mathbb {R} ^{n}$.

#### Calculando o dual de (PL)

Primeiramente,
    $l(x,u,v)=c^{\top }x+u^{\top }(-x)+v^{\top }(b-Ax)$
A função $\alpha$ não precisa ser calculada, pois já se mostrou que
    $\alpha (x)=\left\{{\begin{matrix}f(x)&,{\text{ se }}x\in C\\+\infty &,{\text{ se }}x\not \in C\end{matrix}}\right.$
Por outro lado, quanto à função $\beta$ tem-se:
    $\beta (u,v)=\inf _{x\in \mathbb {R} ^{n}}l(x,u,v)$
    ${\begin{aligned}\beta (u,v)&=\inf _{x\in \mathbb {R} ^{n}}l(x,u,v)\\&=\inf _{x\in \mathbb {R} ^{n}}[c^{\top }x-u^{\top }x+v^{\top }(b-Ax)]\\&=b^{\top }v+\inf _{x\in \mathbb {R} ^{n}}[c-u-A^{\top }v]^{\top }x\\&=\left\{{\begin{array}{rcl}b^{\top }v&,&{\text{ se }}c-u-A^{\top }v=0\\-\infty &,&{\text{ em outros casos}}\end{array}}\right.\end{aligned}}$
Logo, o problema dual é:
    $(D)\left\{{\begin{matrix}\max b^{\top }v\\c-u-A^{\top }v=0\\u\geq 0;\,v\in \mathbb {R} ^{m}\\\end{matrix}}\right.$
ou ainda
    $(D)\left\{{\begin{matrix}\max b^{\top }v\\A^{\top }v\leq c\\v\in \mathbb {R} ^{m}\\\end{matrix}}\right.$

#### Calculando o dual do dual de (PL)

Considere o seguinte problema:
    $(D)\left\{{\begin{matrix}\max b^{\top }v\\A^{\top }v\leq c\\v\in \mathbb {R} ^{m}\\\end{matrix}}\right.$
que, conforme já foi mostrado em um exercício anteriormente, equivale a
    $(D)\left\{{\begin{matrix}\min -b^{\top }v\\A^{\top }v\leq c\\v\in \mathbb {R} ^{m}\\\end{matrix}}\right.$
A lagrangiana é dado por:
    $l(v,y)=-b^{\top }v+y^{\top }(A^{\top }v-c)$
Logo,
    ${\begin{aligned}\beta (y)&=\inf _{v\in \mathbb {R} ^{m}}l(v,y)\\&=\inf _{v\in \mathbb {R} ^{m}}[-b^{\top }v+y^{\top }(A^{\top }v-c)]\\&=-c^{\top }y+\inf _{v\in \mathbb {R} ^{m}}[(Ay-b)^{\top }v]\\&=\left\{{\begin{array}{rcl}-c^{\top }y&,&{\text{ se }}Ay-b=0\\-\infty &,&{\text{ em outros casos}}\end{array}}\right.\end{aligned}}$
Logo, o dual de $(D)$ é:
    $(DD)\left\{{\begin{matrix}\max \beta (y)\\y\geq 0\\\end{matrix}}\right.,$
ou seja,
    $(DD)\left\{{\begin{matrix}\max -c^{\top }y\\Ay=b\\y\geq 0\\\end{matrix}}\right.$
que equivale a
    $(P)\left\{{\begin{matrix}\min c^{\top }x\\Ax=b\\x\geq 0\\\end{matrix}}\right.$

#### Um exemplo numérico contextualizado

Considere a seguinte situação:
    Um empresário que produz cerveja dispões de 240 kg de milho, 5 kg de lúpulo e 596 kg de Malta. Para produzir um barril de cerveja preta requer 2,5 kg de milho, 0,125 kg de lúpulo e 17,5 kg de malta. Enquanto que para produzir um barril de cerveja branca, se precisa de 7,5 kg de milho, 0,125 kg de lúpulo e 10 kg de malta. Por barril de cerveja branca vendido, o empresário recebe 130 reais, enquanto por um barril de cerveja preta, recebe 230 reais. Achar o modelo matemático para otimizar o ganho do empresário.
Na década de 30, 40 e 50 havia diversos livros que tratavam cada problema de programação linear individualmente, deduzindo vez após vez os seus duais, e disso extraindo certas "regras" que eram então sugeridas ao leitor na forma "se o problema for desse tipo, use tal regra, se for daquele tipo, use esta outra, e se for deste outro tipo, use esta regra". Um dos primeiros autores que começou a trabalhar os problemas sob um novo ponto de vista, mais generalizado, foi Werner Oettio (grafia?) . Seguindo-se por George Dantzig (conhecido como inventor do método simplex), Eugen Blumb (grafia?) e Jean-Pierre Crouzeix.

## Aplicação à programação quadrática

Agora, o problema a considerar passa a ser
    $\left\{{\begin{matrix}\min {\frac {1}{2}}x^{\top }Qx+q^{\top }x+\alpha \\x\in C\end{matrix}}\right.$
onde $C$ é um poliedro (interseção finita de semi-espaços), $q\in \mathbb {R} ^{n}$, $\alpha \in \mathbb {R}$ e $Q_{n\times n}$ é uma matriz simétrica positiva definida.
Note que este problema tem solução, uma vez que o problema irrestrito correspondente tem solução (já que $Q$ é uma matriz simétrica positiva definida, a função é limitada inferiormente, e como $C$ é fechado, a função objetivo assume seu valor mínimo em $C$, por Wolfe).
Mesmo para $n=5$, os problemas de programação linear já são difíceis de resolver "à mão". É preciso utilizar alguma técnica mais sofisticada.
Para dar continuidade ao exemplo, considere que o poliedro $C$ é dado por
    $C=\left\{x\in \mathbb {R} ^{n};x\geq 0{\text{ e }}Ax=b\right\}$
com $A_{m\times n}$ e $b\in \mathbb {R} ^{m}$.
Agora será aplicado o esquema de dualidade. A lagrangiana é
    $l:\mathbb {R} ^{n}\times \mathbb {R} ^{n}\times \mathbb {R} ^{m}\mapsto \mathbb {R}$
    $l(x,u,v)={\frac {1}{2}}x^{\top }Qx+q^{\top }x+\alpha \quad +\quad u^{\top }(b-Ax)\quad +\quad v^{\top }(-x)$
além disso,
    $\beta :\mathbb {R} ^{n}\times \mathbb {R} ^{m}\mapsto \mathbb {R} \cup \{-\infty \}$
    $\beta (u,v)=\inf _{x\in \mathbb {R} ^{n}}l(x,u,v)=\min _{x\in \mathbb {R} ^{n}}l(x,u,v)$
e a última igualdade vale pois a função é fortemente convexa.
    ${\begin{aligned}\beta (u,v)&=\inf _{x\in \mathbb {R} ^{n}}l(x,u,v)\\&=\min _{x\in \mathbb {R} ^{n}}l(x,u,v)\\&=\min _{x\in \mathbb {R} ^{n}}[{\frac {1}{2}}x^{\top }Qx+q^{\top }x+\alpha +u^{\top }(b-Ax)+v^{\top }(-x)]\\&=\min _{x\in \mathbb {R} ^{n}}[{\frac {1}{2}}x^{\top }Qx+(q-v-A^{\top }u)^{\top }x+u^{\top }b+\alpha ]\\\end{aligned}}$
Considerando $\nabla _{x}l({\bar {x}},u,v)=Q{\bar {x}}+q-v-A^{\top }u=0$, se deduz que
    ${\bar {x}}=Q^{-1}(A^{\top }u+v-q)$.
Logo,
    ${\begin{aligned}\beta (u,v)&={\frac {1}{2}}\left[Q^{-1}(A^{\top }u+v-q)\right]^{\top }Q\left[Q^{-1}(A^{\top }u+v-q)\right]+(q-v-A^{\top }u)^{\top }\left[Q^{-1}(A^{\top }u+v-q)\right]+u^{\top }b+\alpha \\&={\frac {1}{2}}(A^{\top }u+v-q)^{\top }Q^{-1}(A^{\top }u+v-q)-(A^{\top }u+v-q)^{\top }Q^{-1}(A^{\top }u+v-q)+u^{\top }b+\alpha \\&={\frac {-1}{2}}(A^{\top }u+v-q)^{\top }Q^{-1}(A^{\top }u+v-q)+u^{\top }b+\alpha \end{aligned}}$
Observe que, sendo os autovalores de $Q$ positivos, o mesmo vale obrigatoriamente para $Q^{-1}$. Assim, como a expressão de $\beta$ envolve $(-Q^{-1})$, tal função é fortemente côncava (conforme já era esperado para tal função).
Baseado nestas deduções, o problema dual é
    $(D)\left\{{\begin{matrix}\max {\frac {-1}{2}}(A^{\top }u+v-q)^{\top }Q^{-1}(A^{\top }u+v-q)+u^{\top }b+\alpha \\u\geq 0;\,v\in \mathbb {R} ^{m}\\\end{matrix}}\right.$
ou seja,
    $(D)\left\{{\begin{matrix}\min {\frac {1}{2}}(A^{\top }u+v-q)^{\top }Q^{-1}(A^{\top }u+v-q)-(u^{\top }b+\alpha )\\u\geq 0;\,v\in \mathbb {R} ^{m}\\\end{matrix}}\right.$
Usualmente este tipo de problema $(D)$ é resolvido por meio do método do gradiente projetado.

### Revisão do método do gradiente projetado

O método baseia-se na seguinte proposição:

#### Proposição

Seja $f$ uma função convexa em $C$, um conjunto convexo e fechado. Se o ponto ${\bar {x}}\in C$ é tal que ${\bar {x}}=P_{C}({\bar {x}}-\alpha \nabla f({\bar {x}}))$, então $f({\bar {x}})\leq f(x),\forall x\in C$.

#### Um algoritmo para o método do gradiente projetado

Este algoritmo é bastante simples.
Agora, é interessante observar como se faz para projetar um ponto em $C=[0,+\infty )^{n}\times \mathbb {R} ^{m}$.

##### Exercício

Dado $C=[0,+\infty )^{n}\times \mathbb {R} ^{m}$, mostre que
    $P_{C}\left({\begin{bmatrix}x\\y\end{bmatrix}}\right)={\begin{bmatrix}\max\{x,0\}\\0\end{bmatrix}}$

### Exemplificando a projeção

Seja $u={\begin{bmatrix}1&-1&2&-2&3&-3&4&-4&5&-5\end{bmatrix}}^{\top }$. Então a projeção de $u$ sobre $C=[0,+\infty )^{6}\times \mathbb {R} ^{4}$ é :
    $P_{C}\left({\begin{bmatrix}1&-1&2&-2&3&-3&4&-4&5&-5\end{bmatrix}}^{\top }\right)={\begin{bmatrix}1&0&2&0&3&0&4&-4&5&-5\end{bmatrix}}^{\top }$
Devido a essa simplicidade ao se fazer a projeção de um ponto, o método do gradiente projetado é muito eficiente para resolver o problema $(D)$.

### Exemplo concreto

Seja $C=\{(x,y);\quad x+y=1,\quad x\geq 0,\quad y\geq 0\}$.
Como calcular a projeção do ponto $(1,2)$ sobre o conjunto $C$, $P_{C}(1,2)$?

## Exercícios resolvidos
### Exercício

Encontrar a solução do seguinte problema de programação linear:
    $\left\{{\begin{matrix}\min c^{\top }x\\Ax=b\\x\geq 0\end{matrix}}\right.$
sendo
    $c^{\top }={\begin{bmatrix}2&5&2&1&1\end{bmatrix}}$
    $A={\begin{bmatrix}-1&2&1&-1&0\\1&1&0&0&-1\end{bmatrix}}$
    $b^{\top }={\begin{bmatrix}1&1\end{bmatrix}}$
Resolução :
Ao resolver o problema $(P)$, poderia ter sido escolhido $Ax-b$ em vez de $b-Ax$. Será que isso influenciaria o resultado final?
Acompanhe como ficaria a resolução desta maneira:
Resolução :

### Exercício

Formule como um problema de minimização com restrições o problema de projetar ortogonalmente o ponto $(-5,2)$ sobre o conjunto $C=\{(x,y):x\geq 0,y\geq 0\}$. Depois, calcule explicitamente a função lagrangiana e o problema dual.

### Exercício

No exercício anterior, se $u$ é a variável dual relacionada a variável primal $x$ e $v$ é a variável dual relacionada a variável primal $y$, então verifique se $(u,v)=(10,0)$ é solução dual e se a lagrangiana tem pontos de sela. Em caso afirmativo, calcule um ponto de sela, caso contrário, argumente porque a lagrangiana não tem pontos de sela.

# Método da lagrangiana aumentada

O problema a ser resolvido é:
    $\left\{{\begin{matrix}\min f(x)\\h_{j}(x)=0;j=1,\ldots ,q\end{matrix}}\right.$
Sabe-se que se for aplicado o método da lagrangiana, será considerada a função:
    $l:\mathbb {R} ^{n}\times \mathbb {R} ^{q}\mapsto \mathbb {R}$ dada por
    $l(x,v)=f(x)+\sum _{j=1}^{q}v_{j}h_{j}(x)$.
e também
    $\beta :\mathbb {R} ^{q}\mapsto \mathbb {R} \cup \{-\infty \}$, dada por
    $\beta (v)=\inf _{x\in \mathbb {R} ^{n}}l(x,v)$
A grande dificuldade seria saber quando o valor de $\beta$ é finito. Uma idéia seria modificar um pouco a lagrangiana (aumentando-a, com um termo extra), da seguinte maneira:
    $l(x,v)=f(x)+\sum _{j=1}^{q}v_{j}h_{j}(x)+r\sum _{j=1}^{q}\left(h_{j}(x)\right)^{2}$
Com isso, seria necessário garantir que a idéia de fato resolve o problema. Por este motivo, é preciso desenvolver alguns resultados teóricos. Para fazer a análise deste método, um primeiro resultado importante é o seguinte:

## Lema (Finsler-Debreu)

Seja $A_{n\times n}$ uma matriz simétrica e $B_{p\times n}$. As seguintes afirmações são equivalentes:
* Se $Bx=0$, com $x\not =0$, então $\langle Ax,x\rangle >0$;
* Existe $r>0$ tal que a matriz $A+rB^{\top }B$ é definida positiva;
* Existe $s>0$ tal que a matriz $A+rB^{\top }B$ é definida positiva para todo $r>s$.

## Exercício

Prove a seguinte variante do lema anterior:
    Seja $A_{n\times n}$ uma matriz simétrica e semi-definida positiva, e $B_{p\times n}$. As seguintes afirmações são equivalentes:
   * Se $Bx=0$, com $x\not =0$, então $\langle Ax,x\rangle >0$;
   * Existe $r>0$ tal que a matriz $A+rB^{\top }B$ é definida positiva;
   * Para todo $r>0$, a matriz $A+rB^{\top }B$ é definida positiva.
A partir de agora, o problema será:
    $\left\{{\begin{matrix}\min f(x)\\h_{j}(x)=0;j=1,\ldots ,q\end{matrix}}\right.$
onde se supõe que $f,\,h_{i}:\mathbb {R} ^{n}\mapsto \mathbb {R}$ são funções de classe ${\mathcal {C}}^{2}\left(\mathbb {R} ^{n}\right)$ e que para todo $\lambda \in \mathbb {R}$, o conjunto $\{x\in \mathbb {R} ^{n};f(x)\leq \lambda \}$ é compacto (em inglês costuma-se usar a expressão inf-compact para descrever tais funções).
Sabe-se que a lagrangiana associada ao problema $(P)$ é:
    $l:\mathbb {R} ^{n}\times \mathbb {R} ^{q}\mapsto \mathbb {R}$ dada por
    $l(x,v)=f(x)+\sum _{j=1}^{q}v_{j}h_{j}(x)$.
e ainda, em uma notação mais sintética, considerando a função $H$ dada por:
    $H:\mathbb {R} ^{n}\mapsto \mathbb {R} ^{q}$ definida por
    $H(x)={\begin{bmatrix}h_{1}(x)\\\vdots \\h_{q}(x)\end{bmatrix}}$
tem-se a lagrangiana expressa da seguinte maneira:
    $l(x,v)=f(x)+H(x)^{\top }v$
Para o método da lagrangiana aumentada serão assumidas as seguintes hipóteses:
* Se ${\bar {x}}$ é solução, então existe ${\bar {u}}\in \mathbb {R} ^{q}$ tal que $\nabla _{x}l({\bar {x}},{\bar {u}})=0$;
* Para todo $d\not =0$, o jacobiano de $H$ satizfaz:
    $J_{H}(x)d=0\Rightarrow d^{\top }H_{x}^{2}l({\bar {x}},{\bar {u}})d>0$
Note que a segunda hipótese tem exatamente a mesma forma de uma das condições que aparece no lema de Finsler-Debreu.

## Definição

Dado $\rho >0$, se define a lagrangiana aumentada para o problema $(P)$ como:
    $l_{\rho }:\mathbb {R} ^{n}\times \mathbb {R} ^{q}\mapsto \mathbb {R}$ dada por
    $l_{\rho }(x,v)=f(x)+H(x)^{\top }v+{\frac {\rho }{2}}H(x)^{\top }H(x)=l(x,v)+{\frac {\rho }{2}}H(x)^{\top }H(x)$
Observe que é justamente a aparição do termo ${\frac {\rho }{2}}H(x)^{\top }H(x)$ sendo somado à lagrangiana que justifica o nome lagrangiana aumentada.
Esse conceito possui algumas interpretações:

## Exercício

Verifique que a lagrangiana aumentada $l_{\rho }$ é justamente a lagrangiana do problema $(P)$ penalizado, ou seja, de
    $\left\{{\begin{matrix}\min f(x)+{\frac {\rho }{2}}H(x)^{\top }H(x)\\H(x)=0\end{matrix}}\right.$

## Exercício

Verifique que a função dual $\beta _{\rho }$ (o ínfimo da lagrangiana aumentada em relação à primeira componente), dada por
    $\beta _{\rho }:\mathbb {R} ^{q}\mapsto \mathbb {R} \cup \{-\infty \}$, com
    $\beta _{\rho }(v)=\inf _{x\in \mathbb {R} ^{n}}l_{\rho }(x,v)$
para $0<\rho <\delta$ satisfaz
    $\beta _{\rho }(v)\leq \beta _{\delta }(v)\leq f({\bar {x}})$
${\bar {x}}$
$(P)$

## Exercício

Verifique que $\{x\in \mathbb {R} ^{n};l_{\rho }(x,v)\leq \lambda \}$ é compacto, qualquer que seja $\lambda \in \mathbb {R}$ e $v\in \mathbb {R} ^{q}$.

## Proposição

Se ${\bar {x}}$ é solução de $(P)$, então existe algum $\rho _{0}>0$, algum $\delta _{0}>0$ e alguma vizinhança $X_{0}$ de ${\bar {x}}$ tais que $l_{\rho _{0}}(\cdot ,{\bar {v}})$ é fortemente convexa com parâmetro $\delta _{0}$.
Com essas condições, mostrou-se que em um ponto que seja solução, a lagrangiana aumentada é fortemente convexa.
Antes de apresentar o algoritmo, será fixada mais uma notação:
    $(P_{\rho ,u})\left\{{\begin{matrix}\min l_{\rho }(x,u)\\x\in \mathbb {R} ^{n}\end{matrix}}\right.$

## Algoritmo da lagrangiana aumentada

Dados $\rho >0$ e $\epsilon \in (0,\rho )$.
Este é um dos algoritmos mais usados e mais eficientes para problemas de programação não linear. A garantia de convergência segue dos próximos teoremas.

### Teorema

Sejam $\rho _{0}$, $\delta _{0}$ e $X_{0}$ como na proposição anterior. Se $U$ é uma vizinhança de ${\bar {u}}$, existe algum $\rho _{U}>\rho _{0}$ tal que:
* $X(\rho ,u)\subset X_{0},\forall u\in U$
* $X(\rho ,{\bar {u}})=\{{\bar {x}}\}$ e $\beta _{\rho }({\bar {u}})=f({\bar {x}})$
Observações:
* $X(\rho ,u)$ denota as soluções do problema;
* A igualdade $\beta _{\rho }({\bar {u}})=f({\bar {x}})$ significa que não há salto de dualidade.
* Já foi mostrado que a função é fortemente convexa em uma vizinhança. Logo, os minimizadores devem estar em tal vizinhança.
* A prova é um pouco técnica, e usa as condições de KKT, mostrando que o cone linearizado é igual ao cone tangente.
O segundo teorema é:

### Teorema

Se $\rho$ é suficientemente grande e $\delta$ suficientemente pequeno, então:
* $x_{k}\to {\bar {x}}$
* $l_{\rho }(x_{k},u_{k})\to f({\bar {x}})$
* $\{u_{k}\}$ é limitada
Observações:
* A propriedade 2 praticamente segue do fato de não haver salto de dualidade.
Com esses resultados, tem-se a garantia de que o algoritmo realmente converge para uma solução, desde que os parâmetros sejam tomados adequadamente. A questão que ainda permanece é como identificar os valores adequados de $\rho$ e de $\delta$ para que tal convergência ocorra.

### Exercício

Argumente porque as hipóteses 1, 2 e 3 garantem que a iteração do algoritmo da Lagrangiana aumentada para problemas de minimização com restrições de igualdade tem uma única solução, sendo:
* Todas as funções são de classe ${\mathcal {C}}^{2}$ e a função objetivo tem todos os seus subníveis compactos.
* Se ${\bar {x}}$ é solução do problema, então existe ${\bar {u}}$ tal que o gradiente da Lagrangiana não aumentada com respeito a variável primal se anula em $({\bar {x}},{\bar {u}})$.
* A hessiana da Lagrangiana não aumentada com respeito a variável primal é definida positiva sob a variedade ortogonal de todos os gradientes no ponto ${\bar {x}}$ das restrições.

# Estilo

Nesta página estarão indicadas as convenções adotadas neste wikilivro sobre otimização, no que diz respeito a sua formatação. Recomenda-se a leitura do mesmo, por todos que pretendem contribuir com a melhoria desde texto.

## Definições
### Definição

As definições aparecem em caixas com essa aparência.

### Observações

* Geralmente um termo importante aparece pela primeira vez em uma definição.
* Devido à sua importância, é bom destacar a definição do restante do texto.
* No momento, a forma de destacar uma definição neste wikilivro é a inclusão de bordas duplas em torno do texto da definição, como no exemplo acima. Para facilitar essa tarefa, utiliza-se a predefinição {{Definição}}.
* O conceito que está sendo definido costuma ser colocado em negrito, sendo que o texto da explicação tem sido alinhado a esquerda.

## Propriedades
### Teorema

Sempre que uma propriedade importante dos objetos tratados no texto precisa ser destacada, isto deve ser feito em uma caixa como essa.

### Observações

* Os principais tipos de propriedades a ser destacados são: teoremas, proposições, corolários e pequenos lemas.
* Para conseguir a formatação acima, utiliza-se a predefinição {{Teorema}}.

## Exercícios
### Exercício

Aqui vai o enunciado de um exercício.
* Pode-se colocar vários itens;
* Cada um com a numeração adequada;

## Tarefas pendentes
# Índice remissivo

Nesta página estão listados os conceitos abordados neste livro em ordem alfabética.
O nome de cada conceito possui um link para a página onde o mesmo é definido. Outras ocorrências importantes do conceito são indicadas pelos links numerados, logo após o link principal.

## B

* Brecha de dualidade
* Busca linear

## C

* Condição
    suficiente de segunda ordem
* Condições de otimalidade
* Condições de otimalidade
    de Karush-Kuhn-Tucker
    necessárias
       de primeira ordem
       de segunda ordem
    suficientes
       de segunda ordem
* Condições de qualificação das restrições
    de independência linear dos gradientes das restrições ativas
    de linearidade
    de Mangasarian-Fromovitz
    de Slater
* Cone
    tangente
    tangente linearizado
* Conjunto
    convexo
    de nível
    viável
* Convexidade

## D

* Direção
    de descida
    viável
* Direções
    conjugadas
* Dualidade

## F

* Função
    coerciva
    côncava
    convexa
    de barreira
    de penalidade
       exterior
       interior
    fortemente
       côncava
       convexa
    objetivo
* Funções em dualidade

## H

* Hessiana

## L

* Lagrangiana
    aumentada
* Lema
    de Finsler-Debreu

## M

* Método
    dos gradientes conjugados
    da Lagrangiana aumentada
    de barreira
    de descida
    de direções conjugadas
    de Newton
    de penalidade
       interior
       exterior
    das regiões de confiança
    do gradiente
       conjugado
       projetado
* Minimizador
    global
    local
* Multiplicadores de Lagrange

## P

* Penalidade
    exterior
    interior
* Ponto
    crítico
    de mínimo
* Problema
    de minimização
    de programação
       linear
       quadrática
    dual
    irrestrito
    primal
* Projeção

## R

* Região de confiança
* Regra
    de Armijo
* Restrições ativas

## S

* Sistema
    de Lagrange
* Solução

## T

* Teorema
    de Wolfe

## W

* Wolfe, teorema

## Z
# Bibliografia
## Livros e artigos

* Avriel, Mordecai. Nonlinear Programming: Analysis and methods. New York: Dover, 2003. 528 p. ISBN 0486432270
* Izmailov, Alexey; Solodov, Mikhail. Otimização: Condições de Otimalidade, Elementos de Análise Convexa e de Dualidade. 1ª.ed. Rio de Janeiro: IMPA, 2005. 253 p. 2 v. v. 1. ISBN 8524402385
* Izmailov, Alexey; Solodov, Mikhail. Otimização: Métodos Computacionais. 1ª.ed. Rio de Janeiro: IMPA, 2007. 458 p. 2 v. v. 1. ISBN 9788524402685
* Hiriart-Urruty, Jean-Baptiste, Lemaréchal, Claude. Fundamentals of Convex Analysis. Springer, 2001. ISBN 3540422056
* [confirmar] Fletcher, Roger; Fitches, W. R.. Practical Methods of Optimization. Wiley, 1987.
* [confirmar] Dixon, ???. Practical optimization.
* Crouzeix, Jean Pierre; Keraghel, Abdelkrim; Sosa, Wilfredo. Programmation Mathematique Differential. 2008.
* Hestenes, Magnus R.; Stiefel, Eduard. Methods of Conjugate Gradients for Solving Linear Systems. Journal of Research of the National Bureau of Standards. v. 49 (6). Dezembro, 1952.
* Polak, E.; Ribière, G..Note sur la convergence de directions conjugées. Rev. Francaise Informat Recherche Operationelle, 3e Année 16 (1969) 35-43.
* Fletcher, R.; Reeves, CM.Function minimization by conjugate gradients. The Computer Journal, 1964 - Br Computer Soc.
* Courant, R..Variational methods for the solution of problems of equilibrium and vibrations. Bull. Amer. Math. Soc., 49, 1-23, 1943.
* Finsler, P.. Uber das Vorkommen definiter und semidefiniter Formen in Scharen quadratischer Formen. Commentaria Mathematicae Helvetia. Vol. 9. pp. 188-192, 1937.

## Páginas da internet

* Martínez, José Mario. Otimização Prática Usando o Lagrangiano Aumentado. Departamento de Matemática Aplicada IMECC-UNICAMP. 2009.
* Martínez, José Mario; Santos, Sandra Augusta. Métodos Computacionais de Otimização. Departamento de Matemática Aplicada IMECC-UNICAMP. 262p.
* Gonzaga, Clóvis Caezar. Um Curso de Programação Não Linear. Florianópolis : UFSC, 2004.
* Jonathan Richard Shewchuk. An Introduction to the Conjugate Gradient Method Without the Agonizing Pain - Um artigo sobre o método do gradiente conjugado (pode ser copiado e distribuído livremente)
* Cardoso, Domingos Moreira. Tópicos de Optimização Não Linear. Aveiro: UA, 1999.
* João Antônio de Vasconcelos. Apresentações de slides (em pdf):
   * Otimização em engenharia: Penalidades.
   * Problemas de Programação Matemática Não-Linear
   * Otimização em engenharia: Métodos de Penalidades e Métodos do Lagrangiano Aumentado
   * Algoritmos Genéticos
   * Simulated Anneling Algorithm.
   * Otimização Vetorial.
   * Computação Evolucionária
   * How do ee compare EA performances in multiobjective optimization?

### Material complementar

* Pires, Paulo Sérgio da Motta. Introdução ao SciLab Versão 3.0. Natal: UFRN, 2004.
* Chandler, Graeme; Roberts, Stephen. Introduction to Scilab. 2002.
* LaTeX to Wikicode translation tool - (link direto)