 |
Professor Farid Alizadeh
Rutgers University |
Speaker: Farid Alizadeh, Department of Management Science and Information Systems, Rutgers Business School
Title: Simplex-like algorithms for the problem of finding the minimum ball containing a set of balls and related problems
Bio: Farid Alizadeh received his Ph.D. from the University of Minnesota. After spending two years as a postdoctoral associate at the University of California-Berkeley, he joined Rutgers, first at Rutgers Center for Operations Research and then at Rutgers Business School. Alizadeh is credited for laying the foundation of semidefinite programming (SDP), in particular, extending interior point algorithms from linear programming to SDP, and applying them to solve some combinatorial optimization problems. Later he, along with many others, extended these techniques to symmetric cones, in particular, second-order cones. Presently, his research is focused on developing simplex-like algorithms for some concrete SDP and SOCP problems. He is a recipient of the 2014 INFORMS Optimization Society Farkas Prize.
Abstract:
We consider a number of related geometrical problems that are a special case of the ``infimum problem with respect to the second order cone''. This problem contains as a special case the following: a) find the smallest ball containing a set of balls, b) find the smallest ball intersecting a set of balls, c) find the largest ball in the intersection of a set of balls. These problems can be formulated as second-order cone programs (SOCP) and solved with standard methods like interior point algorithms. We show that in addition these problems may be solved by practical variants of the simplex method. We describe the combinatorial nature of these problems and show a variant of the simplex method can be developed for them. Similarly to the simplex method for linear programming, this extended method is suitable for warm-starting, and for situations where new data are presented as a stream, so the solution has to be updated quickly. Our work is related to the concept of ``LP-type'' algorithms in computational geometry, but we are aiming at practical and implementable methods. This research is joint work with Marta Cavaleiro of Rutgers University.
ثبت نام در همایش