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
---------------------------------------------------------------