OTIMIZAÇÃOESTRUTURALMEDIANTEPROGRAMAÇÃO ...w2.files.scire.net.br/atrio/ufrj-pem_upl/THESIS/21/...OTIMIZAÇÃOESTRUTURALMEDIANTEPROGRAMAÇÃO SEMIDEFINIDA ElmerGiovanniBazánCórdova

OTIMIZAÇÃO ESTRUTURAL MEDIANTE PROGRAMAÇÃOSEMIDEFINIDA

Elmer Giovanni Bazán Córdova

Dissertação de Mestrado apresentada aoPrograma de Pós-graduação em EngenhariaMecânica, COPPE, da Universidade Federaldo Rio de Janeiro, como parte dos requisitosnecessários à obtenção do título de Mestreem Engenharia Mecânica.

Orientador: José Herskovits Norman

Rio de JaneiroJunho de 2012



DISSERTAÇÃO SUBMETIDA AO CORPO DOCENTE DO INSTITUTOALBERTO LUIZ COIMBRA DE PÓS-GRADUAÇÃO E PESQUISA DEENGENHARIA (COPPE) DA UNIVERSIDADE FEDERAL DO RIO DEJANEIRO COMO PARTE DOS REQUISITOS NECESSÁRIOS PARA AOBTENÇÃO DO GRAU DE MESTRE EM CIÊNCIAS EM ENGENHARIAMECÂNICA.

Examinada por:

Prof. José Herskovits Norman, Dr.Ing.

Prof. Fernando Pereira Duda, D.Sc.

Prof. Antonio André Novotny, D.Sc.

RIO DE JANEIRO, RJ – BRASILJUNHO DE 2012

Córdova, Elmer Giovanni BazánOtimização estrutural mediante programação

semidefinida/Elmer Giovanni Bazán Córdova. – Riode Janeiro: UFRJ/COPPE, 2012.

XI, 64 p.: il.; 29, 7cm.Orientador: José Herskovits NormanDissertação (mestrado) – UFRJ/COPPE/Programa de

Engenharia Mecânica, 2012.Referências Bibliográficas: p. 62 – 64.1. Otimização estrutural. 2. Programação

semidefinida. 3. Algoritmo do ponto interior. I.Norman, José Herskovits. II. Universidade Federal do Riode Janeiro, COPPE, Programa de Engenharia Mecânica.III. Título.

iii

A meus pais, Elmer e María,pelo carinho e constante apoio

iv

Agradecimentos

Ao Prof. José Herskovits, pela orientação, apoio e conhecimentos transmitidosao longo da realização deste trabalho.

Ao Prof. Nelson Maculan, pelo apoio e motivação para fazer o curso de Mestradona UFRJ.

Ao Prof. Miguel Aroztegui, pela amizade e apoio na realização deste trabalho.

Aos colegas e amigos do Laboratório OptimizE: Arminda, Henry, Jorge, Mario,Helena e Elielson.

Agradeço à Coordenação de Aperfeiçoamento de Pessoal de Nível Superior(CAPES) pelo suporte financeiro.

v

Resumo da Dissertação apresentada à COPPE/UFRJ como parte dos requisitosnecessários para a obtenção do grau de Mestre em Ciências (M.Sc.)



Junho/2012

Orientador: José Herskovits Norman

Programa: Engenharia Mecânica

As técnicas de programação semidefinida (SDP) são muito eficientes na soluçãode problemas de otimização estrutural [1]. Um problema clássico em otimizaçãoestrutural consiste em minimizar o peso da estrutura sob certas restrições que podemser as frequências naturais assim como a complacência. Apresenta-se, neste trabalho,uma reformulação do algoritmo FDIPA-SDP para resolver problemas de otimizaçãoestrutural, sem mudar a estrutura das matrizes empregadas na análise estruturalpelo método dos elementos finitos (MEF). O algoritmo apresentado baseia-se noalgoritmo de pontos interiores proposto por Aroztegui [2], que resolve as condiçõesde otimalidade de Karush-Kuhn-Tucker para SDP, empregando-se iterações tipoNewton. Finalmente, são apresentados exemplos numéricos em aplicações deotimização estrutural.

vi

Abstract of Dissertation presented to COPPE/UFRJ as a partial fulfillment of therequirements for the degree of Master of Science (M.Sc.)

SEMIDEFINITE PROGRAMMING FOR STRUCTURAL OPTIMIZATION


June/2012

Advisor: José Herskovits Norman

Department: Mechanical Engineering

The Semidefinite Programming Techniques (SDP) are very efficient in solvingstructural optimization problems. A classic problem in structural optimizationconsists on minimizing the weight of the structure under certain constraints thatmay be related to the natural frequencies as well as the compliance. In thiswork, a reformulation of the algorithm FDIPA-SDP to solve structural optimizationproblems is presented without changing the structure of the matrices used instructural analysis by the finite element method (FEM). The algorithm presentedis based on the interior point algorithm proposed by Aroztegui [1] that solves theKarush-Kuhn-Tucker SDP optimality conditions employing Newton-like iterations.Finally, numerical examples are presented in structural optimization applications.

vii

Sumário

Lista de Figuras x

Lista de Tabelas xi

Introdução 1

1 Preliminares 61.1 Notações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.1.1 Programação matemática . . . . . . . . . . . . . . . . . . . . 61.1.2 Matrizes SDP . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.2 Funções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.3 Vetores e Matrizes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.4 Produto de Kronecker . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.4.1 Produto de Kronecker . . . . . . . . . . . . . . . . . . . . . . 131.4.2 Produto Simétrico de Kronecker . . . . . . . . . . . . . . . . . 13

1.5 Transformação linear . . . . . . . . . . . . . . . . . . . . . . . . . . . 161.6 Complacência . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161.7 Complemento de Schur . . . . . . . . . . . . . . . . . . . . . . . . . . 161.8 Programação Matemática . . . . . . . . . . . . . . . . . . . . . . . . 161.9 Método dos Elementos Finitos . . . . . . . . . . . . . . . . . . . . . . 17

2 Formulação do problema de Otimização Estrutural 222.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.2 Componentes de um problema de Otimização Estrutural . . . . . . . 22

2.2.1 Identificação e definição das variáveis de projeto . . . . . . . . 222.2.2 Definição da função objetivo (função custo) . . . . . . . . . . 232.2.3 Identificação e definição das restrições . . . . . . . . . . . . . 23

2.3 Tipos de problemas de Otimização Estrutural . . . . . . . . . . . . . 242.3.1 Otimização Dimensional . . . . . . . . . . . . . . . . . . . . . 242.3.2 Otimização de Forma . . . . . . . . . . . . . . . . . . . . . . . 242.3.3 Otimização Topológica . . . . . . . . . . . . . . . . . . . . . . 24

2.4 Problema de otimização não linear . . . . . . . . . . . . . . . . . . . 24

viii

2.4.1 Notações e Definições . . . . . . . . . . . . . . . . . . . . . . . 252.4.2 Condições de otimalidade de primeira ordem (KKT) . . . . . 25

2.5 Programação semidefinida (SDP) . . . . . . . . . . . . . . . . . . . . 272.6 Formulação tradicional do problema de volume mínimo . . . . . . . . 27

2.6.1 Problema de autovalores . . . . . . . . . . . . . . . . . . . . . 282.6.2 Propriedades do λmin . . . . . . . . . . . . . . . . . . . . . . . 29

2.7 Formulação SDP do problema de volume mínimo . . . . . . . . . . . 32

3 Algoritmo de pontos interiores e direções viáveis (FDIPA) 343.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.2 Descrição do algoritmo FDIPA . . . . . . . . . . . . . . . . . . . . . . 35

3.2.1 Hipóteses e Definições . . . . . . . . . . . . . . . . . . . . . . 353.2.2 Cálculo da direção de busca . . . . . . . . . . . . . . . . . . . 363.2.3 Direção viável . . . . . . . . . . . . . . . . . . . . . . . . . . . 373.2.4 Busca Linear . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3.3 Algoritmo FDIPA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

4 Algoritmo de pontos interiores e direções viáveis para programaçãosemidefinida (FDIPA-SDP) 414.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414.2 Notações e definições . . . . . . . . . . . . . . . . . . . . . . . . . . . 414.3 Condições de otimalidade de primeira ordem de KKT . . . . . . . . . 434.4 Descrição do algoritmo FDIPA-SDP . . . . . . . . . . . . . . . . . . . 44

4.4.1 Matriz do sistema linear . . . . . . . . . . . . . . . . . . . . . 444.4.2 Cálculo da direção de busca . . . . . . . . . . . . . . . . . . . 464.4.3 Direção viável . . . . . . . . . . . . . . . . . . . . . . . . . . . 464.4.4 Busca linear . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474.4.5 Atualização . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

4.5 Algoritmo FDIPA-SDP . . . . . . . . . . . . . . . . . . . . . . . . . . 48

5 Testes Numéricos 505.1 Exemplo 1 - Problema 43 . . . . . . . . . . . . . . . . . . . . . . . . . 525.2 Exemplo 2 - Treliça de 10 barras . . . . . . . . . . . . . . . . . . . . 545.3 Exemplo 3 - Treliça de 10 barras sujeita a restrições de deslocamento 57

6 Conclusões 60

Referências Bibliográficas 62

ix

Lista de Figuras

1 Processo de Otimização Estrutural . . . . . . . . . . . . . . . . . . . 3

1.1 Função convexa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.2 Função semi-contínua superiormente . . . . . . . . . . . . . . . . . . 81.3 Exemplo de uma função semi-contínua superiormente . . . . . . . . . 91.4 Padrão esparso do produto de Kronecker das matrizes A e I. . . . . . 151.5 Padrão esparso do produto simétrico de Kronecker das matrizes A e I. 151.6 Uma treliça bidimensional. . . . . . . . . . . . . . . . . . . . . . . . . 181.7 Definição do elemento barra bidimensional. . . . . . . . . . . . . . . . 181.8 Co-senos diretores. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.1 Condições de KKT do problema 2.2. . . . . . . . . . . . . . . . . . . 262.2 Possível descontinuidade do λmin . . . . . . . . . . . . . . . . . . . . 31

3.1 Direção de busca do algoritmo FIDPA. . . . . . . . . . . . . . . . . . 38

4.1 Busca Linear de Armijo. . . . . . . . . . . . . . . . . . . . . . . . . . 48

5.1 Convergência do algoritmo FDIPA-SDP para o Exemplo 1 . . . . . . 535.2 Treliça de 10 barras com carregamento simples . . . . . . . . . . . . . 545.3 Otimização da treliça de 10 barras do Exemplo 2. . . . . . . . . . . . 555.4 Convergência do algoritmo FDIPA-SDP para o Exemplo 2. . . . . . . 565.5 Otimização da treliça de 10 barras para o Exemplo 3. . . . . . . . . . 585.6 Convergência do algoritmo FDIPA-SDP da treliça de 10 barras do

exemplo 3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

x

Lista de Tabelas

5.1 Otimização do exemplo 1 . . . . . . . . . . . . . . . . . . . . . . . . . 535.2 Evolução da redução do volume da estrutura do Exemplo 2. . . . . . 565.3 Estrutura ótima obtida para a treliça de 10 barras do exemplo 2. . . . 575.4 Evolução da redução do volume da estrutura do Exemplo 3. . . . . . 595.5 Estrutura ótima obtida para a treliça de 10 barras do exemplo 3. . . . 59

xi

Introdução

Neste trabalho, apresenta-se um modelo de otimização estrutural para minimizaro peso de estruturas de treliças mediante a implementação da programaçãosemidefinida ao algoritmo FDIPA (Feasible Direction Interior Point Algorithm),considerando como restrições as frequências naturais da estrutura, a complacênciae os deslocamentos dos nós.

A otimização estrutural tem como objetivo a busca de uma estrutura viável queminimize uma função custo e verifique um conjunto de restrições. A função customais comumente utilizada na engenharia é o peso total da estrutura sob restriçõesmecânicas impostas, sejam elas estáticas ou dinâmicas [3].

A otimização de forma e tamanho de estruturas com restrições de frequêncianatural é muito útil quando se deseja melhorar o comportamento dinâmico destas[4].

Um problema de programação semidefinida linear (SDP) é um problema deminimização de uma função linear sobre restrições lineares tais que as variáveis sãomatrizes semidefinidas positivas [1]. Se a função ou as restrições são não lineares oproblema se denomina programação semidefinida não linear (NL-SDP) [2].

Uma aplicação da programação semidefinida, que recebeu menos atenção foi oprojeto estrutural, onde os problemas mais conhecidos são problemas de otimizaçãoestrutural [5]. Neste caso, existem duas variantes:

• Minimizar o peso da estrutura tal que sua frequência natural permanece acimade um valor crítico;

• Minimizar a complacência (trabalho feito pelas forças externas) da treliça,sujeita a um conjunto de forças que a estrutura tem que suportar.

Recentemente, tem-se encontrado algumas aplicações no campo da otimizaçãoestrutural. Para estruturas tais como treliças, placas com deformação plana, pórticosplanos, placas com seção transversal sanduíche, etc., as matrizes de rigidez e massasão funções lineares das variáveis de projeto e os problemas de otimização comrestrições de frequências naturais e complacência podem ser formuladas por SDP[1].

1

A otimização estrutural tem que seguir um esquema coerente, definido porCASTELEIRO [6], nos seguintes termos:

• Formulação do problema de OtimizaçãoA otimização estrutural pode ser definida como um problema geral deprogramação matemática, como a minimização de uma certa função objetivo(peso estrutural, concentração de tensões, custo, etc.), sujeita a restrições quedevem ser respeitadas, expressas geralmente como desigualdades em funçãodas variáveis de projeto que definem o comportamento estrutural (esforços,tensões, deslocamentos inferiores a certos valores admissíveis, limitaçõesgeométricas, etc.).

• Geração de um modelo de OtimizaçãoDefinição da estrutura através de um conjunto de variáveis de projeto quedeterminam suas propriedades, de modo que se possa realizar sua análisemediante um determinado procedimento de cálculo estrutural e assim obtera informação necessária para o planejamento do problema de otimização(tensões, deslocamentos, etc.).

• Novos métodos de solução de problemasDesenvolvimento e aplicação de novos métodos de solução de problemas deprogramação matemática.

A estrutura apresentada na Figura 1 é utilizada para ilustrar o processo deotimização estrutural descrito por CASTELEIRO [6]. Trata-se de uma treliça detrês barras, onde a função objetivo é o peso da estrutura, com peso inicial Wi,e as variáveis de projeto são as áreas das barras A1, A2 e A3 e o ângulo α. Aestrutura está sujeita a uma carga P dada e considera-se como restrição a tensãomáxima admissível σmáx. Depois da realização do processo de otimização, mediantealguma técnica de programação matemática, os resultados mostraram que as áreasdas barras 1 e 3, na configuração final da estrutura, são maiores que na configuraçãoinicial e o valor da área da barra 2 tornou-se nulo, portanto, o peso final da estruturafoi reduzido em 10%, ou seja, Wf = 0, 9Wi.

Estado da arte

WEI et al. [4] utilizaram algoritmos genéticos paralelos para otimizar asdimensões e forma das estruturas de treliças com restrições de frequência naturale minimizaram o peso da estrutura evitando os efeitos da ressonância causada porexcitações externas.

2

Função Objetivo:

Variáveis do projeto:

Dados:

Dados:

Figura 1: Processo de Otimização Estrutural

3

AROZTEGUI [2] utilizou uma técnica de programação semidefinida não linearna otimização estrutural de materiais lineares elásticos e propôs um novo modelo deotimização de estruturas planas, no qual minimiza-se o volume de estruturas planascom restrições definidas sobre o tensor de elasticidade e restrições locais de tensãoou deslocamento.

ACHTZINGER e KOCVARA [7] formularam diferentes problemas de otimiza-ção topológica de estruturas discretas, mediante a programação semidefinida: oproblema de minimização do peso da estrutura para diferentes casos de carrega-mento, o problema de maximização do autovalor mínimo da estrutura e, o problemade minimização da complacência (maximização da rigidez) estrutural.

BEN-TAL e NEMIROSKI [8] apresentaram uma formulação SDP para o projetotopológico robusto de estruturas com restrições de complacência.

OHSAKI et al. [9] mostraram que as treliças ótimas com multiplicidade defrequências naturais podem ser obtidas sem dificuldades através da técnica deprogramação semidefinida, e o método pode ser estendido a restrições de flambagem.

Objetivos

Este trabalho ter como objetivos:

• Otimizar uma estrutura de treliças fazendo uso da técnica de programaçãosemidefinida;

• Reduzir o peso de uma estrutura de treliças tendo como restrições asfrequências naturais e os deslocamentos;

• Implementar o algoritmo de pontos interiores e direções viáveis paraprogramação semidefinida (FDIPA-SDP);

• Mostrar resultados numéricos para o problema de otimização estrutural.

Organização do trabalho

O trabalho está organizado em seis capítulos, distribuídos da forma que sigue:No capítulo 1, apresentam-se algumas notações e definições matemáticas

necessárias ao desenvolvimento dos conceitos para a formulação de problemas deprogramação semidefinida não linear, e também, uma introdução ao método doselementos finitos para a solução da análise estrutural de treliças.

No capítulo 2, apresenta-se a formulação do problema de otimização estrutural,em duas versões: a formulação tradicional e a formulação para programaçãosemidefinida.

4

No capítulo 3, apresenta-se o algoritmo FDIPA para resolver problemas deotimização não linear da forma:

minimizarx∈Rn

f (x)

sujeito a: g (x) 6 0

onde, x ∈ Rn é o vetor das variáveis de projeto, f : Rn → R é a função objetivoe, g : Rn → Rm é a função das restrições de desigualdade. Neste capítulo, sãodefinidos os conceitos de programação matemática não linear e o fundamento teóriconecessário para a compreensão do método, que é a base do algoritmo de programaçãosemidefinida.

No capítulo 4, apresenta-se o algoritmo FDIPA-SDP para resolver problemas daforma: minimizar

x∈Rnf (x)

sujeito a: G (x) 4 0

onde, x ∈ Rn é o vetor das variáveis de projeto, f : Rn → R é a função objetivo e,G : Rn → Sm é um mapeamento de Rn no espaço Sm das matrizes reais simétricasm×m.

A partir da implementação do algoritmo FDIPA-SDP apresentam-se, no capítulo5, exemplos numéricos que mostram a utilização prática da formulação de problemasSDP em comparação com a formulação tradicional. Os exemplos numéricosmostrados são os seguintes: um problema teste algébrico da coleção de problemasteste de Schittkowski [10] e, dois problemas de otimização estrutural nos quaisconsideram-se restrições de complacência, frequência natural e deslocamentos.

Finalmente, no capítulo 6, são apresentadas as conclusões e as sugestões paratrabalhos futuros.

5

Capítulo 1

Preliminares

Neste capítulo, apresentam-se algumas notações e definições que serão utilizadasao longo deste trabalho.

1.1 Notações

1.1.1 Programação matemática

Um problema de otimização não linear sujeito a restrições de desigualdade podeser formulado da seguinte maneira:

minimizarx∈Rn

f (x)

sujeito a: g (x) 6 0(1.1)

onde, a função f : Rn → R é chamada a função objetivo e, g : Rn → Rm é a funçãodas restrições de desigualdade.

Denote-se por n o número de variáveis de projeto e m o número de restrições dedesigualdade.

O vetor das variáveis de projeto é denotado por x =[x1, . . . , xn

]Te o vetor de

restrições é denotado por g (x) =[g1 (x) , . . . , gm (x)

]T.

O vetor gradiente de uma função f : Rn → R é denotado por:

∇f (x) =[∂f (x)∂xi

, . . . ,∂f (x)∂xn

]T

∈ Rn (1.2)

As derivadas parciais de gi em relação a xi são agrupadas na matriz ∇g (x) ∈Rn×m denotada por:

∇g (x) =[∇g1 (x) , . . . ,∇gm (x)

](1.3)

6

A Hessiana de f em x é denotada por:

∇2f (x) =

∂2f (x)∂x2

1. . .

∂2f (x)∂x1∂xn... . . . ...

∂2f (x)∂xn∂x1

. . .∂2f (x)∂x2

n

(1.4)

onde as componentes ∂2f(x)∂xi∂xj

, i, j = 1, . . . , n são as derivadas parciais de segundaordem da função f .

1.1.2 Matrizes SDP

Para matrizes definidas (ou semidefinidas) positivas, o conjunto de matrizessimétricas de ordem n× n é denotado por Sn.

A matriz A é chamada semidefinida positiva se xT Ax > 0 para todo x ∈ Rn eé chamada definida positiva se xT Ax > 0 para todo x 6= 0 ∈ Rn.

O conjunto de matrizes semidefinidas positivas denota-se por Sn+ e o conjunto de

matrizes definidas positivas denota-se por Sn++.

1.2 Funções

Definição 1.2.1 (Conjunto Convexo). Seja C um subconjunto de Rn. C é umconjunto convexo se, para qualquer par de pontos x,y ∈ C, e para qualquer λ ∈ [0, 1],o ponto λx + (1− λ) y pertence também a C.

Definição 1.2.2 (Função Convexa). Uma função f : C → R definida em umconjunto convexo C é convexa se, e somente se, para todo x,y ∈ C e para λ ∈ [0, 1],se verifica que:

f (λx + (1− λ)y) 6 λf (x) + (1− λ) f (y) (1.5)

Se para todo λ ∈ (0, 1) e x 6= y e λ ∈ (0, 1) vale que:

f (λx + (1− λ)y) < λf (x) + (1− λ) f (y) (1.6)

diremos que f é estritamente convexa.

Definição 1.2.3 (Função quasiconvexa). Uma função f é quasiconvexa se, esomente se, para qualquer x e y, e para qualquer λ ∈ [0, 1], a seguinte desigualdadeé satisfeita:

f (λx + (1− λ)y) 6 max f (x) , f (y) (1.7)

7

Figura 1.1: Função convexa

Definição 1.2.4 (Função semi-contínua superiormente). Uma função f : X → Rdiz-se semi-contínua superiormente (scs) [11] no ponto a ∈ X quando, para cadac > f (a) dado, existe δ > 0 tal que x ∈ X , ‖x− a‖ < δ implica f (x) < c.

Figura 1.2: Função semi-contínua superiormente

Exemplo 1.2.1. Seja a função:

f (x) = −1, x < 0

1, x ≥ 0

semi-contínua superiormente em x0 = 0, como mostra-se na Figura 1.3.

8

Figura 1.3: Exemplo de uma função semi-contínua superiormente

1.3 Vetores e Matrizes

Definição 1.3.1 (Matriz Identidade). Uma matriz identidade é uma matriz diagonalonde seus elementos são todos iguais a um, isto é:

In =

1 0 · · · 00 1 · · · 0... ... . . . ...0 0 · · · 1

(1.8)

Definição 1.3.2 (Matriz Simétrica). Uma matriz quadrada A ∈ Rn×n é chamadasimétrica se a matriz e sua transposta são iguais, isto é:

AT = A (1.9)

Definição 1.3.3 (Matriz esparsa). Uma matriz é esparsa quando o número deelementos nulos é muito maior que o número de elementos não nulos.

Definição 1.3.4 (Menores principais de uma matriz). Seja uma matriz quadradaA ∈ Rn×n. Define-se Mi como uma submatriz de A formada por as i-primeiras filase as i-primeiras colunas de A. Os menores principais de A são os determinantes dassubmatrizes M1,M2, . . . ,Mn.

Exemplo 1.3.1. Seja a matriz A:

A =

1 2 34 5 67 8 9

9

Definem-se as submatrizes de A como:

M1 =(1), M2 =

1 24 5

, M3 =

1 2 34 5 67 8 9

Portanto, os menores principais da matriz A são:

|M1| = 1, |M2| = −3, |M3| = 0

Definição 1.3.5 (Matriz Definida Positiva). Uma matriz M ∈ Rn×n é definidapositiva quando:

vT Mv > 0 (1.10)

para qualquer v 6= 0 ∈ Rn.

Teorema 1.3.1 (Propriedades de uma matriz definida (ou semidefinida) positiva).Seja X ∈ Sn. Os seguintes enunciados são equivalentes:

1. X ∈ Sn+ ou X < 0 (X é semidefinida positiva);

2. zT Xz > 0, ∀z ∈ Rn;

3. λmin (X) > 0, onde λmin é o menor autovalor da matriz X;

4. Todos os menores principais do X são não negativos;

5. X = LLT para algum L ∈ Rn×n é chamada descomposição de Cholesky damatriz X.

Demonstração. Ver [12].

Definição 1.3.6. Para toda matriz simétrica U de ordem n× n, o vetor vec (U) ∈Rn2 define-se como:

vec (U) = (u11, . . . , un1, u12, . . . , un2, u1n, . . . unn)T (1.11)

Exemplo 1.3.2. Seja a matriz

A =

1 −1 2−1 2 42 4 3

Logo

vec (A) =[1,−1, 2,−1, 2, 4, 2, 4, 3

]T

10

Definição 1.3.7. Para toda matriz simétrica U de ordem n×n, o vetor svec (U) ∈R 1

2 n(n+1) define-se como:

svec (U) =(u11,√

2u21, . . . ,√

2un1, u22,√

2u32, . . . ,√

2un2, . . . , unn

)T(1.12)

tal que:svec (U)T svec (U) = tr

(UT U

)= vec (U)T vec (U) (1.13)

Exemplo 1.3.3. Seja a matriz A do exemplo anterior, logo:

svec (A) =[1,−√

2, 2√

2, 2, 4√

2, 3]T

Definição 1.3.8 (Traça de uma matriz). Para uma matriz quadrada A de ordemn, define-se a traça da matriz A como a soma dos elementos da diagonal de A, istoé:

tr (A) =n∑

i=1aii (1.14)

Teorema 1.3.2. Sejam A ∈ Rn×n e B ∈ Rn×n. Os seguintes enunciados sãoequivalentes:

1. tr (A) =n∑

i=1λi (A)

2. tr (A) = tr(AT )

3. tr (AB) = tr (BA)

4. tr(ABT ) = vec (A)T vec (B) =n∑

i,j=1aijbij


Definição 1.3.9 (Produto interno de matrizes). O produto interno entre matrizesem Rm×n define-se a partir do produto, a transposta e a traça de matrizes, isto é:

A •B = 〈A,B〉 = tr(AT B

)=

n∑i=1

m∑j=1

aijbij, A,B ∈ Rm×n (1.15)

Exemplo 1.3.4. Sejam as matrizes:

A =

1 2−1 33 4

, B =

4 52 −31 −2

o produto interno é:

〈A,B〉 = tr(AT B

)= −2

11

Definição 1.3.10 (Norma de uma matriz). Define-se a norma Frobenius em Rm×n

da matriz A, denotada por ‖A‖F como:

‖A‖F = m∑

i=1

n∑j=1

(aij)2

1/2

(1.16)

onde A ∈ Rm×n. A norma de Frobenius em Rn×n define-se através do produtointerno como:

‖A‖ =√〈A,A〉 =

√tr (AAT ) (1.17)

a qual satisfaz as seguintes condições:

1. ‖A‖ > 0 se A 6= O, e ‖O‖ = 0, onde O é a matriz com todos seus elementosnulos;

2. ‖cA‖ = |c| ‖A‖, para todo c ∈ R;

3. ‖A + B‖ 6 ‖A‖+ ‖B‖;

4. ‖AB‖ 6 ‖A‖ ‖B‖.


Definição 1.3.11 (Valores próprios e vetores próprios). Um problema de valorpróprio (ou autovalor) é definido como:

Ay = λy (1.18)

onde, A ∈ Rn×n. Deseja-se encontrar uma solução não trivial, ou seja, quer seencontrar um vetor próprio (ou autovetor) não nulo e o correspondente valor próprioλ que satisfaz a Equação 1.18. A Equação 1.18 pode ser escrita como:

(A− λI) y = 0 (1.19)

Uma solução não nula para y poderá ser obtida quando A − λI seja uma matrizsingular, ou seja:

det (A− λI) = 0 (1.20)

A Equação 1.20 é chamada Equação característica. Pode-se encontrar as n raízesou valores próprios λ1, λ2, . . . , λn. Denote-se por λmin = λ1 o menor autovalor eλmax = λn o maior autovalor. Para cada valor próprio λi, o vetor próprio associadoyi pode ser obtido da Equação 1.19, isto é:

(A− λiI) yi = 0 (1.21)

12

1.4 Produto de Kronecker

1.4.1 Produto de Kronecker

Define-se o produto de Kronecker [5] de duas matrizes G ∈ Rm×n e K ∈ Rr×s,pela matriz bloco de ordem mr × ns, da forma:

G⊗K = [gijK] , i = 1, . . . ,m, j = 1, . . . , n (1.22)

Teorema 1.4.1. Sejam K, L, G e H matrizes reais:

1. (G⊗K) vec (H) = vec(KHGT

);

2. (G⊗K)T = GT ⊗KT ;

3. (G⊗K)−1 = G−1 ⊗K−1;

4. (G⊗K) (H⊗ L) = (GH)⊗ (KL).


Exemplo 1.4.1. Sejam as matrizes A e B, tais que:

A =1 2

3 1

, B =0 3

2 1

O produto de Kronecker é:

C = A⊗B =

0 3 0 62 1 4 20 9 0 36 3 2 1

1.4.2 Produto Simétrico de Kronecker

O produto simétrico de Kronecker [5] de duas matrizes G ∈ Rn×n e K ∈ Rn×n

(não necessariamente simétricas), é uma aplicação (G⊗s K) definida por:

(G⊗s K) u = 12svec

(KUGT + GUKT

)(1.23)

onde, u é um vetor tal que u = svec(U), sendo U uma matriz simétrica n×n. Noteque (G⊗s K) é um operador linear definido implicitamente na Equação 1.23.

Considerando a matriz ortogonal Q ∈ R 12 n(n+1)×n2 com a propriedade seguinte:

Qvec (U) = svec (U) e QT svec (U) = vec (U) , ∀U ∈ Sn, (1.24)

13

a representação matricial de G ⊗s K pode ser caracterizada como no seguinteresultado.

Teorema 1.4.2. Seja Q ∈ R 12 n(n+1)×n2 a única matriz ortogonal que satisfaz a

Equação 1.24. Para qualquer G ∈ Rn×n e K ∈ Rn×n tem-se:

G⊗s K = 12Q (G⊗K + K⊗G) QT (1.25)

Demonstração. Ver [5].No próximo exemplo apresentaremos uma comparação entre o produto de

Kronecker e o produto simétrico de Kronecker.

Exemplo 1.4.2. Sejam as matrizes A e I, onde a matriz A é uma matriz em bandae a matriz I é uma matriz identidade, com as formas seguintes:

A =

1 2 2 2 0 0 0 0 0 02 2 2 2 2 0 0 0 0 02 2 3 2 2 2 0 0 0 02 2 2 4 2 2 2 0 0 00 2 2 2 5 2 2 2 0 00 0 2 2 2 5 2 2 2 00 0 0 2 2 2 4 2 2 20 0 0 0 2 2 2 3 2 20 0 0 0 0 2 2 2 2 20 0 0 0 0 0 2 2 2 1

e

I =

1 0 0 0 0 0 0 0 0 00 1 0 0 0 0 0 0 0 00 0 1 0 0 0 0 0 0 00 0 0 1 0 0 0 0 0 00 0 0 0 1 0 0 0 0 00 0 0 0 0 1 0 0 0 00 0 0 0 0 0 1 0 0 00 0 0 0 0 0 0 1 0 00 0 0 0 0 0 0 0 1 00 0 0 0 0 0 0 0 0 1

As Figuras 1.4 e 1.5 abaixo, mostram o padrão esparso do produto de Kronecker

e do produto simétrico de Kronecker das matrizes A e I respectivamente.Observando a distribuição dos elementos em cada uma das figuras, pode-se

concluir que o custo computacional, no caso do produto de Kronecker é menordo que no caso do produto simétrico de Kronecker.

14

O padrão esparso foi obtido pelo comando spy do MATLAB.

0 10 20 30 40 50 60 70 80 90 100

0

10

20

30

40

50

60

70

80

90

100

nz = 580

Figura 1.4: Padrão esparso do produto de Kronecker das matrizes A e I.

0 10 20 30 40 50

0

10

20

30

40

50

nz = 535

Figura 1.5: Padrão esparso do produto simétrico de Kronecker das matrizes A e I.

15

1.5 Transformação linear

Uma transformação (ou mapeamento) T é uma aplicação, que satisfaz:

1. T (u + v) = T (u) + T (v), para todo u, v no domínio de T ;

2. T (cu) = cT (u), para todo u e todo escalar c.


1.6 Complacência

Define-se a complacência W [1] como o trabalho externo equivalente à energiade deformação:

W = pT u = uT Ku = 2(pT − 1

2uT Ku)

= pT K−1p (1.26)

1.7 Complemento de Schur

Teorema 1.7.1. Seja a matriz:

M = A B

BT C

(1.27)

onde A é uma matriz definida positiva é C é uma matriz simétrica, então a matriz:

D = C−BT A−1B (1.28)

é chamada o complemento de Schur de A em M. Os seguintes enunciados sãoequivalentes:

• M é definida (ou semidefinida) positiva.

• D é definida (ou semidefinida) positiva.


1.8 Programação Matemática

Definição 1.8.1 (Região viável). Define-se Ω o conjunto de pontos viáveis doproblema (1.1) como:

Ω = x ∈ Rn : g (x) 6 0 (1.29)

16

Definição 1.8.2 (Conjunto de restrições ativas). Dado um ponto x ∈ Ω, o conjuntode restrições de desigualdade ativas é:

I (x) := gi : gi (x) = 0,∀x ∈ Ω, i = 1, . . . ,m (1.30)

Definição 1.8.3 (Direção viável). Um vetor d ∈ Rn é uma direção viável em x ∈ Ωse existe θ > 0 tal que x + td ∈ Ω para todo t ∈ [0, θ).

Definição 1.8.4 (Direção de descida). Um vetor d ∈ Rn é uma direção de descidapara uma função suave φ : Rn → R em x ∈ Rn se existe ψ > 0 tal queφ (x + td) < φ (x) para todo t ∈ (0, ψ). Se dT∇φ (x) < 0, então d é uma direçãode descida para φ em x.

Definição 1.8.5 (Mínimo local). O ponto x∗ ∈ Ω é um mínimo local de f , se existeum ε > 0 tal que f (x∗) 6 f (x) para todo x ∈ Ω∩B (x∗, ε). Onde B (x∗, ε) é a bolaaberta de centro x∗ e raio ε.

Definição 1.8.6 (Mínimo local estrito). O ponto x∗ ∈ Ω é um mínimo local estritode f , se existe um ε > 0 tal que f (x∗) < f (x) para todo x ∈ Ω ∩B (x∗, ε).

Definição 1.8.7 (Ponto regular). Um ponto x é dito ponto regular das restriçõesdo problema (1.1) se o conjunto ∇gi (x) : i ∈ I (x) é linearmente independente.

Definição 1.8.8 (Espaço tangente). O espaço tangente no ponto regular x é dadopor:

T (x) :=d : ∇gT

i d = 0, ∀i ∈ I (x)

(1.31)

1.9 Método dos Elementos Finitos

A análise estrutural usa três equações básicas, chamadas equações decompatibilidade, de equilíbrio e constitutivas, também chamadas de relação tensão-deformação.

O Método dos Elementos Finitos usa os conceitos de “discretização” do contínuoe de “matriz de interpolação”, que fornece os deslocamentos em um ponto, no interiordo elemento, em função de seus deslocamentos nodais. O análise de estruturas detreliças pode ser obtido pelo método dos elementos finitos.

Na Figura 1.6 [14] mostra-se uma treliça plana típica. Uma estrutura de treliçassó tem membros sujeitos a duas forças, tração ou compressão. Em uma treliça, oscarregamentos e as reações são aplicadas somente nos nós, e todos os membros estãoconectados nos extremos por meio de articulações sem fricção.

No caso de uma treliça, os eixos das barras têm sentidos diferentes, portantoexistem dois tipos de coordenadas, as coordenadas locais s e as coordenadas globais(x, y).

17

Elemento barra

Nó

Força nodal

Figura 1.6: Uma treliça bidimensional.

Sistema global de

coordenadas

Sistema local de

coordenadas

Figura 1.7: Definição do elemento barra bidimensional.

A Figura 1.7 [15] mostra um elemento barra bidimensional de uma estrutura detreliças. Os nós 1 e 2 são, respectivamente, o nó inicial e o nó final de um elementobarra bidimensional “e”. Cada nó tem dois graus de liberdade no sistema global decoordenadas. O ângulo φ define a rotação do eixo da barra em relação ao sistemaglobal de coordenadas. O sistema local de coordenadas consiste no eixo “s” queencontra-se alinhado ao longo do elemento do nó 1 até o nó 2. O sistema global decoordenadas está fixo e não depende da orientação do elemento.

18

O elemento barra é unidimensional no sistema local de coordenadas, assim osvetores deslocamento e força nodal são definidos como:

u(e) =[u

(e)s1 u

(e)s2

]T(1.32)

f (e) =[f

(e)1s f

(e)2s

]T(1.33)

No sistema global de coordenadas, a força nodal tem duas componentes,similarmente, cada deslocamento nodal tem duas componentes, assim pode-se definiros vetores deslocamento e força nodal como:

u(e) =[u

(e)1 v

(e)1 u

(e)2 v

(e)2

]T(1.34)

f (e) =[f

(e)1x f

(e)1y f

(e)2x f

(e)2y

]T(1.35)

O comprimento do elemento barra pode ser determinado através de seus nós 1 e2, segundo:

L(e) =√(

x(e)2 − x

(e)1

)2+(y

(e)2 − y

(e)1

)2(1.36)

Figura 1.8: Co-senos diretores.

Tomando-se como referência a Figura 1.8, definem-se os valores l(e) e m(e) como:

l(e) = cosφ(e) = x(e)2 − x

(e)1

L(e) (1.37)

m(e) = sinφ(e) = y(e)2 − y

(e)1

L(e) (1.38)

Define-se a matriz de transformação T como:

T(e) =l(e) m(e) 0 0

0 0 l(e) m(e)

(1.39)

Pode-se relacionar os vetores deslocamentos e forças nodais do elemento barra

19

“e” nos sistemas local e global, mediante a matriz de transformação, assim:

u(e) = T(e)u(e) (1.40)

T(e)T f (e) = f (e) (1.41)

Como o elemento barra é unidimensional no sistema de coordenadas local, entãoa matriz de rigidez, referida ao sistema local de coordenadas “s”, é definida como:

K(e) = A(e)E(e)

L(e)

1 −1−1 1

(1.42)

Podem-se relacionar as matrizes de rigidez nos sistemas global e local mediantea matriz de transformação, assim:

K(e) = T(e)T K(e)T(e) (1.43)

Substituindo-se a Equação 1.39 na Equação 1.43 temos que:

K(e) = A(e)E(e)

L(e)

l2

(e)l(e)m(e) −l2(e) −l(e)m(e)

l(e)m(e) m2(e) −l(e)m(e) −m2(e)

−l2(e) −l(e)m(e) l2(e)

l(e)m(e)

−l(e)m(e) −m2(e)l(e)m(e) m2(e)

(1.44)

Da Equação 1.44, pode-se observar que a matriz de rigidez do elemento barradepende do comprimento L, da rigidez axial EA, e do ângulo de orientação φ. Amatriz de rigidez é simétrica e semidefinida positiva e os elementos da diagonal damatriz são zeros ou maiores que zero.

A partir da matriz de rigidez e das forças nodais de cada elemento “e” no sistemaglobal, é feita então a montagem da matriz de rigidez K e das forças nodais f globaisda estrutura em função da conexão entre os elementos [16], obtendo-se a Equaçãode equilíbrio global da estrutura:

Ku = f (1.45)

A matriz de massa do elemento barra é dada por:

M =∫ L

0ρANNTdV (1.46)

sendo ρ a densidade do elemento, N o vetor das funções de forma, e V o volume doelemento.

20

O vetor das funções de forma para o elemento barra é dado por:

NT =[N1 (x) N2 (x)

](1.47)

sendo as funções de forma:

N1 (x) = −x− x2

L(1.48)

N2 (x) = x− x1

L(1.49)

Usando-se as funções de forma e substituindo-se na Equação 1.46 temos que amatriz de massa do elemento barra no sistema local de coordenadas é dada por:

M(e) = ρ(e)A(e)L(e)

6

2 11 2

(1.50)

A matriz de massa no sistema global de coordenadas é dada por:

M(e) = ρ(e)A(e)L(e)

6

2 0 1 00 2 0 11 0 2 00 1 0 2

(1.51)

A montagem da matriz de massa global M é feita da mesma maneira que amontagem da matriz de rigidez.

21

Capítulo 2

Formulação do problema deOtimização Estrutural

2.1 Introdução

A otimização estrutural busca selecionar uma configuração ótima de um conjuntode possíveis candidatos.

Um importante passo na otimização é transcrever as afirmações verbais de umproblema de otimização em uma bem definida afirmação matemática. Na afirmaçãoverbal, o objetivo de um problema de otimização é encontrar o projeto ótimo queminimize (ou maximize) uma função objetivo (ou função custo) sujeita a certasrestrições dadas. Exemplos de funções objetivo em análise estrutural são o peso,a rigidez ou a complacência, a fadiga, o nível de ruído, a amplitude e a frequêncianatural, a segurança, etc [17].

2.2 Componentes de um problema de OtimizaçãoEstrutural

Para formular um problema de otimização estrutural [17] é importante definirtrês componentes do problema: as variáveis de projeto, a função objetivo e a funçãode restrições.

2.2.1 Identificação e definição das variáveis de projeto

As variáveis de projeto em um problema de otimização estrutural podem ser:o tamanho dos elementos, os parâmetros de configuração e, os parâmetros depropriedades físicas e mecânicas [18]. O tamanho de cada elemento, que é a variávelde projeto mais simples, pode representar a área da seção transversal de uma barra,

22

o momento de inércia de um elemento em flexão, ou a espessura de uma placa.A i-ésima variável de projeto denota-se por xi onde i = 1, . . . , n e o conjunto devariáveis são armazenadas em um vetor coluna, tal como visto na Equação 2.1:

x =[x1, . . . , xn

]T(2.1)

sendo n o número de variáveis de projeto. As variáveis de projeto devem serindependentes.

2.2.2 Definição da função objetivo (função custo)

Uma vez definidas as variáveis de projeto, o passo seguinte é definir a funçãoobjetivo do problema. A função objetivo depende das variáveis de projeto. A funçãoobjetivo é a função a minimizar (ou maximizar) em um processo de otimização, e,constitui a base para selecionar um projeto aceitável.

A função objetivo é uma função escalar das variáveis de projeto e, denota-se porf (x), e, representa a propriedade mais importante de um projeto, como o custoou o peso, mas é possível representar a função objetivo como uma função de váriasdas propriedades desejáveis. O peso é a propriedade mais empregada como funçãoobjetivo.

2.2.3 Identificação e definição das restrições

Uma restrição, em qualquer tipo de problema, é uma limitação que deveser satisfeita para que o projeto seja aceitável. A limitação poder ser impostadiretamente em uma variável ou grupo de variáveis (restrição explícita), ou podeainda representar uma limitação sobre quantidades cuja dependência com asvariáveis de projeto não é possível definir diretamente (restrição implícita).

Existem dois tipos de restrições: igualdade e desigualdade. As restrições deigualdade fornecem relações entre as variáveis do projeto ou podem impor condiçõesque deve satisfazer a um projeto viável. Quando a relação é linear, é possível eliminardo processo de otimização uma das variáveis de projeto, e, assim, reduzir o númerode dimensões do problema.

As restrições de desigualdade são mais utilizados em problemas estruturais efornecem os limites de rendimento. Por exemplo, o esforço máximo no projeto deveser menor que o esforço admissível do material. Algumas restrições limitam por cimaou por baixo as variáveis de projeto. A ideia de uma restrição de desigualdade éimportante no projeto estrutural ótimo, para visar a otimalidade é essencial permitirprojetos nos quais nem todas as restrições são satisfeitas diretamente [18].

23

2.3 Tipos de problemas de Otimização Estrutural

Existem três classes de otimização, e na concepção do projeto deve-se escolherqual delas utilizar: otimização dimensional, otimização geométrica e otimizaçãotopológica [3].

2.3.1 Otimização Dimensional

A otimização dimensional utiliza como variável de projeto um parâmetro de umelemento estrutural. No caso de uma estrutura de treliças, a variável de projeto podeser a área da seção transversal da barra, e para uma placa, a variável de projetoé a sua espessura, e, necessita utilizar técnicas de discretização do domínio parapossibilitar a obtenção de uma solução numérica via método dos elementos finitos.

2.3.2 Otimização de Forma

A otimização de forma tem como objetivo definir a melhor fronteira de um sólidocom relação a uma função custo e restrições mecânicas de projeto. O domínio desteproblema necessita ser discretizado para existir um número finito de pontos ao longoda fronteira e, assim, possibilitar uma solução numérica via método dos elementosfinitos.

2.3.3 Otimização Topológica

A otimização topológica tem como objetivo definir, da melhor forma possível,a distribuição de material em um domínio pré-determinado, considerando-se umafunção custo e as restrições mecânicas. A variável de projeto, neste caso, é o própriodomínio, no qual se pode retirar o material, ou seja, criar furos.

O domínio do problema da topologia necessita ser discretizado para se trabalharapenas com um número finito de pontos para se obter uma solução numéricaaproximada das equações diferencias parciais do problema.

2.4 Problema de otimização não linear

Um problema de otimização não linear diferenciável sujeito a restrições dedesigualdade pode ser formulado da seguinte maneira:

minimizarx∈Rn

f (x)


24

onde, x ∈ Rn é o vetor das variáveis de projeto, f : Rn → R é a função objetivoe, g : Rn → Rm é a função das restrições de desigualdade, sendo f e g, funções declasse C1, e, pelo menos uma delas é não linear.

2.4.1 Notações e Definições

Denota-se por x = [x1, . . . , xn]T o vetor das variáveis de projeto, g (x) =[g1 (x) , . . . , gn (x)]T o vetor de restrições, ∇f (x) ∈ Rn o vetor gradiente de f ,∇g (x) ∈ Rn×m a matriz dos gradientes de g. G (x) é uma matriz diagonal talque Gii (x) = gi (x) e λ ∈ Rm é uma variável auxiliar chamada o multiplicador deLagrange.

Definição 2.4.1 (Função Lagrangiana). Define-se a função Lagrangiana L : Rn ×Rm → R, associada ao problema 2.2, como:

L (x,λ) = f (x) + λTg (x) = f (x) +m∑

i=1λigi (x) (2.3)

Definição 2.4.2 (Gradiente da função Lagrangiana). Define-se o gradiente dafunção Lagrangiana em relação a x, associada ao problema 2.2, como:

∇xL (x,λ) = ∇f (x) +m∑

i=1λi∇gi (x) (2.4)

Definição 2.4.3 (Hessiana da função Lagrangiana). Define-se a Hessiana da funçãoLagrangiana H : Rn × Rm → Rn×m, associada ao problema 2.2, como:

H (x,λ) = ∇2f (x) +m∑

i=1λi∇2gi (x) (2.5)

Definição 2.4.4 (Restrição ativa). Uma restrição de desigualdade é chamada ativa,se gi (x) = 0, e, inativa, se gi (x) < 0.

2.4.2 Condições de otimalidade de primeira ordem (KKT)

As condições de otimalidade de primeira ordem de Karush-Kuhn-Tucker,correspondentes ao problema 2.2, podem ser escritas da seguinte maneira:

∇f(x∗) +∇g(x∗)λ∗ = 0 (2.6)G(x∗)λ∗ = 0 (2.7)λ∗ > 0 (2.8)g(x∗) 6 0 (2.9)

25

Definição 2.4.5 (Par de KKT). Um vetor (x∗,λ∗) satisfazendo as Equações 2.6 e2.7 é chamado um par estacionário do problema 2.2 e um par KKT, se este satisfizeras condições de KKT 2.6-2.9.

Definição 2.4.6 (Ponto de KKT). Um vetor x∗ é um ponto estacionário se existeλ∗ tal que as igualdades 2.6 e 2.7 são verdadeiras, e, será um ponto de KKT, setodas as Equações 2.6-2.9 forem confirmadas.

Curvas de nível de

Figura 2.1: Condições de KKT do problema 2.2.

A Figura 2.1 mostra uma interpretação geométrica destas condições [13]. Note-seque o ponto x∗ é um mínimo da função f . Temos somente restrições de desigualdadecom duas variáveis de projeto. A restrição g3 (x) 6 0 é inativa, isto é g3(x∗) < 0;daí λ3 = 0. Pela primeira condição de otimalidade de KKT, temos:

∇f(x∗) +∇g1(x∗)λ1 +∇g2(x∗)λ2 = 0, (2.10)

que é equivalente à:

∇f(x∗) = −∇g1(x∗)λ1 −∇g2(x∗)λ2, (2.11)

onde, λ1 > 0 e λ2 > 0. Portanto, ∇f (x∗) deve ser uma combinação linear dosvetores −∇g1(x∗) e −∇g2(x∗) com coeficientes positivos. Neste caso, os coeficientessão os multiplicadores KKT.

26

2.5 Programação semidefinida (SDP)

A programação semidefinida (SDP) é um tipo de problema de otimização convexacom muitas propriedades numéricas atrativas [5].

YAMASHITA et al. [19] formulam um problema de programação semidefinidanão linear (NL-SDP) da seguinte maneira:

minimizar

x∈Rnf (x)

sujeito a: h (x) = 0X (x) < 0

(2.12)

onde f : Rn → R, h : Rn → Rp e X : Rn → Sm são funções suáveis e de classe C2,Sm denota o conjunto de matrizes reais simétricas de ordem m×m, a matriz X (x)é semidefinida positiva.

O problema 2.12 é uma extensão de um problema SDP linear. Para o caso deproblemas SDP lineares, as funções f e g são lineares e a matriz X (x) é definidacomo:

X (x) =n∑

i=1xiAi −B (2.13)

onde Ai ∈ Sm, i = 1, . . . , n e B ∈ Sm.Os problemas SDP lineares incluem problemas de programação linear, problemas

de programação quadrática convexa e problemas de programação cone de segundaordem, todos eles com diversas aplicações.

Um problema SDP linear pode ser formulado segundo:minimizar tr 〈C,X〉sujeito a: Ai •X = bi, i = 1, . . . ,m

X < 0(2.14)

onde C,Ai ∈ Sn e a matriz X ∈ Sn é semidefinida positiva.

2.6 Formulação tradicional do problema de vo-lume mínimo

Nesta seção, considera-se uma estrutura de treliças elástica linear de dimensãofinita, discretizada pelo método dos elementos finitos. Assumem-se pequenasdeformações.

Denotem-se por m o número de membros da estrutura, n o número de grausde liberdade (gdl), x ∈ Rm o vetor das variáveis de projeto, K (x) ∈ Sn a matrizde rigidez, M (x) ∈ Sn a matriz de massa, s o número de casos de carregamentos,

27

f ∈ Rn×s a matriz que contém os vetores casos de carregamentos fl ∈ Rn, e u ∈ Rn×s

a matriz que contém os vetores deslocamentos ul ∈ Rn. As variáveis de projeto sãoos volumes das barras e as restrições são a Equação de equilíbrio, as frequênciasnaturais e a complacência.

Define-se Equação de equilíbrio ao seguinte sistema linear:

K (x) ul = fl, l = 1, . . . , s (2.15)

O vetor deslocamento ul pode ser obtido através da resolução do sistema lineardado pela Equação 2.15.

O objetivo de um problema de otimização estrutural é encontrar uma estruturacom o menor peso possível que satisfaça à equação de equilíbrio e certas restrições.Na solução do problema, algumas das possíveis barras podem ficar com volume dematerial nulo.

Para estruturas tais como treliças, assume-se que as matrizes de rigidez e massasão funções lineares das variáveis de projeto [1]. Dessa forma, pode-se definir taismatrizes como:

K (x) =m∑

i=1xiKi (2.16)

M (x) =m∑

i=1xiMi (2.17)

onde Ki ∈ Sn e Mi ∈ Sn são matrizes constantes, sendo xiKi e xiMi as matrizesde rigidez e massa dos elementos. Assume-se que xi > 0, para i = 1, . . . ,m, o queimplica que K (x) < 0 e M (x) < 0.

Como as matrizes de rigidez e massa reduzidas Ki e Mi são constantes, entãopode-se calcular a derivada das matrizes em relação a xi como:

∂K (x)∂xi

= Ki (2.18)

∂M (x)∂xi

= Mi (2.19)

2.6.1 Problema de autovalores

A equação diferencial do movimento de uma estrutura para vibrações livres é:

M (x) u + K (x) u = 0 (2.20)

Assume-se que a solução da Equação 2.20 tem a forma:

u = Φejωt (2.21)

28

Substituindo a Equação 2.21 na Equação 2.20, temos:

−ω2M (x) Φejωt + K (x) Φejωt = 0 (2.22)

A Equação 2.22 pode ser escrita como:

[−ω2M (x) Φ + K (x) Φ

]ejωt = 0 (2.23)

Como ejωt 6= 0, então tem-se o seguinte problema de autovalores:

K (x) Φ = λM (x) Φ (2.24)

onde, os autovalores λ são o quadrado das frequências naturais do sistema, ouseja, λ = ω2 e os autovetores associados Φ representam os modos de vibração daestrutura.

Para garantir a existência de uma solução não trivial da Equação 2.24, verifica-seque:

det (K (x)− λM (x)) = 0 (2.25)

O desejável em uma estrutura sob carregamentos dinâmicos é que todas suasfrequências naturais sejam bem maiores do que a máxima frequência possíveldos carregamentos. Para garantir isto, precisa-se impor apenas que a menordas frequências naturais da estrutura seja maior do que um valor previamenteconhecido que considere a maior frequência possível dos carregamentos multiplicadapor um coeficiente de segurança. Com isto, impede-se que a estrutura falhe sobcarregamentos dinâmicos.

Assim, a restrição das frequências naturais para um problema de autovalores [20]pode ser escrita como:

λmin (x) > λ (2.26)

Define-se a função λmin (x) como o menor autovalor do problema (2.24), como:

λmin (x) = min λ : ∃Φ 6= 0 ∈ Rn : K (x) Φ = λM (x) Φ (2.27)

2.6.2 Propriedades do λmin

Define-se o conjunto X como:

X := x ∈ Rn : x > 0 (2.28)

Agora, podem ser definidas algumas propriedades do λmin (x) [8]:

1. λmin (·) é finito e não negativo em X ;

29

2. Para todo x ∈ X ,

λmin (x) = sup λ : K (x)− λM (x) < 0 (2.29)

3. Para todo x ∈ X ,

λmin (x) = infu:M(x)u6=0

uT K (x) uuT M (x) u

(2.30)

4. λmin (·) é semi-contínua superiormente em X ;

5. −λmin (·) é quasiconvexa em X .

Na formulação tradicional do problema de otimização topológica, minimiza-se ovolume ou peso da estrutura, sujeita a condições de equilíbrio e restrições da menorfrequência natural [7].

Levando-se em consideração as afirmações descritas anteriormente, o problemade volume mínimo na formulação tradicional é definido como:

minimizarx∈Rm,u∈Rn×s

m∑i=1

xi

sujeito a: (m∑

i=1xiKi

)ul = fl, l = 1, . . . , s

fTl ul 6 γ, l = 1, . . . , sxi > 0, i = 1, . . . ,mλmin (x) > λ

(2.31)

sendo u ∈ Rn×s a matriz dos vetores deslocamentos, xiKi a matriz de rigidezdos elementos da estrutura, γ o limite superior da complacência, λ o valor limiteda frequência natural. A função objetivo para o problema de mínimo volume é(x,u)→ ∑

xi.A dificuldade desta formulação está na função λmin (x). Esta função pode ser

descontínua [7] quando certas componentes do vetor x são nulos, como é mostradono exemplo seguinte.

Exemplo 2.6.1. Considere a treliça de quatro barras mostrada na Figura 2.2. Atreliça é simétrica com respeito ao eixo x, e somente são consideradas duas variáveisde projeto x1 e x2.

As matrizes de rigidez e massa, que dependem das variáveis de projeto x1 e x2,

30

Figura 2.2: Possível descontinuidade do λmin

são as seguintes:

K (x) =

x1 · 2 0 0 0

0 x1 · 2 0 00 0 x2 · 1, 28 00 0 0 x2 · 0, 32

e

M (x) =

x1 · 2, 83 0 0 0

0 x1 · 2, 83 0 00 0 x2 · 4, 47 00 0 0 x2 · 4, 47

Usando-se a Equação 2.25, os autovalores são:

(λ1, λ2, λ3, λ4) =(

22, 83

x1

x1,

22, 83

x1

x1,1, 284, 47

x2

x2,0, 324, 47

x2

x2

)

Logo, a função λmin (x) tem os seguintes valores:

λmin (x) = 0, 324, 47 ≈ 0, 07, para x2 > 0, x1 > 0

λmin (x) = 22, 83 ≈ 0, 71, para x2 = 0, x1 > 0

e, portanto, tem-se uma descontinuidade em x2 = 0, pelo fato do autovalor 0, 324, 47

x2

x2ser indefinido e λmin (x) “salta” ao segundo menor autovalor.

31

2.7 Formulação SDP do problema de volumemínimo

OHSAKI e KANNO [1] estabelecem que, para estruturas tais como treliças,as matrizes de rigidez e massa são funções lineares das variáveis do projeto, e osproblemas de otimização com restrições de complacência e frequência natural podemser formulados por SDP.

Para reformular um problema de otimização tradicional é necessário definir oseguinte resultado auxiliar mostrado por ACHTZINGER [7].

Proposição 2.7.1. Sejam x ∈ Rm e x > 0 sendo fixos γ ∈ Rn e l = 1, . . . , s.Então existem ul ∈ Rn que satisfaz:

K (x) ul = fl (2.32)

efTl ul 6 γ (2.33)

se e somente se: γ −fl

−fTl K (x)

< 0 (2.34)

Demonstração. Ver [7].Portanto, a formulação do problema de volume mínimo para programação

semidefinida é:

minimizarx∈Rm

m∑i=1

xi

sujeito a: γ −fl

−fTl K (x)

< 0

xi > 0, i = 1, . . . ,mK (x)− λM (x) < 0

(2.35)

Neste problema, γ e λ são dados e, minimiza-se o volume das barrasm∑

i=1xi. Nesta

formulação, o problema é convexo e as funções objetivo e restrições são suaves emrelação à variável de projeto x. Pode-se observar que a restrição de igualdade revertepara a seguinte forma:(

m∑i=1

xiKi

)ul = fl

fTl ul 6 γ

⇔

γ −fl

−fTl K (x)

< 0 (2.36)

32

Além disso, a equivalência entre as restrições do menor autovalor [7] nasformulações tradicional e SDP é:

λmin (x) > λ⇔ K (x)− λM (x) < 0 (2.37)

33

Capítulo 3

Algoritmo de pontos interiores edireções viáveis (FDIPA)

3.1 Introdução

Neste capítulo, apresenta-se o algoritmo de pontos interiores e direções viáveis(FDIPA) proposto por HERSKOVITS [21], para lidar com problemas de otimizaçãonão linear diferenciável com restrições de igualdade e desigualdade. Neste casoem particular, consideram-se somente restrições de desigualdade, portanto, umproblema de otimização não linear diferenciável sujeito a restrições de desigualdadepode ser formulado como se segue:

minimizarx∈Rn

f (x)


onde, x ∈ Rn é o vetor das variáveis de projeto, x = [x1, . . . , xn]T , f : Rn → Ré a função objetivo, g : Rn → Rm é a função das restrições de desigualdade,g (x) = [g1 (x) , . . . , gn (x)]T , f e g são funções de classe C1 e pelo menos umadelas é não linear.

O algoritmo FDIPA converge globalmente para pontos de Karush-Kuhn-Tucker.O algoritmo requer um ponto inicial x, no interior da região definida pelas restriçõesde desigualdades, gerando uma sequência de pontos no interior desta região. Quandotemos somente restrições de desigualdades, a função objetivo é reduzida em cadaiteração.

O método requer somente a solução de dois sistemas de equações lineares, coma mesma matriz em cada iteração, seguida de uma busca linear inexata.

No algoritmo FDIPA, o esquema das iterações é definido como segue:

• Primeiro estágio: define uma direção de descida por meio de resolução de umsistema linear nas variáveis primal e dual;

34

• Segundo estágio: o sistema linear é perturbado de tal forma a se ter umadeflexão na direção de descida e, assim, obter uma direção de descida e viávelpara um problema de otimização não linear.

3.2 Descrição do algoritmo FDIPA

O algoritmo FDIPA é um método de pontos interiores que resolve o problemageral de otimização não linear fazendo iterações nas variáveis de projeto x (variáveisprimárias) e nos multiplicadores de Lagrange (variáveis duais) para resolver ascondições de otimalidade de Karush-Kuhn-Tucker (KKT).

Com o objetivo de garantir convergência para pontos KKT, um sistema éresolvido de tal forma que as Equações 2.8 e 2.9 sejam satisfeitas em cada iteração.

3.2.1 Hipóteses e Definições

Para o desenvolvimento do algoritmo FDIPA, são assumidas as seguinteshipóteses:

Hipótese 3.2.1. Seja Ω ≡ x ∈ Rn : g (x) 6 0 o conjunto de pontos viáveisdo problema (3.1). Então, existe um número real a tal que o conjunto Ωa ≡x ∈ Ω : f (x) 6 a é compacto e tem interior denotado por int (Ωa).

Hipótese 3.2.2. Cada x ∈ int (Ωa) satisfaz g (x) < 0.

Hipótese 3.2.3. As funções f e g são continuamente diferenciáveis em Ωa e suasderivadas satisfazem a condição de Lipschitz em Rn, isto é, existem constantes kf

e kgi, 1 6 i 6 m, tal que para quaisquer x,y ∈ Rn tem-se ‖∇f (y)−∇f (x)‖ 6

kf ‖y− x‖ e ‖∇gi (y)−∇gi (x)‖ 6 kgi ‖y− x‖ , 1 6 i 6 m.

Hipótese 3.2.4 (Condição de regularidade). Um ponto x ∈ Ωa é chamado regular seo conjunto ∇gi (x) : gi (x) = 0, 1 6 i 6 m é linearmente independentes para todox. O FDIPA requer a hipótese de regularidade em uma solução local do problema(3.1).

Seguem algumas definições que foram utilizadas ao longo do trabalho:

Definição 3.2.1 (Direção de descida). Um vetor d ∈ Rn é uma direção de descidade uma função suave φ : Rn → R se dT∇φ < 0.

Definição 3.2.2 (Direção viável). Um vetor d ∈ Rn é uma direção viável doproblema (3.1), em x ∈ Ω, se existe θ > 0 tal que x + td ∈ Ω para todo t ∈ [0, θ].

35

Definição 3.2.3 (Campo de direções viáveis). Um vetor campo d (x) definido emΩ é chamado um campo uniforme de direções viáveis do problema (3.1), se existeum tamanho de passo τ > 0, tal que x + td (x) ∈ Ω, para todo t ∈ [0, τ ] e, paratodo x ∈ Ω.

Segundo HERSKOVITS [22] que d é uma direção viável se dT∇gi (x) < 0 paratodo i tal que gi (x) = 0.

Dado um ponto interior inicial, o FDIPA gera uma sequênciaxk

k∈Nde pontos

interiores tais que:f(xk) < f(x) (3.2)

egi(xk) < 0, para i = 1, . . . ,m (3.3)

que convergem para o conjunto de pontos KKT do problema (3.1).

3.2.2 Cálculo da direção de busca

Em cada iteração, uma direção de busca d é calculada, a qual é uma direçãode descida para a função objetivo e também uma direção viável em Ω. A seguir, osistema linear é perturbado para produzir uma deflexão na direção de descida, nosentido do interior da região viável, de modo a obter uma direção de descida viávelem Ω. Uma busca linear é feita para garantir que o novo ponto pertença ao interiore que o valor da função objetivo decresça.

Como consequência da exigência de viabilidade, d deve constituir um campouniforme de direções viáveis. Caso contrário, o comprimento do passo pode tendera zero, forçando a convergência para pontos que não são KKT.

Resolve-se o sistema de equações (2.6) e (2.7) em (x,λ) por métodos iterativosde ponto fixo. Isto é feito de tal maneira que as Equações 2.8 e 2.9 são confirmadasem cada iteração. Desta forma, obtém-se as soluções das Equações 2.6 e 2.7 que sãopares KKT do problema (5.1).

Uma iteração de Newton para a solução do sistema de Equações 2.6 e 2.7 em(x,λ) é indicado como:

Bk ∇g(xk)Λk∇gT (xk) G(xk)

xk+1 − xk

λk+10 − λk

= −∇f(xk) +∇g(xk)λk

G(xk)λk

(3.4)

onde (xk,λk) é o ponto inicial da iteração, (xk+1,λk+1) é a nova estimativa, Bk

é uma matriz simétrica definida positiva de ordem n × n que pode ser, a própriaHessiana H (x,λ), uma aproximação dela obtida por alguma técnica Quase-Newtonou a matriz identidade, e Λ é uma matriz diagonal da forma Λii ≡ λi.

36

Introduzindo algumas modificações na iteração (3.4), obtém-se, para um dadopar interior (x,λ), uma nova estimativa com valor da função objetivo menor.

Define-se uma direção d0 no espaço primal como d0 = xk+1−xk, então, obtém-seo sistema linear em (dk

0,λk+1):

Bkdk0 +∇g(xk)λk+1

0 = −∇f(xk) (3.5)Λk∇gT (xk)dk

0 + G(xk)λk+10 = 0 (3.6)

A solução (d0,λ0) deste sistema fornece uma direção d0 no espaço primal e umanova estimativa para λ.

Entretanto, d0 pode não ser uma direção viável, pois quando alguma restriçãose aproxima de zero, d0 tende a uma direção tangente ao conjunto viável.

De fato, a Equação 3.6 é equivalente à:

λki∇gT

i (xk)dk0 + gi(xk)λk+1

0i = 0, i = 1, . . . ,m (3.7)

o que implica ∇gTi (xk)dk

0 = 0, para i tal que gi(xk) = 0.

3.2.3 Direção viável

Para evitar este efeito, adiciona-se um vetor negativo no lado direito da Equação3.6 e define-se um novo sistema linear em (d,λ):

Bkdk +∇g(xk)λk+1 = −∇f(xk) (3.8)

Λk∇gT (xk)dk + G(xk)λk+1 = −ρkλk (3.9)

onde, ρ > 0, d é a nova direção e, λ é a nova estimativa de λ. Neste caso, a Equação3.9 é equivalente à:

λki∇gT

i (xk)dk + gi(xk)λk+1i = −ρkλk

i , i = 1, . . . ,m (3.10)

e, ∇gTi (xk)dk < 0, para as restrições ativas tais que λk

i 6= 0. Assim, dk é umadireção viável.

A inclusão do termo negativo do lado direito da Equação 3.6 produz o efeitode deflexão de dk

0, proporcional à ρ na região viável. Como a deflexão de dk0 é

proporcional à ρ, e, dk0 é uma direção de descida em f , é possível encontrar uma

estimativa para ρ que assegure que d seja uma direção viável e de descida, ver [22].Como, dT

0∇f (x) < 0, impondo:

dkT∇f(xk) 6 ξdkT

0 ∇f(xk), ξ ∈ (0, 1) (3.11)

37

o que implica que dkT∇f(xk) < 0.Em geral, a taxa de descida de f ao longo de dk é menor que a longo de dk

0,constituindo-se no custo a pagar para que a direção calculada seja viável.

Vamos considerar o seguinte sistema auxiliar:

Bkdk1 +∇g(xk)λk+1

1 = 0 (3.12)Λk∇gT (xk)dk

1 + G(xk)λk1 = −λk (3.13)

pode-se calcular dk da seguinte forma:

dk = dk0 + ρdk

1 (3.14)

A substituição da Equação 3.14 na Equação 3.11 resulta em:

ρ 6 (ξ − 1) dkT

0 ∇f(xk)dkT

1 ∇f(xk)(3.15)

3.2.4 Busca Linear

Finalmente, para encontrar um novo ponto primal viável e uma diminuiçãosatisfatória da função objetivo, procede-se a busca linear inexata como Armijo,descrita em LUENBERGER [23] ao longo de dk. Diferentes regras de atualizaçãopodem ser adotados para definir uma nova estimativa de λk+1.

Figura 3.1: Direção de busca do algoritmo FIDPA.

A Figura 3.1, representa a direção de busca no caso em que se tem duas variáveisde projeto e uma restrição ativa, isto é g(xk) = 0. O ponto xk fica na fronteira, ed0 é tangente à restrição, mas d é viável.

38

3.3 Algoritmo FDIPA

Nesta seção, apresenta-se a versão básica do algoritmo FDIPA para problemascom restrições de desigualdade que convergem globalmente a pontos de KKT noespaço primal do problema (3.1). Na verdade, obtém-se uma família de algoritmos,estabelecendo-se diferentes regras para atualização da matriz B e do vetor λ. Istopermite a implementação de diferentes versões, dependendo do problema a serresolvido, sobre a informação disponível das funções f e g, e, sobre a taxa deconvergência desejada.

O algoritmo FDIPA será descrito abaixo de forma resumida, a fim de se entendero seu funcionamento.

Parâmetros: ξ ∈ (0, 1), η ∈ (0, 1), ϕ > 0 e ν ∈ (0, 1)

Dados Inicias: x ∈ Ω0a, 0 < λ ∈ Rm e B ∈ Rn×n simétrica e definida positiva.

Passo 1: Cálculo da direção de busca

Passo 1a: Resolva o sistema linear para obter d0 e λ0.

Bd0 +∇g (x)λ0 = −∇f (x) (3.16)Λ∇gT (x) d0 + G (x)λ0 = 0 (3.17)

Se d0 = 0, parar.

Passo 1b: Resolva o sistema linear para obter d1 e λ1

Bd1 +∇g (x)λ1 = 0 (3.18)Λ∇gT (x) d1 + G (x)λ1 = −λ (3.19)

Passo 1c: Se dT1∇f (x) > 0, calcule

ρ = minϕ ‖d0‖2 , (ξ − 1) dT

0∇f (x)dT

1∇f (x)

(3.20)

caso contrário, faça:ρ = ϕ ‖d0‖2

2 (3.21)

Passo 1d: Calcule a direção de busca d e o vetor λ

d = d0 + ρd1 (3.22)

eλ = λ0 + ρλ1 (3.23)

39

Passo 2: Busca LinearCalcule o comprimento do passo t, o primeiro número da série 1, ν, ν2, ν3, . . .,tal que:

f (x + td) 6 f (x) + tη∇fT (x) d (3.24)

egi (x + td) < 0, se λi > 0, i = 1, . . . ,m (3.25)

ougi (x + td) 6 gi (x) , se λi < 0, i = 1, . . . ,m (3.26)

Passo 3: Atualizações

Passo 3a: Obtenha o novo ponto, como: x := x + td.

Passo 3b: Defina novos valores para B simétrica definida positiva.

Passo 3c: Defina novos valores para λ > 0. A seguinte atualização para λ jáfoi considerada por HERSKOVITS [22],

λi := max[λ0i, ε ‖d0‖2

], ε > 0, para i = 1, . . . ,m

Passo 3d: Retorne ao Passo 1.

40

Capítulo 4

Algoritmo de pontos interiores edireções viáveis para programaçãosemidefinida (FDIPA-SDP)

4.1 Introdução

No presente capítulo, apresentaremos o algoritmo de pontos interiores e direçõesviáveis para programação semidefinida, denominado FDIPA-SDP, para lidar comproblemas de otimização estrutural.

No algoritmo original, proposto por Aroztegui [2], foi modificada a matriz dosistema linear, que será descrita na seção 4.3.2, na qual utilizou-se o produto deKronecker no lugar do produto simétrico de Kronecker, com a finalidade de se obteruma matriz diagonalizável, tal como foi mostrada na Figura 1.4.

Mostram-se algumas notações e definições necessárias para o desenvolvimentodo algoritmo FDIPA-SDP, que é descrito na seção 4.4.

4.2 Notações e definições

SHAPIRO [24] formulou um problema de programação semidefinida não linear(NL-SDP) da seguinte maneira:

minimizarx∈Rn

f (x)

sujeito a: G (x) 4 0(4.1)

onde, x ∈ Rn é o vetor das variáveis de projeto, f : Rn → R é a função objetivoe G : Rn → Sm é um mapeamento de Rn no espaço Sm das matrizes simétricasm×m.

41

Assume-se que as funções f e G são suaves. As componentes da função G sãodenotas por gij. Dado que G ∈ Sm é uma matriz simétrica, tem-se que gij = gji.

Para as matrizes A,B ∈ Sm, a notação A < B (ou a notação A 4 B) significaque a matriz A−B é semidefinida positiva (ou semidefinida negativa) e o produtoescalar ou interno das matrizes denota-se por 〈A,B〉 = tr

(AT B

).

Denote-se por λ1 (A) 6 · · · 6 λm (A) os autovalores da matriz A ∈ Sm, dispostosna ordem decrescente, sendo λmin (A) = λ1 (A) o menor autovalor da matriz A.Denote-se por ⊗ o produto de Kronecker das matrizes.

Denote-se por Gi (x) = ∂G (x) /∂xi ∈ Rm×m as matrizes das derivadas parciaisde G, com i = 1, . . . , n, definida como:

Gi (x) = ∂G∂xi

(x) =

∂g11

∂xi

(x) . . .∂g1m

∂xi

(x)... . . . ...

∂g1m

∂xi

(x) . . .∂gmm

∂xi

(x)

(4.2)

Denote-se por ∇G (x) ∈ Rn×m2 a derivada do mapeamento G (·) em x, isto é,∇G (x) é uma transformação linear de Rn em Sm definida por:

∇G (x) = ∂G∂x

(x) =

vec (G1(x))T

...vec (Gm(x))T

(4.3)

Exemplo 4.2.1. Seja a matriz de restrições:

G (x) =x1 + x2 0

0 x1 − x2

As matrizes das derivadas parciais são:

G1 = ∂G∂x1

(x) =1 0

0 1

e

G2 = ∂G∂x2

(x) =1 0

0 −1

Neste exemplo, o número de variáveis é n = 2, a matriz G é de ordem 2 e,

portanto, o gradiente da matriz de restrições é uma matriz de ordem n × m2, ouseja, 2× 4, a cual ter a seguinte forma:

∇G (x) =1 0 0 1

1 0 0 −1

42

Definição 4.2.1 (Região viável). Define-se Ω o conjunto de pontos viáveis doproblema 4.1 como:

Ω = x ∈ Rn : G (x) ≺ 0 (4.4)

Definição 4.2.2 (Função Lagrangiana). Define-se a função Lagrangiana L : Rn ×Sm → R do problema (4.1) como:

L (x,Λ) = f (x) + 〈Λ,G (x)〉 (4.5)

onde Λ ∈ Sm, Λ < 0 e 〈·, ·〉 denota o produto interno de matrizes. Usando-sea seguinte notação g (x) = vec (G(x)) e λ = vec (Λ), então, redefine-se a funçãoLagrangiana como:

L (x,λ) = f (x) +⟨gT (x) ,λ

⟩(4.6)

Definição 4.2.3 (Gradiente da função Lagrangiana). Usando a Equação 4.3, define-se o gradiente da função Lagrangiana em relação a x, como:

∇xL (x,λ) = ∇f (x) +∇G (x)λ (4.7)

4.3 Condições de otimalidade de primeira ordemde KKT

As condições de otimalidade de primeira ordem de Karush-Kuhn-Tuckercorrespondentes ao problema (4.1) podem ser escritas da seguinte forma:

∇f (x∗) +∇G (x∗)λ∗ = 0 (4.8)Λ∗G (x∗) = 0 (4.9)G (x∗) 4 0 (4.10)

Λ∗ < 0 (4.11)

Definição 4.3.1 (Ponto estacionário). Um ponto x∗ é um ponto estacionário doproblema 4.1 se existe Λ∗ ∈ Sm tal que as Equações 4.8-4.10 são verificadassimultaneamente.

Definição 4.3.2 (Ponto regular). Seja p = dim (ker (G (x))) a dimensão do núcleode G (x), e, seja b1, . . . , bp uma base ortonormal do núcleo de G (x). O ponto x∗

é um ponto regular do problema (4.1) se o conjunto de vetores:bT

i G1 (x) bj

...bT

i Gm (x) bj

: i 6 j, i, j = 1, . . . , p

(4.12)

43

é linearmente independente.

Teorema 4.3.1 (Condição de regularidade). A condição de Mangasarian-Fromovitz[24] se verifica no ponto x∗ ∈ Rn se existe um vetor d ∈ Rn tal que:

G(x∗) +n∑

k=1diGi(x∗) ≺ 0 (4.13)


Proposição 4.3.1. Seja x ∈ Ω. G é diferenciável em x e E0 =[b1 . . . bn

]é a

matriz formada pela base ortonormal de G (x). A seguinte condição garante que dé uma direção viável do problema (4.1) em x:

ET0∂G∂d

E0 ≺ 0 (4.14)


Definição 4.3.3. Um ponto de Karush-Kuhn-Tucker (KKT) do problema 4.1 é umponto estacionário x∗ associado a Λ ∈ Sm tal que:

Λ∗ < 0 (4.15)

4.4 Descrição do algoritmo FDIPA-SDP

4.4.1 Matriz do sistema linear

Define-se uma função vetorial φ : Rn+m2 → Rn+m2 , tal que:

φ (x,λ) =φl (x,λ)φc (x,λ)

(4.16)

onde:φl (x,λ) = ∇f (x) +∇G (x)λ (4.17)

eφc (x,λ) = vec (ΛG(x)) (4.18)

Usam-se as propriedades do produto de Kronecker, descritas na seção 1.4.1, coma finalidade de vetorizar o produto ΛG. Portanto, o termo φc (x,λ) da funçãovetorial φ pode ser definida de duas maneiras:

φc (x,λ) = vec(ΛG(x)I) = (I⊗Λ)vec(G(x)) (4.19)

44

ouφc (x,λ) = vec(IΛG(x)) = (G(x)⊗ I)vec(Λ) (4.20)

Para calcular as raízes da função pelo método de Newton, calcula-se a matrizJacobiana de φ. O cálculo da matriz Jacobiana implica a derivação de φ em relaçãoàs duas variáveis x e Λ.

O gradiente da função vetorial φ tem a seguinte forma:

∇φ (x,λ) =∇xφl (x,λ) ∇λφl (x,λ)∇xφc (x,λ) ∇λφc (x,λ)

(4.21)

Derivando-se a Equação 4.17 em relação às variáveis x e λ, respectivamente,temos:

∇xφl (x,λ) = ∇xxL (x,λ) ; (4.22)

e∇λφl (x,λ) = ∇G (x) (4.23)

A Equação 4.22 representa a Hessiana da função Lagrangiana do problema (4.1)e é denotada por H (x,λ).

Da mesma forma, derivando-se as Equações 4.19 e 4.20 em relação às variáveisx e λ, respectivamente, temos:

∇xφc (x,λ) = (I⊗Λ)∇ (G(x))T ; (4.24)

e∇λφc (x,λ) = G(x)⊗ I (4.25)

Substituindo-se as Equações 4.22 - 4.25 na Equação 4.21, temos que o gradienteda função vetorial φ, é:

∇φ (x,λ) = ∇xxL (x,λ) ∇G (x)

(I⊗Λ)∇ (G(x))T G(x)⊗ I

(4.26)

Finalmente, substituindo, na Equação 4.26, a Hessiana H (x,λ) por uma matrizB ∈ Sm

++, pode-se definir a matriz do sistema linear de NewtonW ∈ R(n+m2)×(n+m2)

como:

W (x,B,Λ) = B ∇G (x)

(I⊗Λ)∇G (x)T G (x)⊗ I

(4.27)

onde, Λ 0, B 0, x ∈ Ωa e, a matriz W (x,B,Λ) é invertível. A matriz Bpoderá ser uma matriz quase-Newton [23] ou uma matriz identidade.

45

4.4.2 Cálculo da direção de busca

Em cada iteração do algoritmo, uma direção de busca dk é calculada. Pretende-se que dk seja uma direção viável para o problema 4.1 e de descida para a funçãoobjetivo f no ponto xk.

O cálculo da direção de busca dk se realiza em duas etapas. Ambas etapasenvolvem a resolução de um sistema linear baseado no método de Newton pararesolver o sistema não linear de equações:

∇f(xk) +∇G(xk)λk = 0 (4.28)ΛkG(xk) = 0 (4.29)

Dados o ponto inicial xk ∈ int (Ωa), Λk ∈ Sm e Bk ∈ Sm. Um novo ponto(xk+1,λk+1

0 ) é obtido resolvendo-se o seguinte sistema linear: Bk ∇G(xk)

(I⊗Λk)∇G(xk)T G(xk)⊗ I

xk+1 − xk

λk+10 − λk

= −∇f(xk) +∇G(xk)λk

vec(ΛkG(xk))

(4.30)

Define-se uma direção dk0 no espaço primal, como dk

0 = xk+1−xk. Assim, obtém-se o seguinte sistema linear:

Bkdk0 +∇G(xk)λk+1

0 = −∇f(xk) (4.31)(I⊗Λk)∇GT (xk)dk

0 + (G(xk)⊗ I)λk+10 = 0 (4.32)

Contudo, d0k não é necessariamente uma direção viável.

4.4.3 Direção viável

Para obter uma direção viável, outro sistema linear, com a mesma matrizW (x,B,Λ), deve ser resolvido. Neste caso:

B ∇G (x)(I⊗Λ)∇G (x)T G (x)⊗ I

dλ

=−∇f (x)−ρλ

(4.33)

onde, ρ é um número real positivo.Se dkT

0 ∇f(xk) < 0 então dk0 é uma direção de descida para f em x. Em geral, a

taxa de descida de f ao longo de dk é menor que ao longo de dk0, ou seja:

dkT∇f (x) 6 ξdkT

0 ∇f (x) (4.34)

onde ξ é um parâmetro fixo no intervalo (0, 1).A condição 4.34 é a mesma que à utilizada no algoritmo FDIPA.

46

A direção dk do sistema linear (4.33) pode ser obtida resolvendo-se o seguintesistema alternativo:

Bkdk1 +∇G(xk)λk+1

1 = 0 (4.35)(I⊗Λk)∇G(xk)T dk

1 + (G(xk)⊗ I)λk+11 = −λ (4.36)

e logo define-se dk como:dk = dk

0 + ρdk1 (4.37)

eΛk = Λk

0 + ρΛk1 (4.38)

Substituindo a Equação 4.34 na Equação 4.37, pode-se definir a cota superior deρ da forma:

ρ 6 (ξ − 1) dkT

0 ∇f (x)dkT

1 ∇f (x)(4.39)

se dkT

1 ∇f (x) > 0. Caso contrário, se dkT

1 ∇f (x) 6 0, assume-se que:

ϕ 6 ‖d0‖2 (4.40)

para algum parâmetro fixo ϕ > 0, definido em [21].

4.4.4 Busca linear

Para obter o novo ponto xk+1, realiza-se uma minimização inexata de Armijo[23] ao longo da direção dk de maneira que xk+1 ∈ int (Ωa).

A busca linear de Armijo consiste em achar o passo t, ou seja, o primeiro elementoda sequência 1, ν, ν2, ν3, . . ., tal que:

f (x + td) 6 f (x) + tηdT∇f (x) (4.41)

eG (x + td) ≺ 0 (4.42)

onde η ∈ (0, 1) e ν ∈ (0, 1) são parâmetros fixos.A condição dada pela Equação 4.41 em t garante que a função é reduzida a η

vezes a função linear tangente a f em t = 0.Na Figura 4.1 temos que P1 (t) = f(xk) + tηdk∇f(xk). O passo aceitável está

no intervalo [tl, tu], e pode-se deduzir que tl = inf (1, νtu) [21].

47

Intervalo Admissível

Figura 4.1: Busca Linear de Armijo.

4.4.5 Atualização

Realizam-se operações que preparam os dados para uma nova iteração. Estes são:

1. Atualização do ponto: xk+1 = xk + tkdk;

2. Atualização da matriz quase-Newton Bk com uma nova matriz simétricadefinida positiva;

3. Atualização de Λk+1.

4.5 Algoritmo FDIPA-SDP

O algoritmo de pontos interiores e direções viáveis para programação semidefinida(FDIPA-SDP) consiste no seguinte:

Parâmetros: ξ ∈ (0, 1), η ∈ (0, 1), ϕ > 0, e ν ∈ (0, 1).

Dados Inicias: x ∈ int (Ω), B ∈ Sn++ e Λ = µI ∈ Sm

++.

Passo 1: Cálculo da direção de busca

Passo 1a: Resolva o sistema linear para obter d0 ∈ Rn e λ0 ∈ Rm.

Bd0 +∇G (x)λ0 = −∇f (x) (4.43)(I⊗Λ)∇GT (x) d0 + (G(x)⊗ I)λ0 = 0 (4.44)

Se d0 = 0, parar.

48

Passo 1b: Resolva o sistema linear para obter d1 ∈ Rn e λ1 ∈ Rm

Bd1 +∇G (x)λ1 = 0 (4.45)(I⊗Λ)∇GT (x) d1 + (G(x)⊗ I)λ1 = −λ (4.46)

Passo 1c: Se dT1∇f (x) > 0, calcule

ρ = minϕ ‖d0‖2 , (ξ − 1) dT

0∇f (x)dT

1∇f (x)

(4.47)

caso contrário, calculeρ = ϕ ‖d0‖2 (4.48)

Passo 1d: Calcule a direção de busca d e Λ

d = d0 + ρd1 (4.49)

eΛ = Λ0 + ρΛ1 (4.50)

Passo 2: Busca LinearCalcule o comprimento do passo t, o primeiro número da série 1, ν, ν2, ν3, . . .,tal que:

f (x + td) ≤ f (x) + tη∇fT (x) d (4.51)

eG (x + td) ≺ 0 (4.52)

Passo 3 Atualizações

Passo 3a: Obtenha o novo ponto, como: x := x + td;

Passo 3b: Defina novos valores para B ∈ Sm++;

Passo 3c: Defina novos valores para Λ = µI ∈ Sm++;

Passo 3d: Retorne ao Passo 1.

49

Capítulo 5

Testes Numéricos

No presente capítulo, apresentam-se problemas resolvidos com o algoritmoFDIPA-SDP tais como:

1. Problema algébrico 43 de quatro variáveis de projeto e sujeito a três restriçõesde desigualdade, extraído da Coleção de Problemas Teste de SCHITTKOWSI[10];

2. Problema de otimização estrutural de uma treliça de 10 barras, no qualminimiza-se o peso da estrutura sob restrições de complacência e frequêncianatural;

3. Problema de otimização estrutural de uma treliça de 10 barras, no qualminimiza-se o peso da estrutura sob restrições de complacência, frequêncianatural e deslocamentos verticais.

Em todos os problemas teste foram assumidos os seguintes parâmetros para oalgoritmo FDIPA-SDP:

• Para o cálculo da deflexão ρ: ξ = 0.8 e ϕ = 1;

• Para a busca linear de Armijo: η = 0.1 e ν = 0.7;

• Número máximo de iterações: 100;

• Passo inicial na busca linear de Armijo: t = 1;

• Número máximo de iterações na busca linear de Armijo: 20.

Todos os problemas numéricos resolvidos com o algoritmo FDIPA-SDP sãoconvexos.

Os sistemas primal-dual do FDIPA-SDP são resolvidos através de métodosdiretos.

50

Realiza-se a atualização da matriz quase-Newton utilizando-se o método BFGS,e calcula-se o gradiente das restrições de deslocamentos pelo método de diferençasfinitas.

Se consideraram exemplos numéricos com número de variáveis de projeto enúmero de restrições pequenos, devido ao tamanho do gradiente da matriz derestrições.

As condições de parada do algoritmo FDIPA-SDP são a norma da direção debusca e a norma do gradiente da função lagrangiana:

• ‖d0‖ < 1.0× 10−4;

• ‖glag‖ < 1.0× 10−4.

Os resultados dos problemas numéricos estão organizados da seguinte maneira:

• Cada exemplo está em uma seção diferente;

• Nas Tabelas 5.1, 5.2 e 5.4, utilizou-se a seguinte notação:

– Iter : Iteração k;

– f : Valor da função objetivo avaliada no ponto xk;

– ‖d0‖ : Norma da direção de busca no ponto xk;

– ‖glag‖ : Gradiente da Função Lagrangiana;

– Passo : Comprimento do passo tk da busca linear de Armijo;

– NIBL : Número de iterações na busca linear de Armijo.

• Nas Figuras 5.1, 5.4 e 5.6, mostram-se a convergência do algoritmo FDIPA-SDP para os Exemplos 1, 2 e 3, respectivamente.

• A evolução da redução do volume das barras das estruturas feita pelo algoritmoFDIPA-SDP para os Exemplos 2 e 3 está indicada nas Tabelas 5.2 e 5.4,respectivamente.

• Nas Tabelas 5.3 e 5.5 mostram-se a solução ótima para as estruturas dosExemplos 2 e 3, respectivamente.

51

5.1 Exemplo 1 - Problema 43

O Exemplo 1 é o problema 43, extraído da Coleção de Problemas Teste deSCHITTKOWSI [10].

Representa um problema algébrico com quatro variáveis de projeto e trêsrestrições de desigualdade.

A formulação do problema 43 é a seguinte:

minimizarx∈Rn

x21 + x2

2 + 2x23 + x2

4 − 5x1 − 5x2 − 21x3 + 7x4

sujeito a: −8 + x21 − x2

2 − x23 − x2

4 − x1 + x2 − x3 + x4 6 0−8 + x2

1 − x22 − x2

3 − x24 − x1 + x2 − x3 + x4 6 0

−8 + x21 − x2

2 − x23 − x2

4 − x1 + x2 − x3 + x4 6 0

A descrição do problema 43 é o seguinte:

• Número de variáveis: n = 4

• Número de restrições: m = 3

• Função objetivo:

f (x) = x21 + x2

2 + 2x23 + x2

4 − 5x1 − 5x2 − 21x3 + 7x4

• Restrições:

g1 (x) = −8 + x21 − x2

2 − x23 − x2

4 − x1 + x2 − x3 + x4

g2 (x) = −8 + x21 − x2

2 − x23 − x2

4 − x1 + x2 − x3 + x4

g3 (x) = −8 + x21 − x2

2 − x23 − x2

4 − x1 + x2 − x3 + x4

• Ponto inicial viável: x0 = (0, 0, 0, 0)

• Função avaliada no ponto inicial: f (x0) = 0

• Ponto ótimo: x∗ = (0, 1, 2,−1)

• Função avaliada no ponto ótimo: f (x∗) = 0

A Figura 5.1 mostra a convergência do algoritmo FDIPA-SDP para o Exemplo1. Pode-se observar que a solução ótima foi obtida após 58 análises.

A Tabela 5.1 mostra a solução ótima do Exemplo 1, na qual se pode observarque a solução ótima foi obtida após 18 iterações.

52

Tabela 5.1: Otimização do exemplo 1

Iter f |d0| |glag| Passo NIBL0 0.0001 -34.473 2.0802e+01 2.0802e+01 0.118 72 -42.521 5.5908e+00 5.5908e+00 0.240 53 -43.169 2.7154e+00 2.7154e+00 0.118 74 -43.667 2.6386e−01 2.2702e−01 0.700 25 -43.863 1.3016e−01 8.5965e−01 0.700 26 -43.979 9.5906e−02 2.7799e−01 1.000 17 -43.993 7.4843e−02 4.4019e−01 0.490 38 -43.999 3.9759e−02 2.0961e−01 0.700 29 -44.000 1.5402e−02 1.1826e−01 0.490 310 -44.000 6.3037e−03 5.4891e−02 0.700 211 -44.000 1.8316e−03 1.6030e−02 0.700 212 -44.000 5.4530e−04 4.7691e−03 0.700 213 -44.000 1.6355e−04 1.4303e−03 0.700 214 -44.000 4.1875e−04 4.1875e−04 0.700 215 -44.000 2.7311e−04 2.1542e−03 0.700 216 -44.000 7.1243e−04 9.0652e−04 0.343 417 -44.000 8.8829e−04 1.4319e−03 0.169 618 -44.000 1.5963e−04 8.7683e−04 0.343 4

0 10 20 30 40 50 60−45

−40

−35

−30

−25

−20

−15

−10

−5

0

NF: avaliações da função objetivo

f(x)

: val

or d

a fu

nção

obj

etiv

o

Figura 5.1: Convergência do algoritmo FDIPA-SDP para o Exemplo 1

53

5.2 Exemplo 2 - Treliça de 10 barras

Trata-se de um exemplo de otimização de uma estrutura de treliças formadapor 10 barras, onde procura-se minimizar o peso total da estrutura tendo-se comorestrições a complacência e as frequências naturais.

As variáveis fundamentais do problema são os volumes das barras da estrutura.Na solução do problema algumas das barras poderão resultar com um volume dematerial nulo.

Figura 5.2: Treliça de 10 barras com carregamento simples

A Figura 5.2 mostra a geometria da estrutura composta por 6 nós, com asseguintes características :

• Número de barras: 10;

• Número de variáveis de projeto: 10;

• Número de graus de liberdade: 8;

• Nós fixos: 1 e 2;

• Módulo de elasticidade: 100;

• Densidade: 1;

• Tamanho de cada barra horizontal e vertical: 1;

• Número de estados de carregamento: 1;

54

• Magnitude da carga: 1 aplicada no nó 5;

• Restrição na complacência: γ = 1;

• Restrição na frequência natural: λ = 5× 10−2.

De acordo com a numeração dos graus de liberdade da Figura 5.2, o vetorcarregamento é:

f1 =

00000−100

Assim, a formulação do Exemplo 2 é a seguinte:

minimizarx∈Rm

m∑i=1

xi

sujeito a: γ −fl

−fTl K (x)

< 0

xi > 0, i = 1, . . . ,mK (x)− λM (x) < 0

Figura 5.3: Otimização da treliça de 10 barras do Exemplo 2.

A Figura 5.3 mostra a solução ótima da estrutura para o Exemplo 2, formadapelos nós 1, 2, 3, 4 e 5 e as barras 1, 2, 3, 5, 7, 8 e 9. O nó 6 e as barras 4, 6 e 10não formam parte da solução.

55

Tabela 5.2: Evolução da redução do volume da estrutura do Exemplo 2.

Iter f |d0| |glag| Passo NIBL0 1.000001 0.99583 4.4557e−03 4.4557e−03 1.000 12 0.89398 2-7332e−01 2-7332e−01 0.490 33 0.85715 2.8520e−01 2.8520e−01 0.168 64 0.81121 1.2339e−01 4.9012e−02 0.490 35 0.77508 5.0299e−02 2.1974e−02 1.000 16 0.73737 5.4857e−02 1.4694e−02 1.000 17 0.65262 1.2048e−01 3.9842e−02 1.000 18 0.60684 9.1925e−02 1.7668e−02 0.700 29 0.59518 8.0023e−02 3.1456e−02 0.240 510 0.56596 7.6019e−02 1.6008e−02 0.700 211 0.55117 2.8951e−02 2.8980e−03 0.700 212 0.54256 1.0079e−02 7.4907e−04 1.000 113 0.54240 3.3673e−04 7.4958e−05 0.490 314 0.54233 1.7341e−04 3.2063e−05 0.490 315 0.54226 7.2674e−05 5.6995e−06 1.000 1

0 5 10 15 20 25 30 350.5

0.55

0.6

0.65

0.7

0.75

0.8

0.85

0.9

0.95

1


f(x)

: val

or d

a fu

nção

obj

etiv

o

Figura 5.4: Convergência do algoritmo FDIPA-SDP para o Exemplo 2.

56

Tabela 5.3: Estrutura ótima obtida para a treliça de 10 barras do exemplo 2.

Elemento No. Volume Inicial Volume Final1 0.1000 0.073592 0.1000 0.073673 0.1000 0.147224 0.1000 0.000005 0.1000 0.000016 0.1000 0.000007 0.1000 0.123828 0.1000 0.000029 0.1000 0.0000010 0.1000 0.12389

Densidade 1.0000 1.0000Peso 1.0000 0.54226NF 35

A Figura 5.4 mostra a convergência do algoritmo FDIPA-SDP para o Exemplo2.

A Tabela 5.2 mostra a evolução da redução do volume da estrutura do Exemplo2 e a Tabela 5.3 mostra o volume final da estrutura obtida após 35 análises.

5.3 Exemplo 3 - Treliça de 10 barras sujeita arestrições de deslocamento

A treliça do presente exemplo tem a mesma configuração do exemplo 2, na qualpossui tem uma restrição adicional, o deslocamento vertical u = 0, 1 dos nós 3, 4, 5e 6.

Portanto, a formulação do Exemplo 3 é a seguinte:

minimizarx∈Rm

m∑i=1

xi

sujeito a: γ −fl

−fTl K (x)

< 0

xi > 0, i = 1, . . . ,mK (x)− λM (x) < 0ul 6 u

57

Figura 5.5: Otimização da treliça de 10 barras para o Exemplo 3.

0 10 20 30 40 50 60 700.88

0.9

0.92

0.94

0.96

0.98

1


f(x)

: val

or d

a fu

nção

obj

etiv

o

Figura 5.6: Convergência do algoritmo FDIPA-SDP da treliça de 10 barras doexemplo 3.

A figura 5.5 mostra a estrutura ótima obtida para o exemplo 3, e a Figura 5.6mostra a convergência do algoritmo FDIPA-SDP para o exemplo 3 após 64 análises.

58

Tabela 5.4: Evolução da redução do volume da estrutura do Exemplo 3.

Iter Objetivo (f) |d0| |glag| Passo (t) Iterlin0 1.000001 0.99820 4.4557e−03 2.0554e−03 1.000 12 0.95743 5.1139e−02 5.1139e−02 1.000 13 0.90405 7.0380e−02 7.0380e−02 1.000 14 0.90233 5.6872e−02 2.0754e−02 0.040 105 0.90001 7.4276e−03 2.8959e−03 0.343 46 0.89864 2.9915e−03 1.5438e−03 0.490 37 0.89854 1.7519e−03 9.1171e−04 0.058 98 0.89758 9.5598e−04 1.3475e−04 1.000 19 0.89722 7.3805e−04 1.2905e−04 0.490 310 0.89721 4.1792e−04 1.2881e−05 0.014 1311 0.89708 1.8483e−04 1.0294e−06 0.700 212 0.89680 2.8294e−04 3.5985e−06 1.000 113 0.89680 2.9603e−05 5.1964e−06 0.028 1114 0.89679 1.4275e−05 6.9193e−09 1.000 115 0.89678 1.4444e−05 5.1918e−08 0.700 2

Tabela 5.5: Estrutura ótima obtida para a treliça de 10 barras do exemplo 3.

Elemento No. Volume Inicial Volume Final1 0.1000 0.08382 0.1000 0.10693 0.1000 0.08574 0.1000 0.10295 0.1000 0.11106 0.1000 0.10217 0.1000 0.05628 0.1000 0.05589 0.1000 0.095610 0.1000 0.0968

Densidade 1.0000 1.0000Peso 1.0000 0.8968NF 63

59

Capítulo 6

Conclusões

Neste trabalho foi desenvolvido uma método para resolver problemas deotimização estrutural mediante a programação semidefinida, através do algoritmoFDIPA-SDP.

O método foi baseado no algoritmo proposto Aroztegui [2] em sua Tese deDoutorado no ano 2010.

Com relação ao trabalho feito por Aroztegui [2], realizou-se uma mudança namatriz do sistema linear, descrita na Equação 4.27. Neste caso, utilizou-se o produtode Kronecker no lugar do produto simétrico de Kronecker, com a finalidade deresolver problemas de otimização estrutural que envolvam restrições de frequêncianatural, complacência e deslocamentos.

Por este motivo, foram descritas algumas notações e definições matemáticasnecessárias para a formulação de problemas de programação semidefinida aplicadosna otimização estrutural. Alem disso, foi feita uma comparação entre o produto deKronecker e o produto simétrico de Kronecker através da distribuição dos elementosmatriciais, tal como foi mostrado nas Figuras 1.4 e 1.5.

Foram formulados problemas de otimização estrutural em duas versões: aformulação tradicional e a formulação SDP. Foi feita uma descrição do algoritmoFDIPA-SDP e foi implementado no MATLAB.

O algoritmo desenvolvido neste trabalho mostrou-se eficaz na solução deproblemas de otimização estrutural sujeitos a restrições matriciais. Os resultadosnuméricos foram mostrados nas Figuras 5.3 e 5.5.

Sugestões para trabalhos futurosComo parte dos estudos futuros, destacam-se os seguintes tópicos:

• Estudar possíveis regras de atualização da matriz B.

• Resolver, de forma eficiente, a matriz do sistema linear (4.27) com a finalidadede solucionar problemas de otimização estrutural com grande número de

60

elementos.

• Explorar mais problemas que possam ser resolvidos com o algoritmo deprogramação semidefinida SDP, como por exemplo:

– Minimizar a máxima complacênciaNeste problema, minimiza-se a complacência (maximiza-se a rigidez) daestrutura sujeita à condição de equilíbrio e, tem-se como restrições omínimo autovalor e o volume da estrutura.

– Maximizar o mínimo autovalorNeste problema, maximiza-se o menor autovalor sujeito à condição deequilíbrio e, tem-se como restrições a complacência e o volume.

• Otimização multi-objetivo: Estender as ideias aqui apresentadas paraconsiderar problemas da forma:

minimizarx∈Rn

f (x) = (f1(x), . . . , fs(x))

sujeito a: g (x) 6 0

onde a função objetivo fi : Rn → R e g : Rn → R.

61

Referências Bibliográficas

[1] OHSAKI, M., KANNO, Y., “Semidefinite Programming for Structural Optimi-zation”, In: Advances in Structural Optimization, chap. 19, pp. 541–567,World Scientific, 2007.

[2] AROZTEGUI, M., Técnicas de programação semidefinida e aplicações emotimização de material, Tese de D.Sc., COPPE/UFRJ, Rio de Janeiro,RJ, Brasil, 2010.

[3] FRANÇA, M. D., Uma Técnica para Otimização Estrutural mediante a DerivadaTopológica, Dissertação de M.Sc., COPPE/UFRJ, Rio de Janeiro, RJ,Brasil, 2007.

[4] WEI, L., TANG, T., XIE, X., et al., “Truss optimization on shape and sizingwith frequency constraints based on parallel genetic algorithm”, ISSMO -Journal of the International Society for Structural and MultidisciplinaryOptimization, v. 43, pp. 665–682, 2011.

[5] KLERK, E. D., Aspects of Semidefinide Programming: Interior Point Algorithmsand Selected Applications. Kluber Academic Publishers: USA, 2004.

[6] CASTELEIRO, M., Una metodología general para optimización estructuralen diseño asistido por computadora, Tesis de doctorado, UniversidadPolitécnica de Cataluña, España, 1987.

[7] ACHTZINGER, W., KOCVARA, M., “Structural Topology Optimization withEigenvalues”, SIAM Journal on Optimization, v. 18, pp. 1129–1164, 2007.

[8] BEN-TAL, A., NEMIROVSKI, A., “Robust Truss Topology Design viaSemidefinite Programming”, SIAM Journal on Optimization, v. 7,pp. 991–1016, 1997.

[9] OHSAKI, M., FUJISAWA, K., KATOH, K., et al., “Semi-definite program-ming for topology optimization of trusses under multiple eigenvalueconstraints”, Computer Methods in Applied Mechanics and Engineering,v. 180, pp. 203–217, 1999.

62

[10] HOCK, W., SCHITTKOWSKI, K., Test examples for Nonlinear ProgrammingCodes, Lecture Notes in Economics and Mathematical System. v. 187.Springer-Verlag: Berlin, Germany, 1981.

[11] LIMA, E. L., Análise Real. v. 1. Coleção Matemática Universitária, 2011.

[12] HORN, R. A., JOHNSON, C. R., Matrix Analysis. Cambridge University Press,1985.

[13] CHONG, E., ZAK, S., An Introduction to Optimization. John Wiley & Sons:USA, 2001.

[14] CHANDRUPATLA, T., BELEGUNDU, A., Introducción al estudio delElemento Finito en Ingeniería. 2nd ed. Prentice Hall, 1999.

[15] OÑATE, E., Cálculo de estructuras por el Método de Elementos Finitos.Análisis estático Lineal. 1st ed. Centro Internacional de Métodos enIngeniería: España, 1992.

[16] ELOY, L., Método dos Elementos Finitos em Análise de Estruturas. ElsevierEditora, 2011.

[17] KIM, N., SANKAR, B., Introduction to Finite Element Analysis and Design.John Wiley & Sons, 2009.

[18] GALLAGHER, R., “Diseño Estructural Óptimo - Una Reseña”, RevistaInternacional de Métodos Numéricos para Cálculo y Diseño en Ingeniería,v. 1, pp. 3–20, 1985.

[19] YAMASHITA, H., YABE, H., HARADA, K., “A primal-dual interiorpoint method for Nonlinear Semidefinite Programming”, MathematicalProgramming, v. 132, n. 1–2, pp. 1–30, 2012.

[20] BENDSOE, M., SIGMUND, O., Topology Optimization. Theory, Methods andApplications. Springer-Verlag: Germany, 2003.

[21] HERSKOVITS, J., “A feasible directions interior-point technique for nonlinearoptimization”, JOTA - Journal of Optimization Theory and Applications,v. 99, pp. 53–58, 1998.

[22] HERSKOVITS, J., “A View on Nonlinear Optimization”, In: Advances inStructural Optimization, v. 25, chap. 3, pp. 71–116, Kluber AcademicPublishers, 1995.

63

[23] LUENBERGER, D. G., YE, Y., Linear and Nonlinear Programming. 3rd ed.Springer: Nueva York, USA, 2008.

[24] SHAPIRO, A., “First and Second Order Analysis of Nonlinear SemidefinitePrograms”, Mathematical Programming, v. 77, pp. 301–320, 1997.

64

Documents

OTIMIZAÇÃOESTRUTURALMEDIANTEPROGRAMAÇÃO ...w2.files.scire.net.br/atrio/ufrj-pem_upl/THESIS/21/...OTIMIZAÇÃOESTRUTURALMEDIANTEPROGRAMAÇÃO SEMIDEFINIDA ElmerGiovanniBazánCórdova