Programação quadrática - Quadratic programming

A programação quadrática ( QP ) é o processo de resolver certos problemas de otimização matemática envolvendo funções quadráticas . Especificamente, busca-se otimizar (minimizar ou maximizar) uma função quadrática multivariada sujeita a restrições lineares nas variáveis. A programação quadrática é um tipo de programação não linear .

"Programação", neste contexto, refere-se a um procedimento formal para resolver problemas matemáticos. Esse uso data da década de 1940 e não está especificamente vinculado à noção mais recente de "programação de computador". Para evitar confusão, alguns profissionais preferem o termo "otimização" - por exemplo, "otimização quadrática".

Formulação de problema

O problema de programação quadrática com $n$ variáveis e $m$ restrições pode ser formulado como segue. Dado:

um vetor $c$ $n-$ dimensional com valor real ,
uma matriz simétrica real $n \times n-$ dimensional $Q$ ,
uma matriz real $A$ $m \times n-$ dimensional , e
um vetor real $b$ dimensional $m$ ,

o objetivo da programação quadrática é encontrar um vetor $n-$ dimensional $x$ , que irá

minimizar	${\ displaystyle {\ tfrac {1} {2}} \ mathbf {x} ^ {\ mathrm {T}} Q \ mathbf {x} + \ mathbf {c} ^ {\ mathrm {T}} \ mathbf {x }}$
sujeito a	${\ displaystyle A \ mathbf {x} \ preceq \ mathbf {b},}$

onde $x T$ denota o vetor transposto de $x$ , e a notação $A x ⪯ b$ significa que cada entrada do vetor $A x$ é menor ou igual à entrada correspondente do vetor $b$ (desigualdade por componente).

Mínimos quadrados

Como um caso especial quando Q é simétrico positivo-definido , a função de custo se reduz a mínimos quadrados:

minimizar	${\ displaystyle {\ tfrac {1} {2}} \ \| R \ mathbf {x} - \ mathbf {d} \ \| ^ {2}}$
sujeito a	${\ displaystyle A \ mathbf {x} \ preceq \ mathbf {b},}$

onde $Q = R t R$ decorre da decomposição de Cholesky de $Q$ e $C = - R t d$ . Por outro lado, qualquer programa de mínimos quadrados restritos pode ser enquadrado de forma equivalente como um QP, mesmo para uma matriz $R$ não quadrada genérica .

Generalizações

Ao minimizar uma função $f$ na vizinhança de algum ponto de referência $x 0$ , $Q$ é definido com sua matriz Hessiana $H (f (x 0))$ e $c$ é definido com seu gradiente $\nabla f (x 0)$ . Um problema de programação relacionado, programação quadrática com restrição quadrática , pode ser colocado adicionando restrições quadráticas nas variáveis.

Métodos de solução

Para problemas gerais, uma variedade de métodos são comumente usados, incluindo

No caso em que $Q$ é definido positivo , o problema é um caso especial do campo mais geral de otimização convexa .

Restrições de igualdade

A programação quadrática é particularmente simples quando $Q$ é definido positivo e há apenas restrições de igualdade; especificamente, o processo de solução é linear. Usando multiplicadores de Lagrange e buscando o extremo do Lagrange, pode ser facilmente mostrado que a solução para o problema de igualdade restrita

{\ displaystyle {\ text {Minimize}} \ quad {\ tfrac {1} {2}} \ mathbf {x} ^ {\ mathrm {T}} Q \ mathbf {x} + \ mathbf {c} ^ {\ mathrm {T}} \ mathbf {x}}

{\ displaystyle {\ text {sujeito a}} \ quad E \ mathbf {x} = \ mathbf {d}}

é dado pelo sistema linear

{\ displaystyle {\ begin {bmatrix} Q&E ^ {\ top} \\ E & 0 \ end {bmatrix}} {\ begin {bmatrix} \ mathbf {x} \\\ lambda \ end {bmatrix}} = {\ begin { bmatriz} - \ mathbf {c} \\\ mathbf {d} \ end {bmatriz}}}

onde $λ$ é um conjunto de multiplicadores de Lagrange que saem da solução ao lado de $x$ .

O meio mais fácil de abordar este sistema é a solução direta (por exemplo, fatoração LU ), que para pequenos problemas é muito prática. Para grandes problemas, o sistema apresenta algumas dificuldades incomuns, mais notavelmente que o problema nunca é definido positivamente (mesmo se $Q$ for), tornando potencialmente muito difícil encontrar uma boa abordagem numérica, e há muitas abordagens para escolher dependendo do problema.

Se as restrições não acoplam as variáveis com muita força, um ataque relativamente simples é alterar as variáveis para que as restrições sejam incondicionalmente satisfeitas. Por exemplo, suponha que $d = 0$ (generalizar para um valor diferente de zero é direto). Olhando para as equações de restrição:

{\ displaystyle E \ mathbf {x} = 0}

introduzir uma nova variável $y$ definida por

{\ displaystyle Z \ mathbf {y} = \ mathbf {x}}

onde $y$ tem dimensão de $x$ menos o número de restrições. Então

{\ displaystyle EZ \ mathbf {y} = \ mathbf {0}}

e se $Z$ for escolhido de forma que $EZ = 0,$ a equação de restrição será sempre satisfeita. Encontrar tais $Z$ implica encontrar o espaço nulo de $E$ , o que é mais ou menos simples, dependendo da estrutura de $E$ . Substituir na forma quadrática dá um problema de minimização irrestrito:

{\ displaystyle {\ tfrac {1} {2}} \ mathbf {x} ^ {\ top} Q \ mathbf {x} + \ mathbf {c} ^ {\ top} \ mathbf {x} \ quad \ implica \ quad {\ tfrac {1} {2}} \ mathbf {y} ^ {\ top} Z ^ {\ top} QZ \ mathbf {y} + \ left (Z ^ {\ top} \ mathbf {c} \ right ) ^ {\ top} \ mathbf {y}}

cuja solução é dada por:

{\ displaystyle Z ^ {\ top} QZ \ mathbf {y} = -Z ^ {\ top} \ mathbf {c}}

Sob certas condições em $Q$ , a matriz reduzida $Z T QZ$ será positiva definida. É possível escrever uma variação do método do gradiente conjugado que evita o cálculo explícito de $Z$ .

Dualidade Lagrangiana

O dual Lagrangiano de um QP também é um QP. Para ver isso, vamos nos concentrar no caso em que $c = 0$ e $Q$ é definido positivo. Escrevemos a função Lagrangiana como

{\ displaystyle L (x, \ lambda) = {\ tfrac {1} {2}} x ^ {\ top} Qx + \ lambda ^ {\ top} (Ax-b).}

Definindo a função dupla (Lagrangiana) $g (λ)$ como , encontramos um ínfimo de $L$ , usando uma definição positiva de $Q$ : ${\ displaystyle g (\ lambda) = \ inf _ {x} L (x, \ lambda)}$ ${\ displaystyle \ nabla _ {x} L (x, \ lambda) = 0}$

{\ displaystyle x ^ {*} = - Q ^ {- 1} A ^ {\ top} \ lambda.}

Portanto, a função dupla é

{\ displaystyle g (\ lambda) = - {\ tfrac {1} {2}} \ lambda ^ {\ top} AQ ^ {- 1} A ^ {\ top} \ lambda - \ lambda ^ {\ top} b ,}

e assim o dual Lagrangiano do QP é

{\ displaystyle {\ text {maximize}} _ {\ lambda \ geq 0} \ quad - {\ tfrac {1} {2}} \ lambda ^ {\ top} AQ ^ {- 1} A ^ {\ top} \ lambda - \ lambda ^ {\ top} b}

Além da teoria da dualidade de Lagrang, existem outros pares de dualidade (por exemplo , Wolfe , etc.).

Complexidade

Para $Q$ definido positivo , o método elipsóide resolve o problema em tempo polinomial (fracamente) . Se, por outro lado, $Q$ for indefinido, então o problema é NP-difícil . Pode haver vários pontos estacionários e mínimos locais para esses problemas não convexos. Na verdade, mesmo que $Q$ tenha apenas um autovalor negativo , o problema é (fortemente) NP-difícil .

Restrições inteiras

Existem algumas situações em que um ou mais elementos do vetor $x$ precisarão assumir valores inteiros . Isso leva à formulação de um problema de programação quadrática inteira mista (MIQP). As aplicações do MIQP incluem recursos hídricos e a construção de fundos de índice .

Solucionadores e linguagens de script (programação)

Nome	Informação resumida
AIMMS	Um sistema de software para modelagem e resolução de problemas de otimização e agendamento
ALGLIB	Biblioteca numérica com licença dupla (GPL / proprietária) (C ++, .NET).
AMPL	Uma linguagem de modelagem popular para otimização matemática em grande escala.
APMonitor	Suíte de modelagem e otimização para sistemas LP , QP, NLP , MILP , MINLP e DAE em MATLAB e Python.
Artelys Knitro	Um pacote integrado para otimização não linear
CGAL	Um pacote de geometria computacional de código aberto que inclui um solucionador de programação quadrática.
CPLEX	Solver popular com API (C, C ++, Java, .Net, Python, Matlab e R). Gratuito para acadêmicos.
Função Excel Solver	Um solucionador não linear ajustado para planilhas nas quais as avaliações das funções são baseadas nas células de recálculo. Versão básica disponível como complemento padrão para Excel.
GAMS	Um sistema de modelagem de alto nível para otimização matemática
GNU Octave	Uma linguagem de programação gratuita (sua licença é GPLv 3) de propósito geral e orientada a matrizes para computação numérica, semelhante ao MATLAB. A programação quadrática no GNU Octave está disponível através do comando qp
Gurobi	Solver com algoritmos paralelos para programas lineares de grande escala, programas quadráticos e programas de número inteiro misto. Gratuito para uso acadêmico.
IMSL	Um conjunto de funções matemáticas e estatísticas que os programadores podem incorporar em seus aplicativos de software.
IPOPT	IPOPT (Interior Point OPTimizer) é um pacote de software para otimização não linear em grande escala.
Bordo	Linguagem de programação de uso geral para matemática. A resolução de um problema quadrático no Maple é realizada por meio de seu comando QPSolve .
MATLAB	Uma linguagem de programação de uso geral e orientada a matrizes para computação numérica. A programação quadrática em MATLAB requer a caixa de ferramentas de otimização, além do produto MATLAB base
Mathematica	Uma linguagem de programação de propósito geral para matemática, incluindo recursos simbólicos e numéricos.
MOSEK	Solucionador para otimização em larga escala com API para diversas linguagens (C ++, Java, .Net, Matlab e Python).
Biblioteca Numérica NAG	Uma coleção de rotinas matemáticas e estatísticas desenvolvidas pelo Numerical Algorithms Group para múltiplas linguagens de programação (C, C ++, Fortran, Visual Basic, Java e C #) e pacotes (MATLAB, Excel, R, LabVIEW). O capítulo Otimização da Biblioteca NAG inclui rotinas para problemas de programação quadrática com matrizes de restrição linear esparsas e não esparsas, juntamente com rotinas para a otimização de lineares, não lineares, somas de quadrados de funções lineares ou não lineares com não lineares, limitadas ou sem restrições . A biblioteca NAG tem rotinas para otimização local e global e para problemas contínuos ou inteiros.
Pitão	Linguagem de programação de alto nível com ligações para a maioria dos solucionadores disponíveis. A programação quadrática está disponível por meio da função solve_qp ou chamando um solucionador específico diretamente.
R (Fortran)	Estrutura de computação estatística de plataforma cruzada universal licenciada pela GPL .
SAS / OR	Um conjunto de solucionadores para otimização linear, inteira, não linear, livre de derivativos, rede, combinatória e de restrição; a linguagem de modelagem algébrica OPTMODEL; e uma variedade de soluções verticais dirigidas a problemas / mercados específicos, todas totalmente integradas com o Sistema SAS .
SuanShu	um conjunto de algoritmos de otimização de código aberto para resolver LP , QP, SOCP , SDP , SQP em Java
TK Solver	Sistema de software para modelagem matemática e solução de problemas baseado em linguagem declarativa e baseada em regras, comercializado pela Universal Technical Systems, Inc ..
TOMLAB	Suporta otimização global, programação inteira, todos os tipos de mínimos quadrados, programação linear, quadrática e irrestrita para MATLAB . TOMLAB suporta solucionadores como Gurobi , CPLEX , SNOPT e KNITRO .
XPRESS	Solver para programas lineares de grande escala, programas quadráticos, programas gerais não lineares e de inteiros mistos. Possui API para diversas linguagens de programação, possui também uma linguagem de modelagem Mosel e trabalha com AMPL, GAMS . Gratuito para uso acadêmico.

Veja também

Referências

Leitura adicional

Cottle, Richard W .; Pang, Jong-Shi; Stone, Richard E. (1992). O problema da complementaridade linear . Ciência da Computação e Computação Científica. Boston, MA: Academic Press, Inc. pp. Xxiv + 762 pp. ISBN 978-0-12-192350-1. MR 1150683 .
Garey, Michael R .; Johnson, David S. (1979). Computadores e intratabilidade: um guia para a teoria da NP-completude . WH Freeman. ISBN 978-0-7167-1045-5. A6: MP2, pág.245.
Gould, Nicholas IM; Toint, Philippe L. (2000). "A Quadratic Programming Bibliography" (PDF) . RAL Numerical Analysis Group Relatório interno 2000-1.

Languages

In other projects