DIMACS - RUTGERS EXPERIMENTAL MATHEMATICS SEMINAR

Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

Co-organizers:

Drew Sills, Rutgers University, asills {at} math [dot] rutgers [dot] edu

Doron Zeilberger, Rutgers University, zeilberg {at} math [dot] rutgers [dot] edu

Title: A Newton-Bracketing Method for Convex Minimization and its Application to Location Problems

Speaker: Adi Ben-Israel, Rutgers University (RUTCOR)

Date: Thursday, April 6, 2006 5:00pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

An iterative method for the minimization of convex functions f: R^n --> R, called a Newton Bracketing (NB) method, is presented, [2].

The NB method proceeds by using Newton iterations to improve upper and lower bounds on the minimum value. Each iteration of the NB method does one step of the Directional Newton Method, [1].

An advantage of the NB method (over say gradient methods) is a natural stopping rule (the bracket size.)

The NB method is applied to large scale Fermat-Weber location problems, where it works better the larger is the problem size. This anomaly is due to an interesting and unexpected "experimental factor".

(Joint work with Yuri Levin of Queens University, Canada.)

References:

[1] Y. Levin and A. B-I, Directional Newton Methods in n Variables , Math. of Computation 71(2002), 237-250 

[2] Y. Levin and A. B-I, The Newton Bracketing Method for Convex Minimization , Comput. Optimiz. and Appl. 21(2002), 213-229