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

McCormick, Garth P.

Math. Oper. Res. 14, No. 2, 203-223 (1989).

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

MSC:

90C25	Convex programming
65K05	Numerical mathematical programming methods
90C55	Methods of successive quadratic programming type

Keywords:

projective SUMT method; logarithmic barrier function; binding constraint gradients; matrix inversion approximation

Citations:

Zbl 0557.90065; Zbl 0624.90062