Browse Prior Art Database

A GRADIENT PROJECTION ALGORITHM FOR RELAXATION METHODS

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

Publishing Venue

Software Patent Institute

Related People

J.L. Mohammed: AUTHOR [+5]

Abstract

We consider a particular problem which arises when applying the method of gradient projection for solving constrained optimization and finite dimensional variational inequalities on the convex set formed by the convex hull of the standard basis unit vectors. The method is especially important for relaxation labeling techniques applied to problems in artificial intelligence. Zoutendijk's method for finding feasible directions, which is relatively complicated in general situations, yields a very simple finite algorithm for this problem. We present an extremely simple algorithm for performing the gradient projection and an independent verification of its correctness.

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

Page 1 of 8

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A GRADIENT PROJECTION ALGORITHM FOR RELAXATION METHODS

by J.L. Mohammed, R.A. Hummel, and S.W. Zucker

Technical Report No. 66 Robotics Report No. 9 March, 1933 .. A GRADIENT PROJECTION ALGORITHM FOR RELAXATION METHODS

John L. Mohammed ** Robert A. Hummel

Steven W. Zucker Laboratory for Artificial Intelligence Research Fairchild Advanced Research and Development

4001 Miranda Avenue , MS30-888 Palo Alto, California 94304

** Courant Institute of Mathematical Sciences New York University 251 Mercer Street New York,
N. Y. 10012

Computer Vision and Robotics Lab Department of Electrical Engineering McGill University Montreal, Quebec, Canada H3A 2A

Abstract:

We consider a particular problem which arises when applying the method of gradient projection for solving constrained optimization and finite dimensional variational inequalities on the convex set formed by the convex hull of the standard basis unit vectors. The method is especially important for relaxation labeling techniques applied to problems in artificial intelligence. Zoutendijk's method for finding feasible directions, which is relatively complicated in general situations, yields a very simple finite algorithm for this problem. We present an extremely simple algorithm for performing the gradient projection and an independent verification of its correctness.

Section 1. Formulation of the Projection Problem. We treat the following optimization problem: Let IK be the convex set defined by

(Equation Omitted)

For any vector x e IC, the tangent set TX is given by

(Equation Omitted)

The set of feasible directions at x is defined by

(Equation Omitted)

where G*V is the standard Euclidean norm. Given a "current point" x E IIS, and an arbitrary direction q E JRn'we consider Problem P: Find u E FX such that

(Equation Omitted)

New York University Page 1 Dec 31, 1983

Page 2 of 8

A GRADIENT PROJECTION ALGORITHM FOR RELAXATION METHODS

Clearly, Problem P is a linear optimization problem with quadratic and linear constraints. Problem P arises in the context of labeling problems in artificial intelligence, where iterative techniquessimilar to gradient ascent in 1K have been studied for their use in reducing ambiguity and achieving consistency [1,2]. The convex set IK is especially appropriate for labeling problems. The set IK can be viewed as the convex hull of the standard unit vectors

(Equation Omitted)

. The vector ei is assigned to an object to denote the labeling of that object with label number i. If the identity of the object is ambiguous, and no label can be assigned with complete certainty, a compromise vector p E IY can be assigned to the object, so that

(Equation Omitted)

denotes the labeling of that object with label numbers 1 through n, with degree of certainty al through an respectively. The optimization problem P arises in a solution method proposed for solving a variational inequality on IK [3]. It also arises if one...