At 02:58 PM 1/28/96 -0700, Raj Patil wrote:
>Hi:
>
>I am looking for any references that has detail complexity analysis
>of Interval Branch and Bound methods of for global optimization
>over certain CLASS of optimization problems.
>
A "worst case" complexity analysis is discouraging, but that doesn't
mean the methods aren't practical -- the good problem spaces haven't
been adequately delineated, and many practical problems can be solved.
Caprini, Madsen, et al have done quite a bit of work in this area.
My review in the El Paso proceedings contains some pointers.
Also, I have placed a BibTex bibliography in:
pub/interval_math/bibliographies/optimization_book.bib
Please tell me if you see any errors in the above.
>Also application of these techniques to resonably high
>dimensional problems is also something I am looking for
>(this ofcourse depends on the class of problems).
That is a very open area.
>Similarly
>my efforts to apply these techniques to constrained problems
>has not been very successful (in large dimensions) as the
>box clustering effect is very dominating.
It depends on how you approach the problem. What are
"high dimensions?" I am presently polishing some software
for constrained problems, to be described in a forthcoming
book (towards the end of the year, or next year).
Have you tried the Fritz John system? I have found it is very
easy to get the derivative matrix wrong :-)
>Current algorithms
>suggested in Ratschek and Rokne's, Hansen's book do not scale
>to large dimensions and large set of constraints (even for
>standard linear programming with 100 variables and 100
>constraints).
You should include the constraints in a second-order fashion.
You should also use an approximate constrained optimizer to
get estimates, subsequently to be verified.
>
Best regards,
---------------------------------------------------------------
R. Baker Kearfott, rbk@usl.edu (318) 482-5346 (fax)
(318) 482-5270 (work) (318) 981-9744 (home)
URL: ftp://interval.usl.edu/pub/interval_math/www/kearfott.html
Department of Mathematics, University of Southwestern Louisiana
---------------------------------------------------------------