Método das direções conjugadas no núcleo das restrições para minimização de uma função quadrática sujeita a restrições lineares de igualdade

AUTOR(ES)

Ana Paula Delowski

DATA DE PUBLICAÇÃO

2005

RESUMO

Este trabalho trata do problema de minimizar uma função quadrática sujeita a restrições lineares de igualdade que aparece em geral como um subproblema nos problemas de programação não linear com restrições. Uma grande variedade de algoritmos de otimização com restrições lineares e não lineares usam resolver a cada iteração um subproblema da forma [3], [24]. Minimizar x (x) = xTGx - hT x sujeito a Ax = b. Onde o vetor hk representa em geral o gradiente da funçãoo objetivo ou o gradiente do Lagrangeano, a matriz simetrica Gk é a hessiana da função na k-ésima iteração e a solução xk representa uma direção de busca. Assumiremos nesse trabalho que A é m × n, com n >m e que A tem posto linha completo. Também assumiremos por conveniência que G é definida positiva no espaçoo nulo das restrições, garantindo com isso que o problema acima tenha solução unica. Ordinariamente o problema de programação quadrática é resolvido calculando-se uma base Z para o espaço nulo de A, e usando-se essa base para eliminar as restrições, e então utilizando-se um método de minimização irrestrita para resolver o problema reduzido [4]. Neste trabalho apresentaremos um algoritmo baseado no metodo do gradiente conjugado, que não utiliza eliminar as restrções. Existem pelo menos duas boas razões para isso. As dificuldades inerentes ao precondicionamento quando a base escolhida não é ortogonal, e o problema de perda de esparsidade da matriz hessiana reduzida ZTGZ, que é usualmente densa, mesmo quando a G é esparsa.

ASSUNTO(S)

Álgebra linear mathematical optimization algoritmos otimização matemática algebras, linear conjugate gradient methods engenharia de producao production engineering programação quadrática quadratic programming métodos de gradiente conjugado algorithms

Documentos Relacionados

• Um novo algoritmo para resolver problemas de minimização de funções não lineares sujeita a restrições lineares de igualdade
• Algoritmos para minimização de funções com restrições não lineares
• Estimação adaptativa de parametros atraves de minimos quadrados sujeitos a restrições lineares de igualdade
• Função Quadrática: um estudo didático de uma abordagem computacional
• O apoio institucional como uma das faces da função apoio no Núcleo de Apoio à Saúde da Família (NASF): para além das diretrizes