Linear and Semidefinite Programming Using a Technique from Interior Points and Feasible Directions
Autores
7219 |
3156,44,2945
|
|
7220 |
3156,44,2945
|
|
7221 |
3156,44,2945
|
Informações:
Publicações do PESC
Propomos uma adaptação do Algoritmo de Pontos Interiores de Direção Viável (FDIPA) de J. Herskovits, para a resolução de programas lineares de grande porte. Este algoritmo requer um ponto inicial no interior de uma região viável definida pelas restrições e gera uma sequência de pontos no interior desta região que converge para a solução do problema. A cada iteração, a solução de dois sistemas lineares com a mesma matriz de coeficientes é determinada, o que envolve um esforço computacional significativo. Reduzir o tempo de solução de sistemas lineares é, portanto, uma forma de melhorar o desempenho do método. Os sistemas lineares a serem resolvidos estão associados a matrizes simétricas definidas positivas. Portanto, usamos o método do Gradiente Conjugado Pré-condicionado {\it Split} (SPCG) para resolvê-los, juntamente com um pré-condicionador Cholesky incompleto usando a função ICHOL do Matlab. Também propomos usar a primeira iteração do gradiente conjugado e pré-solucionador antes de aplicar o algoritmo, a fim de reduzir o custo computacional. A seguir, fornecemos demonstrações matemáticas de que as iterações se aproximam aos pontos de Karush-Kuhn-Tucker do problema sob suposições razoáveis. Finalmente, evidências numéricas mostram que o método não só funciona na teoria, mas também é competitivo com métodos mais avançados.
Consideramos também a extensão de FDIPA, para programação linear sujeitos às restrições nas quais matrizes m x m devem ser semi-definidas.
We propose an adaptation of the Feasible Direction Interior Points Algorithm (FDIPA) by J. Herskovits, for solving large-scale programs. This algorithm requires a starting point inside a feasible region defined by the constraints and generates a sequence of points inside this region that converges to the solution of the problem. At each iteration, the solution of two linear systems with the same coefficient matrix is determined. This step involves a significant computational effort. Reducing the solution time of linear systems is, therefore, a way to improve the performance of the method. The linear systems to be solved are associated with definite positive symmetric matrices. Therefore, we use Split Preconditioned Conjugate Gradient (SPCG) method to solve them, together with an Incomplete Cholesky preconditioner using Matlab’s ICHOL function. We also propose to use the first iteration of the conjugate gradient, and to presolve before applying the algorithm, in order to reduce the computational cost. Following, we then provide mathematica proof that show that the iterations approach Karush-Kuhn-Tucker points of the problem under reasonable assumptions. Finally, numerical evidence show that the method not only works in theory but is also competitive with more advanced methods.
We also consider the extension of FDIPA, for linear programming subject to constraints in which matrices m x m must be semi-defined.