Tópicos em otimização com restrições lineares por Marina Andretta - Versão HTML

ATENÇÃO: Esta é apenas uma visualização em HTML e alguns elementos como links e números de página podem estar incorretos.
Faça o download do livro em PDF, ePub, Kindle para obter uma versão completa.

Tópicos em otimizaç˜

ao

com restriç˜

oes lineares

Marina Andretta

Tese apresentada

ao

Instituto de Matemática e Estat´ıstica

da

Universidade de S˜

ao Paulo

para

obtenc

¸˜

ao do t´ıtulo

de

Doutor em Ciências

Área de Concentraç˜

ao: Ciência da Computaç˜

ao

Orientador: Prof. Dr. Ernesto G. Birgin

Durante o desenvolvimento deste trabalho a autora recebeu aux´ılio financeiro do CNPq.

ao Paulo, agosto de 2008

Tópicos em otimizaç˜

ao

com restriç˜

oes lineares

Este exemplar corresponde à redaç˜

ao

final da tese devidamente corrigida

e defendida por Marina Andretta

e aprovada pela Comiss˜ao Julgadora.

Banca Examinadora:

Prof. Dr. Ernesto G. Birgin (orientador) - IME-USP.

Prof. Dr. Carlos Humes Jr - IME-USP.

Prof. Dr. José Mario Mart´ınez - IMECC-UNICAMP.

Prof. Dr. Nelson Maculan Filho - COPPE-UFRJ.

Prof. Dr. Marcos Raydan - UCV e USB, Venezuela.

Para minha m˜

ae e meu pai.

Agradecimentos

Ao professor Ernesto, pelas discuss˜

oes, conversas, idéias e paciência nestes anos de trabalho.

Ao professor José Mario Mart´ınez por idéias e sugest˜oes feitas ao longo do desenvolvimento deste trabalho.

Ao grupo de otimizaç˜

ao cont´ınua, ao pessoal da “salinha”, aos professores que tive, por

todo apoio, dicas e suporte técnico.

A toda minha fam´ıla, em especial à M´ıriam, Maira, Dina, Euler, Neto e Miguilim, por

tudo. E, claro, à minha m˜

ae e meu pai, que sempre me deram todo o apoio e aos quais dedico

este trabalho.

A todos os meus amigos, do IME e de outros lugares, pelo apoio, conversas, bagunças,

festas, pizzas e muito mais. N˜ao vou citar nomes para n˜

ao ser injusta com ninguém, mas

vocês sabem quem s˜

ao!

Resumo

Métodos do tipo Lagrangiano Aumentado s˜

ao muito utilizados para minimizaç˜

ao de funç˜

oes

sujeitas a restriç˜

oes gerais. Nestes métodos, podemos separar o conjunto de restriç˜

oes em

dois grupos: restriç˜

oes fáceis e restriç˜

oes dif´ıceis. Dizemos que uma restriç˜

ao é fácil se existe

um algoritmo dispon´ıvel e eficiente para resolver problemas restritos a este tipo de restriç˜

ao.

Caso contrário, dizemos que a restriç˜

ao é dif´ıcil. Métodos do tipo Lagrangiano aumentado

resolvem, a cada iteraç˜

ao, problemas sujeitos às restriç˜

oes fáceis, penalizando as restriç˜

oes

dif´ıceis.

Problemas de minimizaç˜

ao com restriç˜

oes lineares aparecem com freqüência, muitas vezes

como resultados da aproximaç˜

ao de problemas com restriç˜

oes gerais. Este tipo de problema

surge também como subproblema de métodos do tipo Lagrangiano aumentado. Assim, uma

implementaç˜

ao eficiente para resolver problemas com restriç˜

oes lineares é relevante para a

implementaç˜

ao eficiente de métodos para resoluç˜

ao de problemas de programaç˜

ao n˜

ao-linear.

Neste trabalho, começamos considerando fáceis as restriç˜

oes de caixa.

Introduzimos

Betra-esparso, uma vers˜

ao de Betra [3] para problemas de grande porte. Betra é um

método de restriç˜

oes ativas que utiliza regi˜

oes de confiança para minimizaç˜

ao em cada face e

gradiente espectral projetado para sair das faces. Utilizamos Betra (denso ou esparso) na

resoluç˜

ao dos subproblemas que surgem a cada iteraç˜

ao de Algencan (um método de La-

grangiano aumentado). Para decidir qual algoritmo utilizar para resolver cada subproblema,

desenvolvemos regras que escolhem um método para resolver o subproblema de acordo com

suas caracter´ısticas.

Em seguida, introduzimos dois algoritmos de restriç˜

oes ativas desenvolvidos para resol-

ver problemas com restriç˜

oes lineares (Betralin e Genlin). Estes algoritmos utilizam, a

cada iteraç˜

ao, o método do Gradiente Espectral Projetado Parcial quando decidem mudar

o conjunto de restriç˜

oes ativas. O método do Gradiente Espectral Projetado Parcial foi de-

senvolvido especialmente para este propósito. Neste método, as projeç˜

oes s˜

ao computadas

apenas em um subconjunto das restriç˜

oes, com o intuito de torná-las mais eficientes.

Por fim, tendo introduzido um método para minimizaç˜

ao com restriç˜

oes lineares, consi-

deramos como fáceis as restriç˜

oes lineares. Incorporamos Betralin e Genlin ao arcabouço

de Lagrangianos aumentados e verificamos experimentalmente a eficiência e eficácia destes

métodos que trabalham explicitamente com restriç˜

oes lineares e penalizam as demais.

Palavras-chave: minimizaç˜

ao com restriç˜

oes lineares, métodos de restriç˜

oes ativas, gradiente

espectral projetado, métodos de Lagrangiano aumentado, programaç˜

ao n˜

ao-linear.

Abstract

Augmented Lagrangian methods are widely used to solve general nonlinear programming

problems. In these methods, one can split the set of constraints in two groups: the set of easy and hard constraints. A constraint is called easy if there is an efficient method available to solve problems subject to that kind of constraint. Otherwise, the constraints are called hard.

Augmented Lagrangian methods solve, at each iteration, problems subject to the set of easy

constraints while penalizing the set of hard constraints.

Linearly constrained problems appear frequently, sometimes as a result of a linear appro-

ximation of a problem, sometimes as an augmented Lagrangian subproblem. Therefore, an

efficient method to solve linearly constrained problems is important for the implementation

of efficient methods to solve nonlinear programming problems.

In this thesis, we begin by considering box constraints as the set of easy constraints. We

introduce a version of Betra to solve large scale problems. Betra is an active-set method

that uses a trust-region strategy to work within the faces and spectral projected gradient to leave the faces. To solve each iteration’s subproblem of Algencan (an augmented Lagrangian

method) we use either the dense or the sparse version of Betra. We develope rules to decide

which box-constrained inner solver should be used at each augmented Lagrangian iteration

that considers the main characteristics of the problem to be solved.

Then, we introduce two active-set methods to solve linearly constrained problems (Betra-

lin and Genlin). These methods use Partial Spectral Projected Gradient method to change

the active set of constraints. The Partial Spectral Projected Gradient method was developed

specially for this purpose. It computes projections onto a subset of the linear constraints, aiming to make the projections more efficient.

At last, having introduced a linearly-constrained solver, we consider the set of linear

constraints as the set of easy constraints. We use Betralin and Genlin in the framework of

augmented Lagrangian methods and verify, using numerical experiments, the efficiency and

robustness of those methods that work with linear constraints and penalize the nonlinear

constraints.

Keywords: linearly-constrained methods, active-set methods, spectral projected gradient,

augmented Lagrangian methods, nonlinear programming.

Sumário

Introduç˜

ao

xiii

1 Lagrangiano aumentado com restriç˜

oes de caixa no n´ıvel inferior

1

1.1

Algoritmo interno: método de restriç˜

oes ativas para minimizaç˜

ao em caixas . .

4

1.2

Detalhes de implementaç˜

ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.3

Resultados numéricos

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.4

Conclus˜oes

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

2 Novo método para minimizaç˜

ao com restriç˜

oes lineares

39

2.1

Método de restriç˜

oes ativas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

2.2

Cálculo da projeç˜

ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

2.3

Método do Gradiente Espectral Projetado Parcial . . . . . . . . . . . . . . . . . 43

2.4

Algoritmos “irrestritos” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

2.5

Teoria de convergência . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

2.6

Detalhes de implementaç˜

ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

2.7

Resultados numéricos

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

2.8

Conclus˜oes

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

3 Lagrangiano aumentado com restriç˜

oes lineares no n´ıvel inferior

95

3.1

Resultados numéricos

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

3.2

Conclus˜oes

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

Conclus˜

oes e trabalhos futuros

113

A Gráfico de perfil de desempenho

115

Referências bibliográficas

117

xi

xii

Introduç˜

ao

Estamos interessados em resolver problemas de programaç˜ao n˜

ao-linear definidos da seguinte

forma:

Minimizar f (x)

sujeita a

h(x) = 0

(1)

g(x) ≤ 0

x ∈ Ω,

onde h : IRn → IRm, g : IRn → IRp, f : IRn → IR s˜ao suaves e Ω ∈ IRn é um conjunto de

restriç˜

oes fáceis. Quando dizemos que Ω é um conjunto de restriç˜

oes fáceis, queremos dizer

que existem métodos eficientes para resolver problemas restritos ao conjunto Ω.

Uma maneira de resolver o problema (1) é utilizar métodos do tipo Lagrangiano aumen-

tado. Nestes métodos, penalizamos as restriç˜

oes hi e gj e, a cada iteraç˜ao, resolvemos apro-

ximadamente um subproblema de minimizaç˜

ao de uma funç˜

ao de Lagrangiano aumentado

(neste trabalho, PHR [30, 43, 48]) restrita ao conjunto Ω.

Há várias vantagens no uso de métodos de Lagrangiano aumentado [7]. Algumas delas

ao:

1. Progresso na análise e implementaç˜

ao de métodos de otimizaç˜

ao eficientes para resolver

problemas simples produzem um efeito positivo quase imediato na eficiência e robustez

dos métodos de Lagrangiano aumentado correspondentes.

2. Minimizaç˜

ao global dos subproblemas implica em convergência a minimizadores globais

do método de Lagrangiano aumentado.

3. Em vários problemas práticos, a Hessiana do Lagrangiano é uma matriz estruturalmente

densa (ou seja, qualquer entrada pode ser diferente de zero para Hessianas calculadas em

diferentes pontos) mas geralmente esparsa (dado um ponto no dom´ınio, a Hessiana do

Lagrangiano neste ponto é esparsa). Métodos Newtonianos geralmente têm dificuldades

em problemas deste tipo, tanto em termos de memória como em termos de tempo

computacional, pois o padr˜ao de esparsidade muda a cada iteraç˜

ao. Esta dificuldade

é praticamente irrelevante para métodos do tipo Lagrangiano aumentado que utilizam

subalgoritmos que necessitam de pouca memória.

4. Independentemente da densidade da Hessiana do Lagrangiano, a estrutura do sistema

KKT pode ser muito ruim para fatoraç˜

oes esparsas. Este é um problema grave para

xiii

métodos Newtonianos, mas n˜

ao para boas implementaç˜

oes de métodos de Lagrangiano

aumentado baseados na formulaç˜

ao PHR.

5. Se o problema de programaç˜

ao n˜

ao-linear possui muitas restriç˜

oes de desigualdade, o

uso de variáveis de folga feito por métodos de pontos interiores (também usado em

[2, 18]) pode n˜

ao ser conveniente. Há várias maneiras de reduzir os efeitos causados por

muitas variáveis de folga, mas eles podem n˜

ao ser t˜

ao efetivos como n˜

ao usar variáveis de

folga. A desvantagem de n˜

ao usar variáveis de folga é a ausência de segundas derivadas

cont´ınuas da funç˜

ao de Lagrangiano aumentado. Em muitos casos, isto n˜

ao se mostra

um inconveniente na prática (veja [4]).

6. Problemas de grande porte têm a desvantagem óbvia em termos de necessidade de

armazenamento. Métodos do tipo Lagrangiano aumentado apresentam uma soluç˜

ao:

dados do problema podem ser computados apenas quando necessários, usados quando

preciso para os subproblemas, sem nenhum armazenamento. Isto n˜

ao é poss´ıvel quando

se usam métodos matriciais, independentemente da estratégia de esparsidade adotada.

7. Se, na soluç˜

ao do problema, n˜

ao valem condiç˜

oes de qualificaç˜

ao de restriç˜

ao fortes,

o desempenho de métodos Newtonianos podem ser fortemente afetados. Métodos de

Lagrangiano aumentado n˜

ao s˜

ao sens´ıveis a este tipo de desvantagem.

Algencan é uma implementaç˜

ao de um método de Lagrangiano aumentado com Ω =

{x ∈ IRn | ℓ ≤ x ≤ u}, que utiliza Gencan [8] para resolver os subproblemas de minimizaç˜ao

com restriç˜

oes de caixa. Em [3] foi introduzido um método (chamado Betra) para mini-

mizaç˜

ao em caixas, mais adequado para problemas de pequeno porte. Estamos interessados

em desenvolver uma vers˜

ao para grande porte de Betra e, ent˜

ao, desenvolver uma imple-

mentaç˜

ao de Algencan que utilize Betra, na vers˜

ao densa ou esparsa, ou Gencan como

subalgoritmo, o que for mais apropriado para o problema a ser resolvido. Desejamos também

criar regras para decidir qual algoritmo interno deve ser utilizado a cada iteraç˜

ao, baseadas

no número de variáveis, grau de esparsidade da matriz Hessiana do Lagrangiano aumentado,

etc.

Estamos interessados, também, em desenvolver um método de Lagrangiano aumentado,

baseado em Algencan, que considere Ω = {x ∈ IRn | Ax = b, Cx ≤ d, ℓ ≤ x ≤ u}, ou seja,

trabalhe explicitamente com restriç˜

oes lineares e de caixa e penalize as demais restriç˜

oes. Isso

porque restriç˜

oes lineares possuem uma estrutura conhecida e desejamos verificar se penalizá-

las ou n˜

ao torna o método de Lagrangiano aumentado mais eficiente e robusto.

Para o desenvolvimento deste novo método, que deixa as restriç˜

oes lineares no n´ıvel infe-

rior, é necessário desenvolver um método eficiente para minimizaç˜

ao com restriç˜

oes lineares.

Os princ´ıpios reitores do método para minimizaç˜

ao com restriç˜

oes lineares s˜

ao os seguintes:

1. Metodologia de pontos admiss´ıveis: no caso de restriç˜

oes lineares, consideramos que a

facilidade relativa de preservar a admissibilidade dos iterandos de um método sobre-

passa qualquer vantagem imaginável de sacrificar tal propriedade. Este é um princ´ıpio

norteador do desenvolvimento do método aqui preconizado.

2. Uso de estratégia de restriç˜

oes ativas: a regi˜

ao admiss´ıvel do problema se divide na-

turalmente no que chamamos faces. Uma face da regi˜

ao admiss´ıvel se caracteriza por

xiv

um conjunto dado de restriç˜

oes satisfeito estritamente e o conjunto complementar é

satisfeito de maneira n˜

ao-estrita. A regi˜

ao viável é a uni˜

ao disjunta de suas faces. Os

algoritmos de restriç˜

oes ativas, conceitualmente, visitam as diferentes faces da regi˜

ao e

as exploram, até que decidem abandoná-las.

3. Uso de estratégias de gradiente espectral projetado para o abandono de faces: dentro de

cada face, o algoritmo funciona como um minimizador sem restriç˜

oes. Pode continuar

funcionando desta maneira até que uma de duas possibilidades aconteça. Os iterandos

atingem uma face de dimens˜ao menor (na fronteira) ou chegam a um ponto t˜

ao bom,

dentro da face, que n˜

ao vale a pena continuar sua exploraç˜

ao. Neste caso, se um ponto

KKT do problema original ainda n˜

ao foi atingido, dizemos que a face corrente deve

ser abandonada. O abandono da face é um problema delicado porque, essencialmente,

comporta a resoluç˜

ao de um novo problema de otimizaç˜

ao, que pode ser relativamente

custoso.

O algoritmo interno é o encarregado de minimizar dentro de uma face dada. Uma face

se caracteriza por um conjunto de restriç˜

oes de igualdade, portanto o algoritmo interno mi-

nimiza a funç˜

ao, restrita a uma variedade afim. Dentre as estratégias existentes para este

objetivo, somos partidários daquelas baseadas no espaço nulo determinado pelas restriç˜

oes.

Isto significa que há de se determinar uma base do subespaço paralelo à variedade afim sob

consideraç˜

ao e reduzir o problema a um problema irrestrito, cujas variáveis s˜

ao os coeficientes

na base desse espaço nulo. Reduzido a esta situaç˜

ao, o problema pode ser de grande porte ou

ao, dependendo da dimens˜ao da variedade afim. Isso motiva o uso de diferentes algoritmos

internos, que dever˜

ao ser escolhidos e analisados.

Quando uma face está esgotada, ela deve ser abandonada. A maneira mais clássica de

abandonar uma face é a introduzida por Rosen em seu algoritmo clássico de gradiente proje-

tado:

(a) Considera-se que o esgotamento de uma face é dado pela anulaç˜

ao do gradiente reduzido

a ela.

(b) Verifica-se a condiç˜

ao KKT, ou seja, calculam-se os multiplicadores de Lagrange. Se

todos eles tem o sinal “correto” o ponto é KKT.

(c) Abandona-se uma restriç˜

ao para a qual o multiplicador de Lagrange tem o sinal incor-

reto.

Este procedimento ainda tem vigência quando algumas condiç˜

oes s˜

ao satisfeitas. O número

de restriç˜

oes ativas deve ser pequeno e as restriç˜

oes devem ser linearmente independentes. Em

geral, deve-se apelar a outros procedimentos mais eficazes. Com o procedimento de Rosen,

apenas uma restriç˜

ao é abandonada em cada iteraç˜

ao deste tipo, o que pode fazer o processo

de resolver o problema muito caro. Uma alternativa é definir um sistema de coordenadas

local pelo qual o problema do abandono fica reduzido a um problema local de minimizaç˜

ao

em caixa. Desta maneira, podem ser abandonadas muitas restriç˜

oes ao mesmo tempo. En-

tretanto, a existência de outras restriç˜

oes muito próximas às abandonadas (ou eventualmente

coincidentes, no caso degenerado) motiva a introduç˜

ao de outros procedimentos mais abran-

gentes. Uma possibilidade é usar o gradiente espectral projetado [11, 12] no conjunto total de restriç˜

oes ou em um subconjunto delas, aquelas satisfeitas com menos folga.

xv

Este trabalho está organizado da seguinte maneira: No Cap´ıtulo 1, apresentamos novas

vers˜

oes de Algencan, que utilizam Betra denso ou esparso como subalgoritmo. Introduzi-

mos regras para decidir qual algoritmo interno será utilizado em cada iteraç˜

ao de Lagrangiano

aumentado. Apresentamos detalhes da implementaç˜

ao de cada um dos métodos, resultados

numéricos comparando estes métodos entre si e com outros conhecidos para resoluç˜

ao de pro-

blemas de programaç˜

ao n˜

ao-linear. No Cap´ıtulo 2, apresentamos duas vers˜

oes de um novo

método de restriç˜

oes ativas para minimizaç˜

ao com restriç˜

oes lineares. Explicamos o emba-

samento teórico, mostramos a teoria de convergência do método, apresentamos resultados

numéricos comparando o desempenho das duas vers˜

oes entre si e com métodos conhecidos

que resolvem problemas com restriç˜

oes lineares. No Cap´ıtulo 3, apresentamos duas novas

vers˜

oes de Algencan, que utilizam os métodos do Cap´ıtulo 2 como subalgoritmos. Ou seja,

trabalham explicitamente com restriç˜

oes lineares e de caixa e penalizam as demais. Por fim,

apresentamos as conclus˜oes finais deste trabalho e idéias para trabalhos futuros.

xvi

index-17_1.png

index-17_2.png

index-17_3.png

Cap´ıtulo 1

Lagrangiano aumentado com

restriç˜

oes de caixa no n´ıvel inferior

Muitos problemas práticos podem ser escritos na forma

Minimizar f (x)

(1.1)

sujeita a

x ∈ Ω1 ∩ Ω2,

com Ω2 tal que subproblemas da forma

Minimizar F (x)

(1.2)

sujeita a

x ∈ Ω2

ao muito mais simples de resolver do que o problema (1.1). Ou seja, existem algoritmos

eficientes para resolver (1.2) que n˜

ao podem ser aplicados a (1.1).

Problemas da forma (1.1) podem ser resolvidos usando métodos de Lagrangiano aumen-

tado. Estes métodos penalizam as restriç˜

oes Ω1 e, a cada iteraç˜ao, resolvem um subproblema

do tipo (1.2). Considere o problema de programaç˜

ao n˜

ao-linear

Minimizar f (x)

sujeita a

h1(x) = 0

g1(x) ≤ 0

(1.3)

h2(x) = 0

g2(x) ≤ 0,

onde h1 : IRn → IRm1, g1 : IRn → IRp1, h2 : IRn → IRm2, g2 : IRn → IRp2, f : IRn → IR

ao suaves. Defina Ω1 = {x ∈ IRn | h1(x) = 0 e g1(x) ≤ 0} e Ω2 = {x ∈ IRn | h2(x) =

0 e g2(x) ≤ 0}. A mais popular e, provavelmente, mais eficiente funç˜ao de Lagrangiano

aumentado (veja [4]) é dada pela fórmula PHR (Powell-Hestenes-Rockafellar [30, 43, 48]):

ρ

m1

λ 2

p1

µ

2

L

i

i

ρ(x, λ, µ) = f (x) +

h

+

max 0, g

2

1i(x) + ρ

1i(x) + ρ

i=1

i=1

para todo x ∈ IRn, λ ∈ IRm1, µ ∈ IRp1

+ , ρ > 0.

1

index-18_1.png

Métodos de Lagrangiano aumentado que usam a formulaç˜

ao PHR para resolver o problema

(1.3) s˜

ao baseados na minimizaç˜

ao (aproximada) iterativa de Lρ com respeito a Ω2, seguida

da atualizaç˜

ao do parâmetro de penalidade ρ e dos multiplicadores de Lagrange λ e µ. Em [1],

foi introduzido um método de Lagrangiano aumentado usando a formulaç˜

ao PHR que n˜

ao usa

variáveis de folga e pode ter restriç˜

oes arbitrárias no conjunto de restriç˜

oes do n´ıvel inferior

Ω2. Convergência baseada nas condiç˜oes CPLD e a limitaç˜ao dos parâmetros de penalidade

foram provados em [1], dadas hipóteses razoáveis sobre o problema.

A forma geral do método de Lagrangiano aumentado baseado na formulaç˜

ao PHR é a

seguinte:

Algoritmo 1.1 (Método de Lagrangiano aumentado usando formulaç˜

ao PHR)

Sejam λmin < λmax, µmax > 0, γ > 1, 0 < τ < 1. Seja {εk} uma seqüência de números n˜ao negativos tal que limk→∞ εk = 0. Sejam λ1i ∈ [λmin, λmax], i = 1, . . . , m1, µ1i ∈ [0, µmax], i =

1, . . . , p1 e ρ1 > 0. Faça k ← 1.

Passo 1. Resoluç˜

ao do subproblema

Calcule xk ∈ IRn uma soluç˜ao aproximada de

Minimizar Lρ (x, λk, µk) sujeita a x ∈ Ω

k