XXXV ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Perspectivas Globais para a Engenharia de Produção
Fortaleza, CE, Brasil, 13 a 16 de outubro de 2015.
ABORDAGEM PARA A SOLUÇÃO DE
DESIGUALDADES VARIACIONAIS: A
FUNÇÃO GAP
SARA MEIRA MOUTTA RABELO (UESC)
[email protected]
gudelia g. morales de arica (UENF)
[email protected]
O trabalho apresenta uma descrição sobre a função de mérito ou de
decisão, chamada função gap, utilizada no cálculo de soluções de modelos
definidos por Problemas de Desigualdades Variacionais (PDV). A
resolução se baseia no uso dos métodos da Programação Matemática,
definindo um modelo de otimização equivalente ao (PDV).
Palavras-chave: desigualdades variacionais, otimização, função gap
XXXV ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Perspectivas Globais para a Engenharia de Produção
Fortaleza, CE, Brasil, 13 a 16 de outubro de 2015.
1. Introdução
Em Programação Matemática, que consiste de uma variada coleção de métodos para a resolução
de problemas de otimização (minimização ou maximização) de funções f: Rn  R reais de
variável vetorial, onde se aplicam os conceitos: pontos críticos, multiplicadores de Lagrange e
direções de descida (subida). Essa função que se deseja minimizar (maximizar) recebe diferentes
nomes nas aplicações, pois fornece um indicador ou critério de decrescimento (crescimento).
Assim, se encontra na literatura definida como função de mérito, função de decisão e comumente
em programação matemática como função objetivo.
Este trabalho apresenta uma relação de conceitos e definições de cálculo diferencial de várias
variáveis ligadas ao estudo da Programação Matemática, fazendo uma descrição da função de
mérito chamada função gap, utilizada no cálculo de soluções de modelos definidos por Problemas
de Desigualdades Variacionais (PDV).
A possibilidade de uso de uma função gap para resolver um PDV é de grande valia, visto que
nem sempre os PDV podem ser facilmente resolvidos. Entretanto, ao reformular o PDV,
utilizando uma função gap, obtém-se um problema de otimização, cujo conjunto solução é
exatamente igual ao conjunto solução do PDV. Sendo assim, este trabalho busca desenvolver
alternativas de resolução de problemas de otimização que podem ser representados por um PDV,
reformulando este PDV como um problema de otimização equivalente através de uma função
gap.
A estrutura do trabalho é a seguinte: Na seção 2 apresenta-se uma introdução ao estudo de
desigualdades variacionais. Na seção 3 apresenta-se um estudo sobre a função de mérito chamada
função gap, suas propriedades e um exemplo numérico no qual se aplica funções gap para o
cálculo de soluções de modelos definidos por Problemas de Desigualdades Variacionais (PDV).
Na seção 4 apresentam-se algumas conclusões sobre o tema abordado.
Este trabalho usa algumas definições matemáticas como desigualdade de Young-Fenchel, função
indicadora Ic(x) e função conjugada Ic*(y) que são definidas em Auchmuty (1989).
2
XXXV ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Perspectivas Globais para a Engenharia de Produção
Fortaleza, CE, Brasil, 13 a 16 de outubro de 2015.
2. Desigualdades variacionais
Historicamente, Hartman e Stampacchia (1966) (apud Trujillo (2003)) introduziram a teoria das
desigualdades variacionais como uma ferramenta para o estudo de problemas mecânicos
formulados usando equações diferenciais parciais. Entretanto, um dos eventos que marcou o
início da teoria das desigualdades variacionais aconteceu na década de 80, quando Dafermos
(1980) reconheceu que uma condição de equilíbrio em redes de transporte, formulada por Smith
(1979), apresentava a estrutura de uma desigualdade variacional. Daí em diante, a teoria das
desigualdades variacionais foi amplamente utilizada para o estudo das condições de equilíbrio em
problemas de diferentes naturezas, tais como: economia, ciência administrativa/pesquisa
operacional, mecânica, física, engenharia do tráfego e na teoria de controle ótimo.
Definição 1: Seja um conjunto C  Rn, não vazio, convexo e fechado, e F: C  Rn uma função
contínua dada. O problema de desigualdade variacional da aplicação F sobre C, denotado
PDV(F,C), é definido como:
Encontrar um vetor x  C que satisfaz F(x), (y - x)  ≥ 0,  y  C
(1)
Observar os seguintes casos quando C  Rn e F: C  Rn
 Se n = 1, a desigualdade variacional torna-se:
F(x)(y-x) ≥ 0.
Se n = 2, F = (F1, F2), a desigualdade variacional torna-se:
(F1(x), F2(x)),((y1 – x1), (y2 – x2))  ≥ 0 que é equivalente a
F1(x)(y1 – x1) + F2(x)(y2 – x2) ≥ 0
Se n não for explicitado, a desigualdade variacional se escreve, então:
(2)
 Geometricamente, a relação (1) diz que: deve-se encontrar um vetor x*  C tal que o
vetor F(x*), imagem da aplicação F em x*, forme um ângulo agudo com os vetores (x –
x*) para cada x  C.
Figura 1 - Interpretação geométrica do problema de desigualdade variacional
3
XXXV ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Perspectivas Globais para a Engenharia de Produção
Fortaleza, CE, Brasil, 13 a 16 de outubro de 2015.
Existem vários métodos para resolver um problema de desigualdade variacional, um deles obtémse reformulando o problema de desigualdade variacional como um problema de otimização
equivalente (neste caso, minimização), de apenas um nível, através de uma função associada. A
função objetivo do modelo de otimização associada ao PDV(F,C) é o indicador de decrescimento
(crescimento) em relação à proximidade do ponto solução do PDV(F, C). Assim, vai ser chamada
neste trabalho de função de mérito. A função de mérito associada ao PDV(F,C) em (1) foi
chamada de função gap (Hearn (1981), Auchmuty (1989), Morales (1997)).
Um caso particular do problema de desigualdade variacional é estabelecido, quando a função F é
o gradiente de alguma funcional f: Rn  R, convexa e diferenciável, isto é, F(x) = f(x). Neste
caso, o problema pode ser escrito como:
Encontrar x  C, tal que,  f(x),(y - x)  ≥ 0,  y  C.
(3)
Notar que a relação (3), sob as hipóteses acima indicadas para f, não é mais do que a condição
necessária e suficiente de otimalidade de primeira ordem.
3. Funções gap
Como um método alternativo para resolver problemas de desigualdades variacionais Auslender
(1976) (apud Trujillo (2003)) reformulou o problema de desigualdade variacional PDV (F, C)
apresentado em (1) como um problema equivalente de otimização. Para isto, foi utilizada uma
função de mérito, definida por:
G( x)  sup yC
F ( x), ( x  y)
(4)
Onde o conjunto C  Rn é um conjunto não vazio, convexo e fechado, e F: C  Rn é uma função
vetorial contínua dada. A função G(x) definida acima é chamada de função gap.
Se o conjunto C adicionalmente for limitado, pode-se reformular G(x) como:
G ( x)  max
yC
G ( x)   min
yC
F ( x), ( x  y )
(5)
F ( x), ( y  x)
4
XXXV ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Perspectivas Globais para a Engenharia de Produção
Fortaleza, CE, Brasil, 13 a 16 de outubro de 2015.
No caso particular onde F(x) =  f(x), para alguma f: Rn  R convexa e diferenciável a função
gap associada ao problema de desigualdade variacional PDV (F, C) em (3) é definida por:
G( x)  max f ( x), ( x  y )
(6)
yC
Em seguida será mostrada a propriedade mais útil, do ponto de vista computacional, da função
G(x) que é a de ser não negativa no conjunto C e ter o valor G(x) = 0 se, e somente se, y C
resolve o problema PDV (F, C) definido em (1). Assim a desigualdade variacional PDV (F, C)
pode ser reformulada como um problema de otimização equivalente onde será procurado o valor
mínimo igual a zero:
min
G ( x)
xC
(7)
Observação: na verdade a minimização, para a função gap em (6), é um problema min xC
maxyC f(x)T (x - y).
3.1 Propriedades da função gap
Seja C  Rn um conjunto não vazio, convexo e fechado, e F: C  Rn uma função contínua dada.
Considere a função : C  R  {} definida, Auchmuty (1989), por:
( x )  x, F ( x )  IC* ( F ( x ))
(8)
Procura-se minimizar  em C e encontrar o valor:
  inf ( x )
(9)
xC
Aplicando a desigualdade de Young para a função indicadora Ic(x) e substituindo o vetor y por –
F(x) na sua função conjugada Ic*(y), obtém-se:
IC (x) + I*C (–F(x)) ≥  x, –F(x)  para todo x em R n
IC (x) + I*C (–F(x)) -  x, –F(x)  ≥ 0
IC (x) + I*C (–F(x)) +  x, F(x)  ≥ 0
Da definição da função indicadora, IC (x) ≥ 0, logo:
( x )  x, F ( x )  IC* (F ( x ))  0
Portanto o valor ínfimo de , representado por , é:
  inf ( x )  0
xC
(10)
(11)
Observar que da definição da função conjugada da função indicadora Ic:
( x)  x, F ( x)  sup  z, F ( x)  I C ( z )
zR n
5
XXXV ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Perspectivas Globais para a Engenharia de Produção
Fortaleza, CE, Brasil, 13 a 16 de outubro de 2015.
Em particular, para z C, tem-se:
sup  z,F ( x)  I C ( z)  sup  z,F ( x)
zR
Então,
zR
n

n
( x)  x, F ( x)  sup  z, F ( x)

zR n
( x)  sup  x, F ( x)  z, F ( x)

zR n
( x)  sup  F ( x)( x  z ) 
zR n
Logo, pela relação
em (4), pode-se concluir que a função  tem condições de se chamar uma
função gap.
Agora, considere C  Rn um conjunto não vazio, convexo e fechado, f: Rn  R  {} uma
função convexa semi-contínua inferior, contínua e diferenciável numa vizinhança aberta de C.
Seja g: Rn  R  {} a extensão convexa da função f restrita a C sobre Rn definida por:
g(x) = f(x) + IC(x)
(12)
Seja h: C R  {} definida por:
h(x) = f(x) + g*( f(x) – F(x)) +  x, F(x) -  f(x) 
Queremos encontrar:
  inf h( x )
xC
(13)
(14)
Tomando a desigualdade de Young para g, temos:
g(x) + g*(y) ≥ x,y para todo x,y em R n
(15)
Substituindo g(x) por seu valor em (12), tem-se:
f(x) + IC(x)+ g*(y) - x,y ≥ 0
(16)
Tomando y =  f(x) – F(x) aplicado em (15)
f(x) + IC(x)+ g*( f(x) – F(x)) -  x,  f(x) – F(x)  ≥ 0
(17)
Para x  C, IC(x) ≥ 0. Logo:
h(x) = f(x) + g*( f(x) – F(x)) +  x, F(x)- f(x)  ≥ 0
(18)
  inf h( x )  0
(19)
xC
Note que quando f  0 a função h(x) torna-se igual à função (x).
Após as relações desenvolvidas de (12)-(19) podem ser formuladas as seguintes propriedades:
6
XXXV ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Perspectivas Globais para a Engenharia de Produção
Fortaleza, CE, Brasil, 13 a 16 de outubro de 2015.
Propriedade 1 - Seja C  Rn um conjunto não vazio, convexo e compacto, F: C  Rn uma função
contínua e  definida em (8). Então:
(i)
 é não negativa, semi-contínua inferior e limitada em C;
(ii)
 (x) = 0 somente se x é uma solução de (1);
(iii)
  inf ( x )  0 e existe um x* em C que minimiza  em C.
xC
Prova: ver Auchmuty (1989).
A propriedade a seguir relaxa a hipótese de compacidade do conjunto viável C.
Propriedade 2 - Seja C  Rn um conjunto não vazio, convexo e fechado, F:CRn uma função
contínua e  definida em (8). Então:
(i)
 é semi-contínua inferior e não negativa em C;
(ii)
 (x) = 0 se e somente se x é solução do PDV(F, C) definido em (1).
Prova: ver Auchmuty (1989).
Propriedade 3 – Seja C  Rn um conjunto não vazio, convexo e fechado; F: C  Rn uma função
contínua. Seja f : Rn  R  {} uma função convexa semi-contínua inferior que é
continuamente diferenciável numa vizinhança aberta de C e g(x), h(x) e  definidos em 12,13 e
14 respectivamente. Então:
(i)
h é não negativa e semi-contínua inferior em C;
(ii)
h (x) = 0 se e somente se x é uma solução de (1);
(iii)
Quando C é compacto, então  = 0 e h atinge seu ínfimo em C na solução do PDV(F,
C) definido em (1).
Prova: ver Auchmuty (1989).
4. Exemplo
Considere o seguinte problema:
Encontrar um x  C que satisfaz  2x, (y - x)  ≥ 0,  y  C
(20)
Onde C = [1,3].
A nossa proposta é mostrar que a solução deste PDV é igual à solução do problema:
7
XXXV ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Perspectivas Globais para a Engenharia de Produção
Fortaleza, CE, Brasil, 13 a 16 de outubro de 2015.
Min G(x)
s. a. x  C
(21)
Onde G(x) é uma função gap associada ao problema de desigualdade variacional (20).
Para resolver o PDV (F, C), precisamos encontrar x C tal que:
2x (y - x) ≥ 0, para todo y  [1,3],
2xy - 2x2 ≥ 0
2xy ≥ 2x2
Observação: Apesar de não ser necessário resolver esta desigualdade, não é difícil concluir que a
solução deste PDV (F, C) é x = 1.
A função gap associada a este problema de desigualdade variacional pode ser definida por:
G( x)  max 2 x, ( x  y )
yC
G( x)  max 2 x 2  2 xy
(22)
yC
Como foi visto, a solução do PDV (F, C) ocorre quando G(x) = 0; e o comportamento da função
gap é G(x) ≥ 0, então para achar a solução do PDV (F, C) basta fazer:

min max
xC
yC

2 x 2  2 xy 

(23)
A solução deste problema ocorre no ponto x=1 e y=1. Exatamente igual a solução do PDV.
5. Conclusão
Os Problemas de Desigualdades Variacionais (PDV) nem sempre podem ser facilmente
resolvidos, pois dependendo de qual seja a função F(x) os cálculos podem se tornar complicados.
Sendo assim, a aplicação da função gap na resolução destes problemas torna-se muito útil, visto
que toda a manipulação para utilizá-la faz com que o PDV se transforme em um problema de
otimização equivalente, cuja solução pode ser encontrada por algoritmos existentes.
Neste sentido, o estudo da função gap torna-se muito importante para ampliar as áreas de
aplicação na engenharia, economia e transporte, para as que poderão se encontrar soluções a PDV
utilizando os métodos de programação matemática que calculam soluções de modelos de
otimização de sua função gap associada. Este estudo integra a preparação em ferramentas que a
engenharia de produção precisará abordar para problemas de equilíbrio em redes ambientais, de
migração e de conhecimentos.
6. Referências Bibliográficas
8
XXXV ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Perspectivas Globais para a Engenharia de Produção
Fortaleza, CE, Brasil, 13 a 16 de outubro de 2015.
AUCHMUTY, G. Variational Principles for Variational Inequalities. Numerical Functional Analysis and
Optimization, Texas, nº 10, P. 863-874. 1989.
AUSLENDER, A. Optimization: méthodes numériques. Masson S. A. 120 Bd Saint-Germain, Paris 6. 1976.
DAFERMOS, S. C. Treffic Equilibrium and Variational inequalities. Transportation Science, nº 14, P. 42-54.
1980.
HARTMAN, P; STAMPACCHIA, G. On Some Nonlinear Elliptic Differential Functional Equations. Acta
Mathematica, nº 115, P. 153-188. 1966.
HEARN, D. W. The Gap Function of a Convex Program. Operations Research Letters, USA, P. 67-71. 1981.
MORALES, G. O problema de programação matemática com restrições generalizadas de Equilíbrio. Rio
de Janeiro: UFRJ, 1997. Tese (Doutorado) – Programa de Pós-Graduação em Engenharia de Sistemas de
Computação, Universidade Federal do Rio de Janeiro, Rio de Janeiro, 1997.
SMITH, M. J. The existence, uniqueness and stability of traffic equilibria. Transportation Research, 1979. P.
295-304.
TRUJILLO, C. E. V. Algoritmos de Descida baseados em Funções Gap para resolver Problemas
Variacionais Monótonos. Campos dos Goytacazes: UENF, 2003. 67p. Tese (Mestrado) – Programa de PósGraduação em Engenharia de Produção, Universidade Estadual do Norte Fluminense, Campos dos Goytacazes,
2003.
9