Otimização (matemática)

A otimização é um ramo da matemática que tenta modelar, analisar e resolver analiticamente ou numericamente os problemas que devem minimizar ou maximizar uma função em um conjunto.

A otimização desempenha um papel importante na pesquisa operacional (um campo na fronteira entre a ciência da computação , matemática e economia ), na matemática aplicada (fundamental para a indústria e engenharia ), análise e análise numérica. , Em estatísticas para a estimativa da probabilidade máxima de uma distribuição , para a busca de estratégias no âmbito da teoria dos jogos , ou na teoria de controle e comando .

Muitos sistemas que podem ser descritos por um modelo matemático são otimizados. A qualidade dos resultados e das previsões depende da relevância do modelo, da escolha certa das variáveis que se pretende otimizar, da eficiência do algoritmo e dos meios de processamento digital .

História e nome

antiguidade

Os primeiros problemas de otimização foram formuladas por Euclides , o III ª século aC, na sua obra histórica itens . Trezentos anos depois, Heron de Alexandria em Catoptrica afirma o "princípio do caminho mais curto" no contexto da óptica (ver figura).

Introdução ao cálculo diferencial

No XVII th século, o surgimento de cálculo leva à invenção de técnicas de otimização, ou pelo menos faz sentir a necessidade. Newton desenvolve um método iterativo que permite encontrar os extremos locais de uma função , colocando em jogo a noção de derivada , resultante de seu trabalho com Leibniz . Essa nova noção permite grandes avanços na otimização de funções, pois o problema se reduz à busca das raízes da derivada.

Durante o XVIII th século, o trabalho de matemáticos Euler e Lagrange levam ao cálculo das variações , um ramo da análise funcional que envolve vários métodos de otimização. Este último inventa uma técnica de otimização sob restrições: os multiplicadores de Lagrange .

Desenvolvimentos, aplicativos e nome

O XIX ª século foi marcado pelo crescente interesse dos economistas para a matemática. Eles estabelecem modelos econômicos que devem ser otimizados, o que acelera o desenvolvimento da matemática. A partir deste período, a otimização tornou-se um pilar da matemática aplicada e a profusão de técnicas é tal que não se pode resumir em poucas linhas.

Pode-se mesmo assim evocar a invenção de vários métodos iterativos usando o gradiente da função , bem como o uso do termo “programação matemática”, para designar problemas de otimização.

Historicamente, o primeiro termo introduzido foi o de "programação linear", cunhado por George Dantzig por volta de 1947. O termo "programação" neste contexto não se refere à programação de computadores (embora os computadores sejam amplamente usados hoje para resolver problemas. Programas matemáticos). Vem do uso da palavra "programa" pelas forças armadas americanas para estabelecer horários de treinamento e escolhas logísticas , que Danzig estava estudando na época. O uso do termo "programação" também foi de interesse para liberar fundos em um momento em que o planejamento estava se tornando uma prioridade para os governos .

Assim, a partir de 1939, o matemático Leonid Kantorovich iniciou um trabalho teórico sobre otimização linear com o objetivo de desenhar aplicações concretas para a otimização da produção econômica planejada da União Soviética .

O termo "programação matemática", que requer a longa explicação acima, tende a ser abandonado. Por exemplo, em junho de 2010, a sociedade internacional culta que representa essa disciplina viu seu nome anterior Mathematical Programming Society ser alterado para Mathematical Optimization Society ; pelo mesmo motivo, hoje preferimos usar as expressões “linear / quadrática /… otimização” ao invés de “linear / quadrática /… programação”

Definições

Minimização

Mais formalmente, a otimização é o estudo de problemas que são expressos como segue.

Problema de otimização - Dada uma função definida em um conjunto com valores no conjunto de números reais (possivelmente na linha completa ), encontre um elemento de tal que para all in . $f: A \ rightarrow \ mathbb {R}$ $NO$ $\ mathbb {R}$ ${\ displaystyle {\ overline {\ mathbb {R}}}: = \ mathbb {R} \ cup \ {- \ infty, + \ infty \}}$ ${\ bar x}$ $NO$ ${\ displaystyle f ({\ bar {x}}) \ leqslant f (x)}$ $x$ $NO$

Dizemos que buscamos minimizar a função ao longo do conjunto . $f$ $NO$

A função tem vários nomes: função de custo ou simplesmente custo , função objetivo ou simplesmente objetivo , critério , etc. $f$

O conjunto é chamado de conjunto admissível e os pontos de são chamados de pontos admissíveis do problema (especialmente quando ele faz parte de outro conjunto e não queremos que pertença ao complementar ). Dizemos que o problema é realizável se não for vazio (o conjunto admissível é frequentemente definido implicitamente, seu caráter não vazio não é necessariamente óbvio, o que justifica a necessidade desse conceito de realizabilidade). $NO$ $NO$ $B$ ${\ bar x}$ $B \ setminus A$ $NO$

O ponto é denominado solução do problema de otimização (ou mínimo ou minimizador ). Às vezes, também é chamado de solução global para diferenciá-lo dos conceitos locais apresentados a seguir. Diz-se ser um bare mínimo se e para tudo . ${\ bar x}$ ${\ displaystyle {\ bar {x}} \ in A}$ ${\ displaystyle f ({\ bar {x}}) <f (x)}$ ${\ displaystyle x \ in A \ setminus \ {{\ bar {x}} \}}$

Podemos escrever esse problema de maneiras diferentes:

${\ displaystyle \ inf _ {x \ in A} \, f (x) \ quad {\ mbox {ou}} \ quad \ inf {\ {f (x) \ mid x \ in A \}} \ quad { \ mbox {ou}} \ quad \ inf {f (A)} \ quad {\ mbox {ou}} \ quad \ left \ {{\ begin {array} {l} \ inf {f (x)} \\ x \ in A. \ end {array}} \ right.}$

Às vezes, notamos todas as soluções para o problema. ${\ displaystyle \ operatorname {arg \, min} \, \ {f (x) \ mid x \ in A \}}$

O conjunto é parte de (ou se seus valores estão em ) e seu limite inferior (ou mínimo) é chamado de valor ótimo do problema. Este valor ótimo é alcançado (ou seja, existe tal que ) se, e somente se, o problema de otimização tiver uma solução. Sim , dizemos que o problema é limitado . ${\ displaystyle f (A): = \ {f (x) \ mid x \ in A \}}$ $\ mathbb {R}$ ${\ displaystyle {\ overline {\ mathbb {R}}}}$ $f$ ${\ displaystyle {\ overline {\ mathbb {R}}}}$ ${\ displaystyle \ inf {f (A)}}$ ${\ displaystyle {\ bar {x}} \ in A}$ ${\ displaystyle f ({\ bar {x}}) = \ inf \, f (A)}$ ${\ displaystyle \ inf {f (A)}> - \ infty}$

Dizemos que o problema é convexo se for uma parte convexa de um espaço vetorial e se for uma função convexa ligada . ${\ displaystyle \ inf {\ {f (x) \ mid x \ in A \}}}$ $NO$ $f$ $NO$

Maximização

O problema descrito acima é um problema de minimização . Como nós temos

${\ displaystyle \ sup _ {x \ in A} {f (x)} = - \ inf _ {x \ in A} \ left (-f (x) \ right),}$

um problema de maximização de função (à esquerda acima) é equivalente ao problema de minimização de (à direita acima). Equivalência aqui significa que as soluções são as mesmas e que os valores ótimos são opostos. Em particular, um método para analisar / resolver um problema de minimização pode ser usado para analisar / resolver um problema de maximização. $f$ $-f$

Solução local

Sob certas condições, o processo de otimização encontra o máximo geral. Mas em alguns casos de otimização - como redes neurais artificiais , o resultado pode ser uma solução local.

Um máximo local é um ponto tal que existe um bairro onde para todos , . Um mínimo local é definido de forma semelhante. $no$ $NO$ $V$ $x \ in V$ ${\ displaystyle f (x) \ leqslant f (a)}$

Geralmente é fácil determinar numericamente os máximos locais com algoritmos de descida - como com o Algoritmo de Gradiente . Para verificar se a solução encontrada é um máximo global , às vezes é possível recorrer a conhecimentos adicionais sobre o problema. Dependendo da natureza da ou da função , vários teoremas fornecem propriedades particulares da solução que simplificam sua pesquisa (ver princípio do máximo ). $NO$ $f$

Otimização combinatória

Na maioria das vezes, é um subconjunto do espaço euclidiano . Quando é um subconjunto de ou , consistindo de vetores que satisfazem um certo número de restrições (do tipo igualdade ou desigualdade), falamos de otimização combinatória . $NO$ $\ mathbb {R} ^ {n}$ $NO$ ${\ displaystyle \ mathbb {N} ^ {n}}$ ${\ displaystyle \ mathbb {N} ^ {p} \ times \ mathbb {R} ^ {q}}$

Algumas classes de problemas

A otimização é dividida em subdisciplinas sobrepostas, de acordo com a forma da função objetivo e das restrições: a otimização em dimensão finita ou infinita (estamos falando aqui da dimensão do espaço vetorial das variáveis a serem otimizadas) , otimização contínua ou combinatória (as variáveis a serem otimizadas são discretas no último caso), otimização diferenciável ou não suave (qualifica aqui a regularidade das funções que definem o problema), otimização linear (funções afins), quadrática (objetivo quadrático e restrições afins), semi-definida positiva (a variável a ser otimizada é uma matriz para a qual a positividade semi-definida é necessária ), copositive (a variável a ser otimizada é uma matriz para a qual a co -positividade é necessária ), cônica (generalização das disciplinas anteriores, em que minimizamos uma função linear na intersecção de um cone e um subespaço afim), convexa ( funções convexas ), não linear , o comando otimização e otimizada , estocástica (en) e robusta (presença de perigos), otimização multicritério ( busca-se um compromisso entre vários objetivos contraditórios), otimização algébrica (funções polinomiais), otimização de dois níveis , otimização sob restrições de complementaridade , o disjuntivo otimização (o conjunto admissível é uma reunião de conjuntos), etc.

Essa abundância de disciplinas vem do fato de que praticamente qualquer classe de problemas modeláveis pode levar a um problema de otimização, desde que introduzamos parâmetros a serem otimizados. Além disso, as condições de otimalidade desses problemas de otimização às vezes fornecem expressões matemáticas originais que, pelo mecanismo anterior, por sua vez, levam a novos problemas de otimização.

A otimização linear estuda o caso em que a função objetivo e as restrições que caracterizam todas são lineares . É um método amplamente utilizado para estabelecer programas de refinaria de petróleo, mas também para determinar a composição mais lucrativa de uma mistura salgada, sob restrições, a partir dos preços atuais de mercado. $NO$
A programação inteira estuda os problemas de otimização linear em que algumas ou todas as variáveis são restringidas para assumir valores inteiros. Esses problemas podem ser resolvidos por diferentes métodos: separação e avaliação , método dos planos secantes .
A otimização quadrática estuda o caso em que a função objetivo é uma forma quadrática (com restrições lineares ) $NO$
A otimização não linear considerando o caso geral em que a lente ou as restrições (ou ambas) contêm porções não lineares, possivelmente não convexas.
A otimização estocástica (in) estuda o caso em que algumas das restrições dependem de variáveis aleatórias . Na otimização robusta , pressupõe-se que os perigos estejam localizados em intervalos em torno das posições nominais e buscamos otimizar o sistema sujeito a tais perigos, no pior dos casos.
A programação dinâmica usa a propriedade de que uma solução consiste em soluções necessariamente subótimas (nota: o oposto não é verdade em geral) para decompor o problema evitando a explosão combinatória . Pode ser usado quando a função objetivo é uma soma de funções monotônicas crescentes cujos argumentos são desconhecidos distintos. É uma programação dinâmica que permite, por exemplo:
- fabricantes de aeronaves para encontrar os melhores planos de decolagem para suas máquinas,
- engenheiros de bacia para distribuir a produção de mineração entre seus diferentes poços,
- produtores de eletricidade para planejar a operação de usinas hidrelétricas,
- aos planejadores de mídia para distribuir com eficiência um orçamento de publicidade entre as diferentes mídias.

Métodos numéricos

Uma técnica para resolver um problema de otimização matemática denota aqui

a transformação do problema original em um problema equivalente,
um método teórico cuja descrição permite o desenvolvimento de um algoritmo numericamente aplicável.

A escolha de uma técnica apropriada depende de

a natureza da função objetivo , de sua regularidade ( continuidade , derivabilidade ), de propriedades específicas ( paridade , convexidade ), do conhecimento de vizinhanças de seus extremos, $f$
constrangimentos que caracterizam o conjunto de pontos admissíveis. $NO$

Simplificações

Para encontrar uma solução para a otimização, o problema original é substituído por um problema equivalente. Por exemplo, é possível alterar as variáveis permitindo a decomposição do problema em subproblemas ou a substituição de incógnitas possibilitando a redução do seu número.

A técnica do multiplicador de Lagrange permite superar certas restrições; este método equivale a introduzir penalidades crescentes à medida que o ponto se aproxima das restrições. Um algoritmo de Hugh Everett torna possível atualizar de forma consistente os valores dos multiplicadores a cada iteração para garantir a convergência. Ele também generalizou a interpretação desses multiplicadores para aplicá-los a funções que não são contínuas nem deriváveis. O lambda expressa um coeficiente de penalidade (noção de custo marginal de uma restrição na economia ).

Encontrando Zeros de Gradiente

Muitos métodos e algoritmos permitem encontrar um zero da derivada de (alguns são específicos para as funções de uma variável ) ou de seu gradiente . Eles se aplicam validamente em situações onde as restrições sobre não são muito ativas. $f$ $\ mathbf {\ nabla} f$ $NO$

Todos esses métodos são desenvolvidos dentro da estrutura de um processo iterativo .

Essas abordagens podem apresentar algumas falhas:

A função deve ser regular o suficiente (pelo menos localmente) para ser diferenciável (ou mesmo duas vezes diferenciável para acessar a matriz de Hessian ou uma aproximação dela).
Nem sempre é possível expressar expressamente o gradiente da função objetivo.
As condições iniciais precisam ser definidas antes de iniciar o processo iterativo. A escolha inicial pode influenciar consideravelmente o resultado (divergência do processo iterativo). Os métodos de convergência rápida são geralmente mais sensíveis deste ponto de vista.
Em certos casos, a velocidade de convergência pode ser desastrosa: as iterações sucessivas progridem laboriosamente (estagnação) ao longo de um vale estreito ( função de Rosenbrock ).
Se a solução obtida for de fato um extremo (depois de verificar se não é um ponto de sela ), este pode acabar sendo local.

Caso particular: Quando é polinomial de grau 2 em seus argumentos (forma quadrática e linear ) e sem restrição, cancelar o gradiente equivale a resolver um sistema linear (cf Categoria: Análise numérica de matriz ). $f$

Métodos analíticos diretos

Nesta categoria, a maioria dos algoritmos gerais se aplica a situações em que as restrições sobre não são muito ativas. Eles são baseados em algumas idéias dominantes: $NO$

Movimentos ao longo de uma linha realizada por um gradiente.
Aproximação por uma função mais simples (por exemplo, a expansão de Taylor de ordem 2), atualizada durante as iterações. $f$

Várias melhorias foram feitas para evitar:

estagnações (por exemplo, método de gradiente conjugado em otimização não linear (em) )
o cálculo explícito ou muito frequente da matriz Hessiana (por exemplo BFGS )

As mesmas falhas mencionadas na categoria anterior também podem ocorrer aqui.

O algoritmo Categoria: Otimização apresenta uma lista e dá acesso a esses métodos.

Técnicas de otimização combinatória

As técnicas de otimização combinatória lidam com problemas em que uma parte (pelo menos) das variáveis do conjunto assume valores discretos . Nós os encontramos dentro da estrutura de $NO$

a teoria dos grafos ( caminho ideal cujo problema com o caixeiro viajante )
a teoria do jogo ( desempenho de estratégia )
a teoria de controle , regulação e automático (cf Categoria: Automático )
a otimização multidisciplinar

Heurísticas e metaheurísticas

Para resolver problemas difíceis (por exemplo, aqueles com muitos extremos locais pobres), técnicas foram desenvolvidas para determinar pontos que não são estritamente ótimos, mas aproximam-se deles. Esses métodos, chamados de heurísticas e metaheurísticas , geralmente são baseados em fenômenos físicos, biológicos, sócio-psicológicos ou por acaso. Os campos de aplicação são vastos e freqüentemente se estendem muito além dos problemas para os quais foram originalmente projetados.

o recozimento simulado
o método Nelder-Mead com recozimento simulado
os algoritmos de colônias de formigas
os algoritmos genéticos
os algoritmos evolutivos
métodos de otimização de enxame de partículas

A Categoria: Metaheurística apresenta uma lista e dá acesso a esses métodos.

Técnicas de otimização multiobjetivo

Os problemas de otimização multiobjetivo vão além do quadro estrito da definição dada acima: até um ponto admissível, a função objetivo não associa um valor numérico, mas um ponto de um conjunto que na maioria das vezes será associado a um vetor. O objetivo é então otimizar simultaneamente todos os componentes deste vetor. Pode-se também ver a otimização multiobjetivo como um conjunto de problemas de otimização que dependem dos mesmos parâmetros, tendo objetivos possivelmente contraditórios, e que se busca resolver da melhor forma possível.

Em geral, o espaço no qual o vetor solução é expresso é fornecido com uma ordem parcial envolvendo critérios de dominância (por exemplo, em relação à fronteira de Pareto ). A resolução consiste em encontrar um ponto admissível cujo objetivo não seja dominado por nenhum outro.

Áreas de aplicação

Eles são extremamente variados: otimização de uma rota , a forma de um objeto , um preço de venda , uma reação química , controle de tráfego aéreo , a eficiência de um dispositivo, o funcionamento de um motor , a gestão de linhas ferroviárias, a escolha do econômico investimentos, a construção de um navio , etc. A otimização destes sistemas permite encontrar uma configuração ideal, para obter uma economia de esforço, tempo, dinheiro, energia, matéria-prima, ou mesmo satisfação.

Os problemas da dinâmica de sólidos indeformáveis (especialmente a dinâmica de corpos rígidos articulados) muitas vezes precisam de técnicas de otimização matemática, uma vez que podemos ver a dinâmica de corpos rígidos como a resolução de uma equação diferencial ordinária em uma variedade restrita; as restrições são várias restrições geométricas não lineares, como "esses dois pontos devem sempre coincidir" ou "este ponto deve estar sempre nesta curva". Além disso, o problema de cálculo das forças de contato pode ser concluído resolvendo um problema de complementaridade linear , que também pode ser visto como um problema de otimização quadrática.

Vários problemas de projeto também podem ser expressos como problemas de otimização. Esse aplicativo é chamado de otimização de forma. Um subconjunto recente e crescente deste campo é denominado Otimização Multidisciplinar que, embora útil em vários problemas, tem sido particularmente aplicado a problemas de engenharia e tecnologia espacial .

Outra área que usa técnicas de otimização é a pesquisa operacional .

A otimização é uma das ferramentas centrais da microeconomia que se baseia no princípio da racionalidade e otimização do comportamento, lucro para as empresas e utilidade para os consumidores .

Na mecânica, existem três formas de otimização:

otimização de tamanho ou otimização paramétrica , que consiste em otimizar dimensões (comprimento, espessura, diâmetro, etc.) da estrutura mecânica;
a otimização da forma , que consiste em otimizar a envolvente de uma divisão sem alterar a topologia, ou seja, sem adicionar furos na peça;
a otimização da topologia , que envolve variar a distribuição do material dentro de um determinado volume inicial.

Longe de constituir uma lista exaustiva, esses poucos exemplos atestam a variedade de formulações e prenunciam a diversidade de ferramentas matemáticas capazes de resolver esses problemas.

Notas e referências

(fr) Este artigo foi retirado parcial ou totalmente do artigo da Wikipedia em inglês intitulado " Otimização (matemática) " ( veja a lista de autores ) .

Sebastian Xhonneux, " Percepção de Otimização em Matemática e Economia ao Longo dos Séculos e o Ensino do Teorema de Lagrange " , na APMEP ,27 de outubro de 2008(acessado em 15 de março de 2010 ) .
Ver o artigo " Método de Newton ".
(in) GB Danzig, "Maximização de uma função linear de variáveis sujeitas a desigualdades lineares" em Tj. C. Koopmans, Activity Analysis of Production and Allocation , Nova York, Wiley,1951, p. 339-347.
(em) " Mathematical Optimization Society (MOS) ' on mathopt.org .
M. Gori e A. Tesi , “ On the problem of local mínimos in backpropagation ”, IEEE Transactions on Pattern Analysis and Machine Intelligence , vol. 14, n o 1,1992, p. 76–86 ( ISSN 0162-8828 , DOI 10.1109 / 34.107014 , ler online , acessado em 21 de agosto de 2019 )
Catherine Vayssade, " Otimização mecânica, Otimização topológica " ,2004(acessado em 24 de dezembro de 2008 ) .

Veja também

Obras gerais

(en) JF Bonnans, J. Ch. Gilbert, C. Lemaréchal e C. Sagastizábal, Numerical Optimization - Theoretical and Numerical Aspects [ detalhe das edições ]
(en) JF Bonnans e A. Shapiro, Perturbation analysis of optimization problems , Springer, 2000 ( ISBN 978-0-387-98705-7 )
(in) Christodoulos A. Floudas Pardalos e Panos M. (eds) Encyclopedia of Optimization , 2 a edição, 2009 ( ISBN 978-0-387-74758-3 )
Michel Minoux, Programação matemática - teoria e algoritmos , edições Dunod, 1983 ( ISBN 2040154876 )

links externos

" O rio " [PDF] , em ÉducMath : problema do caminho mais curto entre duas casas que passam pelo rio
(en) Guia NEOS
(pt) " Glossário de programação matemática "