Browse Prior Art Database

Performance of Approximate Algorithms for Global Minimization

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

Publishing Venue

Software Patent Institute

Related People

J.B. Rosen: AUTHOR [+3]

Abstract

I've parlor.rnanca of a class of algorithms for solving global minimization Px Dblarns is analyzed. Pe°o'ai.erns which may have a iav°ge number of variables a.p;-xearing orly linearly din addition to the -ticsrli.near variables) arc considered. "i ti.a analysis Es based'. on Finding, an e-ax>pray-imal:E: solui,iazi, in i"rie sense that the function Vaice ouirnd as known to be no Ynore than ~~,~1 gxea[~-~r than tile global m.irdraum, wlere A~,, is a known scale factor arid ; ile

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

Page 1 of 4

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Performance of Approximate Algorithms for Global Minimization

J.B. Rosen

Computer Science Department Institute oftTechnology

136 Lind Hall University of Minnesota Minneapolis, Minnesota 55455

Technical Report 83-6

March Performance of pproximategorithms for Global Minimization J.F3. Rosen* Computer Science Department University of Minnesota

Abstract

I've parlor.rnanca of a class of algorithms for solving global minimization Px Dblarns is analyzed. Pe°o'ai.erns which may have a iav°ge number of variables a.p;-xearing orly linearly din addition to the -ticsrli.near variables) arc considered. "i ti.a analysis Es based'. on Finding, an e-ax>pray- imal:E: solui,iazi, in i"rie sense that the function Vaice ouirnd as known to be no Ynore than ~~,~1 gxea[~-~r than tile global m.irdraum, wlere A~,, is a known scale factor arid ; ile

(Equation Omitted)

, will depend an the specific algorithm used. A tree of this type is illustrated below for

(Equation Omitted)

(Equation Omitted)

(Equation Omitted)

A special case is given by an algorithm in which the bound difference A+j, is reduced at each level by a reduction in the size of the active feasible domain. Rather than partitioning the original domain into two or more active sub-domains, the original domain is reduced at each iteration by adding one or mare cutting planes, and solving one or rnorc LP's. These cutting planes arc deter-mined so as to eliminate subdornains for which the lower bound exceeds the best known upper bound. This special case corresponds to a = 1.

>In order to analyze the performance of a specific algorithm, we first obtain a relation giving the minimum value of L which satisfies (5), in terms of p and s. Directly Prom (5~ and (6) we have

(Equation Omitted)

or

University of Minnesota Page 1 Dec 31, 1983

Page 2 of 4

Performance of Approximate Algorithms for Global Minimization

(Equation Omitted)

(Equation Omitted)

An integer L satisfying (8) is given by

f) = smallest integer wry.

This gives

(Equation Omitted)

The total computing effort required far each algorithm considered will depend primarily on the total number of nodes in the tree. More specifically, 2n LP's are solved far the first node, and v LP's for each node in levels 2 through L of the trcc, whcrc v is a small intcgcr (typically, U = 2 or
2). Thus if we dcnatc by N the total number of nodes in the tree, then NLp, the total number of LP's solved is given by

(Equation Omitted)

For a.= 1, we have one node per level, so that fvT = 1. Directly from (1(J) we bet

(Equation Omitted)

Far a > 1, an upper bound on 1V in terms of a and l is given by:

(Equation Omitted)

Then using (1t?) and (8) we get

(Equation Omitted)

(Equation Omitted)

where (15)

(Equation Omitted)

> Directly from (14) we obtain the more convenient bound on N:

(Equation Omitted)

For a > 1, it is clear from (ifi) that N cannot increase faster than linearly in provided w < 1. From
(15) we see th...