Generalization of the primal and dual affine scaling algorithms

F. G. M. Cunha (gevanecos.ufrj.br)
A. W. M. Pinto (awagnerfua.br)
P. R. Oliveira (poliveircos.ufrj.br)
J. X. da C. Neto (jxavierufpi.br)

Abstract: We obtain a new class of primal affine scaling algorithms for the linearly constrained convex programming. It is constructed through a family of metrics generated by -r power, r=>1, of the diagonal iterate vector matrix. We prove the so-called weak convergence. It generalizes some known algorithms. Working in dual space, we generalize the dual affine scaling algorithm of Adler, Karmarkar, Resende and Veiga, similarly depending on a r-parameter and we give its global convergence proof for nondegenerate linear programs. With the purpose of observing the computational performance of the methods, we compare them with classical algorithms (when r = 1 or r = 2), implementing the proposed families and applying to some linear programs obtained from NETLIB library. In the case of primal family, we also apply it to some quadratic programming problems described in the Maros and Meszaros repository.

Keywords: Interior Point Algorithms; Affine Scaling Algorithms; Linear Convex Programming

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: TR ES 675/05, April, PESC/COPPE, Federal University of Rio de Janeiro, 2005

Download: [Postscript][PDF]

Entry Submitted: 04/28/2005
Entry Accepted: 04/28/2005
Entry Last Modified: 04/28/2005

Modify/Update this entry