Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!linus!philabs!cmcl2!seismo!ut-sally!utastro!bill
From: bill@utastro.UUCP (William H. Jefferys)
Newsgroups: net.math,net.micro,net.micro.pc
Subject: Re: simplex algorithsm for curve fitting---any disadvantage ??
Message-ID: <401@utastro.UUCP>
Date: Fri, 21-Feb-86 17:30:32 EST
Article-I.D.: utastro.401
Posted: Fri Feb 21 17:30:32 1986
Date-Received: Mon, 24-Feb-86 05:47:05 EST
References: <1217@princeton.UUCP> <236@vu-vlsi.UUCP> <1836@trwrba.UUCP>
Distribution: net
Organization: U. Texas, Astronomy, Austin, TX
Lines: 37
Xref: linus net.math:2506 net.micro:12665 net.micro.pc:6877
Summary: Wrong Simplex Method

In article <1836@trwrba.UUCP>, ice@trwrba.UUCP (Douglas L. Ice) writes:
> In article <236@vu-vlsi.UUCP> perry@vu-vlsi.UUCP (Rick Perry) writes:
> >> I recently ported the curve fitting program, listed on BYTE 1984 May p.340,
> >> The authors claimed that the program could fit *any* equation with *any*
> >> number of parameters and variables to experimental data.
> >
> >[...]
> >   The only disadvantage that I would note is that it has more or less linear
> >convergence, so it may take more cpu time to get the answers with this method.
> In general, the simplex algorithm is classified as NP-complete -- in
> other words, given an arbitrary set of variables and constraints, it
> is currently unknown if the algorithm terminates in an amount of time
> which is a polynomial function of the input length.  

Wrong simplex method.  What Rick and his respondent are talking about here
is the Simplex Method for minimizing nonlinear functions, due to Nedler
and Meade, (Comput. J.  *7*, 308, 1965), and NOT Dantzig's Simplex Method
of Linear Programming, which was invented in the 1950's.  The two methods
have nothing whatsoever to do with each other, other than that they
unfortunately have the same name.

I believe that Smale recently showed that the Dantzig's Simplex Method 
"usually" gets its answer in polynomial time, where "usually" was 
described precisely.  This explains why it is such a good method in
practice even though there are pathological cases for which it doesn't
get the answer in polynomial time.  But this result has nothing to do
with the rate of convergence of Nedler and Meade's algorithm.

-- 
Glend.	I can call spirits from the vasty deep.
Hot.	Why, so can I, or so can any man; But will they come when you
	do call for them?    --  Henry IV Pt. I, III, i, 53

	Bill Jefferys  8-%
	Astronomy Dept, University of Texas, Austin TX 78712   (USnail)
	{allegra,ihnp4}!{ut-sally,noao}!utastro!bill	(UUCP)
	bill@astro.UTEXAS.EDU.				(Internet)