O que é programação quadrática?
A programação quadrática é um método usado para otimizar uma função quadrática multivariável que pode ou não ser linearmente restrita. Muitos problemas do mundo real, como otimizar o portfólio de uma empresa ou reduzir os custos de um fabricante, podem ser descritos usando um programa quadrático. Se a função objetiva for convexa, uma solução viável poderá existir e poderá ser resolvida por algoritmos conhecidos, como o algoritmo simplex expandido. Existem métodos para resolver algumas funções quadráticas não convexas, mas são complicadas e não estão prontamente disponíveis.
Técnicas de otimização matemática são usadas na programação quadrática para minimizar uma função objetiva. A função objetiva é composta por várias variáveis de decisão que podem ou não ser limitadas. As variáveis de decisão têm poderes 0, 1 ou 2. A função objetiva pode ser submetida a várias restrições lineares de igualdade e desigualdade sobre as variáveis de decisão. Um exemplo de programação quadrática é:Minimize f (x, y) = x
Muitas vezes é interessante usar funções quadráticas multivariadas para descrever problemas do mundo real. Por exemplo, usando a teoria da portfólio moderna, um analista financeiro tentará otimizar o portfólio de uma empresa escolhendo a proporção de ativos que minimizam o risco associado a um determinado retorno esperado. Uma equação quadrática composta de pesos de ativo e a correlação entre os ativos descreve a variação do portfólio que pode ser minimizada usando programação quadrática. Outro exemplo pode ser um fabricante que usa uma equação quadrática para descrever a relação entre diferentes componentes de qualidade e o custo de um produto. O fabricante pode minimizar os custos, mantendo determinados padrões adicionando restrições lineares ao programa quadrático.
um dos conditio mais importantesNS na solução de um programa quadrático é a convexidade da equação objetiva. A convexidade de uma função quadrática é determinada pelo hessiano ou pela matriz de suas segundas derivadas. A função é chamada convexa se a matriz hessiana for positiva definida ou semi-definida positiva, ou seja, se os valores próprios forem positivos ou não negativos, respectivamente. Se o hessiano for positivo e existe uma solução viável, esse mínimo local é único e é um mínimo global. Se o hessiano for semi-positivo, uma solução viável pode não ser única. Funções quadráticas não convexas podem ter mínimos locais ou globais, mas são mais difíceis de determinar.
Existem muitas abordagens para resolver uma função quadrática convexa usando programação quadrática. A abordagem mais comum é uma expansão do algoritmo simplex. Alguns outros métodos incluem o método de ponto interior ou barreira, método de conjunto ativo e o método do gradiente conjugado. Esses métodos são integrados ao CERProgramas Tain como Mathematica® e Matlab® e estão disponíveis em bibliotecas para muitas linguagens de programação.