Generalizações dos Algoritmos Afim Escala Primal e Dual e um Algoritmo Proximal para Programação Quase-Convexa
Autores
|
4025 |
304,303,1787
|
|
|
4026 |
304,303,1787
|
|
|
5998 |
304,303,1787
|
Informações:
Publicações do PESC
Em Pint,o et al. [73] é proposta uma classe de algoritmos primais de pontos interiores para programação convexa com restrições lineares, de um certo tipo afim escala generalizado. Esta classe, dependente de um parâmetro r, generaliza alguns algoritmos conhecidos. De um modo similar, trabalhando no espaço dual, propomos uma classe de algoritmos afim escala duais para programação linear que generaliza o algoritmo afim escala dual de Adler et al. [I]. Esta classe é construída através da transformação dada pela potência S-r >= 1, onde S é a matriz diagonal do vetor de iteradas. Provamos a convergência global da classe afim escala dual generalizada para problemas de programação linear cujo dual seja não-degenerado. Em um outro enfoque, analisamos o método de ponto proximal com g-divergência para programação quase-convexa sobre Rn+. Provamos, sem hipótese de limitação de nível para a função objetivo, que s sequência gerada converge para um ponto estacionário. Em adição, provamos também que quando os parâmetros de regularização vão para zero, a sequencia converge para uma solução ótima. Observamos o desempenho computacional das classes de algoritmos afim escala primal e dual, realizando testes com problemas de programação linear da biblioteca NETLIB. Para a classe primal experimentamos também alguns problemas de programação quadrática descritos no repositório Maros e Mészáros. Verificamos a eficiência do algoritmo proximal em problemas quase-convexos sobre Rn+ por meio de experimentos realizados com problemas testes gerados aleatoriamente.
In Pinto et al. [73], it is proposed a class of primal interior point algorithms for convex programnming with linear constraints, belonging to a certain generalized affine scaling type. That class, depending on a r-parameter, generalizes some known algorithms. In a similar way, working in the dual space, we propose a class of dual affine scaling algorithms to linear programming that generalize the dual afine scaling algorithm of Adler et al. [1]. This class is constructed through the transformation given by the power S-r, r >= 1, where S is the diagonal iterate vector matrix. We show the global convergence of the generalized dual affine scaling class for linear programs whose dual is nondegenerate. In another focus, we analyze the proximal point method with g-divergence to quasiconvex programming on Rn+. We prove, without assumption of boundedness level to the objective function, that the generated sequence converges to a stationary point. In addition, we also prove that when the regularization parameters go to zero, the sequence converges to an optimal solution. We observe the computational performance of the classes of primal and dual affine scaling algorithms, accomplishing tests with linear programs from the NETLIB library. For the primal class we also experiment some quadratic programming problems described in the Maros and Mészáros repository. We verify the effectiveness of the proximal algorithm in quasiconvex problems on Rn+ via numerical experiments accomplished with tests problems randomly generated.