The projective SUMT method for convex programming. (English) Zbl 0675.90067

The author proposes a new algorithm, named projective SUMT method, for solving convex programming problems. This method is derived from the differential equation characterizing the trajectory of unconstrained minimizers of the classical logarithmic barrier function. A proof of convergence to a global minimizer of convex programming problems is given under the assumption that binding constraint gradients are linearly independent. The projective SUMT method has many similarities with the algorithm proposed by N. Karmarkar [Combinatorica 4, 373-395 (1984; Zbl 0557.90065)] for the problem: min \(c^ Tx\), s.t. \(Ax=0\), \(e^ Tx=n\), \(x_ j\geq 0\), \(j=1,n\), which projects x into another space where the objective function is nonlinear and tries to minimize the transformed problem. So, Karmarkar obtains a direction for the new iteration, which is proportional to the direction given by the projective SUMT algorithm. This similarity was pointed out by P. E. Gill, W. Murray, M. Saunders and J. Tomlin [Math. Program 36, 183-209 (1986; Zbl 0624.90062)].
Considering a discrete form of the projective SUMT algorithm, the author gives a matrix inversion approximation, which greatly reduces the traditional problems in inverting the badly conditional matrix.
Full of informations, with many interesting applications, this work opens new views for the future of mathematical programming.
Reviewer: A.Donescu


90C25 Convex programming
65K05 Numerical mathematical programming methods
90C55 Methods of successive quadratic programming type
Full Text: DOI