Otimização convexa - Convex optimization

Otimização convexa é um subcampo da otimização matemática que estuda o problema de minimizar funções convexas sobre conjuntos convexos . Muitas classes de problemas de otimização convexa admitem algoritmos de tempo polinomial, enquanto a otimização matemática é geralmente NP-difícil .

A otimização convexa tem aplicações em uma ampla gama de disciplinas, como sistemas de controle automático , estimativa e processamento de sinais , comunicações e redes, projeto de circuitos eletrônicos , análise e modelagem de dados, finanças , estatísticas ( projeto experimental ideal ) e otimização estrutural , onde o conceito de aproximação tem se mostrado eficiente. Com os avanços recentes em algoritmos de computação e otimização , a programação convexa é quase tão direta quanto a programação linear .

Definição

Um problema de otimização convexa é um problema de otimização em que a função objetivo é uma função convexa e o conjunto viável é um conjunto convexo . Uma função de mapeamento de alguns subconjuntos de dentro é convexa se o seu domínio é convexa e para todos e todos no seu domínio, a seguinte condição: . Um conjunto S é convexo se, para todos os membros e todos , tivermos isso . ${\ displaystyle f}$${\ displaystyle \ mathbb {R} ^ {n}}$${\ displaystyle \ mathbb {R} \ cup \ {\ pm \ infty \}}$${\ displaystyle \ theta \ in [0,1]}$${\ displaystyle x, y}$${\ displaystyle f (\ theta x + (1- \ theta) y) \ leq \ theta f (x) + (1- \ theta) f (y)}$${\ displaystyle x, y \ in S}$${\ displaystyle \ theta \ in [0,1]}$${\ displaystyle \ theta x + (1- \ theta) y \ in S}$

Concretamente, um problema de otimização convexa é o problema de encontrar algum consecução ${\ displaystyle \ mathbf {x ^ {\ ast}} \ in C}$

${\ displaystyle \ inf \ {f (\ mathbf {x}): \ mathbf {x} \ in C \}}$,

onde a função objetivo é convexa, como é o conjunto viável . Se tal ponto existe, ele é referido como um ponto ideal ou solução ; o conjunto de todos os pontos ótimos é chamado de conjunto ótimo . Se for ilimitado abaixo ou se o mínimo não for atingido, o problema de otimização é considerado ilimitado . Caso contrário, se for o conjunto vazio, o problema é considerado inviável . ${\ displaystyle f: {\ mathcal {D}} \ subseteq \ mathbb {R} ^ {n} \ to \ mathbb {R}}$${\ displaystyle C}$${\ displaystyle f}$${\ displaystyle C}$${\ displaystyle C}$

Forma padrão

Um problema de otimização convexa está na forma padrão se for escrito como

${\ displaystyle {\ begin {align} & {\ underset {\ mathbf {x}} {\ operatorname {minimize}}} && f (\ mathbf {x}) \\ & \ operatorname {subject \ to} && g_ {i} (\ mathbf {x}) \ leq 0, \ quad i = 1, \ dots, m \\ &&& h_ {i} (\ mathbf {x}) = 0, \ quad i = 1, \ dots, p, \ end {alinhado}}}$

onde é a variável de optimização, a função é convexa, , , são convexos, e , , são afim . Esta notação descreve o problema de encontrar que minimiza entre todos satisfazendo , e , . A função é a função objetivo do problema, e as funções e são as funções de restrição. ${\ displaystyle \ mathbf {x} \ in \ mathbb {R} ^ {n}}$${\ displaystyle f: {\ mathcal {D}} \ subseteq \ mathbb {R} ^ {n} \ to \ mathbb {R}}$${\ displaystyle g_ {i}: \ mathbb {R} ^ {n} \ to \ mathbb {R}}$${\ displaystyle i = 1, \ ldots, m}$${\ displaystyle h_ {i}: \ mathbb {R} ^ {n} \ to \ mathbb {R}}$${\ displaystyle i = 1, \ ldots, p}$${\ displaystyle \ mathbf {x} \ in \ mathbb {R} ^ {n}}$${\ displaystyle f (\ mathbf {x})}$${\ displaystyle \ mathbf {x}}$${\ displaystyle g_ {i} (\ mathbf {x}) \ leq 0}$${\ displaystyle i = 1, \ ldots, m}$${\ displaystyle h_ {i} (\ mathbf {x}) = 0}$${\ displaystyle i = 1, \ ldots, p}$${\ displaystyle f}$${\ displaystyle g_ {i}}$${\ displaystyle h_ {i}}$

O conjunto viável do problema de otimização consiste em todos os pontos que satisfazem as restrições. Este conjunto é convexo porque é convexo, os conjuntos de subnível de funções convexas são convexos, os conjuntos afins são convexos e a interseção de conjuntos convexos é convexa. ${\ displaystyle C}$${\ displaystyle \ mathbf {x} \ in {\ mathcal {D}}}$${\ displaystyle {\ mathcal {D}}}$

Uma solução para um problema de otimização convexa é atingir qualquer ponto . Em geral, um problema de otimização convexa pode ter zero, uma ou várias soluções. ${\ displaystyle \ mathbf {x} \ in C}$${\ displaystyle \ inf \ {f (\ mathbf {x}): \ mathbf {x} \ in C \}}$

Muitos problemas de otimização podem ser formulados de forma equivalente neste formulário padrão. Por exemplo, o problema de maximizar uma função côncava pode ser reformulado de forma equivalente ao problema de minimizar a função convexa . O problema de maximizar uma função côncava sobre um conjunto convexo é comumente chamado de problema de otimização convexa. ${\ displaystyle f}$${\ displaystyle -f}$

Propriedades

A seguir estão propriedades úteis de problemas de otimização convexa:

• todo mínimo local é um mínimo global ;
• o conjunto ótimo é convexo;
• se a função objetivo for estritamente convexa, o problema terá no máximo um ponto ótimo.

Esses resultados são usados ​​pela teoria da minimização convexa junto com noções geométricas da análise funcional (em espaços de Hilbert), como o teorema da projeção de Hilbert , o teorema do hiperplano de separação e o lema de Farkas .

Formulários

Ben-Hain e Elishakoff (1990), Elishakoff et al. (1994) aplicou a análise convexa para modelar a incerteza .

As seguintes classes de problemas são todos problemas de otimização convexa ou podem ser reduzidas a problemas de otimização convexa por meio de transformações simples:

Uma hierarquia de problemas de otimização convexa. (LP: programa linear, QP: programa quadrático, programa de cone de segunda ordem SOCP, SDP: programa semidefinido, CP: programa de cone.)

• Mínimos quadrados
• Programação linear
• Minimização quadrática convexa com restrições lineares
• Minimização quadrática com restrições quadráticas convexas
• Otimização cônica
• Programação geométrica
• Programação de cone de segunda ordem
• Programação semidefinida
• Maximização de entropia com restrições apropriadas

A otimização convexa tem aplicações práticas para o seguinte.

• otimização de portfólio
• análise de risco do pior caso
• publicidade ótima
• variações de regressão estatística (incluindo regularização e regressão de quantis )
• ajuste de modelo (particularmente classificação multiclasse )
• otimização de geração de eletricidade
• otimização combinatória

Multiplicadores de Lagrange

Considere um problema de minimização convexa dado na forma padrão por uma função de custo e restrições de desigualdade para . Então o domínio é: ${\ displaystyle f (x)}$${\ displaystyle g_ {i} (x) \ leq 0}$${\ displaystyle 1 \ leq i \ leq m}$${\ displaystyle {\ mathcal {X}}}$

${\ displaystyle {\ mathcal {X}} = \ left \ {x \ in X \ vert g_ {1} (x), \ ldots, g_ {m} (x) \ leq 0 \ right \}.}$

A função Lagrangiana para o problema é

${\ displaystyle L (x, \ lambda _ {0}, \ lambda _ {1}, \ ldots, \ lambda _ {m}) = \ lambda _ {0} f (x) + \ lambda _ {1} g_ {1} (x) + \ cdots + \ lambda _ {m} g_ {m} (x).}$

Para cada ponto em que minimiza mais , existem números reais chamados multiplicadores de Lagrange , que satisfazem estas condições simultaneamente: ${\ displaystyle x}$${\ displaystyle X}$${\ displaystyle f}$${\ displaystyle X}$${\ displaystyle \ lambda _ {0}, \ lambda _ {1}, \ ldots, \ lambda _ {m},}$

1. ${\ displaystyle x}$minimiza sobre tudo${\ displaystyle L (y, \ lambda _ {0}, \ lambda _ {1}, \ ldots, \ lambda _ {m})}$${\ displaystyle y \ in X,}$
2. ${\ displaystyle \ lambda _ {0}, \ lambda _ {1}, \ ldots, \ lambda _ {m} \ geq 0,}$ com pelo menos um ${\ displaystyle \ lambda _ {k}> 0,}$
3. ${\ displaystyle \ lambda _ {1} g_ {1} (x) = \ cdots = \ lambda _ {m} g_ {m} (x) = 0}$ (folga complementar).

Se existe um "ponto estritamente viável", ou seja, um ponto que satisfaça ${\ displaystyle z}$

${\ displaystyle g_ {1} (z), \ ldots, g_ {m} (z) <0,}$

então a declaração acima pode ser reforçada para exigir isso . ${\ displaystyle \ lambda _ {0} = 1}$

Por outro lado, se algum em satisfaz (1) - (3) para escalares com, então certamente minimizará over . ${\ displaystyle x}$${\ displaystyle X}$ ${\ displaystyle \ lambda _ {0}, \ ldots, \ lambda _ {m}}$${\ displaystyle \ lambda _ {0} = 1}$${\ displaystyle x}$${\ displaystyle f}$${\ displaystyle X}$

Algoritmos

A otimização convexa irrestrita pode ser facilmente resolvida com a descida gradiente (um caso especial de descida mais íngreme ) ou o método de Newton , combinado com a busca em linha para um tamanho de passo apropriado; pode-se provar matematicamente que estes convergem rapidamente, especialmente o último método. A otimização convexa com restrições de igualdade linear também pode ser resolvida usando técnicas de matriz KKT se a função objetivo for uma função quadrática (que generaliza para uma variação do método de Newton, que funciona mesmo se o ponto de inicialização não satisfaz as restrições), mas também pode geralmente resolvido eliminando as restrições de igualdade com álgebra linear ou resolvendo o problema dual. Finalmente, a otimização convexa com restrições de igualdade linear e restrições de desigualdade convexa pode ser resolvida aplicando uma técnica de otimização convexa irrestrita à função objetivo mais os termos de barreira logarítmica . (Quando o ponto de partida não é viável - isto é, satisfazendo as restrições - isso é precedido pelos chamados métodos da fase I , que localizam um ponto viável ou mostram que não existe. Os métodos da Fase I geralmente consistem em reduzir a pesquisa em questão a outro problema de otimização convexa.)

Problemas de otimização convexa também podem ser resolvidos pelos seguintes métodos contemporâneos:

• Métodos de pacote (Wolfe, Lemaréchal, Kiwiel) e
• Métodos de projeção de subgradiente (Polyak),
• Métodos de ponto interior , que fazem uso de funções de barreira auto-concordantes e funções de barreira auto-regulares.
• Métodos de plano de corte
• Método elipsóide
• Método de subgradiente
• Subgradientes duplos e o método drift-plus-penalty

Os métodos de subgradiente podem ser implementados de forma simples e, portanto, são amplamente usados. Os métodos de subgradiente duplo são métodos de subgradiente aplicados a um problema duplo . O método de deriva mais penalidade é semelhante ao método de subgradiente duplo, mas leva uma média de tempo das variáveis ​​primárias.

Implementações

Otimização convexa e algoritmos relacionados foram implementados nos seguintes programas de software:

Extensões

Extensões de otimização convexa incluem a otimização de funções biconvexas , pseudo-convexas e quase -convexas . Extensões da teoria da análise convexa e métodos iterativos para resolver aproximadamente problemas de minimização não convexa ocorrem no campo da convexidade generalizada , também conhecida como análise convexa abstrata.

Veja também

• Dualidade
• Condições de Karush – Kuhn – Tucker
• Problema de otimização
• Método de gradiente proximal

Notas

Referências

• Bertsekas, Dimitri P .; Nedic, Angelia; Ozdaglar, Asuman (2003). Análise e otimização convexa . Belmont, MA: Athena Scientific. ISBN 978-1-886529-45-8.
• Bertsekas, Dimitri P. (2009). Teoria da Otimização Convexa . Belmont, MA: Athena Scientific. ISBN 978-1-886529-31-1.
• Bertsekas, Dimitri P. (2015). Algoritmos de otimização convexa . Belmont, MA: Athena Scientific. ISBN 978-1-886529-28-1.
• Borwein, Jonathan; Lewis, Adrian (2000). Análise convexa e otimização não linear: teoria e exemplos, segunda edição (PDF) . Springer . Recuperado em 12 de abril de 2021 .
• Christensen, Peter W .; Anders Klarbring (2008). Uma introdução à otimização estrutural . 153 . Springer Science & Business Media. ISBN 9781402086663.

• Hiriart-Urruty, Jean-Baptiste e Lemaréchal, Claude . (2004). Fundamentos da análise convexa . Berlim: Springer.
• Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Análise convexa e algoritmos de minimização, Volume I: Fundamentos . Grundlehren der Mathematischen Wissenschaften [Princípios Fundamentais das Ciências Matemáticas]. 305 . Berlim: Springer-Verlag. pp. xviii + 417. ISBN 978-3-540-56850-6. MR  1261420 .
• Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Análise convexa e algoritmos de minimização, Volume II: Teoria avançada e métodos de pacote . Grundlehren der Mathematischen Wissenschaften [Princípios Fundamentais das Ciências Matemáticas]. 306 . Berlim: Springer-Verlag. pp. xviii + 346. ISBN 978-3-540-56852-0. MR  1295240 .
• Kiwiel, Krzysztof C. (1985). Métodos de descida para otimização não diferenciável . Notas de aula em matemática. Nova York: Springer-Verlag. ISBN 978-3-540-15642-0.
• Lemaréchal, Claude (2001). "Relaxamento Lagrangiano". Em Michael Jünger e Denis Naddef (ed.). Otimização combinatória computacional: Artigos da Spring School realizada em Schloß Dagstuhl, de 15 a 19 de maio de 2000 . Notas de aula em Ciência da Computação. 2241 . Berlim: Springer-Verlag. pp. 112–156. doi : 10.1007 / 3-540-45586-8_4 . ISBN 978-3-540-42877-0. MR  1900016 . S2CID  9048698 .
• Nesterov, Yurii; Nemirovskii, Arkadii (1994). Métodos Polinomiais de Ponto Interior em Programação Convexa . SIAM.
• Nesterov, Yurii. (2004). Palestras introdutórias sobre otimização convexa , Kluwer Academic Publishers
• Rockafellar, RT (1970). Análise convexa . Princeton: Princeton University Press.

• Ruszczyński, Andrzej (2006). Otimização não linear . Princeton University Press.
• Schmit, LA; Fleury, C. 1980: Síntese estrutural pela combinação de conceitos de aproximação e métodos duais . J. Amer. Inst. Aeronauta. Astronauta 18, 1252-1260

links externos

• EE364a: Otimização convexa I e EE364b: Otimização convexa II , páginas iniciais do curso de Stanford
• 6.253: Convex Analysis and Optimization , uma página inicial do curso MIT OCW
• Brian Borchers, Uma visão geral do software para otimização convexa