Fred Krogh's Unfinished Business
Everything we post here is public
domain, do with as you wish. Fred is in hospice care, and wishes to pass this
on to any who might be interested.
A paper on an algorithm for integer programming problems
This paper suggests using
only specially constructed planes, and never requires branching. The resulting
algorithm could result in polynomial time solutions for problems that now require
exponential time. See paper on integer programming.
Big zip file with work we have done on an active set method.
See The big zip file See Background on directions for this active set method.
Patterson's formulas for quadrature
If done properly we have solid evidence that these formulas are easily twice as
efficient (in terms of evaluations of the integrand), with much better
reliability.
There are two things that need attention here. Most vexing is an efficient and
reliable way to isolate singularities. If this is not done, the code may work,
but reliability takes a big hit. In the zip file here is a big dump of files
used for quadrature. This includes some test code to isolate singularities
using fourth differences. This show some promise, but some clever person might
find something better.
The second issue is picking interval to solve next as well as the target order
of the formula to use. All this is fairly straight forward, but still requires
more work.
This algorithm has been used for multi-dimensional quadrature, and should be
useful for this purpose for up to 3 dimensions. The zip file should be enough
to scare most people away.
Van Snyder has been very involved with the development of this code,
Email: Van Snyder Van has also
been an essential guru for my dealing with the latest versions of Fortran.
See zip file for quadrature code.
A neglected idea for using trust regions in solving nonlinear problems.
See, R. J. Hanson and Fred T. Krogh, A Quadratic-Tensor Model Algorithm for Nonlinear
Least-Squares Problems with Linear Constraints", acm-TOMS,
v. 18 number 2, pp 115-133.
The key point here is that allowing increases in the nonlinear objective can pay big
dividends. But of course allowing arbitrary large increases in the objective has
it own hazards. The key is to us Levenberg Marquardt stabilization to define a
trust region. The size of the this trust region shrinks if the nonlinear
problem has an increased objective, but one allows an arbitrary increase in the
objective if the solution to the linear problem has an expected objective that
is less than the best seen so far. Of course, if that test fails, one must go
back to the solution giving the previous best nonlinear objective and start
there with a much smaller trust region. Allow big increases in the nonlinear
objective can get one to the desired solution much more quickly, as long
exercises some care to insure that things don't get out of hand.\
An improvement on Filon's method for quadrature of oscillating
functions
I have thought for some time that this would make a nice master thesis project.
The problem with Filon's method it that it is not as accurate as it might, and
more importantly provides no error estimates. Both of these problems can be
addressed by using the same idea as in Filon's method and to apply them to using
Gregory's formula (like Euler-McClaurin, but using differences instead of
derivatives). One must be prepared to deal with cancellation for some cases by
using some symbolic algebra system, to derive good results when otherwise severe
cancellation would result in useless results.
Comments
As long as I'm able, if you send an email, I will post both nice and nasty
comments below. Email Fred
1.
Last modified: /Thu Feb, 1 16:37:47 PDT 2024