Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

On The Convergence of Rosen's Gradient Projection Method

IP.com Disclosure Number: IPCOM000128569D
Original Publication Date: 1983-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 14 page(s) / 31K

Publishing Venue

Software Patent Institute

Related People

X.S. Zhang: AUTHOR [+3]

Abstract

Since Rosen's gradient projection method was published in 1960, a rigorous convergence proof of his method has remained an open question. A convergence proof is given in this paper. More precisely, convergence is guaranteed if a constant parameter in the algorithm is properly chosen. This research was supported in part by the National Science Foundation under the research grant MCS 81-01214.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 19% of the total text.

Page 1 of 14

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

On The Convergence of Rosen's Gradient Projection Method

by

X.S. Zhang

Computer Science Department

136 Lind Hall

Institute of Technology

University of Minnesota

Minneapolis, Minnesota 55455

Technical Report 83-11 June 1983

ON THE CONVERGENCE OF

ROSEN'S GRADIENT PROJECTION METHOD

X.S.Zhang

Computer Science Department University of Minnesota

Institute of Applied Mathematics Academia Sinica, Beijing

ABSTRACT

Since Rosen's gradient projection method was published in 1960, a rigorous convergence proof of his method has remained an open question. A convergence proof is given in this paper. More precisely, convergence is guaranteed if a constant parameter in the algorithm is properly chosen. This research was supported in part by the National Science Foundation under the research grant MCS 81-01214.

I. Introduction.

Rosen's gradient projection method, published in 1960 11,27, is the first method in the history of mathematical programming for solving constrained nonlinear programming problems. The importance of this method in the literature of nonlinear programming also stems from the fact that many more efficient algorithms developed later incorporated the basic ideas propounded by Roses. Goldfarb's method E3,41, Murtagh and Sargent's method and many others are among the algorithms described above. The discussion in this paper will center on the convergence property of Rosen's method. In recent years substantial efforts have been made in the study of

University of Minnesota Page 1 Dec 31, 1983

Page 2 of 14

On The Convergence of Rosen's Gradient Projection Method

the unified convergence theory of nonlinesr programming algorithms C6-121, but none of the results obtained can be successfully applied to Rosen's method. In paper 1117, the author applied his result to a very principal.class of projection method, but which does not include Rosen's method. In fact, almost all recently published books (such as 13-15), which have a chapter to introduce Rosen's method, recognize the non-existence of either a convergence proof or a counter example. In 1971, E.Polak 18,163 suggested a complex version of the gradient method which he proved was convergent under some regularity assumption. An improved Rosen-Polak method was given by X.S.Zhang E17,183. . Polak's method not only has some unneccesary complexity but also uncertainty for the practical effectiveness. We will give a convergence proof for Rosen's original method in this paper.

Let the problem to solved is

(Equation Omitted)

where the ai has been normalized, i.e.,

(Equation Omitted)

can be written as

(Equation Omitted)

Let

(Equation Omitted)

be the feasible domain, where A in n x m, b is a m-dimentional vector, Let AJ denote a submatri.x of A consisting of columns

(Equation Omitted)

Notation tJf is used to denote the number of subscripts in J.

For any feasible point x, let

(Equation Omitted)

is a subset of I consisting of subscripts...