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

AN EFFECTIVE ALGORITHM FOR QUADRATIC MINIMIZATION PROBLEMS

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

Publishing Venue

Software Patent Institute

Related People

M. J. Best: AUTHOR [+4]

Abstract

An algorithm is described that determines a stationary point of a quadratic minimization problem in a finite number of steps. This finite termination property is based on the use of conjugate directions. The main feature of the algorithm is a new update procedure which preserves conjugate directions if the set of active constraints changes. AMS(MOS) Subject Classification - 90C20 Key Words: Quadratic programmingo conjugate directions, finite termination. Work Unit No. 5 -'Mathematical Programming and Operations Research Sponsored by the United States Army under Contract No. DAAG29-75-C-0024.

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

Page 1 of 22

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

AN EFFECTIVE ALGORITHM FOR QUADRATIC MINIMIZATION PROBLEMS

M. J. Best and K. Ritter

Technical Summary Report # 1691 October 1976

ABSTRACT

An algorithm is described that determines a stationary point of a quadratic minimization problem in a finite number of steps. This finite termination property is based on the use of conjugate directions. The main feature of the algorithm is a new update procedure which preserves conjugate directions if the set of active constraints changes.

AMS(MOS) Subject Classification - 90C20

Key Words: Quadratic programmingo conjugate directions, finite termination.

Work Unit No. 5 -'Mathematical Programming and Operations Research

Sponsored by the United States Army under Contract No. DAAG29-75-C-0024.

1. Introduction

A method of conjugate directions is presented for the solution of quad-ratic minimization problems with linear inequality constraints. The algorithm terminates after a finite number of steps with a stationary point. It is a modi-fication of methods of conjugate directions for general nonlinear objective functions described in [1] and [3].

With each point x determined by the algorithm an (n., n) -matrix is associated., where n is the number of variables. If q < n constraints areactive at x . then n - q columns of this matrix are conjugate and orthogonal to the gradients of all constraints active at x . This property allows an easy construction of search directions which are either Newton directions or are conjugate to certain previous search directions. Combined with an appro-priate policy for dropping active constraints this choice of search directions results in the finiteness of the algorithm.

A critical feature of the method to be presented is the procedure used to update the matrix associated with x . If at the next point, x . constructed by the algorithm, no new constraint becomes active this matrix is updated in the same way as the basis matrix is updated in the simplex-method. If how-ever, a new constraint becomes active at x . the normal update procedure results in the loss of the conjugate directions, Therefore, a new update formula is developed which allows the preservation of conjugate directions in

a simple and computationally efficient way.

Sponsored by the United States Army under Contract No. DAAG29-75-C-0024.

University of Wisconsin Page 1 Dec 31, 1976

Page 2 of 22

AN EFFECTIVE ALGORITHM FOR QUADRATIC MINIMIZATION PROBLEMS

2. General description of the algorithm

We consider the following quadratic minimization problem: Minimize

(Equation Omitted)

(Equation Omitted)

where

(Equation Omitted)

is a symmetric (n,n)-matrix and A is an (mn)-matrix.

If x* is a local or an optimal solution to this problem it follows from the Kuhn -Tucker -Theorem (see e. g [21) that there is a vector U* E E m such that

(2.1) .

(Equation Omitted)

Any point satisfying the conditions (2.1) - (2. 3) is called a stationary point. If C is posit...