14
III Seminário da Pós-graduação em Engenharia Elétrica UM MÉTODO PRIMAL-DUAL DE PONTOS INTERIORES APLICADO AO PROBLEMA DE DESPACHO ECONÔMICO COM PONTO DE VÁLVULA Diego Nunes da Silva Aluno do Programa de Pós-Graduação em Engenharia Elétrica Unesp Bauru Prof. Dr. Antonio Roberto Balbo Orientador Departamento de Matemática Unesp Bauru RESUMO Métodos de pontos interiores têm sido empregados com sucesso em diversos problemas reais, como problemas de fluxo de potência ótimo, em engenharia elétrica, bem como em problemas de despacho e pré-despacho de geração. Neste trabalho, é proposto um método de otimização determinístico híbrido para a resolução do Problema de Despacho Econômico com Ponto de Válvula (PDE-PV), que é um problema da área de sistemas de energia caracterizado pela não-diferenciabilidade e não-convexidade da função objetivo. Para tanto, apresenta-se um método primal-dual de pontos interiores, que utiliza a função lagrangiana barreira logarítmica modificada, associado a um aproximante baseado na função tangente hiperbólica para tratar as não-diferenciabilidades decorrentes de termos modulares presentes na função objetivo. Tendo em vista que o PDE-PV é um problema não-convexo, o método proposto ainda inclui uma estratégia de convergência global, variante de Levenberg- Marquardt, que reajusta a matriz dual normal caso esta não seja definida positiva, a fim de obter pontos de mínimo local. Cabe salientar que, devido às suas características, o PDE-PV comumente é resolvido através de algoritmos estocásticos, como os algoritmos genéticos e simulated annealing, os quais não possuem garantias de convergência, sendo quase inexistentes as abordagens determinísticas para o mesmo. O método apresentado é, então, validado em um problema-teste matemático e no caso de 3 geradores do PDE-PV. PALAVRAS-CHAVE: Pontos Interiores, Função Barreira Modificada, Despacho Econômico com Ponto de Válvula. 1 INTRODUÇÃO Nos últimos anos, o campo da programação matemática, e juntamente a ele a área de otimização, evoluiu de maneira significativa, permitindo a resolução de uma variedade cada vez maior de problemas, em especial aqueles para os quais a obtenção de soluções analíticas é inviável. Problemas de otimização podem apresentar diversas características, como não- linearidade, não-convexidade, não-diferenciabilidade e integralidade de variáveis, o que pode dificultar sua resolução. Desta forma, o desenvolvimento de métodos numéricos eficientes e com convergência satisfatória se tornou um importante campo de pesquisa. Quando problemas de otimização apresentam não-diferenciabilidades, métodos clássicos de otimização usualmente não podem ser aplicados diretamente, uma vez que estes se baseiam em informações relacionadas ao gradiente e matriz hessiana para determinar as direções de busca. Por este motivo, diante deste cenário, vários autores recorrem a algoritmos estocásticos e heurísticas para sua resolução, como os algoritmos genéticos, busca tabu e simulated annealing. Algoritmos estocásticos têm obtido sucesso na resolução de uma ampla

III Seminário da Pós-graduação em Engenharia Elétrica · energia caracterizado pela não-diferenciabilidade e não-convexidade da função objetivo. Para ... associado a um aproximante

  • Upload
    lecong

  • View
    220

  • Download
    0

Embed Size (px)

Citation preview

Page 1: III Seminário da Pós-graduação em Engenharia Elétrica · energia caracterizado pela não-diferenciabilidade e não-convexidade da função objetivo. Para ... associado a um aproximante

III Seminário da Pós-graduação em Engenharia Elétrica

UM MÉTODO PRIMAL-DUAL DE PONTOS INTERIORES APLICADO AO

PROBLEMA DE DESPACHO ECONÔMICO COM PONTO DE VÁLVULA

Diego Nunes da Silva

Aluno do Programa de Pós-Graduação em Engenharia Elétrica – Unesp – Bauru

Prof. Dr. Antonio Roberto Balbo

Orientador – Departamento de Matemática – Unesp – Bauru

RESUMO Métodos de pontos interiores têm sido empregados com sucesso em diversos

problemas reais, como problemas de fluxo de potência ótimo, em engenharia elétrica, bem

como em problemas de despacho e pré-despacho de geração. Neste trabalho, é proposto um

método de otimização determinístico híbrido para a resolução do Problema de Despacho

Econômico com Ponto de Válvula (PDE-PV), que é um problema da área de sistemas de

energia caracterizado pela não-diferenciabilidade e não-convexidade da função objetivo. Para

tanto, apresenta-se um método primal-dual de pontos interiores, que utiliza a função

lagrangiana barreira logarítmica modificada, associado a um aproximante baseado na função

tangente hiperbólica para tratar as não-diferenciabilidades decorrentes de termos modulares

presentes na função objetivo. Tendo em vista que o PDE-PV é um problema não-convexo, o

método proposto ainda inclui uma estratégia de convergência global, variante de Levenberg-

Marquardt, que reajusta a matriz dual normal caso esta não seja definida positiva, a fim de

obter pontos de mínimo local. Cabe salientar que, devido às suas características, o PDE-PV

comumente é resolvido através de algoritmos estocásticos, como os algoritmos genéticos e

simulated annealing, os quais não possuem garantias de convergência, sendo quase

inexistentes as abordagens determinísticas para o mesmo. O método apresentado é, então,

validado em um problema-teste matemático e no caso de 3 geradores do PDE-PV.

PALAVRAS-CHAVE: Pontos Interiores, Função Barreira Modificada, Despacho

Econômico com Ponto de Válvula.

1 INTRODUÇÃO

Nos últimos anos, o campo da programação matemática, e juntamente a ele a área de

otimização, evoluiu de maneira significativa, permitindo a resolução de uma variedade cada

vez maior de problemas, em especial aqueles para os quais a obtenção de soluções analíticas é

inviável. Problemas de otimização podem apresentar diversas características, como não-

linearidade, não-convexidade, não-diferenciabilidade e integralidade de variáveis, o que pode

dificultar sua resolução. Desta forma, o desenvolvimento de métodos numéricos eficientes e

com convergência satisfatória se tornou um importante campo de pesquisa.

Quando problemas de otimização apresentam não-diferenciabilidades, métodos

clássicos de otimização usualmente não podem ser aplicados diretamente, uma vez que estes

se baseiam em informações relacionadas ao gradiente e matriz hessiana para determinar as

direções de busca. Por este motivo, diante deste cenário, vários autores recorrem a algoritmos

estocásticos e heurísticas para sua resolução, como os algoritmos genéticos, busca tabu e

simulated annealing. Algoritmos estocásticos têm obtido sucesso na resolução de uma ampla

Page 2: III Seminário da Pós-graduação em Engenharia Elétrica · energia caracterizado pela não-diferenciabilidade e não-convexidade da função objetivo. Para ... associado a um aproximante

III Seminário da Pós-graduação em Engenharia Elétrica

gama de problemas. Sua desvantagem, contudo, é a inexistência de resultados que garantam

sua convergência, ao menos para um mínimo local, possibilitando apenas a obtenção de

soluções denominadas sub-ótimas.

No Brasil, a geração elétrica está sustentada quase que completamente na geração

hidráulica, que corresponde a cerca de 90% de toda energia elétrica produzida em território

nacional. Esta, porém, não é a realidade mundial, em que mais de 60% da geração de energia

elétrica é obtida através de termelétricas tradicionais. Assim, na engenharia elétrica, um

problema de otimização restrito e não-linear de grande relevância é o Problema de Despacho

Econômico (PDE). De acordo com STEINBERG E SMITH (1943), tal problema pode ser definido

como o processo de alocação ótima da demanda de energia elétrica entre as unidades

geradoras disponíveis, de modo que as restrições operacionais sejam cumpridas e o custo de

geração seja mínimo.

O PDE clássico é representado por um problema de otimização quadrático que,

sendo convexo, pode ser solucionado de modo eficiente por métodos de pontos interiores,

com garantias de obtenção do mínimo global. Entretanto, este modelo pode ser enriquecido,

de modo a considerar os efeitos dos pontos de válvula que estão associados a abertura de

válvulas de admissão em pontos operacionais específicos dos geradores. Este problema é

denominado Problema de Despacho Econômico com Ponto de Válvula (PDE-PV).

Diferentemente do PDE clássico, o PDE-PV possui em sua função objetivo termos modulares,

que o tornam um problema não-convexo e não-diferenciável em determinados pontos do

domínio.

Assim, tendo em vista sua importância, o PDE tem sido resolvido por diversos

métodos, visando otimizar o processo de alocação de potência ativa demandada. No trabalho

de SAMED (2004), casos do PDE clássico e do PDE-PV são resolvidos utilizando algoritmos

genéticos híbridos coevolutivos. O PDE clássico também é explorado no trabalho de BALBO

ET AL (2012). Já STANZANI (2012) soluciona o PDE clássico, considerando também o aspecto

ambiental presente no Problema de Despacho Ambiental. Para tanto, a autora admite uma

formulação multiobjetivo do problema e o resolve utilizando duas estratégias: o método da

soma ponderada e o método do -restrito.

Neste sentido, o objetivo deste trabalho é apresentar uma estratégia para tratamento

de problemas de otimização cuja função objetivo possua termos modulares, através de um

aproximante baseado na função tangente hiperbólica, de modo que um método clássico de

otimização, a saber, um método primal-dual previsor-corretor de pontos interiores barreira

logarítmica modificada, possa ser aplicado à sua resolução. O método de pontos interior aqui

apresentado e implementado se baseia no trabalho de PINHEIRO (2012), e inclui uma estratégia

de convergência global variante de Levenberg-Marquardt, que visa corrigir a matriz dual

normal caso esta não seja definida positiva.

2 O PROBLEMA DE DESPACHO ECONÔMICO COM PONTO DE VÁLVULA

(PDE-PV)

De acordo com STEINBERG E SMITH (1943), o Problema de Despacho Econômico

pode ser definido como o processo de alocação ótima da demanda de potência ativa entre as

unidades geradoras disponíveis, ao mesmo tempo em que se minimiza o custo dos

combustíveis empregados na geração termelétrica e as restrições operacionais do sistema são

respeitadas. No PDE clássico, estas restrições estão relacionadas essencialmente aos

limitantes de potência gerada para cada uma das unidades geradoras e à satisfação da

Page 3: III Seminário da Pós-graduação em Engenharia Elétrica · energia caracterizado pela não-diferenciabilidade e não-convexidade da função objetivo. Para ... associado a um aproximante

III Seminário da Pós-graduação em Engenharia Elétrica

demanda. Modelos mais complexos do PDE podem incluir outras restrições, como restrições

de segurança, relacionadas ao fluxo de potência nos ramos do sistema.

O PDE pode ser entendido como um subproblema do problema de Fluxo de Potência

Ótimo (FPO), proposto por CARPENTIER (1962). Contudo, a preocupação com os custos dos

combustíveis das usinas termelétricas antecede o trabalho de Carpentier, sendo que um dos

primeiros métodos utilizados para se resolver este problema foi o Carregamento por Ordem de

Mérito. Por este método, solicitava-se potência do gerador mais eficiente até que este

atingisse o limite de geração, então se passava para o próximo gerador mais eficiente. A falha

deste método para minimizar os custos residia no fato de que se desconsiderava que a

eficiência de uma unidade geradora é uma função da potência gerada.

Este método foi utilizado até a década de 30, quando o Critério dos Custos

Incrementais Iguais passou a produzir melhores resultados. O custo incremental, por sua vez,

considerava que a eficiência era função da potência gerada, e que o ponto de menor custo

seria aquele em que os custos incrementais das unidades geradoras é igual. Este critério

somente veio a ser comprovado matematicamente em 1943, por STEINBERG E SMITH (1943).

Entretanto, segundo BALBO ET AL (2012), do ponto de vista da otimização, este critério

somente assegura que o custo incremental (derivadas) das funções de custo das unidades

geradoras deve ser igual, se não há restrições ativas no ponto de operação ótimo, mas podem

ocorrer custos incrementais distintos caso alguma restrição inativa seja satisfeita por esse

ponto. Ressalta-se que, atualmente, este critério ainda é amplamente aplicado pelos

operadores de sistema de energia dos países em confronto com a vastidão de métodos já

desenvolvidos pelos pesquisadores dessa área, que possibilitariam a economia de custo e de

geração de energia para as empresas e consumidores, respectivamente.

2.1 Modelo matemático do PDE-PV

O PDE clássico pode ser formulado como um problema de otimização quadrático,

uma vez que a função custo de cada unidade geradora é modelada por polinômios de grau 2, e

a restrição de atendimento da demanda é linear. Matematicamente, ele é expresso por

(1)

em que é a função custo total das unidades geradoras, é o número de unidades

geradoras, é a função custo da -ésima unidade geradora, , e são os coeficientes

da função de custo da -ésima unidade geradora, é a potência ativa gerada pela -ésima

unidade, é a potência demandada, e são os limites operacionais inferior e

superior de saída da -ésima unidade geradora.

O modelo expresso por (1) pode ser estendido, de modo a incluir os efeitos dos

pontos de válvula, pois em grandes geradores com turbinas a vapor, pode existir um número

de válvulas de admissão, que são abertas sequencialmente para obter a saída da unidade.

Neste caso, a função custo da -ésima unidade geradora é expressa por

(2)

Page 4: III Seminário da Pós-graduação em Engenharia Elétrica · energia caracterizado pela não-diferenciabilidade e não-convexidade da função objetivo. Para ... associado a um aproximante

III Seminário da Pós-graduação em Engenharia Elétrica

Assim, o modelo matemático para o PDE-PV é dado por

(3)

A maior dificuldade para a resolução do PDE-PV pelos métodos de otimização

clássicos está relacionada ao termo modular que caracteriza o ponto de válvula na função

objetivo. Este termo é responsável por tornar não-convexa e não-diferenciável em

determinados pontos do domínio. A Figura 1 apresenta o comportamento da função custo de

um gerador, no caso do PDE (azul) e do PDE-PV (vermelho). Daí a razão deste problema ser,

usualmente, resolvido utilizando métodos heurísticos, como em SAMED (2004).

Figura 1 – Representação da função custo de uma unidade geradora

Neste sentido, o objetivo deste trabalho é apresentar uma estratégia para suavização

dos termos modulares em funções objetivo, de modo a obter uma função aproximada que seja

diferenciável e permita a utilização de métodos determinísticos de otimização.

3 O MÉTODO PREVISOR-CORRETOR PRIMAL-DUAL DE PONTOS

INTERIORES BARREIRA LOGARÍTMICA MODIFICADA

Nesta seção é apresentado o Método Previsor-Corretor Primal-Dual de Pontos

Interiores Barreira Logarítmica Modificada (MPCPDPIBLM) que foi implementado para a

obtenção dos resultados apresentados neste trabalho. Uma estratégia adotada com frequência

para facilitar o cálculo das direções no passo previsor é desconsiderar o parâmetro de barreira,

seguindo a linha proposta por WU, DEBS E MARSTEN (1994), e somente considera-lo no

procedimento corretor. Neste trabalho, contudo, optou-se por utilizar o parâmetro de barreira

tanto no passo previsor quanto no corretor, conforme PINHEIRO (2012). Esta opção se justifica

pelo fato do parâmetro de barreira ser responsável por manter a trajetória centralizada,

auxiliando a evitar que pontos da sequência gerada pelo método se tornem infactíveis.

Page 5: III Seminário da Pós-graduação em Engenharia Elétrica · energia caracterizado pela não-diferenciabilidade e não-convexidade da função objetivo. Para ... associado a um aproximante

III Seminário da Pós-graduação em Engenharia Elétrica

Seja o seguinte modelo de otimização não-linear com restrições de igualdade,

restrições de desigualdade canalizadas e variáveis canalizadas, em que as funções envolvidas

são de classe :

(4)

em que é a função objetivo, , , , são,

respectivamente, os vetores de limitantes inferiores e superiores das restrições de

desigualdade, são, respectivamente, os vetores de limitantes inferiores e

superiores para as canalizações de variáveis. A fim de resolver o problema (4), convertemos o

mesmo em um problema irrestrito, associando a função lagrangiana barreira logarítmica

modificada, apresentada em (5):

(5)

Na equação (5), é o vetor de variáveis

primais e duais, é o parâmetro de barreira, , são os vetores

estimadores dos multiplicadores de Lagrange das restrições de desigualdade, é o

vetor multiplicador de Lagrange das restrições de igualdade, , são os

vetores multiplicadores de Lagrange das restrições de desigualdade. Além disso,

, , e , onde ,

são as variáveis de folga. Pelo método da função barreira modificada, estas

variáveis são relaxadas, de modo que , , e ,

onde e .

3.1 Procedimento previsor

Sobre (5) aplicam-se as condições necessárias de primeira ordem, ou seja,

. A fim de resolver o sistema não-linear obtido, dada uma solução corrente ,

obtém-se o próximo ponto, , determinando uma direção e comprimentos de passo a

serem dados nessa direção. Para tanto, o sistema é linearizado utilizando um aproximante de

Taylor de primeira ordem. Com isto, obtém-se um sistema linear da forma

(6)

Page 6: III Seminário da Pós-graduação em Engenharia Elétrica · energia caracterizado pela não-diferenciabilidade e não-convexidade da função objetivo. Para ... associado a um aproximante

III Seminário da Pós-graduação em Engenharia Elétrica

no qual

(7)

, ,

, (8)

e

(9)

em que e são as matrizes jacobianas dos funcionais e ,

respectivamente. Além disso,

, (10)

é a matriz identidade de ordem , é a matriz identidade de ordem , ,

, , e é o

vetor de direções.

O vetor em (9) é denominado vetor de resíduos. No procedimento previsor, os

termos não-lineares da forma presentes nos resíduos de complementaridade, ,

, são desconsiderados, uma vez que as direções de busca não são conhecidas a

priori. Uma vez desconsiderados estes termos, e seguindo o trabalho de Pinheiro (2012), a

Page 7: III Seminário da Pós-graduação em Engenharia Elétrica · energia caracterizado pela não-diferenciabilidade e não-convexidade da função objetivo. Para ... associado a um aproximante

III Seminário da Pós-graduação em Engenharia Elétrica

esparsidade da matriz é explorada para resolver o sistema e calcular as direções de busca

separadamente. Com isso, as seguintes direções de busca são determinadas:

, (11)

, (12)

, , , (13)

, (14)

em que

, (15)

, (16)

, (17)

3.2 Procedimento corretor

Uma vez que as direções do passo previsor são calculadas, utilizamos as mesmas

para determinar as direções corrigidas. Para tanto, utilizamos as direções (11)-(14) para

considerar os termos não-lineares , . Com isto, determina-se as seguintes

direções corrigidas:

, (18)

, (19)

, , , (20)

, (21)

em que

, (22)

3.3 Comprimento do passo e obtenção do novo ponto

A solução corrente, , é atualizada por . O parâmetro

geralmente é assumido como valendo e , ,

. Os números e são denominados passo primal e passo dual, sendo

determinados pela condição de positividade das folgas, conforme GRANVILLE (1994):

Page 8: III Seminário da Pós-graduação em Engenharia Elétrica · energia caracterizado pela não-diferenciabilidade e não-convexidade da função objetivo. Para ... associado a um aproximante

III Seminário da Pós-graduação em Engenharia Elétrica

, (23)

, (24)

com e .

3.4 Atualização do parâmetro de barreira, estimadores dos multiplicadores de

Lagrange e critério de parada

A heurística empregada para a atualização do parâmetro de barreira foi:

, (25)

Diferentemente do trabalho de POLYAK (1994), que apresentou a função barreira

modificada, neste trabalho adotou-se a estratégia apresentada por PINHEIRO (2012) para

atualização dos estimadores dos multiplicadores de Lagrange, e que é de baixo custo

computacional:

(26)

O critério de parada consiste em verificar, sobre a nova solução calculada, , se

as condições de factibilidade primal e dual são verificadas, bem como as condição de folgas

complementares, ou seja, se

(27)

em que é a precisão desejada. O método deve parar quando (27) ocorrer, uma vez que

é uma solução com a precisão definida. Caso contrário, uma nova iteração dos

procedimentos previsor e corretor deve ser realizada.

3.5 Convergência global: uma variante de Levenberg-Marquardt

Neste trabalho, propõe-se uma estratégia de convergência global para o método de

pontos interiores adotado, baseada em PINHEIRO (2012), e que é uma variante de Levenberg-

Marquardt. Este tipo de estratégia é importante, em particular porque o PDE-PV é um

problema de otimização não-linear e não-convexo, de modo que a matriz dual normal, ,

utilizada no cálculo das direções, pode não ser definida positiva. Isto pode ocasionar

instabilidades numéricas que inviabilizam a utilização do método proposto, e até mesmo a

convergência para pontos que não são mínimos locais.

Page 9: III Seminário da Pós-graduação em Engenharia Elétrica · energia caracterizado pela não-diferenciabilidade e não-convexidade da função objetivo. Para ... associado a um aproximante

III Seminário da Pós-graduação em Engenharia Elétrica

Uma matriz é definida positiva se, e somente se, é possível realizar sua

Decomposição de Cholesky (DC). Assim, pode-se checar se a matriz é definida positiva

utilizando a DC. Caso a DC não seja possível, é efetuada uma perturbação diagonal na matriz

, visando torna-la definida positiva. Esta perturbação é realizada da seguinte forma:

(28)

em que é a matriz identidade de ordem (igual à da matriz ) e . Chamamos

de parâmetro de amortecimento. Este incremento na diagonal da matriz é realizado até que

a nova matriz obtida, , seja definida positiva, isto é, até que a DC possa ser realizada. O

valor de é incrementado pela expressão:

(29)

Quando a DC for satisfeita, define-se . Ao final de uma iteração, o

parâmetro de amortecimento inicial para a iteração seguinte é atualizado segundo a seguinte

heurística, apresentada por PINHEIRO (2012):

(i) Se , então ;

(ii) Se , então é atualizado pela heurística (29);

(iii) Se , então permanece o mesmo.

4 A ESTRATÉGIA DE SUAVIZAÇÃO DA FUNÇÃO OBJETIVO

Seja um problema de otimização da forma

(30)

em que é uma função de classe . Nota-se que a função objetivo em (30) pode ser

não diferenciável, nos pontos em que . A ideia da estratégia aqui proposta é

substituir o problema (30) por um problema com função objetivo aproximada, porém

diferenciável em todos os pontos do domínio. Isto porque problemas diferenciáveis

usualmente podem ser resolvidos por métodos de pontos interiores de modo mais eficiente do

que a utilização de métodos não-diferenciáveis, como métodos de feixes ou subgradientes.

É sabido que, dado um número real qualquer, é válida a identidade:

(31)

em que é a função sinal, definida por:

Page 10: III Seminário da Pós-graduação em Engenharia Elétrica · energia caracterizado pela não-diferenciabilidade e não-convexidade da função objetivo. Para ... associado a um aproximante

III Seminário da Pós-graduação em Engenharia Elétrica

(32)

Deste modo, podemos escrever:

(33)

Isto significa que, se pudermos aproximar a função sinal através de uma função

de, no mínimo, classe , podemos aproximar por . Deste

modo, podemos substituir o problema (30) pelo seguinte problema aproximado:

(34)

Desde que e sejam de classe , a função também o

será, uma vez que resulta da composição e produto de funções de classe . Portanto,

podemos aplicar ao problema (34) o MPCPDPIBLM desenvolvido na Seção 3. Naturalmente,

a qualidade da solução obtida através do problema aproximado dependerá da qualidade da

aproximação, , feita para a função sinal. Neste trabalho, empregou-se um aproximante da

função sinal, baseado na função tangente hiperbólica, isto é, adotou-se , em

que é um parâmetro que controla a proximidade de da função . Para tanto, resolveu-

se o seguinte problema aproximado:

(35)

Na próxima seção apresentamos os resultados obtidos com esta abordagem, aplicada

a um problema-teste matemático e ao caso do PDE-PV com 3 geradores.

5 RESULTADOS NUMÉRICOS

A estratégia apresentada foi aplicada a dois problemas que envolvem a minimização

de funções com termos modulares: um problema-teste matemático e o caso do PDE-PV com 3

geradores.

5.1 Problema-teste matemático

O problema-teste matemático utilizado foi

(36)

Os parâmetros iniciais utilizados pelo método foram: , , e

os estimadores dos multiplicadores de Lagrange iguais a . O ponto inicial foi

Page 11: III Seminário da Pós-graduação em Engenharia Elétrica · energia caracterizado pela não-diferenciabilidade e não-convexidade da função objetivo. Para ... associado a um aproximante

III Seminário da Pós-graduação em Engenharia Elétrica

, e as demais variáveis primais e duais foram calculadas assumindo que os

resíduos são nulos em (9). A precisão do critério de parada foi . Com isto, o método

convergiu em 16 iterações, para o ponto . O valor da função

objetivo original no ponto ótimo é , enquanto a função aproximada vale

. O parâmetro de amortecimento, a final do processo, vale

, o que indica que, à medida que o método se aproxima do mínimo local, a

necessidade de reajustar a matriz dual normal se torna menos necessária. A Figura 1 apresenta

o processo de convergência do método.

Figura 2 – Processo de convergência do método: problema-teste matemático

As curvas em verde – uma parábola e dois eixos – correspondem aos pontos em que

a função é não-diferenciável. A curva em laranja corresponde à restrição de igualdade,

enquanto a circunferência em magenta corresponde à fronteira da restrição de desigualdade.

Isto significa que a região factível é dada pelos trechos da curva em laranja no interior da

circunferência. Nota-se que o método foi inicializado em um ponto infactível, mesmo para a

restrição de desigualdade. Ainda assim o método pôde convergir, devido à relaxação realizada

através da função barreira modificada.

5.2 PDE-PV com 3 geradores

O seguinte caso do PDE-PV com 3 geradores foi extraído de SAMED (2004):

(37)

em que:

Page 12: III Seminário da Pós-graduação em Engenharia Elétrica · energia caracterizado pela não-diferenciabilidade e não-convexidade da função objetivo. Para ... associado a um aproximante

III Seminário da Pós-graduação em Engenharia Elétrica

(38)

A fim de permitir a interpretação geométrica do problema, podemos utilizar a

restrição de igualdade , de modo a converter o

problema (37) em um problema com duas variáveis equivalente:

(39)

Neste caso, os parâmetros iniciais foram: , , e os

estimadores dos multiplicadores de Lagrange iguais a . O ponto inicial foi

. Do mesmo modo que no caso anterior, as demais

variáveis primais e duais foram calculadas assumindo que os resíduos são nulos em (9) e a

precisão adotada foi . Com isto, o método convergiu em 17 iterações, para o ponto

. O valor da função objetivo original no ponto ótimo é

, enquanto a função aproximada vale , evidenciando

a proximidade entre a função objetivo original e aproximada. A Figura 2 representa o

processo de convergência do problema equivalente (39).

Figura 3 – Processo de convergência do método: PDE-PV de 3 geradores

Neste caso, a região factível é dada pelo pentágono delimitado pelas retas em

magenta, destacado na Figura 5. Nota-se que o método quase convergiu para um mínimo

local, mas em algum momento um passo maior foi dado, o que permitiu uma inversão na

trajetória e a determinação do mínimo global. Justifica-se esse fato devido a resultados

discutidos em PINHEIRO (2012) sobre os procedimentos de passo longo intrínsecas ao

MPCPDPIBLM quando considera-se a sua estratégia de convergência global (seção 3.5),

Page 13: III Seminário da Pós-graduação em Engenharia Elétrica · energia caracterizado pela não-diferenciabilidade e não-convexidade da função objetivo. Para ... associado a um aproximante

III Seminário da Pós-graduação em Engenharia Elétrica

apesar dessa não garantir que sempre o método obterá o mínimo global do problema, se esse

existir.

6 CONCLUSÃO

Este trabalho apresentou um método primal-dual previsor-corretor de pontos

interiores híbrido com métodos de aproximantes (suavizadores) de funções para a resolução

de problemas de otimização não linear, não-convexos e não-diferenciáveis. Para tanto,

utilizou a função barreira logarítmica modificada, que realiza uma relaxação na região factível

e permite a inicialização por pontos infactíveis. Apresentou-se, ainda, uma estratégia para

suavização de funções com termos modulares, bem como uma estratégia de convergência

global, que permitiram ao método, respectivamente, o tratamento de não-diferenciabilidades e

não-convexidades da função objetivo e a obtenção de mínimos locais. O método proposto foi

implementado em Matlab 2011, e os resultados mostraram que a estratégia desenvolvida foi

eficiente na resolução um problema-teste matemático e de um caso do PDE-PV com 3

geradores, em que as funções envolvidas eram não-convexas e não-diferenciáveis devido a

termos modulares.

REFERÊNCIAS BIBLIOGRÁFICAS

BALBO, A. R.; SOUZA, M. A. S.; BAPTISTA, E. C.; NEPOMUCENO, L. Predictor-Corrector

Primal-Dual Interior Point Method for Solving Economic Dispatch Problems: A

Postoptimization Analysis. Mathematical Problems in Engineering, vol. 2012, Article ID

376546, 26 pages, 2012. doi: 10.1155/2012/376546.

CARPENTIER, J. Contributions to the economic dispatch problem. Bulletin de la Societe

Francoise des Electriciens, vol. 3, n. 8, pp. 431-447, 1962.

GRANVILLE, S. Optimal reactive dispatch through interior point method. IEEE Transactions

on Power Systems, vol. 9, n. 1, pp. 136-146, 1994.

PINHEIRO, R. B. N. Um método previsor-corretor primal-dual de pontos interiores

barreira logarítmica modificada, com estratégias de convergência global e de ajuste

cúbico, para problemas de programação não-linear e não-convexa. Dissertação

(mestrado) – Faculdade de Engenharia de Bauru, Universidade Estadual Paulista, Bauru,

2012.

POLYAK, R. A. Modified barrier functions. Mathematical Programming, vol. 54, n. 2, pp.

177-222, 1992.

SAMED, M. M. A. Um algoritmo genético híbrido co-evolutivo para resolver problemas de

despacho. Tese (doutorado) – Departamento de Engenharia Química, Universidade Estadual

de Maringá, Maringá, 2004.

SOUSA, V. A. Resolução do problema de fluxo de potência ótimo reativo via método da

função lagrangiana barreira modificada. Tese (doutorado) – Escola de Engenharia de São

Carlos, Universidade de São Paulo, São Carlos, 2006.

Page 14: III Seminário da Pós-graduação em Engenharia Elétrica · energia caracterizado pela não-diferenciabilidade e não-convexidade da função objetivo. Para ... associado a um aproximante

III Seminário da Pós-graduação em Engenharia Elétrica

STANZANI, A. L. Método previsor-corretor primal-dual de pontos interiores em

problemas multiobjetivo de despacho econômico e ambiental. Dissertação (mestrado) –

Faculdade de Engenharia de Bauru, Universidade Estadual Paulista, Bauru, 2012.

STEINBERG, M. J. C.; SMITH, T. H. Economic loading of power plants and electric systems.

McGraw-Hill, 1943.

WU, Y.; DEBS, A. S.; MARSTEN, R. E. A direct nonlinear predictor-corrector primal-dual

interior point algorithm for optimal power flows. IEEE Transactions on Power Systems,

vol. 9, no. 2, pp. 876-883, 1994.