Condições de otimalidade de primeira e segunda ordem em

Condições de otimalidade de primeira e segundaordem em otimização não linear

Gabriel HaeserDepartamento de Matemática Aplicada,

Instituto de Matemática e Estatística, Universidade de São Paulo

16 de Março de 2015

ResumoNeste trabalho estamos interessados em identificar propriedades de primeira

e segunda ordem que são satisfeitas por um minimizador local de um problemageral de otimização não linear. Nosso interesse principal é encontrar condiçõesque possam ser verificadas por algoritmos práticos. Definimos condições deotimalidade de primeira e segunda ordem mais fortes que as usuais, impondocondições menos restritivas sobre o problema, e como consequência mostramosque diversas classes de algoritmos de primeira e segunda ordem tem convergên-cia global para pontos estacionários sob hipóteses mais fracas.

Palavras chave: otimização não-linear; condições de otimalidade; condi-ções de qualificação; algoritmos práticos.

AbstractIn this work we are interested in identifying first and second order properties

satisfied by a local minimizer of a nonlinear optimization problem. Our maingoal is to find conditions that can be verified by practical algorithms. We de-fine first and second order optimality conditions stronger than the usual ones,requiring less restrictive assumptions on the problem, and as a consequence,we show global convergence to stationarity of several classes of first and secondorder algorithms under less restrictive assumptions.

Key words: nonlinear optimization; optimality conditions; constraint qua-lifications; practical algorithms.

4

à Etiene e Giovana.

6

Conteúdo

1 Introdução 9

2 Condições de otimalidade de primeira ordem 132.1 Condições de qualificação . . . . . . . . . . . . . . . . . . . . . . 132.2 Condições sequenciais de primeira ordem . . . . . . . . . . . . . . 21

3 Condições de otimalidade de segunda ordem 293.1 Condições de qualificação . . . . . . . . . . . . . . . . . . . . . . 313.2 Condições sequenciais de segunda ordem . . . . . . . . . . . . . . 41

4 Conclusões 47

7

8 G. Haeser

Capítulo 1

Introdução

Considere o problema geral de otimização não linear

Minimizar f0(x),Sujeito a fi(x) = 0, i = 1, . . . ,m,

fi(x) ≤ 0, i = m+ 1, . . . ,m+ p,

onde fi : Rn → R, i = 0, . . . ,m+p são funções continuamente diferenciáveis.

Denotamos por Ω = x ∈ Rn | fi(x) = 0, i = 1, . . . ,m, fi(x) ≤ 0, i =m + 1, . . . ,m + p o chamado conjunto viável. Para x ∈ Ω, denotamos porA(x) = i ∈ m + 1, . . . ,m + p | fi(x) = 0 o conjunto de índices derestrições de desigualdade ativas em x. Por simplicidade assumiremos queA(x) = m + 1, . . . ,m + r em um ponto de interesse x. A rigor, r := r(x),entretanto, o ponto x associado a r estará claro do contexto. Um ponto viávelx∗ ∈ Ω é uma solução (ou minimizador) local do problema se existe uma vizi-nhança B de x∗ tal que f0(x∗) ≤ f0(x) para todo x ∈ Ω ∩ B. Se x∗ satisfaz apropriedade acima com B = Rn, dizemos que x∗ é uma solução global.

Estamos interessados em estudar propriedades analíticas de uma soluçãolocal do problema, com o intuito de que tais propriedades possam ser explora-das na prática para guiar um processo iterativo que busca por uma solução doproblema, bem como para fornecer um critério de parada. Tais condições sãodenominadas condições de otimalidade.

Formalmente, uma condição de otimalidade é qualquer condição satisfeitapor uma solução. Por exemplo, tanto a mera viabilidade quanto a própria oti-malidade local são condições de otimalidade. Entretanto, encontrar um pontoque cumpre apenas a primeira condição não auxilia na tarefa de encontrar umasolução, já que existem muitos pontos viáveis que não são uma solução do pro-blema, enquanto a segunda condição é muito difícil de ser verificada na prática.Neste trabalho estamos interessados em desenvolver condições de otimalidade

9

10 G. Haeser

fortes, no sentido que existam poucas soluções que não cumprem a condição; quesejam de fácil verificação prática e, além disso, que sejamos capazes de desenvol-ver algoritmos para encontrar pontos que cumprem a condição de otimalidade.Estes serão os candidatos a solução do problema.

Assumindo que x∗ é uma solução, uma primeira condição de otimalidade útil,chamada condição geométrica, é obtida analisando o ângulo de ∇f0(x∗) comdireções que apontam para o interior do conjunto viável. Ou seja, considerandouma sequência de pontos viáveis xk ∈ Ω convergindo para x∗ e sendo d ∈Rn a direção unitária pela qual xk converge para x∗, isto é, d = lim xk−x∗

‖xk−x∗‖ ,assumindo que o limite exista, temos

f0(xk) = f0(x∗) +∇f0(x∗)T(xk − x∗) + o(xk − x∗),

onde o(xk−x∗)‖xk−x∗‖ → 0, k → +∞. Dividindo por ‖xk − x∗‖ e tomando o limite em

k, observando que f0(x∗) ≤ f0(xk) temos que ∇f0(x∗)Td ≥ 0. Formalizamoseste resultado a seguir.

Definição 1.1 (Cone tangente) Dado x ∈ Ω, denotamos por T (x) o conetangente a Ω em x, dado por

T (x) = 0 ∪d ∈ Rn | ∃xk ∈ Ω, xk → x,

xk − x‖xk − x‖

→ d

‖d‖

.

Definição 1.2 (Cone polar) Seja C ⊂ Rn um cone. Denotamos por C ocone polar de C, dado por

C =v ∈ Rn | vTd ≤ 0,∀d ∈ C

.

Teorema 1.3 (Condição de otimalidade geométrica) Se x∗ ∈ Ω é umasolução local, então −∇f0(x∗) ∈ T (x∗).

Observe que a verificação da condição geométrica na prática é muito difícil,pois o cone tangente é um objeto geométrico, difícil de ser representado no com-putador (e mais ainda, o seu polar), que depende do conjunto viável Ω, e nãodas funções fi que o definem. (Note que um mesmo conjunto Ω pode possuirdescrições analíticas distintas).

Uma primeira condição analítica aparece nos trabalhos Kuhn-Tucker [35] eFritz John [33], onde temos o seguinte resultado:

Teorema 1.4 (Condição de Fritz John) Se x∗ é uma solução local, entãoexiste 0 6= (λ0, λ) ∈ R× Rm+r tal que

m+r∑i=0

λi∇fi(x∗) = 0, λ0 ≥ 0, λi ≥ 0, i ∈ A(x∗).

Condições de otimalidade de 1a e 2a ordem em otimização não linear 11

Prova: Veja a observação após a prova do Teorema 2.6.

Note que a condição depende apenas das restrições de desigualdade ativasem x∗. De fato, as restrições inativas não desempenham nenhum papel na aná-lise local da solução, já que se fi(x∗) < 0, então a restrição fi(x) ≤ 0 não éviolada em toda uma vizinhança de x∗, o que faz com que x∗ continue sendouma solução local do problema, mesmo se esta restrição é removida. Observeainda que a condição geométrica também não depende das restrições inativas,já que o cone tangente T (x) permanece inalterado independente se incluímosou não as restrições inativas no problema.

Fritz John desenvolveu esta condição estudando conjuntos convexos. Umprimeiro problema formulado por ele é o de encontrar a esfera de menor raioque contém um conjunto limitado S ⊂ Rm. Este problema foi formulado como

Minimizar xm+1,Sujeito a

∑mi=1(xi − yi)2 ≤ xm+1,∀y ∈ S.

Utilizando a condição de Fritz John e uma formulação análoga, em [33], F.John mostrou que todo conjunto convexo compacto S ⊂ Rn de interior nãovazio, possui um maior elipsóide em seu interior (elipsóide de John), além disso,existe um elipsóide “semelhante” ao elipsóide de John, com razão de semelhança≤ n e que contém S.

Para os problemas estudados por Fritz John, a condição que ele desenvolveuera uma boa ferramenta, entretanto, a condição de Fritz John pode valer comλ0 = 0, e então teríamos uma condição de otimalidade pouco útil, pois ela nãodependeria da função objetivo. No caso em que λ0 = 0, a condição de FritzJohn fala mais sobre uma falha na descrição do conjunto viável (com restriçõesredundantes), do que sobre otimalidade do ponto. Sendo assim, Kuhn e Tuckerestudaram propriedades sobre as funções que descrevem o conjunto viável quegarantem a condição de Fritz John com λ0 6= 0. Tais condições são chamadasqualificações de restrição, em inglês (constraint qualifications), mas em portu-guês utilizamos o termo condições de qualificação. A condição de Fritz-John comλ0 6= 0 (equivalentemente, λ0 = 1) é chamada condição de Karush-Kuhn-Tucker(KKT). Karush [34], de forma independente, também estudou tais condições,mas em seu trabalho ele não enuncia o resultado de Fritz John.

Karush desenvolveu seu resultado em 1939, em sua dissertação de mestradono Departamento de Matemática da Universidade de Chicago. Tal departa-mento era muito ativo no problema de otimização análogo em dimensão infinita(cálculo variacional), e a dissertação de Karush não chamou muita atenção porse tratar de um caso marginal do problema de interesse do departamento, epor isso o resultado não foi publicado. Seu trabalho só veio a ser reconhecidopela comunidade científica na década de 70, anos depois de Kuhn e Tuckerterem obtido grande atenção pela publicação do teorema em 1951. Tucker,

12 G. Haeser

um topólogo de Princeton e Kuhn, doutorando na área de álgebra, utilizaramideias de teoria dos jogos de Von Neumann para formular a teoria de otimiza-ção não linear e dualidade. As ferramentas de teoria dos jogos são utilizadaspara estudar o equilíbrio de Nash L(x∗, λ) ≤ L(x∗, λ∗) ≤ L(x, λ∗),∀x, λ, ondex∗ é uma solução e λ∗ multiplicador de Lagrange associado, onde L(x, λ) =f0(x) +

∑m+pi=1 λifi(x), λi ≥ 0, i = m+ 1, . . . ,m+ p é a função lagrangiana. Na

década de 50, com a introdução dos computadores e com os casos de sucesso deimplementações do método simplex de Dantzig em problemas lineares advindosda área militar, o financimento e o interesse em otimização cresceu muito, tor-nando os resultados de (Karush, ) Kuhn e Tucker muito conhecidos.

No Capítulo 2, iremos apresentar diversas condições de otimalidade baseadasem condições de qualificação distintas. Além disso, apresentaremos as chamadascondições sequenciais de otimalidade, que não dependem de uma condição dequalificação e estão mais intimamente ligadas à convergência de algoritmos. NoCapítulo 3, desenvolvemos condições de otimalidade mais específicas, utilizandoinformações de segunda-ordem do problema. No Capítulo 4 apresentamos algu-mas conclusões e trabalhos futuros.

Este trabalho é baseado em alguns artigos do autor na área e seus cola-boradores. A definição de condição sequencial é apresentada em [7] e novascondições de qualificação associadas a algoritmos são apresentadas em [9, 10].Novas condições de segunda ordem teóricas são apresentadas em [2] e condiçõespráticas para algoritmos de segunda ordem são apresentadas em [8].

Capítulo 2

Condições de otimalidadede primeira ordem

2.1 Condições de qualificaçãoSendo o cone tangente T (x) um objeto geométrico difícil de ser simulado nu-

mericamente, podemos definir um objeto analítico que captura o mesmo espíritodo cone tangente. Em torno de x ∈ Ω, as restrições não lineares fi(x + d) =0, i = 1, . . . ,m serão substituídas pelo hiperplano tangente x+ d,∇fi(x)Td = 0e de forma análoga, as restrições de desigualdade fi(x + d) ≤ 0, i ∈ A(x) se-rão substituídas por ∇fi(x)Td ≤ 0. Desta maneira, podemos definir um coneque coincide com o cone tangente em muitos casos, chamado cone linearizadoconforme a definição abaixo:

Definição 2.1 (Cone linearizado) Dado x ∈ Ω, denotamos por L(x) o conelinearizado de Ω em x, dado por

L(x) =d ∈ Rn | ∇fi(x)Td = 0, i = 1, . . . ,m,∇fi(x)Td ≤ 0, i ∈ A(x)

.

Com um argumento análogo à prova da condição geométrica, é facil ver queT (x) ⊂ L(x), embora a igualdade possa não acontecer. De fato, basta considerarΩ ⊂ R2 definido por x1x2 = 0, x1 ≥ 0, x2 ≥ 0 em torno da origem, onde o conelinearizado é o ortante positivo, enquanto o cone tangente é formado pela uniãodos semi-eixos positivos. Embora os cones não coincidam, é fácil verificar que opolar de ambos os cones é o ortante negativo. O conjunto em R2 definido porx2 ≤ −x3

1, x2 ≥ x31 em torno da origem mostra que, em geral, T (x) 6= L(x),

embora, é claro, L(x) ⊂ T (x).Assumindo que T (x) = L(x), a condição de otimalidade geométrica se

reduz a −∇f0(x) ∈ L(x), e ocorre que o polar do cone linearizado pode serfacilmente computado utilizando o Lema de Farkas, obtendo:

13

14 G. Haeser

L(x) =v ∈ Rn | v =

m+r∑i=1

λi∇fi(x), λi ≥ 0, i ∈ A(x).

Com efeito, seja S(x) o cone do lado direito da igualdade acima. É fácilobserver que S(x) = L(x) e sendo S(x) um cone convexo fechado, (S(x)) =S(x).

Note que a condição −∇f0(x) ∈ L(x) é precisamente a condição KKT.

Teorema 2.2 (Karush-Kuhn-Tucker) Seja x uma solução e assuma que T (x) =L(x), então existem multiplicadores de Lagrange λi, i = 1, . . . ,m+ r tais que

∇f0(x) +m+r∑i=1

λi∇fi(x) = 0, λi ≥ 0, i ∈ A(x). (2.1)

Os pontos viáveis x ∈ Ω que cumprem (2.1) são chamado pontos estacio-nários (ou pontos KKT) do problema, e são os principais candidatos à soluçãoquando o problema cumpre uma condição de qualificação.

Sendo assim, a igualdade dos cones polares é uma condição de qualificação,chamada condição de Guignard [31]. Mais do que isso, a condição de Guignardé a condição de qualificação mais fraca possível [29], no sentido de que, fixadox ∈ Ω, se para qualquer função objetivo f0 tal que x é solução do problema deminimizar f0(x) sujeito a x ∈ Ω, vale que x é um ponto estacionário, então acondição de Guignard é satisfeita em x. O resultado segue da inclusão

T (x) ⊂ −∇f0(x) | f0 assume um minimizador local restrito em x

e será feita no Teorema 2.3 no final desta sessão, onde corrigimos uma pequenaimprecisão de [29]. Note que a inclusão recíproca

T (x) ⊃ −∇f0(x) | f0 assume um minimizador local restrito em x

tambem é satisfeita, e é precisamente uma re-escrita da condição de otimalidadegeométrica do Teorema 1.3.

Formalmente, a condição KKT puramente não é uma condição de otimali-dade, já que para o problema de minimizar x, sujeito a x2 = 0, a solução x = 0não é um ponto estacionário. As condições de otimalidade clássicas associadasà condição KKT são da forma

KKT ou não-CQ,

onde CQ é uma condição de qualificação qualquer. Quanto menos exigente acondição de qualificação, mais forte é a condição de otimalidade associada, emais interessante se torna na prática. Embora conheçamos a condição de qua-lificação mais fraca possível, não se conhece um algoritmo capaz de encontrarpontos estacionários, a menos que se exija mais regularidade do problema. Sendo


assim, o estudo de condições de qualificação mais exigentes que Guignard, masque permitam a prova de convergência global de algoritmos, é o tema centraldeste trabalho. Em mais detalhes, temos tipicamente que algoritmos de otimi-zação são iterativos e geram sequências possivelmente divergentes, entretanto,o que somos capazes de provar é que, para qualquer escolha do ponto inicial, seuma sequência gerada por um algoritmo possui um ponto de acumulação, entãosob uma condição de qualificação (mais forte que Guignard), este ponto é esta-cionário para o problema. A um resultado deste tipo chamamos de convergênciaglobal, ou convergência global de primeira ordem.

A condição de igualdade entre os cones T (x) = L(x), mais exigente queGuignard, é chamada condição de Abadie [1], e é frequentemente satisfeita soba maioria das condições de qualificação clássicas. Entretanto, supor Abadieainda não é suficiente para a convergência global de algoritmos. Vamos listarcondições de qualificação associadas à algoritmos, iniciando das mais restritivas,embora a conexão com algoritmos seja postergada para a próxima seção.

Uma das condições de qualificação mais frequentes na literatura de otimi-zação é a linear independence constraint qualification (LICQ) - ou regularidade- que afirma que os gradientes das restrições de igualdade e de desigualdadeativas são linearmente independentes, isto é,

∇fi(x)m+ri=1 é linearmente independente.

Uma abordagem clássica para a prova da existência de multiplicadores deLagrange em uma solução do problema consiste em supor LICQ na solução eusar o Teorema da Função Implícita para provar a igualdade dos cones tangentee linearizado (condição de Abadie). Sob LICQ, é fácil ver que os multiplicadoresde Lagrange são únicos.

Exigindo LICQ, há pouco espaço para redundância na descrição do pro-blema. De fato, se os gradientes de duas restrições são coincidentes, LICQnão é satisfeita. Na definição a seguir podemos enfraquecer LICQ de modo apermitir este tipo de redundância.

Explorando o fato que os multiplicadores de Lagrange associados às res-trições de desigualdade são não-negativos, é possível definir uma condição dequalificação menos exigente que LICQ, denominada condição de Mangasarian-Fromovitz (MFCQ, [40]). Vale MFCQ em x ∈ Ω quando

m+r∑i=1

αi∇fi(x) = 0, αi ≥ 0,∀i ∈ A(x)⇒ αi = 0,∀i = 1, . . . ,m+ r.

Neste caso diremos que os gradientes ∇fi(x), i = 1, . . . ,m e ∇fi(x), i = m +1, . . . ,m + r são positivo-linearmente independentes. Utilizando um teoremade alternativa, podemos ver que a condição MFCQ é equivalente ao fato queexiste uma direção estritamente viável, no seguinte sentido: ∇fi(x), i = 1, . . . ,mé linearmente independente e existe uma direção d ∈ Rn tal que ∇fi(x)Td =

16 G. Haeser

0, i = 1, . . . ,m e ∇fi(x)Td < 0, i ∈ A(x). Ver [47]. De fato, esta é a maneiracomo a condição foi originalmente proposta.

Embora sob MFCQ não se possa garantir a unicidade dos multiplicadores deLagrange, sabe-se que ela é equivalente ao fato do conjunto de multiplicadoresde Lagrange ser um conjunto compacto não vazio [27]. Mais especificamente,MFCQ garante a compacidade do conjunto de multiplicadores de Lagrange inde-pendente da função objetivo, e, se existe uma função objetivo tal que o conjuntode multiplicadores de Lagrange é compacto, então vale MFCQ.

É interessante observar que a condição de otimalidade oriunda de MFCQ,isto é, “KKT ou não-MFCQ” é precisamente a condição de Fritz John.

A condição equivalente ao fato dos multiplicadores de Lagrange serem únicosé denominada strict MFCQ, SMFCQ [36] e é definida a seguir. Suponha queλ ∈ Rm+r seja um multiplicador de Lagrange associado a x ∈ Ω. Vale SMFCQquando os gradientes ∇fi(x), i ∈ 1, . . . ,m ∪ i ∈ A(x)|λi > 0 e ∇fi(x), i ∈i ∈ A(x)|λi = 0 são positivo-linearmente independentes, isto é, as restriçõesde desigualdade ativas associadas a um multiplicador positivo são tratadas comorestrições de igualdade na definição de MFCQ.

Para mostrar a equivalência de SMFCQ com a unicidade do multiplicador,assuma que λ 6= λ seja outro multiplicador de Lagrange associado a x ∈ Ω,então, da condição KKT temos∑

i∈1,...,m∪i∈A(x)|λi>0

(λi − λi)∇fi(x) +∑

i∈A(x)|λi=0

λi∇fi(x) = 0,

o que contradiz SMFCQ. Reciprocamente, se não vale SMFCQ, existe 0 6= α ∈Rm+r com αi ≥ 0, i ∈ i ∈ A(x) | λi = 0 tal que

∑m+ri=1 αi∇fi(x) = 0. Temos

então ∇f0(x) +∑m+ri=1 (λi +αi)∇fi(x) = 0. Tomando α pequeno o suficiente de

modo que λi + αi ≥ 0 para i ∈ A(x) temos que o multiplicador de Lagrange λnão é único.

Notemos que a definição de SMFCQ depende previamente da existência demultiplicadores de Lagrange, e portanto depende implicitamente da função ob-jetivo. Uma condição de qualificação que é equivalente à existência e unicidadede multiplicadores de Lagrange para qualquer função objetivo é a LICQ [50],isto é, se assumimos que para qualquer função objetivo, existem multiplicadoresde Lagrange que cumprem SMFCQ, então vale LICQ. Com efeito, sendo x∗ ∈ Ωe definindo f0(x) := −

∑i∈A(x∗) fi(x) temos que x∗ é um minimizador local de

f0 em Ω. Supondo que existem únicos multiplicadores de Lagrange, a saberλ∗i = 1, i ∈ A(x∗) e λ∗i = 0 caso contrário, se α é tal que

∑m+ri=1 αi∇fi(x∗) = 0,

é fácil ver que para C > 0 grande o suficiente, λ := λ + αC também são multi-

plicadores de Lagrange, donde concluímos que α = 0 e vale LICQ.Uma outra maneira de enfraquecer LICQ é, ao invés de requerer posto com-

pleto para o conjunto de gradientes, permitir que o posto seja deficiente, desdeque permaneça deficiente em uma vizinhança do ponto. Esta condição é cha-mada dependência linear constante. Para que este enfraquecimento seja de fatouma condição de qualificação, é necessario exigir tal propriedade para todos ossubconjuntos de gradientes, da maneira a seguir. Dizemos que vale a condi-ção de posto constante (constant rank constraint qualification, CRCQ, [32]) em


x ∈ Ω se existe uma vizinhança B de x tal que para todo I ⊂ 1, . . . ,m + r,se ∇fi(x), i ∈ I é linearmente dependente, então ∇fi(y), i ∈ I é linearmentedependente para todo y ∈ B. Equivalentemente, a condição de dependêncialinear constante pode ser substituída pela condição de posto constante, isto é,vale CRCQ se, e somente se, existe uma vizinhança B de x tal que para todoI ⊂ 1, . . . ,m+r o posto de ∇fi(y), i ∈ I não se altera, para cada y ∈ B. Noteque A(x) = m+ 1, . . . ,m+ r, e quando analisamos restrições avaliadas em yna vizinhança de x, algumas restrições podem deixar de ser ativas, alterando oconjunto de restrições ativas ou, possivelmente, tornando o ponto inviável (em-bora sempre possamos escolher a vizinhança pequena o suficiente de modo queas restrições inativas em x permaneçam inativas em y, isto é, A(y) ⊂ A(x)). Dequalquer maneira, o símbolo r utilizado será sempre correspondente às restriçõesativas em x.

Em uma primeira análise, CRCQ parece ter pouca relação com LICQ, jáque CRCQ faz exigências em toda uma vizinhança de x, além de ser descritapara todo subconjunto de restrições. Entretanto, ao exigirmos LICQ, estamosexigindo independência linear para todos os subconjuntos de restrições e em todauma vizinhança do ponto, em outras palavras, LICQ pode ser equivalentementedescrita como: existe uma vizinhança B de x tal que para todo I ⊂ 1, . . . ,m+r, o conjunto ∇fi(y), i ∈ I é linearmente independente, para todo y ∈ B, oque mostra que CRCQ é mais fraca que LICQ.

Um caso frequente em modelagem é quando uma restrição de igualdadeh(x) = 0 é descrita como duas restrições de desigualdade f1(x) := h(x) ≤0 e f2(x) := −h(x) ≤ 0. Neste caso, embora os gradientes sejam positivo-linearmente dependentes, o que faz com que MFCQ falhe, a dependência linearse mantém em uma vizinhança, o que faz com que CRCQ seja satisfeita. Outrocaso frequente em que CRCQ é satisfeita é quando as restrições são descritas porfunções afins (restrições lineares), o que justifica o fato que em otimização linear,sempre existem multiplicadores de Lagrange (dados pela solução do problemadual).

Embora CRCQ e MFCQ não tenham nenhuma relação de implicação, ésabido que sob CRCQ, é possível reformular o problema de modo a cumprirMFCQ (ver [37]).

Da mesma maneira que MFCQ enfraquece LICQ olhando para o sinal dosmultiplicadores, a condição de dependência linear positiva constante (CPLD,[45]) enfraquece CRCQ no mesmo sentido. Vale CPLD em x ∈ Ω se existe umavizinhança B de x tal que para todo I ⊂ 1, . . . ,m + r, se ∇fi(x), i ∈ I épositivo-linearmente dependente, então ∇fi(y), i ∈ I deve permanecer positivo-linearmente dependente para todo y ∈ B. Note que na definição de dependêncialinear positiva, devemos considerar os gradientes associados às restrições dedesigualdade ativas como os índices associados aos escalares não-negativos. Ri-gorosamente, deveríamos dizer que os gradientes ∇fi(x), i ∈ I ∩ 1, . . . ,m e∇fi(x), i ∈ I ∩ m + 1, . . . ,m + r são positivo-linearmente dependentes, masisto fica claro do contexto.

18 G. Haeser

Mais recentemente, outro tipo de enfraquecimento destas condições surgiuna literatura. A ideia é não considerar todos os subconjuntos de restriçõesI ⊂ 1, . . . ,m+ r. Dizemos que vale Relaxed-CRCQ (RCRCQ, [42]) se existeuma vizinhança B de x ∈ Ω tal que para todo 1, . . . ,m ⊂ I ⊂ 1, . . . ,m+ r,o posto de ∇fi(y), i ∈ I é constante para todo y ∈ B. Ou seja, só é necessárioverificar a propriedade de posto constante para subconjuntos que incluem todasas restrições de igualdade.

Para definirmos uma relaxação análoga para CPLD (Relaxed-CPLD, RC-PLD, [9]), vamos interpretar a condição RCRCQ em termos de dependêncialinear constante. Seja B ⊂ 1, . . . ,m tal que ∇fi(x), i ∈ B forma uma basepara span∇fi(x)mi=1. A condição RCRCQ pode ser equivalentemente definidacomo a existência de uma vizinhança B de x tal que:

• ∇fi(y)mi=1 tem posto constante para todo y ∈ B

• para todo I ⊂ A(x), se ∇fi(x)i∈B∪I é linearmente dependente, então∇fi(y)i∈B∪I é linearmente dependente ∀y ∈ B

A definição de RCPLD é como a definição acima, mas utilizando a proprie-dade de dependência linear positiva constante, isto é, fixado B ⊂ 1, . . . ,m talque ∇fi(x), i ∈ B forma uma base para span∇fi(x)mi=1, vale RCPLD em x se

• ∇fi(y)mi=1 tem posto constante para todo y ∈ B

• para todo I ⊂ A(x), se ∇fi(x)i∈B∪I é positivo-linearmente dependente,então ∇fi(y)i∈B∪I é positivo-linearmente dependente ∀y ∈ B

As relaxações acima são incompletas no sentido que ainda exigem a veri-ficação da condição para todos os subconjuntos de restrições de desigualdadeativas. A seguir, vamos definir a condição CRSC (constant rank of the subspacecomponent, [10]) que detecta exatamente qual é o subconjunto de gradientes quedeve ser considerado para garantir a existência de multiplicadores de Lagrange.Considere o polar do cone linearizado

L(x) =v ∈ Rn | v =

m+r∑i=1

λi∇fi(x), λi ≥ 0, i ∈ A(x),

e considere o maior subespaço contido em L(x), isto é, span∇fi(x)i∈J−(x),onde J−(x) = i ∈ 1, . . . ,m + r | −∇fi(x) ∈ L(x). É claro que J−(x)contém todos os índices de restrições de igualdade, mas contém também, possi-velmente, alguns índices de restrições de desigualdade. Tais restrições de desi-gualdade correspondem a uma restrição de desigualdade que se comporta comouma restrição de igualdade, pelo menos na maneira de compor o polar do conelinearizado, já que os escalares correspondentes a esta restrição tem sinal irres-trito.

Dizemos que x ∈ Ω satisfaz CRSC quando existe uma vizinhança B de x talque os gradientes ∇fi(y), i ∈ J−(x) tem posto constante para todo y ∈ B.


De fato, sob CRSC, é possível mostrar (ver [10]) que as restrições em J−(x)atuam localmente como igualdades, isto é, existe uma vizinhança B de x tal quepara todo y ∈ B ∩ Ω e para todo i ∈ J−(x), vale fi(y) = 0.

A condição CRSC unifica todas as demais, no sentido que é implicada pelascondições apresentadas anteriormente. O conceito de posto constante é ade-quado para lidar com restrições de igualdade, enquanto o conceito de depen-dência linear positiva se adequa melhor às desigualdades, enquanto a CRSCincorpora de maneira simples os dois conceitos. Em certo sentido, todas as con-dições de qualificação anteriores estão garantindo que a decomposição de L(x)na soma direta entre seu maior subespaço e um cone pontudo, seja tal que acomponente de subespaço mantenha localmente a dimensão.

Todos os enfraquecimentos acima são possíveis ainda mantendo o fato de seruma condição de qualificação, além disso, as condições apresentadas são está-veis, no sentido que se valem em um ponto, então valem em uma vizinhançadeste ponto. Mais importante, as condições de qualificação apresentadas for-necem condições de otimalidade mais fortes e possíveis de serem verificadas naprática, no sentido que somos capazes de construir algoritmos eficientes comconvergência global para um ponto estacionário sob estas condições, além disto,todas as condições apresentadas garantem a validade de um error bound, isto é,a distância ao conjunto viável pode ser medida, em uma vizinhança de x, uti-lizando uma medida analítica de inviabilidade, isto é, vale a condição de errorbound em x ∈ Ω se existe uma vizinhança B de x e uma constante α > 0 talque para todo y ∈ B vale:

minz∈Ω‖z−y‖ ≤ αmax|f1(y)|, . . . , |fm(y)|,max0, fm+1(y), . . . ,max0, fm+p(y).

Esta propriedade é uma condição de qualificação, já que dado d ∈ L(x) facil-mente verificamos por Taylor que fi(x + td) = o(t), i = 1, . . . ,m, fi(x + td) ≤o(t), i ∈ A(x) e fi(x+ td) < 0, i = m+ r+1, . . . ,m+p. Assim, dist(x+ td,Ω) =o(t), com o(t)

t → 0, o que não é difícil ver, equivale ao fato de d ∈ T (x), e por-tanto a condição de Abadie é satisfeita. A Figura 2.1 mostra a relação entre ascondições apresentadas. É interessante observar que o error bound é a condiçãode qualificação mais fraca possível que garante a validade da condição KKTpara todas as funções objetivo da forma f0 := g + h, onde g é continuamentediferenciável e h é convexa possivelmente não suave [17].

No caso suave, ou seja, quando h = 0, a condição mais fraca possível quegarante KKT é a condição de Guignard. Terminamos esta sessão com a provadeste resultado de [29], onde corrigimos algumas pequenas imprecisões do tra-balho original.

Teorema 2.3 Seja x ∈ Ω. Então L(x) = T (x) (condição de Guignard) éequivalente ao fato que para qualquer função f0 que assume mínimo restrito aΩ em x, é tal que x é um ponto KKT.

20 G. Haeser

LICQ

CRCQMFCQ

RCRCQCPLD

RCPLD

CRSC

Error Bound

Abadie

Guignard ∀f0(·), min. local ⇒ KKT

∀f0 := g + h, min. local ⇒ KKT

Figura 2.1: Relação entre as condições de qualificação apresentadas. g é umafunção C1 e h é uma função convexa (possivelmente não suave) quaisquer.

Prova: O fato que a condição de Guignard é uma condição de qualificação jáfoi mostrado ao longo do texto. Sabemos também que L(x) ⊂ T (x). Agora,seja 0 6= d ∈ T (x) e vamos construir uma função suave f0 que assume ummínimo local em x (restrito a Ω), de modo que d = −∇f0(x). A hipótesede x ser estacionário para este problema resulta em d ∈ L(x). DefinimosCk, k ≥ 1 o cone de direções não nulas que formam ângulo entre 0 e π

2 −πk+3

com d. Então, para cada k ≥ 1, existe εk > 0, tal que Ω ∩ B(x, εk) ⊂ Rn\Ck.Com efeito, se existisse k tal que x` ∈ Ck ∩ Ω, x` → x, então

⟨d, x`

‖x`‖

⟩≥

‖d‖ cos(π2 −πk+3 ) > 0. Tomando o limite em ` para uma subsequência temos

〈d, y〉 > 0 com y ∈ T (x), o que contradiz o fato de d ∈ T (x). Definimosε1 = min(ε1, 1) e εk = min(εk, εk−1

2 ), k > 1. Vamos assumir sem perda degeneralidade que x = 0 e d = (0, . . . , 0, 1), assim, definimos P : Rn−1 → R nosubespaço ortogonal a d da seguinte maneira:

P (z) =

0 se z = 0,tan(π3 ) se ‖z‖ ≥ ε2,

tan( πk+2 )εk+1 + tan( π

k+1 )εk−tan( πk+2 )εk+1

εk−εk+1(‖z‖ − εk+1) se εk+1 ≤ ‖z‖ < εk.

Observamos que P é linear por partes e contínua. Além disso, para εk+1 ≤‖z‖ < εk, observamos que tan( π

k+2 )‖z‖ ≤ P (z) ≤ tan( πk+1 )‖z‖. Este fato

é uma propriedade geométrica de funções afins crescentes que assumem umvalor negativo na origem. Isso mostra que P é diferenciável na origem com


∇P (0) = 0. Agora, seja f0 : Rn → R definida por f0(y) = P (z) − dTy, ondey = (z, w) ∈ Rn−1 ×R e vamos mostrar que f0 restrita a Ω assume um mínimolocal em 0. Com efeito, seja 0 6= y = (z, w) ∈ Rn−1 × R, y ∈ Ω ∩ B(0, ε3), comod = (0, . . . , 0, 1) e P (0) = 0, basta mostrar que w < P (z). Se z = 0, caso w > 0teríamos que y seria um múltiplo positivo de d ∈ T (0), o que contradiz o fatode y ∈ Ω. Então w < 0 = P (z).

Sendo z 6= 0, existe k ≥ 2 tal que εk+1 ≤ ‖z‖ < εk. Logo P (z) ≥‖z‖ tan( π

k+2 ). Note que y 6∈ Cr é equivalente a dizer que w < tan( πr+3 )‖z‖.

Sendo y ∈ Ω ∩ B(0, ε3) ⊂ Rn\C3 temos w < tan( π3+3 )‖z‖ < ‖z‖. Assumindo

w > 0, já que caso contrário o resultado é trivialmente verdadeiro, temos ‖y‖ =√‖z‖2 + |w|2 <

√2‖z‖ < 2εk ≤ εk−1. Portanto y ∈ Ω∩B(0, εk−1) ⊂ Rn\Ck−1.

Sendo y 6∈ Ck−1, temos w < tan( πk−1+3 )‖z‖. Segue que w < P (z).

Sendo f0(0) = 0 e f0(y) > 0 para 0 6= y ∈ S suficientemente pequeno, segueda hipótese que x = 0 é um ponto KKT, ou seja d = −∇f0(0) ∈ L(x).

Observamos que a construção pode ser feita com f0 diferenciável em todoRn e de modo que x seja o único minimizador global de f0 restrito a Ω. Ver[48], Teorema 6.11.

2.2 Condições sequenciais de primeira ordemNa prática, um algoritmo iterativo não verifica condições do tipo “KKT ou

não-CQ” onde CQ é alguma condição de qualificação. Isso porque um algoritmogera uma sequência xk, onde apenas no limite esta condição é verificada. Naprática, é preciso utilizar condições de otimalidade que possam ser verificadasno ponto xk disponível na iteração k do método. Sendo assim, o que se verifica,tipicamente, é se xk satisfaz, aproximadamente, a condição KKT. Isso fornececerta confiança de que xk é um bom candidado para a solução do problema eo algoritmo para. Condições sequenciais de otimalidade fornecem a ferramentateórica que justifica esta prática. Dizemos que x satisfaz a condição sequencialde otimalidade associada à proposição matemática P se existe uma sequênciaxk → x tal que P(xk) é satisfeita. A proposição deve ser de tal forma quesempre que x é uma solução do problema, deve existir uma sequência xk → xque cumpre P. Tipicamente o cumprimento de P está associado a um parâmetroεk → 0. Assim, se sabemos que um algoritmo gera sequência que cumpre P,é seguro terminar a execução do algoritmo quando o parâmetro εk associado épequeno o suficiente. A condição sequencial de otimalidade mais frequentementeutilizada na prática é a condição Aproximadamente-KKT que definimos a seguir:

Definição 2.4 (Aproximadamente-KKT, [7]) Dizemos que x ∈ Ω satisfaza condição Aproximadamente-KKT (AKKT) se existem sequências xk → x,λk ⊂ Rm+r com λki ≥ 0, i ∈ A(x) tais que ∇f0(xk) +

∑m+ri=1 λki∇fi(xk)→ 0.

Quando xk é uma sequência como na definição acima dizemos que xk é umasequência AKKT.

22 G. Haeser

O teorema a seguir mostra como verificar AKKT na prática

Teorema 2.5 O ponto x satisfaz AKKT se, e só se, existem sequências xk → x,λk ⊂ Rm+p com λki ≥ 0, i = m+ 1, . . . ,m+ p e εk ⊂ R, εk ≥ 0 tais que

‖(fi(xk))mi=1‖ ≤ εk, ‖(max0, fi(xk))m+pi=m+1‖ ≤ εk,

‖∇f0(xk) +m+p∑i=1

λki∇fi(xk)‖ ≤ εk,

∀i = m+ 1, . . . ,m+ p, se fi(xk) < −εk então λki = 0,εk → 0+.

Prova: Assuma que x satisfaz AKKT e defina

εk = max‖(fi(xk))mi=1‖, ‖(max0, fi(xk))m+pi=m+1‖,

‖∇f0(xk) +m+r∑i=1

λki∇fi(xk)‖,−fj(xk), j ∈ A(x).

Temos εk → 0+. Note que se i ∈ m + 1, . . . ,m + p é tal que fi(xk) < −εk,então −fi(xk) > εk ≥ −gj(xk),∀j ∈ A(x). Em particular, i 6∈ A(x). Portanto,basta definir λki = 0 e temos o resultado.

Assumindo as condições do teorema, a continuidade das funções garante quex ∈ Ω, e basta observar que se i 6∈ A(x), então fi(x) < 0, e portanto, para ksuficientemente grande vale fi(xk) < −εk, logo λki = 0 e vale AKKT.

Assim, se um algoritmo gera uma sequência que cumpre as condições acimacom εk ≤ ε, com ε > 0 uma tolerância pequena previamente estabelecida,é seguro dizer que a sequência xk gerada é, provavelmente, uma sequênciaAKKT, logo, o iterando xk está próximo de um ponto AKKT, um candidato àsolução do problema.

Resta mostrar que AKKT é uma condição de otimalidade. De fato, é interes-sante observar que AKKT é satisfeita em uma solução do problema independenteda validade de condições de qualificação.

Para isto, vamos considerar o algoritmo de penalidade externa para o pro-blema

Minimizar f0(x),Sujeito a fi(x) = 0, i = 1, . . . ,m,

fi(x) ≤ 0, i = m+ 1, . . . ,m+ p,x ∈ Ω,

onde Ω ⊂ Rn é um conjunto fechado e não vazio.Escolha uma sequência ρk ⊂ R com ρk → +∞ e para cada k, seja xk a

solução (global), caso exista, para o problema

Minimizar f0(x) + ρkP (x),Sujeito a x ∈ Ω,


onde P (x) é a função P (x) = ‖(fi(xk))mi=1‖2 + ‖(max0, fi(xk))m+pi=m+1‖2.

Agora, seja x∗ um ponto limite arbitrário de xk, caso exista. Temos x∗ ∈Ω. Para mostrar que x∗ é um minimiador global de P (x), sujeito a x ∈ Ω,assuma P (x∗) > P (z), z ∈ Ω. Em uma subsequência apropriada temos P (xk) >P (z) + c para alguma constante c > 0, o que podemos re-escrever como f(xk) +ρkP (xk) > f(z) +ρkP (z) + (ρkc+f(xk)−f(z)). Para k suficientemente grandetemos (ρkc+ f(xk)− f(z)) > 0 e portanto f(xk) + ρkP (xk) > f(z) + ρkP (z), oque contradiz a definição de xk.

Assumindo que o problema admite um ponto viável z ∈ Ω, P (z) = 0, temosque x∗ é um ponto viável. Mas neste caso podemos mostrar que x∗ é umasolução, já que f(xk) ≤ f(xk) + ρkP (xk) ≤ f(z) + ρkP (z),∀z ∈ Ω, ou seja,para z viável temos f(xk) ≤ f(z). Tomando o limite para uma subsequênciaapropriada segue que f(x∗) ≤ f(z), e portanto todos os pontos limites, casoexistam, são soluções (globais) do problema quando a região viável é não vazia.

Para mostrarmos que AKKT é uma condição de otimalidade, considere x∗uma solução e vamos considerar a aplicação do algoritmo de penalidade externapara o problema

Minimizar f0(x) + 12‖x− x

∗‖2,Sujeito a fi(x) = 0, i = 1, . . . ,m,

fi(x) ≤ 0, i = m+ 1, . . . ,m+ p,‖x− x∗‖2 ≤ δ,

onde δ > 0 é suficientemente pequeno e Ω = x | ‖x − x∗‖2 ≤ δ é não vazioe compacto. Note que x∗ é a única solução global. Pela compacidade de Ω, asequência xk gerada pelo algoritmo de penalidade externa está bem definida,além disso, sendo o conjunto viável não vazio, todos os seus pontos limites sãosoluções globais. Da compacidade de Ω temos a existência de pelo menos umponto limite, e da unicidade da solução, temos que há um único ponto limite, asaber, x∗, isto é, xk → x∗.

Para mostrar que xk é uma sequência AKKT, basta observar que ‖xk −x∗‖ < δ para k suficientemente grande, e portanto, usando a definição da funçãoP (x) e o fato que o gradiente de f0(x) + 1

2‖x− x∗‖2 + ρkP (x) se anula em xk,

temos

∇f0(xk)+xk−x∗+m∑i=1

(2ρkfi(xk))∇fi(xk)+m+p∑i=m+1

(2ρk max0, fi(xk))∇fi(xk) = 0.

Definindo λki = 2ρkfi(xk), i = 1, . . . ,m e λki = 2ρk max0, fi(xk) ≥ 0, i = m+1, . . . ,m+p e observando que se fi(x∗) < 0, então λki = 0 para k suficientementegrande temos

∇f0(xk) + xk − x∗ +m+r∑i=1

λki∇fi(xk) = 0.

Tomando o limite temos que x∗ satisfaz AKKT. Temos então o seguinte resul-tado.

24 G. Haeser

Teorema 2.6 Se x∗ é uma solução local, então x∗ satisfaz AKKT.

Observação: A existência de multiplicadores Fritz John (Teorema 1.4) podeser provada como uma consequência do Teorema 2.6. De fato, sendo x∗ umasolução local, considere sequências xk, λk, λki ≥ 0, i ∈ A(x∗) como na De-finição 2.4 de AKKT, de modo que εk := ∇f0(xk) +

∑m+ri=1 λki∇fi(xk) → 0.

Dividindo εk por ‖(1, λk)‖, temos αk0∇f0(xk) +∑m+ri=1 αki∇fi(xk) → 0 com

‖(αk0 , αk)‖ = 1 e αki ≥ 0, i ∈ 0∪A(x∗). Tomando o limite em uma subsequên-cia tal que (αk0 , αk) é convergente, seu limite é um multiplicador que satisfazas condições do Teorema 1.4. Dada a equivalência da condição de Fritz Johncom a condição de otimalidade “KKT ou não-MFCQ”, a demonstração anteriortambém prova que um ponto AKKT que satisfaz MFCQ deve ser um pontoKKT. Os Teoremas 2.9 e 2.12 generalizam este resultado.

Em [10] foi mostrado que algoritmos do tipo Lagrangiano aumentado [4, 5],Programação Quadrática Sequencial [45, 44], Restauração Inexata [41, 26] ePontos Interiores [24] geram sequências AKKT. Vamos mostrar este resultadoapenas para o algoritmo de Lagrangiano aumentado definido abaixo:

Considere a função Lagrangiano aumentado:

Lρ(x, λ) := f0(x) + ρ

2

(m∑i=1

(fi(x) + λi

ρ

)2+

m+p∑i=m+1

(max

0, fi(x) + λi

ρ

)2),

ρ > 0, λi ≥ 0, i = m+ 1, . . . ,m+ p. Definimos abaixo o algoritmo:

Passo 0 (inicialização): Sejam λmini < λmax

i , i = 1, . . . ,m + p, com 0 =λmini , i = m+ 1, . . . ,m+ p; γ > 1, τ ∈ (0, 1), εk ≥ 0, εk → 0+. Sejam λ1 ∈ Rm+p

com λmin ≤ λ1 ≤ λmax, ρ1 > 0 e x0 ∈ Rn. Definimos V 0i := fi(x0), i =

1, . . . ,m;V 0i = max0, fi(x0), i = m+ 1, . . . ,m+ p. Inicialize k := 1.

Passo 1 (minimização): Encontre umminimizador aproximado xk de Lρk(x, λk),isto é,

‖∇Lρk(xk, λk)‖ ≤ εk.

Passo 2 (atualização do parâmetro de penalidade): Defina V ki := fi(xk), i =1, . . . ,m;V ki := maxfi(xk),−λ

ki

ρk, i = m + 1, . . . ,m + p. Se ‖V k‖ ≤ τ‖V k−1‖

definimos ρk+1 := ρk, senão ρk+1 := γρk.

Passo 3 (atualização do multiplicador de Lagrange): Calcule λk ∈ Rm+p

com λmin ≤ λk ≤ λmax. Faça k := k + 1 e vá para o Passo 1.

Teorema 2.7 Seja x∗ um ponto limite da sequência xk gerada pelo algorit-mos. Então x∗ é um ponto estacionário para o problema de minimizar 1

2∑mi=1 fi(x)2+∑m+p

i=m+1 max0, fi(x)2.


Prova: Se ρk é limitada, V k → 0 e portanto fi(x∗) = 0, i = 1, . . . ,m; fi(x∗) ≤0, i = m + 1, . . . ,m + p. Senão, temos δk := ∇f0(xk) +

∑m+pi=1 λki∇fi(xk)

com ‖δk‖ ≤ εk, onde λki = λki + ρkfi(xk), i = 1, . . . ,m; λki = max0, λki +ρkfi(xk), i = m + 1, . . . ,m + p. Dividindo δk por ρk, como λk é limitada,observamos que λki

ρkconverge para fi(x∗) se i = 1, . . . ,m e para max0, fi(x∗)

se i = m+ 1, . . . ,m+ p e o resultado segue.

Teorema 2.8 Assuma que a sequência xk gerada pelo algoritmo de Lagran-giano aumentado admite um ponto limite viável x. Então x é um ponto AKKT.

Prova: Pela definição de Lρ e pelo Passo 1 do algoritmo temos

‖∇f0(xk) +m+p∑i=1


onde λki = λki + ρkfi(xk), i = 1, . . . ,m; λki = max0, λki + ρkfi(xk), i = m +1, . . . ,m+ p. Se fi(x∗) < 0, i = m+ 1, . . . ,m+ p, para o caso ρk → +∞, comoλki é limitada, temos λki = 0. Caso contrário, V k → 0 e portanto −λ

ki

ρk→ 0.

Logo λki = 0. Segue que x∗ satisfaz AKKT.

Tipicamente a convergência global de um algoritmo é dada mostrando quesob uma condição de qualificação, os pontos limites gerados pelo algoritmo sãopontos estacionários. Resta saber qual é a relação entre a condição de otimali-dade sequencial AKKT e condições de otimalidade “pontuais” do tipo “KKT ounão-CQ”. Vamos mostrar que AKKT é mais forte que “KKT ou não-CPG” ondea condição de qualificação constant positive generators (CPG, [10]) é mais fracaque CRSC. Em particular, algoritmos que geram sequências AKKT tem pontoslimites estacionários exigindo CPG ou qualquer outra condição de qualificaçãomais forte como CRSC, CPLD, MFCQ, etc...

Para definir a condição CPG, considere vetores V = v1, . . . , vm+r ∈ Rn evamos estudar cones da forma

span +(I,J ;V) = w ∈ Rn | w =∑

i∈I∪Jλivi, λi ≥ 0, i ∈ J ,

onde I = 1, . . . ,m,J = m+ 1, . . . ,m+ r e os vetores v1, . . . , vm+r estarãoclaros do contexto. Note que quando vi = ∇fi(x), i = 1, . . . ,m + r, temosspan+(I,J ;V) = L(x).

Para cones desta forma (cones positivamente gerados), podemos definir umanoção de base. Diremos que o par ordenado (I ′,J ′), I ′,J ′ ⊂ 1, . . . ,m + rforma uma base para span+(I,J ;V) quando span+(I ′,J ′;V) = span+(I,J ;V)e os vetores vi, i ∈ I ′ e vi, i ∈ J ′ são positivo-linearmente independentes. Mos-tramos a seguir a existência de uma base. Para isso, note que vetores ori-ginalmente em J podem estar em I ′. No nosso contexto, isto representa uma

26 G. Haeser

restrição de desigualdade que será considerada como uma restrição de igualdade.Se os vetores vi, i ∈ I e vi, i ∈ J são positivo-linearmente dependentes, isto é,existe 0 6= α ∈ Rm+r tal

∑m+ri=1 αivi = 0, αi ≥ 0, i = m + 1, . . . ,m + r, temos

duas possibilidades: se vi, i ∈ I é linearmente dependente, considere I ′ obtidode I removendo um índice redundante. Claramente temos span+(I ′,J ′;V) =span+(I,J ;V) com J ′ = J . Se vi, i ∈ I é linearmente independente, entãoexiste j ∈ J tal que −vj ∈ span+(I,J ;V) e definindo I ′ = I∪j J ′ = J −jé fácil ver que span+(I ′,J ′;V) = span+(I,J ;V). Repetindo esta construçãoaté obter vetores vi, i ∈ I ′ e vi, i ∈ J ′ positivo-linearmente independentes ob-temos uma base para span+(I,J ;V).

Considerando V(x) = ∇fi(x)m+ri=1 , I = 1, . . . ,m e J = A(x), dizemos

que vale CPG em x ∈ Ω quando existe uma base (I ′,J ′) de span+(I,J ,V(x)) =L(x) que é suficiente para gerar o cone em uma vizinhança, isto é,

span +(I,J ,V(y)) ⊂ span +(I ′,J ′,V(y)),

para todo y em alguma vizinhança de x.Considerando a decomposição de L(x) na soma direta de seu maior subes-

paço v | v =∑i∈J−(x) λi∇fi(x) com o cone pontudo v | v =

∑i 6∈J−(x) λi∇fi(x), λi ≥

0,∀i, podemos considerar apenas I ′ ⊂ J−(x) tal que vi, i ∈ I ′ forma uma basepara a componente do subespaço, enquanto J ′ = i | i 6∈ J−(x).

Considere o conjunto viável definido por f1(x1, x2) := x31−x2 ≤ 0, f2(x1, x2) :=

x31 + x2 ≤ 0, f3(x1, x2) := x1 ≤ 0. Em x = (0, 0), J−(x) = 1, 2. TomandoI ′ = 1 e J ′ = 3 temos ∇f1(x) e ∇f3(x) são positivo-linearmente inde-pendentes tais que span+(I ′,J ′;V(x)) = span+(∅, 1, 2, 3;V(x)), e ainda, emy 6= 0, span+(I ′,J ′;V(y)) é o semi-espaço que contém propriamente o cone pon-tudo span+(∅, 1, 2, 3;V(y)), portanto vale CPG, entretanto, CRSC não vale,já que o posto de ∇f1(0),∇f2(0) é 1, enquanto para qualquer y 6= 0 o postoaumenta. O Teorema a seguir mostra que CPG é de fato mais fraca que CRSC.

Teorema 2.9 Se x ∈ Ω satisfaz CRSC, então x satisfaz CPG

Prova: Seja (I ′,J ′) uma base para span+(I,J ,V(x)). Como I ′ ⊂ J−(x) cor-responde a uma base para span∇fi(x), i ∈ J−(x), sendo o posto de ∇fi(y), i ∈J−(x) constante, esta base deve permanecer uma base em uma vizinhança.

Incluindo a restrição f4(x1, x2) := x32 ≤ 0 no exemplo analisado, observamos

que a condição Error Bound não é satisfeita. Para ver isto, basta considerarxk = (−(1/k)1/3, 1/k). A distância de xk para o conjunto viável é 1/k, enquantoa medida de inviabilidade é 1/k3. Embora CPG não cumpra com Error Bound,temos que CPG implica Abadie. Ver [10].

Mostraremos a seguir que sob CPG, um ponto AKKT é de fato KKT. Comotodo minimizador é AKKT, isso mostra que CPG é de fato uma condição dequalificação, e além disso, garante a convergência global para algoritmos que ge-ram sequência AKKT sob CPG. Com isso concluímos a conexão entre condiçõespontuais e sequenciais.

Teorema 2.10 Se x ∈ Ω é AKKT e satisfaz CPG, então x cumpre KKT.


Prova: Sejam xk ⊂ Rn, xk → x e λk ⊂ Rm+r com λki ≥ 0, i ∈ A(x) e∇f0(xk) +

∑m+ri=1 λki∇fi(xk)→ 0.

Sendo (I ′,J ′) uma base para L(x) tal que span+(1, . . . ,m, A(x);V(y)) ⊂span+(I ′,J ′;V(y)) para y em uma vizinhança de x, temos para k suficien-temente grande que existem λki , i ∈ I ′ ∪ J ′ com λki ≥ 0, i ∈ J ′ tais que∇f0(xk) +

∑i∈I′∪J ′ λ

ki∇fi(xk)→ 0.

Sendo Mk = max|λki |, i ∈ I ′ ∪ J ′, se Mk é ilimitada, dividindo por Mk

podemos tomar uma subsequência tal que λkiMk→ αi com αi não todos nulos e

αi ≥ 0, i ∈ J ′, assim, tomando o limite temos∑i∈I′∪J ′ αi∇fi(x) = 0 o que

contradiz a independência linear positiva.Se Mk é limitada podemos tomar uma subsequência tal que λki → λi,

λi ≥ 0, i ∈ J ′ e tomando o limite temos ∇f0(x) +∑i∈I′∪J ′ λi∇fi(x) = 0.

Sendo (I ′,J ′) base para L(x) temos que x é KKT. Acreditava-se que CPG era a condição de qualificação mais fraca possível

que garante que AKKT implica KKT. Entretanto, em [46, 11], é definida acondição de qualificação CCP (cone continuity property) com tal propriedade.CCP é estritamente mais fraca que CPG, embora CCP implique Abadie.

Definição 2.11 (CCP, [46]) Diremos que x ∈ Ω satisfaz a propriedade docone contínuo (CCP) quando a multifunção K(·) é semi-contínua exteriormenteem x, isto é, limsupy→xK(y) ⊂ K(x), onde

K(y) = v ∈ Rn | v =m+r∑i=1

λi∇fi(y), λi ≥ 0, i ∈ A(x)

elimsupy→x

K(y) = w ∈ Rn | ∃yk → x, ∃wk → w,wk ∈ K(yk).

Teorema 2.12 ([46]) x ∈ Ω satisfaz CCP, se e somente se, para qualquerfunção objetivo f0 tal que x é AKKT, vale que x é KKT.

Prova: Seja x ∈ Ω tal que vale CCP e f0 uma função objetivo tal que x éAKKT. Logo existem sequências xk → x, λk ⊂ Rm+r, λki ≥ 0, i ∈ A(x) taisque ∇f0(xk) + ωk → 0, onde ωk =

∑m+ri=1 λki∇fi(xk) ∈ K(xk).

Como ωk → −∇f0(x), temos que −∇f0(x) ∈ limsupy→xK(y). Da condiçãoCCP temos −∇f0(x) ∈ K(x) = L(x) e x satisfaz KKT.

Reciprocamente, seja ω ∈ limsupy→xK(y). Logo existem sequências xk → x

e ωk → ω com ωk ∈ K(xk). Para provar que ω ∈ K(x), definimos a função ob-jetivo f0(y) = −

∑ni=1 ωiyi. Do fato de ωk ∈ K(xk), existe λk ⊂ Rm+r, λki ≥

0, i ∈ A(x) tal que ωk =∑m+ri=1 λki∇fi(xk), assim, como ∇f0(xk) = −ω e

ωk → ω temos ∇f0(xk) +∑m+ri=1 λki∇fi(xk) → 0 e x cumpre AKKT. Da hipó-

tese, x é KKT, ou seja, −∇f0(x) = ω ∈ K(x) e CCP é satisfeita. Na Figura 2.2 apresentamos um diagrama completo de relações entre diversas

condições de qualificação.

28 G. Haeser

LICQ

CRCQSMFCQ

MFCQRCRCQ

CPLD

RCPLD

CRSC

CPG

CCP ∀f0(·), AKKT ⇒ KKTError Bound

Abadie

Guignard ∀f0(·), min. local ⇒ KKT

Pseudonormalidade

Quasinormalidade

∀f0 := g + h, min. local ⇒ KKT

Figura 2.2: Relações entre condições de qualificação. g é uma função C1 e h éuma função convexa (possivelmente não suave) quaisquer.

Capítulo 3

Condições de otimalidadede segunda ordem

Neste capítulo vamos assumir que as funções fi : Rn → R, i = 0, . . . ,m + psão duas vezes continuamente diferenciáveis.

Considere o problema

Minimizar f0(x) := −x21 − x2

2,Sujeito a f1(x) := x1 + 2x2 − 2 ≤ 0,

f2(x) := −x1 ≤ 0,f3(x) := −x2 ≤ 0.

A região viável é o triângulo de vértices (0, 0), (2, 0) e (0, 1) descrito na figuraabaixo juntamente com as curvas de nível da função objetivo:

No ponto x = (0.4, 0.8) temos A(x) = 1 e a condição KKT

∇f0(x) + λ1∇f1(x) = 0, λ1 ≥ 0

é satisfeita com λ1 = 0.8, entretanto, observamos que x não é uma solução.De fato, a partir de x, a função objetivo f0 aumenta ao longo de direções que

29

30 G. Haeser

apontam para o interior da região viável (ou seja, direções d ∈ R2 tais que∇f1(x)Td < 0), mas ao longo de direções viáveis ortogonais ao gradiente de f1,a função objetivo decresce. O que ocorre é que a aproximação de primeira ordemnão olha para direções viáveis ortogonais ao gradiente das restrições ativas emx, e erroneamente declara que o ponto x em questão é um candidato a minimi-zador. A dificuldade é que tais direções, denominadas direções críticas, podemou não ser direções viáveis, dependendo da curvatura das restrições. Condi-ções de otimalidade de segunda ordem exigem que ao longo de direções críticasa aproximação de segunda ordem da função objetivo não seja decrescente. Defato, neste exemplo, observamos que ao longo da direção crítica d = (2,−1) com∇f1(x)Td = 0, temos f0(x+ d) ≈ f0(x) + 1

2dT∇2f0(x)d e como dT∇2f0(x)d < 0

podemos perceber que x não é um minimizador local.

No caso geral de restrições não-lineares, a curvatura das restrições desempe-nha um papel importante, sendo assim, a análise acima pode ser aplicada consi-derando o problema com função objetivo dada por L(x) = f0(x)+

∑m+pi=1 λifi(x),

para um multiplicador de Lagrange λ fixado, que subestima f0 em pontos viá-veis.

Definição 3.1 Dizemos que o ponto KKT x ∈ Ω, A(x) = m+1, . . . ,m+r sa-tisfaz a condição necessária (forte) de segunda ordem associada ao multiplicadorde Lagrange λ (associado a x) quando

dT

(∇2f0(x) +

m+r∑i=1

λi∇2fi(x))d ≥ 0,∀d ∈ CS(x),

onde

CS(x) = d ∈ Rn | ∇fi(x)Td = 0, i = 1, . . . ,m,∇fi(x)Td ≤ 0, i ∈ A(x) ∪ 0

é o cone crítico (forte).

Note que, independente da escolha do multiplicador de Lagrange λ associadoa x, a descrição do cone crítico pode ser feita da seguinte maneira:

CS(x) =d ∈ Rn | ∇fi(x)Td = 0, i ∈ 1, . . . ,m ∪ i ∈ m+ 1, . . . ,m+ r | λi > 0

∇fi(x)Td ≤ 0, i ∈ m+ 1, . . . ,m+ r | λi = 0

Assim, para todo d ∈ CS(x) temos ∇f0(x)Td = 0.

Note que definindo a função Lagrangiana L : Rn × Rm × Rp+ como

L(x, λ) := L(x, (λi)mi=1, (λi)m+pi=m+1) = f0(x) +

m+p∑i=1

λifi(x),

temos que a condição de otimalidade de primeira ordem em um ponto x ∈ Ω ésatisfeita se existe λ ∈ Rm+p com λi ≥ 0, i = m + 1, . . . ,m + p e λi = 0, i =


m+1, . . . ,m+p com i 6∈ A(x) tal que ∇xL(x, λ) = 0. Além disso, a condição desegunda ordem associada a λ é satisfeita se ∇2

xxL(x, λ) é semidefinida positivaem CS(x). Quando temos um multiplicador de Lagrange λ ∈ Rm+r associadoa x∗ com A(x∗) = m + 1, . . . ,m + r faremos o abuso de notação L(x, λ)significando L(x, λ), onde λ ∈ Rm+p é o vetor λ aumentado de zeros nas posiçõesm+ r + 1, . . . ,m+ p.

Observamos que, embora fora do escopo destas notas, uma condição sufi-ciente de otimalidade local estrita é dada independentemente da validade decondições de qualificação, pela existência de um multiplicador de Lagrange as-sociado a x ∈ Ω que cumpre a condição de segunda ordem com desigualdadeestrita para d 6= 0, ou seja, se ∇2

xxL(x, λ) é definida positiva em CS(x)\0.Tipicamente os livros de otimização tratam de provar a validade da condição

necessária de segunda ordem em um minimizador sob a hipótese de regularidade.A unicidade do multiplicador, neste caso, simplifica a análise. Neste capítuloapresentaremos outras condições de qualificação que garantem a validade dacondição necessária de otimalidade e mostraremos outras condições de otima-lidade de segunda ordem mais úteis para a análise de convergência global dealgoritmos.

3.1 Condições de qualificaçãoÉ interessante observar que mesmo sem assumir nenhuma condição de qua-

lificação é possível descrever uma condição de otimalidade de segunda ordem.O teorema a seguir estende o resultado de Fritz-John (Teorema 1.4) para o casoem que as funções possuem segunda derivada contínua.

Teorema 3.2 (Condição de Fritz John de segunda ordem) Se x∗ ∈ Ω éuma solução local, então para cada d ∈ CS(x∗) existe 0 6= (λ0, λ) ∈ R × Rm+r

com∑m+ri=0 λi∇fi(x∗) = 0, λ0 ≥ 0, λi ≥ 0, i ∈ A(x∗) tal que

dT

(m+r∑i=0

λi∇2fi(x))d ≥ 0.

Prova: No caso em que ∇fi(x∗)mi=1 é linearmente dependente com∑mi=1 λi∇fi(x∗) =

0 e λ 6= 0, tomamos um multiplicador Fritz John satisfazendo as condições con-siderando λ ou −λ e os demais λi’s nulos. Caso contrário, fixamos d ∈ CS(x∗)e consideramos o seguinte problema de otimização linear nas variáveis z e w:

Minimizar z,Sujeito a ∇fi(x∗)Tw + dT∇2fi(x∗)d = 0, i = 1, . . . ,m,

∇fi(x∗)Tw + dT∇2fi(x∗)d ≤ z, i ∈ 0 ∪ i ∈ A(x∗) | ∇fi(x∗)Td = 0

Aplicando o Teorema da Função Implícita, é possível mostrar que o problemaacima possui valor ótimo finito não-negativo (ver detalhes em [23], página 443).

32 G. Haeser

Assim, o problema dual abaixo nas variáveis λi, i = 0, . . . ,m + r possui omesmo valor ótimo:

Maximizar dT(∑m+r

i=0 λi∇2fi(x))d,

Sujeito a∑m+ri=0 λi∇fi(x∗) = 0,∑m+ri=0 λi = 1,

λi ≥ 0, i ∈ 0 ∪ i ∈ A(x∗) | ∇fi(x∗)Td = 0,λi = 0, i ∈ A(x∗),∇fi(x∗)Td < 0.

A solução ótima do problema acima é um multiplicador do tipo Fritz Johnque satisfaz as condições do enunciado.

Embora fora do escopo destas notas, é interessante observar que se assumir-mos uma versão mais forte da tese do teorema acima em um ponto x∗ ∈ Ω, asaber, que a desigualdade vale no sentido estrito quando d 6= 0, então obtemosuma condição suficiente do tipo Fritz John para a otimalidade local estrita de x∗.

A condição necessária de segunda ordem do tipo Fritz John tem a desvanta-gem que λ0 pode ser igual a zero, desprezando a função objetivo. Este problemaé resolvido assumindo a condição de qualificação de Mangasarian-Fromovitz.

Teorema 3.3 (Condição de segunda ordem sob MFCQ) Se x∗ ∈ Ω é umasolução local que satisfaz MFCQ, então para cada d ∈ CS(x∗) existe um multi-plicador de Lagrange λ ∈ Rm+r, λi ≥ 0, i ∈ A(x∗) associado a x∗ tal que

dT

(∇2f0(x) +

m+r∑i=1

λi∇2fi(x))d ≥ 0.

Prova: Basta aplicar o teorema anterior e observar que sob MFCQ os multi-plicadores do tipo Fritz John são multiplicadores de Lagrange (λ0 > 0).

A desvantagem da condição anterior é que ela depende do conjunto de multi-plicadores de Lagrange, enquanto na prática, tipicamente, temos um candidatox à solução e um candidato λ ao multiplicador associado a x. Idealmente gosta-ríamos de definir condições de segunda ordem que possam ser verificadas nestasituação. Observe que sob SMFCQ, ou seja, assumindo a unicidade dos multi-plicadores de Lagrange associados a uma solução x∗, o teorema anterior diz quex∗ satisfaz a condição necessária de segunda ordem da Definição 3.1.

Teorema 3.4 Suponha que x∗ ∈ Ω é um minimizador local que satisfaz SMFCQ.Logo o único multiplicador de Lagrange λ ∈ Rm+r, λi ≥ 0, i ∈ A(x∗) associadoa x∗ é tal que a condição necessária (forte) de segunda ordem é satisfeita.

Nosso objetivo é obter uma versão do teorema anterior com hipóteses menosrestritivas. Uma primeira tentativa é utilizar MFCQ, mas o exemplo abaixodescrito em [13] (originalmente proposto em [15]) mostra que existem problemas


que cumprem MFCQ na solução, onde a condição necessária de otimalidade desegunda ordem não é satisfeita em nenhum multiplicador:

Minimizar x3,x3 ≥ (x1, x2)TQk(x1, x2), k = 0, . . . , 4,

ondeQk =(

cos(kπ4 ) − sin(kπ4 )sin(kπ4 ) cos(kπ4 )

)(1 00 −2

)(cos(kπ4 ) sin(kπ4 )− sin(kπ4 ) cos(kπ4 )

), k =

0, . . . , 3.

O seguinte exemplo, mais simples, analisado na origem, é apresentado em[18].

Minimizar x3,

x3 ≥ 2√

3x1x2 − 2x22,

x3 ≥ x22 − 3x2

1,

x3 ≥ −2√

3x1x2 − 2x22.

Figura 3.1: MFCQ não garante a validade da condição de otimalidade de se-gunda ordem

A Figura 3.1 mostra as três superfícies definidas pelas expressões do ladodireito das desigualdades do problema. A região viável é formada por todos ospontos acima das três superfícies. Neste caso o gradiente da função objetivo naorigem coincide com o oposto dos três gradientes das restrições de modo que osmultiplicadores de Lagrange formam o simplex λ1+λ2+λ3 = 1, λ1, λ2, λ3 ≥ 0. Ocone crítico é o plano xy e o fato que a condição de segunda ordem não é satisfeita

34 G. Haeser

em um mesmo multiplicador se traduz no fato que qualquer combinação convexadas funções que definem as três superfícies é decrescente ao longo de algumadireção do cone crítico.

Frente a isto e de acordo com a Figura 2.1, as únicas condições de qualificaçãoque conhecemos que poderiam garantir a validade da condição de segunda ordemsão CRCQ e RCRCQ. De fato, em [6], o resultado é provado sob CRCQ e em [9],observamos que os resultados de [6] também garantem a validade da condiçãode segunda ordem sob RCRCQ. É interessante notar que o resultado de [6]garante que a condição de segunda ordem é válida independente da escolha domultiplicador de Lagrange, o que simplifica a sua verificação prática.

Teorema 3.5 Suponha que x∗ ∈ Ω é um minimizador local que satisfaz RCRCQ.Então qualquer multiplicador de Lagrange λ ∈ Rm+r, λi ≥ 0, i ∈ A(x∗) associ-ado a x∗ é tal que a condição necessária (forte) de segunda ordem é satisfeita.

Para provar este resultado vamos utilizar uma variação do Teorema do PostoConstante ([49], Teorema 2.9) descrita abaixo:

Teorema 3.6 (Posto Constante, [32]) Seja hi(x), i ∈ K uma família fi-nita de funções de classe Ck, k ≥ 1, hi : Rn → Rm tais que o posto de∇hi(y), i ∈ K é constante para todo y em uma vizinhança de x. Então existeum difeomorfismo local de classe Ck, φ : U → V , com U e V vizinhanças dex tal que φ(x) = x, ∇φ(x) é a matriz identidade e hi(φ−1(x + d)) é constantepara todo d com x+ d ∈ V tal que ∇hi(x)Td = 0, i ∈ K.

Lema 3.7 ([6]) Assuma que x ∈ Ω satisfaz RCRCQ. Então para cada d talque ∇fi(x)Td = 0, i = 1, . . . ,m, ∇fi(x)Td ≤ 0, i ∈ A(x) existe um função demesma classe que as fi’s, ξ : (−ε, ε) → Rn, ε > 0 com ξ(0) = x, ξ′(0) = d eξ(t) ∈ Ω para t ∈ [0, ε). Além disso, se ∇fi(x)Td = 0 temos fi(ξ(t)) = 0 paratodo t ∈ (−ε, ε).

Prova: Fixado d nas condições do enunciado, defina K = i ∈ 1, . . . ,m+r | ∇fi(x)Td = 0. Como vale RCRCQ podemos usar o Teorema do PostoConstante com a família hi := fi, i ∈ K, obtendo um difeomorfismo φ com aspropriedades mencionadas. Definimos ξ(t) = φ−1(x+ td) para todo t em algumintervalo aberto contendo a origem. Utilizando a expansão de Taylor para φ−1

temos ξ′(0) = limt→0ξ(t)−xt = d.

Assim, se ∇fi(x)Td = 0 temos fi(ξ(t)) = fi(φ−1(x+ td)) = fi(φ−1(x)) = 0.Para mostrar que ξ(t) ∈ Ω para t ≥ 0 basta observar que se ∇fi(x)Td < 0

temos fi(ξ(t)) = t∇fi(x)Td + o(t), o(t)t → 0, logo fi(ξ(t)) < 0 para t suficiente-mente pequeno. Além disso, se i 6∈ A(x), reduzindo possivelmente o intervalotemos claramente fi(ξ(t)) < 0.

Prova (Teorema 3.5): Assuma que x∗ ∈ Ω satisfaz RCRCQ e seja λ ∈Rm+r com λi ≥ 0, i ∈ A(x∗) qualquer multiplicador de Lagrange associado a x∗


(o fato de RCRCQ ser uma condição de qualificação garante que o conjunto dosmultiplicadores de Lagrange é não vazio). Seja d ∈ CS(x). Então

∇fi(x∗)Td = 0, i ∈ 0, 1, . . . ,m ∪ i ∈ m+ 1, . . . ,m+ r | λi > 0,∇fi(x∗)Td ≤ 0, i ∈ i ∈ m+ 1, . . . ,m+ r | λi = 0.

Definimos φ(t) = f0(ξ(t)), onde ξ : (−ε, ε) → Rn é obtida aplicando o Lema3.7. Já que ξ(t) é viável para t ≥ 0 e ξ(0) = x∗ temos que t∗ = 0 é umminimizador local de φ(t), t ≥ 0. Logo, φ′′(0) ≥ 0. Como ξ′(0) = d temosφ′′(0) = dT∇2f0(x∗)d+∇f0(x)Tξ′′(0) ≥ 0.

Sendo fi(ξ(t)) = 0 para todo t e i ∈ 1, . . . ,m ∪ i ∈ m+ 1, . . . ,m+ r |λi > 0 temos

R(t) =m+r∑i=1

λifi(ξ(t)) = 0,−ε < t < ε.

Assim,

R′′(0) = dT(m+r∑i=1

λi∇2fi(x∗))d+ (m+r∑i=1

λi∇fi(x∗))Tξ′′(0) = 0.

Logo, φ′′(0) + R′′(0) = dT(∇f0(x∗) +∑m+ri=1 λi∇fi(x∗))d ≥ 0 e a condição de

otimalidade de segunda ordem é satisfeita.

Podemos considerar uma versão mais fraca de RCRCQ, a saber, exigindoposto constante apenas para o conjunto de todos os gradientes de restriçõesativas ∇fi(x)m+r

i=1 . Esta condição é denominada condição de posto constantefraca (weak constant rank, WCR [12]) e embora não seja uma condição de qua-lificação (de fato, considere o problema de minimizar f0(x) := −x1, sujeito af1(x) := x2 − x2

1 = 0, f2(x) := −x1 ≤ 0, f3(x) = x2 ≤ 0, a solução x∗ = (0, 0)não satisfaz KKT, mas o posto de ∇fi(x)3i=1 é constante em uma vizinhançada origem), é possível mostrar que sob WCR, caso existam multiplicadores deLagrange, eles devem satisfazer a chamada condição de otimalidade necessáriafraca de segunda ordem.

Definição 3.8 Dizemos que o ponto KKT x ∈ Ω, A(x) = m + 1, . . . ,m + rsatisfaz a condição necessária fraca de otimalidade de segunda ordem associadaao multiplicador de Lagrange λ (associado a x) quando

dT

(∇2f0(x) +

m+r∑i=1

λi∇2fi(x))d ≥ 0,∀d ∈ CW (x),

ondeCW (x) = d ∈ Rn | ∇fi(x)Td = 0, i = 0, . . . ,m+ r

é o cone crítico fraco.

36 G. Haeser

Teorema 3.9 ([6]) Se x∗ ∈ Ω é um minimizador local que cumpre KKT e valeWCR, então para qualquer multiplicador de Lagrange, x∗ satisfaz a condiçãofraca de otimalidade de segunda ordem.

Prova: Basta observar que o Teorema do Posto Constante pode ser aplicadoobtendo uma curva viável ξ(t) com fi(ξ(t)) = 0, i = 1, . . . ,m+r e a prova seguecomo no Teorema 3.5.

Note que o cone crítico fraco é um subespaço vetorial contido no cone críticoforte. Conforme comentaremos na próxima seção, a versão fraca do teorema desegunda ordem é mais interessante do ponto de vista de aplicações. Observe queos cones críticos coincidem se vale a complementaridade estrita, isto é, se existeum multiplicador de Lagrange que não se anula em nenhum índice de restriçãode desigualdade ativa.

É interessante observar que o exemplo de Anitescu/Arutyunov apresentadomostra também que apenas sob MFCQ, nem mesmo a condição de otimalidadefraca de segunda ordem é satisfeita. Sendo assim, é frequente na literatura atentativa de assumir MFCQ e alguma outra condição com o objetivo de obtercondições de otimalidade de segunda ordem (fracas ou fortes). O inconvenientedesta abordagem é que, tipicamente, não é possível mostrar que a condição valepara todos os multiplicadores, mas sim que existe um multiplicador de Lagrangeque cumpre a condição. Um primeiro exemplo, apresentado no Teorema 3.4, éa condição SMFCQ que garante a condição forte para o único multiplicadorde Lagrange existente. Em [12] é provado que sob MFCQ+WCR a condiçãode otimalidade fraca de segunda ordem é satisfeita para algum multiplicador.Embora este resultado seja mais fraco que o do Teorema 3.9, em [12] é mos-trado que nestas condições, um algoritmo do tipo Lagrangiano Aumentado gerauma sequência cujos pontos limites satisfazem a condição necessária fraca desegunda ordem. Em [18] é provado que existe um multiplicador de Lagrangeque cumpre a condição forte de segunda ordem se vale MFCQ e o problemapossui duas ou menos variáveis, ou, duas ou menos restrições de desigualdadeestão ativas na solução. Em [19] é provada a existência de um multiplicadorde Lagrange que cumpre a condição forte de segunda ordem sob MFCQ e seo conjunto de multiplicadores de Lagrange é um segmento de reta, além disso,assume-se que existe no máximo um índice i0 de restrição de desigualdade ativatal que a componente i0 de qualquer multiplicador de Lagrange é sempre nula.Os autores conjecturam que a última condição não é necessária. Além disso,os autores mostram que se a deficiência do posto dos gradientes das restriçõesde igualdade e desigualdade ativas é no máximo 1, então o conjunto de multi-plicadores de Lagrange é um segmento de reta (possivelmente ilimitado). Em[20] é mostrado que sob MFCQ e assumindo que o problema é convexo (con-dição de Slater), existe um multiplicador de Lagrange que cumpre a condiçãoforte de segunda ordem. Em [12] conjectura-se que existe um multiplicador deLagrange que cumpre a condição fraca de segunda ordem sob MFCQ e desdeque o aumento do posto em uma vizinhança do ponto esteja limitado em no


máximo 1. Outros resultados de segunda ordem (envolvendo condições sobre asderivadas segundas das restrições) são obtidos em [21, 14, 16]. Resultados desegunda ordem para problemas em dimensão infinita podem ser obtidos em [22]e resultado para problemas multi-objetivo em [38, 39].

A seguir descrevemos os resultados de [2].

Consideremos Ω = x | fi(x) = 0, i = 1, . . . ,m, fi(x) ≤ 0, i = m+1, . . . ,m+p o conjunto viável do problema original e, fixado x∗ ∈ Ω com A(x∗) = m+1, . . . ,m + r, definimos o conjunto viável auxiliar Ω′ = x | fi(x) = 0, i =1, . . . ,m + r. Note que x∗ ∈ Ω′ mas não existe, em geral, uma relação deinclusão entre Ω e Ω′. É claro que a condição de posto constante fraco (WCR)independe se consideramos x∗ ∈ Ω ou x∗ ∈ Ω′. Vamos mostrar que WCRimplica que vale Abadie para Ω′. Nas definições 1.1 e 2.1 vamos denotar o conetangente por TΩ(x∗) e o cone linearizado por LΩ(x∗) e vamos considerar estescones definidos em Ω e Ω′.

Teorema 3.10 Se x∗ ∈ Ω satisfaz WCR, então x∗ satisfaz a condição de Abadiepara as restrições de igualdade fi(x) = 0, i = 1, . . . ,m+ r.

Prova: Seja 0 6= d ∈ LΩ′ , isto é, ∇fi(x∗)Td = 0, i = 1, . . . ,m + r. Como naprova do Lema 3.7 e Teorema 3.9, podemos aplicar o Teorema do Posto Cons-tante para construir uma curva ξ : (−ε, ε)→ Ω′, ε > 0 com ξ(0) = x∗, ξ′(0) = d.Em particular, d = limt→0+

ξ(t)−x∗t . Assim, sendo ξ′(0) 6= 0, podemos reduzir ε

se necessário para que ξ(t) 6= x∗. Logo ξ(t)−x∗‖ξ(t)−x∗‖ = ξ(t)−x∗

tt

‖ξ(t)−x∗‖ →d‖d‖ para

t→ 0+, o que mostra que d ∈ TΩ′ .

É importante observar que, como WCR não é uma condição de qualificação,o fato de valer Abadie para Ω′ não é uma condição de qualificação para x∗ ∈ Ω.Vamos provar que a condição de Abadie para Ω′ garante que qualquer multipli-cador de Lagrange (caso existam) satisfaz a condição fraca de segunda ordem.Este resultado generaliza o Teorema 3.9. Para isto, provamos primeiramente olema abaixo:

Lema 3.11 Seja x∗ ∈ Ω um minimizador local, λ ∈ Rm+r um multiplicador deLagrange associado a x∗. Então

dT

(∇2f0(x∗) +

m+r∑i=1

λi∇2fi(x∗))d ≥ 0,

para todo d nulo ou tal que existe xk → x∗ satisfazendo xk−x∗‖xk−x∗‖ →

d‖d‖ e, para

todo i = 1, . . . ,m+p com λi > 0 vale fi(xk) = o(‖xk−x∗‖2). (Em particular, acondição é satisfeita quando fi(xk) = 0, i ∈ 1, . . . ,m ∪ i ∈ A(x∗) | λi > 0.)

38 G. Haeser

Prova: Temos L(xk, λ) = f0(xk) +∑m+ri=1 λifi(xk) = f0(xk) + o(‖xk − x∗‖2),

assim, sendo x∗ um minimizador local e xk viável, temos

0 ≤ f0(xk)− f0(x∗)= L(xk, λ)− L(x∗, λ) + o(‖xk − x∗‖2)

= ∇xL(x∗, λ)T(xk − x∗) + 12(xk − x∗)T∇2

xxL(xk, λ)(xk − x∗) + o(‖xk − x∗‖2)

= 12(xk − x∗)T∇2

xxL(xk, λ, µ)(xk − x∗) + o(‖xk − x∗‖2),

onde xk está no segmento de reta entre x∗ e xk. Assim, dividindo por ‖xk−x∗‖2e tomando o limite em k temos dT∇L2

xx(x∗, λ)d ≥ 0.

Note que o conjunto de direções do lema acima é um cone contido no conetangente.

Teorema 3.12 Seja x∗ ∈ Ω um minimizador local e assuma que a condição deAbadie é satisfeita em x∗ considerando as restrições fi(x) = 0, i = 1, . . . ,m +r. Então a condição de otimalidade fraca de segunda ordem é satisfeita paraqualquer multiplicador de Lagrange associado a x∗ (caso existam).

Prova: Note que CW (x∗) = LΩ′(x∗), além disso, a hipótese garante que estescones coincidem com TΩ′(x∗), que por sua vez coincide com o cone de direçõesdado no Lema 3.11 e o resultado segue.

Quando o conjunto viável possui apenas igualdades, isto é, Ω = Ω′ comA(x∗) = ∅, a hipótese do Teorema 3.12 se traduz para a condição de qualificaçãode Abadie, assim, além de garantir a existência de multiplicadores de Lagrange,todos os multiplicadores satisfazem a condição de segunda ordem (no caso semdesigualdades o cone crítico forte coincide com o cone fraco e as condições fortee fraca são equivalentes).

Corolário 3.13 Assuma que o conjunto viável possui apenas restrições de igual-dade e x∗ ∈ Ω é um minimizador local que satisfaz a condição de Abadie. Então,x∗ é um ponto KKT e todos os multiplicadores de Lagrange associados a x∗ sa-tisfazem a condição de otimalidade (forte) de segunda ordem.

A seguir vamos provar um resultado a respeito da condição de otimalidadeforte de segunda ordem no conjunto viável Ω com igualdades e desigualdades.A hipótese será uma condição do tipo Abadie para um subconjunto fixo dasrestrições tratado como igualdades. Para identificar este subconjunto especialde restrições, consideramos algumas definições e lemas abaixo:

Definição 3.14 Seja x ∈ Ω um ponto KKT. Definimos A0(x) o conjunto deíndices i de restrições de desigualdade ativas em x tais que λi = 0 para qualquermultiplicador de Lagrange associado a x. O conjunto A+(x) = A(x)\A0(x) é oconjunto de índices i de restrições de desigualdade ativas em x tais que λi > 0para algum multiplicador de Lagrange associado a x.


Sendo x ∈ Ω um ponto KKT, para cada i ∈ A+(x) existe um multiplicador

de Lagrange λi ∈ Rm+r associado a x tal que λii > 0, assim, λ =∑

i∈A+(x)λi

|A+(x)| éum multiplicador de Lagrange associado a x tal que λi > 0 para todo i ∈ A+(x).Portanto o cone crítico forte pode ser descrito como

CS(x) = d ∈ Rn | ∇fi(x)Td = 0, i ∈ 1, . . . ,m∪A+(x);∇fi(x)Td ≤ 0, i ∈ A0(x).

O lema a seguir caracteriza o conjunto A0(x).

Lema 3.15 Se x ∈ Ω é um ponto KKT, então

A0(x) = i ∈ A(x∗) | ∃d ∈ CS(x),∇fi(x)Td < 0.

Prova: Seja j ∈ A0(x) ⊂ A(x). Então o problema de otimização linear abaixoé viável e possui valor ótimo nulo:

Maximizarλ λj ,

Sujeito a∑m+ri=1 λi∇fi(x) = −∇f0(x),

λi ≥ 0, i ∈ A(x).

Segue do teorema de dualidade forte para otimização linear que o problema dualabaixo também é viável e com o mesmo valor ótimo:

Minimizard ∇f0(x)Td,Sujeito a ∇fi(x)Td = 0, i = 1, . . . ,m,

∇fi(x)Td ≤ 0, i ∈ A(x)\j,∇fj(x)Td ≤ −1.

A solução d deste problema satisfaz as restrições e é tal que ∇f0(x)Td = 0,logo d ∈ CS(x) e ∇fj(x)Td < 0, o que mostra que A0(x) ⊂ i ∈ A(x∗) | ∃d ∈CS(x),∇fi(x)Td < 0. A inclusão recíproca é óbvia.

Corolário 3.16 Seja x ∈ Ω um ponto KKT. Então existe d ∈ CS(x) tal que

∇fi(x)Td = 0, i ∈ 1, . . . ,m ∪A+(x),∇fi(x)Td < 0, i ∈ A0(x).

Prova: Basta somar os vetores dados pelo Lema 3.15 para cada i ∈ A0(x).

O teorema a seguir mostra que a condição forte de segunda ordem é satisfeitapara qualquer multiplicador de Lagrange (caso existam) quando a condição deAbadie é satisfeita considerando as restrições em A+(x) como igualdades.

Teorema 3.17 Seja x∗ ∈ Ω um minimizador local e assuma que a condição deAbadie é satisfeita em x∗ considerando as restrições

Ω+ = x | fi(x) = 0, i ∈ 1, . . . ,m ∪A+(x∗); fi(x) ≤ 0, i ∈ A0(x∗).

Então a condição de otimalidade forte de segunda ordem é satisfeita para qual-quer multiplicador de Lagrange associado a x∗ (caso existam).

40 G. Haeser

Prova: Seja 0 6= d ∈ CS(x∗), isto é, ∇fi(x∗)Td = 0, i ∈ 1, . . . ,m ∪ A+(x∗) e∇fi(x∗)Td ≤ 0, i ∈ A0(x∗). Logo, por hipótese, segue que d ∈ TΩ+(x∗). Ou seja,existe xk → x∗, fi(xk) = 0, i ∈ 1, . . . ,m ∪ A+(x∗), fi(xk) ≤ 0, i ∈ A0(x∗) talque xk−x∗

‖xk−x∗‖ →d‖d‖ . Do Lema 3.11 segue que dT∇2

xxL(x∗, λ)d ≥ 0 para qualquermultiplicador de Lagrange λ associado a x∗.

A seguir mostramos que o Teorema 3.17 generaliza o Teorema 3.5.

Teorema 3.18 Se x∗ ∈ Ω satisfaz RCRCQ, então x∗ satisfaz a condição deAbadie para o conjunto de restrições fi(x) = 0, i ∈ 1, . . . ,m∪A+(x∗); fi(x) ≤0, i ∈ A0(x∗).

Prova: É uma adaptação da prova do Teorema 3.10.

Note que a definição do conjunto Ω+ só faz sentido quando x∗ é um pontoKKT. Neste caso, a hipótese do Teorema 3.17 é uma versão mais restrita dacondição de Abadie para Ω, já que ela é satisfeita quando LΩ+(x∗) ⊂ TΩ+(x∗),sendo que CS(x∗) = LΩ+(x∗) = LΩ(x∗) e TΩ+(x∗) ⊂ TΩ(x∗). Vamos mostrarque a hipótese do Teorema 3.17 pode ser reformulada para desprezarmos asrestrições em A0(x∗) na definição do cone tangente.

Teorema 3.19 Se x∗ é um minimizador local, então

CS(x∗) ⊂ TΩ+(x∗)⇔ CS(x∗) ⊂ TF+(x∗),

onde F+ = x | fi(x) = 0, i ∈ 1, . . . ,m ∪A+(x∗).

Prova: Sendo Ω+ ⊂ F+, a implicação direta é imediata. Seja 0 6= d ∈ CS(x∗)e assuma sem perda de generalidade que ‖d‖ = 1. Seja h ∈ CS(x∗) dado peloCorolário 3.16 tal que ∇fi(x∗)Th = 0, i ∈ 1, . . . ,m ∪ A+(x∗) e ∇fi(x∗)Th <

0, i ∈ A0(x∗) e defina dk = d+ 1k dk

‖d+ 1k dk‖ , segue que dk ∈ CS(x∗) com ∇fi(x∗)Tdk =

0, i ∈ 1, . . . ,m ∪A+(x∗) e ∇fi(x∗)Tdk < 0, i ∈ A0(x∗) para todo k.A hipótese garante que dk ∈ TF+(x∗), isto é, existe x` → x∗ com fi(x`) =

0, i ∈ 1, . . . ,m ∪ A+(x∗) tal que x`−x∗‖x`−x∗‖ → dk. Mostraremos que fi(x`) <

0, i ∈ A0(x∗) para ` suficientemente grande. De fato, para i ∈ A0(x∗) temosfi(x`) = ∇fi(x`)(x` − x∗) para algum x` entre x∗ e x`, já que fi(x∗) = 0.Assim, como ∇fi(x`) → ∇fi(x∗), x`−x∗

‖x`−x∗‖ → dk e ∇fi(x∗)Tdk < 0 segue quefi(x`) < 0 para ` suficientemente grande, e portanto dk ∈ TΩ+(x∗). Comodk → d e TΩ+(x∗) é fechado, segue que d ∈ TΩ+(x∗).

Em [20] é apresentado um resultado similar ao Teorema 3.17.

Teorema 3.20 Fixado um ponto KKT x∗ ∈ Ω, e fixado um multiplicador deLagrange λ ∈ Rm+r associado a x∗, definimos o conjunto de restrições

Ωλ =x | fi(x) = 0, i ∈ 1, . . . ,m ∪ i ∈ A(x∗) | λi > 0;

fi(x) ≤ 0, i ∈ i ∈ A(x∗) | λi = 0

.


Se a condição de Abadie é satisfeita em x∗ com relação a Ωλ, então λ satisfaza condição de otimalidade forte de segunda ordem.

Prova: A demonstração é feita exatamente como na prova do Teorema 3.17.

Observamos que independente de λ, LΩλ(x∗) = CS(x∗) e que Ω+ ⊂ Ωλ.O Teorema 3.20 garante que se vale Abadie para Ωλ, então vale a condição desegunda ordem para este multiplicador λ e para todos os outros λ′ tais queΩλ ⊂ Ωλ′ , ou seja, se o conjunto de índices de multiplicadores positivos de λcontém o conjunto de índices de multiplicadores positivos de λ′. Se λ é tomadocom λi > 0 para todo i ∈ A+(x∗) e a condição do Teorema 3.20 é satisfeita,então Ωλ ⊂ Ωλ′ para qualquer multiplicador de Lagrange λ′ associado a x∗ ecomo Ωλ = Ω+, a consequência é a mesma do Teorema 3.17.

Observamos ainda que se não estamos interessados em obter uma condiçãode segunda ordem para todos os multiplicadores, é possível que a condição doTeorema 3.20 seja satisfeita para algum multiplicador, mas não para todos. Defato, considere o problema

Minimizar x2,Sujeito a f1(x) := −x2

1 − x2 ≤ 0,f2(x) := −x2 ≤ 0,f3(x) := x1 ≤ 0

na solução x∗ = (0, 0). Temos que os multiplicadores são da forma λ1 ≥ 0, λ2 ≥0, λ1 + λ2 = 1, λ3 = 0. Segue que A+(x∗) = 1, 2 e A0(x∗) = 3. O conecrítico é dado por CS(x∗) = d | d1 ≤ 0, d2 = 0. Considerando um multipli-cador de Lagrange com o número máximo de entradas positivas, por exemplo,λ1 = λ2 = 1

2 , λ3 = 0 temos Ωλ = Ω+ = (0, 0), e portanto o cone tangente aeste conjunto não contém CS(x∗). Entretanto, considerando µ = (0, 1, 0) temosΩµ = x | x1 ≤ 0, x2 = 0 e portanto CS(x∗) ⊂ TΩµ(x∗) e podemos garantir avalidade da condição de otimalidade forte de segunda ordem apenas para µ.

Em [2] mostramos também que se um minimizador local x∗ ∈ Ω satisfazMFCQ e para todo I ⊂ 1, . . . ,m∪A+(x∗) com cardinalidade um a menos que1, . . . ,m∪A+(x∗) vale que ∇fi(x)i∈I tem posto constante em torno de x∗,então a condição fraca de segunda ordem vale para pelo menos um multiplicadorde Lagrange associado a x∗. Além disso, se A0(x∗) tem no máximo um índice,então vale a condição forte de segunda ordem para pelo menos um multiplicadorde Lagrange.

3.2 Condições sequenciais de segunda ordemEm [30], é considerado o problema quadrático em R4 de minimizar f0(x) :=

12x

THx, sujeito a x ≥ 0, onde H = I − 32zzT

‖z‖2 e z = e− 4e1, sendo e o vetor de1’s e e1 o primeiro vetor da base canônica. Para qualquer sequência de parâme-tro de barreira µk → 0+, definimos as funções bk(x) = f0(x)− µk

∑4i=1 log(xi)

42 G. Haeser

(barreira logarítmica). Observamos que xk = √µke é um minimizador localestrito do problema de minimizar bk(x), sujeito a x > 0 que satisfaz a condiçãosuficiente de segunda ordem. Como esperado, xk converge para zero, um pontoestacionário, entretanto, a condição de otimalidade forte de segunda ordem nãoé satisfeita já que eT

1He1 < 0. Este exemplo mostra que, na prática, não seespera que um algoritmo razoável tenha garantia de gerar uma sequência cu-jos pontos limites satisfazem a condição forte de segunda ordem. De fato, amera verificação da condição forte de segunda ordem é um problema NP-difícil[43]. Por estes motivos, em se tratando de algoritmos práticos, a condição deotimalidade de segunda ordem de interesse é a condição fraca. Há diversos algo-ritmos na literatura que com pequenas modificações tem convergência global apontos estacionários de segunda ordem: Lagrangiano aumentado, programaçãoquadrática sequencial, pontos interiores, regiões de confiança, entre outros.

Nesta sessão vamos definir um análogo de segunda ordem para a condiçãosequencial de otimalidade AKKT e vamos mostrar a relação desta condição comcondições de otimalidade pontuais de segunda ordem. Em particular, estamosinteressados em condições de qualificação (CQ2) tais que

WSONC ou não-CQ2

é uma condição de otimalidade, onde WSONC (weak second order necessaryoptimality condition) é a condição necessária de otimalidade fraca de segundaordem.

Definição 3.21 Dizemos que x ∈ Ω é um ponto Aproximadamente Estacio-nário de Segunda Ordem (AKKT2) se existem sequências xk → x, λk ⊂Rm+r, λki ≥ 0, i = m + 1, . . . ,m + r, θk ⊂ Rm+r, θki ≥ 0, i = 1, . . . ,m + r,δk ≥ 0, δk → 0+ tais que

∇xL(xk, λk) = ∇f0(xk) +m+r∑i=1

λki∇fi(xk)→ 0,

∇2xxL(xk, λk) +

m+r∑i=1

θki∇fi(xk)∇fi(xk)T −δkId,

para k suficientemente grande, onde A B significa que a matriz A − B ésemidefinida positiva e Id é a matriz identidade.

Vamos mostrar que AKKT2 é uma condição de otimalidade (sequencial),isto é, se x∗ ∈ Ω é um minimizador local, então x∗ satisfaz AKKT2. Para isso,vamos utilizar o lema abaixo de [12]:

Lema 3.22 Se f : Rn → R, gi : Rn → R, i = 1, . . . , p admitem segundaderivada contínua na vizinhança de x∗, onde x∗ é um minimizador local deF (x) = f(x) + 1

2∑pi=1 gi(x)2

+, sendo gi(x)+ = max0, gi(x), então H(x) =∇2f(x) +

∑pi=1 gi(x)+∇2gi(x) +

∑i|gi(x∗)≥0∇gi(x)∇gi(x)T é semidefinida po-

sitiva em x∗.


Prova: Defina F (x) = f(x)+ 12∑i|gi(x∗)≥0 gi(x)2. Note que F (x∗) = F (x∗),

∇F (x∗) = ∇F (x∗) e que F é duas vezes continuamente diferenciável em x∗

sendo ∇2F (x∗) = H(x∗). Sendo F (x) ≤ F (x), suponha que H(x∗) não é semi-definida positiva. Então x∗ não é um minimizador local de F . Logo existe umasequência xk → x∗ com F (xk) ≤ F (xk) < F (x∗) = F (x∗), o que contradiz adefinição de x∗.

Teorema 3.23 Se x∗ ∈ Ω é um minimizador local, entao x∗ satisfaz AKKT2.

Prova: Consideramos uma construção análoga à prova do Teorema 2.6, a saber,vamos aplicar o método de penalidade externa ao problema:

Minimizar f0(x) + 14‖x− x

∗‖4,Sujeito a fi(x) = 0, i = 1, . . . ,m,

fi(x) ≤ 0, i = m+ 1, . . . ,m+ p,‖x− x∗‖2 ≤ δ,

.

obtendo uma sequência xk → x∗ definida como uma solução global de mini-mizar F (x) := f0(x)+ 1

4‖x−x∗‖4 +ρk(

∑mi=1 fi(x)2 +

∑m+pi=m+1 fi(x)2

+), sujeito a‖x− x∗‖2 ≤ δ. Sendo ‖xk − x∗‖2 < δ para k suficientemente grande, temos quexk é um minimizador local irrestrito de F (x) e portanto pelo Lema 3.22 temos:

∇f0(xk) +m∑i=1

2ρkfi(xk)∇fi(xk) +m+p∑i=m+1

2ρkfi(xk)+∇fi(xk) + ‖xk − x∗‖3(xk − x∗) = 0,

∇2f0(xk) +m∑i=1

2ρkfi(xk)∇2fi(xk) +m+p∑i=m+1

2ρkfi(xk)+∇2fi(xk) +m∑i=1

2ρk∇fi(xk)∇fi(xk)T

+m+p∑

i=m+1|fi(xk)≥0

2ρk∇fi(xk)∇fi(xk)T + 2(xk − x∗)(xk − x∗)T + 3‖xk − x∗‖2Id 0.

Definindo λki = 2ρkfi(xk), i = 1, . . . ,m;λki = 2ρkfi(xk)+, i = m+1, . . . ,m+p; θki = 2ρk, i ∈ 1, . . . ,m ∪ i ∈ m + 1, . . . ,m + p | fi(xk) ≥ 0; θki = 0, i ∈i ∈ m+ 1, . . . ,m + p | fi(xk) < 0; δk = 3‖xk − x∗‖2 notemos que λki = 0 eθki = 0 para i = m+r+1, . . . ,m+p, além disso, δk → 0 e 2(xk−x∗)(xk−x∗)T 0,portanto, x∗ satisfaz AKKT2.

Em [12] um algoritmo de Lagrangiano aumentado de segunda ordem é cons-truído com convergência global para a condição de otimalidade WSONC ounão-CQ2 onde a condição de qualificação CQ2 usada é MFCQ + WCR. Mos-traremos que AKKT2 é mais forte que WSONC ou não-(MFCQ+WCR) e queo algoritmo de Lagrangiano aumentado de segunda ordem, entre outros, gerasequências AKKT2. Um fato principal é o lema abaixo de [12]:Lema 3.24 Se x ∈ Ω satisfaz WCR, então para todo d ∈ CW (x) e para todasequência xk → x, existe sequência dk → d tal que ∇fi(xk)Tdk = 0, i =1, . . . ,m+ r para k suficientemente grande.

44 G. Haeser

Prova: Seja I ⊂ 1, . . . ,m + r tal que ∇fi(x)i∈I seja uma base paraspan∇fi(x)m+r

i=1 . Como x satisfaz WCR, ∇fi(y)i∈I é uma base para span∇fi(y)m+ri=1

se y está suficientemente próximo de x. Definimos a matriz∇fI(x) sendo∇fi(x)sua i-ésima coluna, i ∈ I. Definindo dk = [Id−∇fI(xk)(∇fI(xk)T∇fI(xk))−1∇fI(xk)T]d,a projeção de d no espaço ortogonal às colunas de ∇fI(xk), temos que dk estábem definido para k suficientemente grande e ∇fi(xk)Tdk = 0, i = 1, . . . ,m+ r.Tomando o limite, pela continuidade das funções temos dk → [Id−∇fI(x)(∇fI(x)T∇fI(x))−1∇fI(x)T]d,a projeção de d em CW (x), que coincide com d já que d ∈ CW (x).

Teorema 3.25 Seja x ∈ Ω tal que vale AKKT2. Se MFCQ e WCR valemem x, então existe um multiplicador de Lagrange associado a x que satisfaz acondição de otimalidade fraca de segunda ordem.

Prova: Da definição de AKKT2 existem sequências xk → x, λk ⊂ Rm+r, λki ≥0, i = m+ 1, . . . ,m+ r, θk ⊂ Rm+r, θki ≥ 0, i = 1, . . . ,m+ r, δk ≥ 0, δk → 0+

tais queεk := ∇xL(xk, λk)→ 0,

Mk := ∇2xxL(xk, λk) +

m+r∑i=1

θki∇fi(xk)∇fi(xk)T −δkId.

A sequência λk é limitada, caso contrário, tomando o limite em uma sub-sequência para εk

‖λk‖ teríamos uma contradição com MFCQ. Vamos tomar umasubsequência tal que λk → λ, λi ≥ 0, i ∈ A(x∗). O limite εk → 0 mostra que λé um multiplicador de Lagrange associado a x. Seja d ∈ CW (x∗) e tome dk → ddado pelo Lema 3.24. Segue que

(dk)TMkdk = (dk)T∇2

xxL(xk, λk)dk +m+r∑i=1

θki (∇fi(xk)Tdk)2 ≥ −δk‖dk‖2,

e portanto (dk)T∇2xxL(xk, λk)dk ≥ −δk‖dk‖2. Tomando o limite em k temos

dT∇2xxL(x, λ)d ≥ 0.

Vamos mostrar que o algoritmo de Lagrangiano aumentado de segunda or-dem [12, 3] gera sequências AKKT2. Em [8] mostramos que o algoritmo SQPregularizado [28], de regiões de confiança [25], entre outros, também geramsequências AKKT2.

Como o lagrangiano aumentado Lρ não é duas vezes diferenciável nos pontosem que fi(x)+ λi

ρ = 0, i = m+1, . . . ,m+p, definimos o simbolo ∇2 que coincide

com∇2 quando a função é duas vezes diferenciável e ∇2(

max

0, fi(x) + λiρ

)2:=

∇2(fi(x) + λi

ρ

)2se fi(x) + λi

ρ = 0, i = m + 1, . . . ,m + p. O algoritmo de La-grangiano aumentado de segunda ordem é o mesmo definido para o Teorema2.8 com a diferença que o Passo 1 é substituído por:


Passo 1’ (minimização): Encontre umminimizador aproximado xk de Lρk(x, λk),isto é,

‖∇Lρk(xk, λk)‖ ≤ εk e ∇2Lρk(xk, λk) −εkId.

Teorema 3.26 Assuma que a sequência xk gerada pelo algoritmo de Lagran-giano aumentado de segunda ordem admite um ponto limite viável x. Então xé um ponto AKKT2.

Prova: O fato que x satisfaz AKKT foi demonstrado no Teorema 2.8. De fato

‖∇f0(xk) +m+p∑i=1


onde λki = λki + ρkfi(xk), i = 1, . . . ,m; λki = max0, λki + ρkfi(xk), i = m +1, . . . ,m+r, λki = 0, i = m+r+1, . . . ,m+p. Pelo Passo 1’ do algoritmo temos:

∇2L(xk, λk)+ρkm∑i=1∇fi(xk)∇fi(xk)T+ρk

m+p∑fi(xk)+

λkiρk≥0,i=m+1

∇fi(xk)∇fi(xk)T εkId.

Com argumento análogo ao do Teorema 2.8 verificamos que o índice do segundosomatório varia em A(x) e portanto vale AKKT2.

A seguir vamos provar um resultado análogo ao Teorema 2.12. Isto é, vamosdefinir uma condição de qualificação, chamada continuidade do cone de segundaordem, CCP2, mais fraca que MFCQ+WCR de modo que CCP2 em x∗ é equi-valente ao fato que para qualquer função objetivo f0 tal que AKKT2 é satisfeitaem x∗ implica que x∗ satisfaz a condição fraca de segunda ordem para algummultiplicador de Lagrange.

Fixado x∗ ∈ Ω, definimos para cada x ∈ Rn, o cone CW (x, x∗) = d ∈Rn | ∇fi(x)Td = 0, i ∈ 1, . . . ,m ∪ A(x∗). Note que CW (x∗, x∗) = CW (x∗).Definimos então o cone

KW2 (x) :=

⋃λ∈Rm×Rr+

(m+r∑i=1

λi∇fi(x), H) | H m+r∑i=1

λi∇2fi(x) em CW (x, x∗), H simétrica.

Note que a condição necessária fraca de segunda ordem (WSONC) é dadapor (−∇f0(x∗),−∇2f0(x∗)) ∈ KW

2 (x∗). Definimos abaixo a condição de qua-lificação CCP2 e mostramos que esta é a condição de qualificação mais fracapossível associada a AKKT2.

Definição 3.27 Dizemos que x∗ ∈ Ω satisfaz CCP2 se a multifunção KW2 (x)

é semi-contínua exteriormente em x∗, isto é, limsupx→x∗ KW2 (x) ⊂ KW

2 (x∗).

Teorema 3.28 x∗ ∈ Ω satisfaz CCP2, se e somente se, para qualquer fun-ção objetivo f0 tal que x∗ é AKKT2, vale que x∗ satisfaz WSONC para algummultiplicador de Lagrange.

46 G. Haeser

Prova: Veja [8].

Os Teoremas 3.25 e 3.28 garantem que CCP2 é mais fraca que MFCQ+WCR(de fato, considerando Ω = x | x ≤ 0,−x ≤ 0 ⊂ R verificamos que CCP2 éestritamente mais fraca que MFCQ+WCR). O teorema a seguir garante queCCP2 é mais fraca que RCRCQ. Este resultado, em particular, mostra quealgoritmos que geram sequências AKKT2 tem convergência global para pontosestacionários de segunda ordem sob RCRCQ.

Teorema 3.29 Se x∗ ∈ Ω satisfaz RCRCQ, então x∗ satisfaz CCP2.

Prova: Veja [8].

Considerando o conjunto viável Ω = (x1, x2) | x1 = 0,−x21 + x2 ≤ 0,−x2

1 +x3

2 ≤ 0 verificamos que a recíproca do Teorema 3.29 não é válida.A seguir mostramos a relação entre as condições de qualificação apresenta-

das.

LICQ

CRCQ

RCRCQMFCQ+WCR

CCP2 ∀f0(·),AKKT2 ⇒ WSONC

Figura 3.2: Relação entre as condições de qualificação apresentadas.

Capítulo 4

Conclusões

Em geral, um algoritmo de primeira ordem gera uma sequência xk de ite-randos cujos pontos limites satisfazem uma condição de otimalidade pontual dotipo KKT ou não-CQ, para alguma condição de qualificação (CQ). Esta condi-ção não fornece naturalmente um critério de parada para o algoritmo, pois elasó pode ser verificada no limite. Descrevemos a teoria de condições sequenciaisde otimalidade, em particular, a condição AKKT, que justifica critérios práticosde parada utilizados por diversos algoritmos. O desenvolvimento desta teoriapermite a prova de convergência global de algoritmos a pontos KKT sob condi-ções de qualificação mais fracas do que as usuais. O mesmo pode ser feito paraalgoritmos de segunda ordem. Com a teoria de segunda ordem desenvolvidaprovamos que a convergência global de algoritmos de segunda ordem pode serobtida sob condições de qualificação mais fracas, em particular, sob a condiçãode posto constante. Como trabalho futuro pretendemos generalizar a teoria de-senvolvida para problemas de otimização de outra natureza, como otimizaçãosemi-definida. Outra questão relevante de pesquisa está relacionada ao problemade medir a distância entre um iterando e uma solução do problema quando umalgoritmos para satisfazendo AKKT com uma tolerância ε > 0 pequena.

47

48 G. Haeser

Bibliografia

[1] J.M. Abadie. On the Kuhn-Tucker theorem. In J.M. Abadie, editor, Non-linear Programming, pages 21–36. John Wiley, 1967.

[2] R. Andreani, R. Behling, G. Haeser, and P.J.S. Silva. On second orderoptimality conditions for nonlinear optimization. 2014. submitted.

[3] R. Andreani, E. G. Birgin, J. M. Martinez, and M. L. Schuverdt. Second-order negative-curvature methods for box-constrained and general constrai-ned optimization. Computational Optimization and Applications, 45:209–236, 2010.

[4] R. Andreani, E.G. Birgin, J.M. Martínez, and M.L. Schuverdt. On aug-mented lagrangian methods with general lower–level constraints. SIAMJournal on Optimization, 18:1286–1309, 2007.

[5] R. Andreani, E.G. Birgin, J.M. Martínez, and M.L. Schuverdt. Augmentedlagrangian methods under the constant positive linear dependence cons-traint qualification. Mathematical Programming, 112:5–32, 2008.

[6] R. Andreani, C. E. Echagüe, and M. L. Schuverdt. Constant-Rank Condi-tion and Second-Order Constraint Qualification. Journal of OptimizationTheory and Applications, 146(2):255–266, February 2010.

[7] R. Andreani, G. Haeser, and J.M. Martínez. On sequential optimalityconditions for smooth constrained optimization. Optimization, 60(5):627–641, 2011.

[8] R. Andreani, G. Haeser, A. Ramos, and P.J.S. Silva. On second-order se-quential optimality conditions for nonlinear optimization and applications.2015. submitted.

[9] R. Andreani, G. Haeser, M.L. Schuverdt, and P.J.S. Silva. A relaxed cons-tant positive linear dependence constraint qualification and applications.Mathematical Programming, 135:255–273, 2012.

[10] R. Andreani, G. Haeser, M.L. Schuverdt, and P.J.S. Silva. Two new weakconstraint qualifications and applications. SIAM Journal on Optimization,22(3):1109–1135, 2012.

49

50 G. Haeser

[11] R. Andreani, J. M. Martinez, A. Ramos, and P.J.S. Silva. A cone-continuityconstraint qualification and algorithmic consequences. Optimization On-line, February, 2015.

[12] R. Andreani, J. M. Martínez, and M. L. Schuverdt. On second-order opti-mality conditions for nonlinear programming. Optimization, 56(5-6):529–542, 2007.

[13] M. Anitescu. Degenerate nonlinear programming with a quadratic growthcondition. SIAM Journal on Optimization, 10(4):1116–1135, 2000.

[14] A. V. Arutyunov. Smooth abnormal problems in extremum theory andanalysis. Russian Math. Surveys, 67(3):403–457, 2012.

[15] A.V. Arutyunov. Perturbations of extremal problems with constraintsand necessary optimality conditions. Journal of Soviet Mathematics,54(6):1342–1400, 1991.

[16] E.R. Avakov, A.V. Arutyunov, and A.F. Izmailov. Necessary conditions foran extremum in a mathematical programming problem. Proceedings of theSteklov Institute of Mathematics, 256(1):2–25, 2007.

[17] D. Azé. A characterization of the Lagrange-Karush-Kuhn-Tucker property.Optimization Online, December, 2014.

[18] A. Baccari. On the Classical Necessary Second-Order Optimality Condi-tions. Journal of Optimization Theory and Applications, 123(1):213–221,October 2004.

[19] A. Baccari and A. Trad. On the Classical Necessary Second-Order Opti-mality Conditions in the Presence of Equality and Inequality Constraints.SIAM Journal on Optimization, 15(2):394–408, January 2005.

[20] M.S. Bazaraa, H.D. Sherali, and C.M. Shetty. Nonlinear Programming:Theory and Algorithms. Wiley, third edition, 2006.

[21] A. Ben-Tal. Second-order and related extremality conditions in nonli-near programming. Journal of Optimization Theory and Applications,31(2):143–165, 1980.

[22] A. Ben-Tal and J. Zowe. A unified theory of first and second order con-ditions for extremum problems in topological vector spaces. In MoniqueGuignard, editor, Optimality and Stability in Mathematical Programming,volume 19 of Mathematical Programming Studies, pages 39–76. SpringerBerlin Heidelberg, 1982.

[23] J.F. Bonnans and A. Shapiro. Perturbation Analysis of Optimization Pro-blems. Springer, 2000.


[24] L. Chen and D. Goldfarb. Interior-point `2-penalty methods for nonlinearprogramming with strong global convergence properties. Mathematical Pro-gramming, 108:1–26, 2006.

[25] J. E. Dennis and L. N. Vicente. On the convergence theory of trust-region-based algorithms for equality-constrained optimization. SIAM Journal ofOptimization, 7(4):927–950, 1997.

[26] A. Fischer and A. Friedlander. A new line search inexact restoration ap-proach for nonlinear programming. Computational Optimization and Ap-plications, 46(2):333–346, 2010.

[27] J. Gauvin. A necessary and sufficient regularity condition to have boun-ded multipliers in nonconvex programming. Mathematical Programming,12:136–138, 1977.

[28] P. E. Gill, V. Kungurtsev, and D. P. Robinson. A regularized SQP methodwith convergence to second-order optimal points. Optimization Online,2013.

[29] F.J. Gould and J.W. Tolle. A necessary and sufficient qualification forconstrained optimization. SIAM Journal on Applied Mathematics, 20:164–172, 1969.

[30] N. I. M. Gould and P. L. Toint. A note on the convergence of barrieralgorithms to second-order necessary points. Mathematical Programming,85(2):433–438, June 1999.

[31] M. Guignard. Generalized Kuhn-Tucker conditions for mathematical pro-gramming problems in Banach space. SIAM Journal on Control, 7:232–241,1969.

[32] R. Janin. Directional derivative of the marginal function in nonlinear pro-gramming. Mathematical Programming Study, 21:110–126, 1984.

[33] F. John. Extremum problems with inequalities as subsidiary conditions.In K.O. Friedrichs et al., editor, Studies and Essays, Courant AnniversaryVolume, pages 187–204. Wiley/Interscience, 1948.

[34] W. Karush. Minima of functions of several variables with inequalities asside constraints. Master’s thesis, Dept. of Mathematics, Univ. of Chicago,1939.

[35] H.W. Kuhn and A.W. Tucker. Nonlinear programming. In J. Neyman,editor, Proceedings of the Second Berkeley Symposium on MathematicalStatistics and Probability, pages 481–492. University of California Press,1951.

[36] J. Kyparisis. On uniqueness of Kuhn-Tucker multipliers in nonlinear pro-gramming. Mathematical Programming, 32:242–246, 1985.

52 G. Haeser

[37] Shu Lu. Implications of the constant rank constraint qualification. Mathe-matical Programming, 126(2):365–392, 2011.

[38] M. C. Maciel, S. A. Santos, and G. N. Sottosanto. On second-order opti-mality conditions for vector optimization. Journal of Optimization Theoryand Applications, 149(2):332–351, 2011.

[39] M. C. Maciel, S. A. Santos, and G. N. Sottosanto. On second-order opti-mality conditions for vector optimization: Addendum. Journal of Optimi-zation Theory and Applications, pages 1–6, 2012.

[40] O.L. Mangasarian and S. Fromovitz. The Fritz John optimality conditionsin the presence of equality and inequality constraints. Journal of Mathe-matical Analysis and Applications, 17:37–47, 1967.

[41] J. M. Martínez and E. A. Pilotta. Inexact restoration methods for nonlinearprogramming: advances and perspectives. In L.Q. Qi, K.L. Teo, and X.Q.Yang, editors, Optimization and Control with applications, pages 271–292.Springer, 2005.

[42] L. Minchenko and S. Stakhovski. Parametric Nonlinear Programming Pro-blems under the Relaxed Constant Rank Condition. SIAM Journal onOptimization, 21(1):314–332, 2011.

[43] K. G. Murty and S. N. Kabadi. Some np-complete problems in quadraticand nonlinear programming. Mathematical Programming, 39(2):117–129,1987.

[44] E. R. Panier and A. L. Tits. On combining feasibility, descent and super-linear convergence in inequality constrained optimization. MathematicalProgramming, 59(1-3):261–276, March 1993.

[45] L. Qi and Z. Wei. On the constant positive linear dependence conditionand its applications to SQP methods. SIAM Journal on Optimization,10(4):963–981, 2000.

[46] A. Ramos. Tópicos em condições de otimalidade para otimização não linear.PhD thesis, IME-USP, Departamento de Matemática Aplicada, 2015.

[47] R.T. Rockafellar. Lagrange multipliers and optimality. SIAM Review,35(2):183–238, 1993.

[48] R.T. Rockafellar and R. J-B Wets. Variational Analysis. Springer, 2009.

[49] M. Spivak. A Comprehensive Introduction to Differential Geometry, vo-lume 1. Publish or Perish, third edition, 1999.

[50] G. Wachsmuth. On LICQ and the uniqueness of Lagrange multipliers.Operations Research Letters, 41(1):78 – 80, 2013.

Documents

Condições de otimalidade de primeira e segunda ordem em