Robert J. Vanderbei

Last updated

Robert J. Vanderbei (born 1955) is an American mathematician and Emeritus Professor in the Department of Operations Research and Financial Engineering at Princeton University.

Contents

Biography

Robert J. Vanderbei was born in Grand Rapids, MI, in 1955. He received his BS in Chemistry in 1976 and an MS in Operations Research and Statistics in 1978 from Rensselaer Polytechnic Institute and his PhD in Applied Mathematics from Cornell University in 1981. In his thesis, [1] he developed probabilistic potential theory for random fields consisting of tensor products of Brownian motions. He was postdoctoral research fellow at New York University's Courant Institute of Mathematical Sciences and then at the Mathematics Department at the University of Illinois Urbana-Champaign. In 1984, he left academia and joined Bell Labs, where he served as a team member of AT&T's Advanced Decision Support Systems venture. In 1990, Vanderbei returned to academia to teach at Princeton University. He is currently a Professor in the Department of Operations Research and Financial Engineering (ORFE). In addition to his appointment in ORFE, he also has courtesy appointments in Mathematics, Astrophysics, Computer Science, and Applied Mathematics. He is also a member of the Bendheim Center for Finance.

Research

Mathematical programming

Vanderbei’s arrival at Bell Labs coincided with Narendra Karmarkar’s discovery of a new polynomial-time algorithm for linear programming. In May 1985, he became the first nonmanagement team member of AT&T's Advanced Decision Support Systems venture, where he served as the interface to Karmarkar and as the lead developer of the first release of the linear programming software.

In 1985, Vanderbei, with Bell Labs colleagues Marc Meketon and Barry Freedman, wrote a paper proving convergence of a variant of Karmarkar's algorithm that became known as the Affine-Scaling algorithm. [2] Eventually it became known that I.I. Dikin, working in Siberia and publishing in Russian, had proved convergence of the same algorithm under weaker nondegeneracy assumptions many years earlier. [3] Vanderbei, both individually and with Meketon, and Freedman was awarded US Patents for his theoretical and practical work on the affine-scaling algorithm. [4] [5] [6] Taken together with the three patents awarded to Karmarkar, this suite of patents represented the first awarded for what was considered pure mathematics. At the time, they generated loud objections [7] from other researchers in optimization algorithms.

In 1987, Vanderbei left the development team and moved to the Bell Labs' Math Research Center in Murray Hill, NJ. In 1990, he returned to academia to teach at Princeton University. Throughout the 1990s Vanderbei's research governed the development of interior-point solvers. In 1993, Helmberg, Rendl, Vanderbei, and Wolkowicz developed an interior-point algorithm for semidefinite programming. [8] Vanderbei later developed algorithms for quadratic problems, convex, and finally nonlinear optimization problems. [9] [10]

Vanderbei is the author of a textbook on linear programming [11] and a software package for nonlinear programming called LOQO.

Purple America

Vanderbei received widespread attention for something that was only intended to be an exercise for the freshman computer programming course. U.S. News & World Report magazine, among other media outlets, reprinted his so-called Purple America map, which he made after the 2000 US Presidential election (and then subsequent national elections) to depict on a county-by-county level how the elections turned out.

Recent research interests

Since 2001, most of Vanderbei's research has been devoted to developing high-contrast imaging systems with the eventual aim of direct imaging of exoplanets. The concepts he has contributed to include shaped-pupil coronagraphs, PIAA-style pupil mapping coronagraphs, and space-based external occulters. Together with J. Richard Gott, Vanderbei is the author of a National Geographic book called Sizing Up The Universe (Book website).

Other interests

Vanderbei also was a serious glider pilot for many years. From 1988 to 1999 he was chief flight instructor for the Central Jersey Soaring Club. In 1999, he retired from soaring and took up the hobby of astrophotography. He regularly posts new astroimages on his astro gallery website.

Awards and honors

He was elected to the 2006 class of Fellows of the Institute for Operations Research and the Management Sciences. [12] In 2012 he became a fellow of the Society for Industrial and Applied Mathematics for "contributions to technologies for exoplanet searches and to interior-point methods for nonlinear optimization". [13] In 2014 he became a fellow of the American Mathematical Society, for "contributions to linear programming and nonlinear optimization problems". [14] In 2017 he was award the Khachiyan Prize by the INFORMS Optimization Society. [15]

Related Research Articles

Quadratic programming (QP) is the process of solving certain mathematical optimization problems involving quadratic functions. Specifically, one seeks to optimize a multivariate quadratic function subject to linear constraints on the variables. Quadratic programming is a type of nonlinear programming.

<span class="mw-page-title-main">Linear programming</span> Method to solve optimization problems

Linear programming (LP), also called linear optimization, is a method to achieve the best outcome in a mathematical model whose requirements and objective are represented by linear relationships. Linear programming is a special case of mathematical programming.

<span class="mw-page-title-main">Mathematical optimization</span> Study of mathematical algorithms for optimization problems

Mathematical optimization or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfields: discrete optimization and continuous optimization. Optimization problems arise in all quantitative disciplines from computer science and engineering to operations research and economics, and the development of solution methods has been of interest in mathematics for centuries.

In mathematics, nonlinear programming (NLP) is the process of solving an optimization problem where some of the constraints are not linear equalities or the objective function is not a linear function. An optimization problem is one of calculation of the extrema of an objective function over a set of unknown real variables and conditional to the satisfaction of a system of equalities and inequalities, collectively termed constraints. It is the sub-field of mathematical optimization that deals with problems that are not linear.

Narendra Krishna Karmarkar is an Indian mathematician. Karmarkar developed Karmarkar's algorithm. He is listed as an ISI highly cited researcher.

The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at each (triennial) International Symposium of the MOS. Originally, the prizes were paid out of a memorial fund administered by the AMS that was established by friends of the late Delbert Ray Fulkerson to encourage mathematical excellence in the fields of research exemplified by his work. The prizes are now funded by an endowment administered by MPS.

<span class="mw-page-title-main">Interior-point method</span> Algorithms for solving convex optimization problems

Interior-point methods are algorithms for solving linear and non-linear convex optimization problems. IPMs combine two advantages of previously-known algorithms:

Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets. Many classes of convex optimization problems admit polynomial-time algorithms, whereas mathematical optimization is in general NP-hard.

Karmarkar's algorithm is an algorithm introduced by Narendra Karmarkar in 1984 for solving linear programming problems. It was the first reasonably efficient algorithm that solves these problems in polynomial time. The ellipsoid method is also polynomial time but proved to be inefficient in practice.

<span class="mw-page-title-main">Margaret H. Wright</span> American computer scientist and applied mathematician (b. 1944)

Margaret H. Wright is an American computer scientist and mathematician. She is a Silver Professor of Computer Science and former Chair of the Computer Science department at Courant Institute of Mathematical Sciences, New York University, with research interests in optimization, linear algebra, and scientific computing. She was elected to the National Academy of Engineering in 1997 for development of numerical optimization algorithms and for leadership in the applied mathematics community. She was elected to the National Academy of Sciences in 2005. She was the first woman to serve as President of the Society for Industrial and Applied Mathematics.

<span class="mw-page-title-main">Dimitri Bertsekas</span> Greek electrical engineer

Dimitri Panteli Bertsekas is an applied mathematician, electrical engineer, and computer scientist, a McAfee Professor at the Department of Electrical Engineering and Computer Science in School of Engineering at the Massachusetts Institute of Technology (MIT), Cambridge, Massachusetts, and also a Fulton Professor of Computational Decision Making at Arizona State University, Tempe.

Yinyu Ye is a Chinese American theoretical computer scientist working on mathematical optimization. He is a specialist in interior point methods, especially in convex minimization and linear programming. He is a professor of Management Science and Engineering and Kwoh-Ting Li Chair Professor of Engineering at Stanford University. He also holds a courtesy appointment in the Department of Electrical Engineering. Ye also is a co-founder of minMax Optimization Inc.

MOSEK is a software package for the solution of linear, mixed-integer linear, quadratic, mixed-integer quadratic, quadratically constrained, conic and convex nonlinear mathematical optimization problems. The applicability of the solver varies widely and is commonly used for solving problems in areas such as engineering, finance and computer science.

<span class="mw-page-title-main">Criss-cross algorithm</span> Method for mathematical optimization

In mathematical optimization, the criss-cross algorithm is any of a family of algorithms for linear programming. Variants of the criss-cross algorithm also solve more general problems with linear inequality constraints and nonlinear objective functions; there are criss-cross algorithms for linear-fractional programming problems, quadratic-programming problems, and linear complementarity problems.

<span class="mw-page-title-main">Klee–Minty cube</span> Unit hypercube of variable dimension whose corners have been perturbed

The Klee–Minty cube or Klee–Minty polytope is a unit hypercube of variable dimension whose corners have been perturbed. Klee and Minty demonstrated that George Dantzig's simplex algorithm has poor worst-case performance when initialized at one corner of their "squashed cube". On the three-dimensional version, the simplex algorithm and the criss-cross algorithm visit all 8 corners in the worst case.

Artelys Knitro is a commercial software package for solving large scale nonlinear mathematical optimization problems.

<span class="mw-page-title-main">Affine scaling</span> Algorithm for solving linear programming problems

In mathematical optimization, affine scaling is an algorithm for solving linear programming problems. Specifically, it is an interior point method, discovered by Soviet mathematician I. I. Dikin in 1967 and reinvented in the U.S. in the mid-1980s.

Kim-Chuan Toh is a Singaporean mathematician, and Leo Tan Professor in Science at the National University of Singapore (NUS). He is known for his contributions to the theory, practice, and application of convex optimization, especially semidefinite programming and conic programming.

<span class="mw-page-title-main">Tamás Terlaky</span> Hungarian mathematician (born 1955)

Tamás Terlaky is a Hungarian-Canadian-American professor of Industrial and Systems Engineering at Lehigh University. He is especially well known for his work on criss-cross algorithms, interior-point methods, Klee-Minty examples for path following algorithms, and optimization.

James Milton Renegar Jr. is an American mathematician, specializing in optimization algorithms for linear programming and nonlinear programming.

References

This article incorporates material from Robert J. Vanderbei's bio, which is licensed under the Creative Commons Attribution/Share-Alike License.

  1. ↑ Vanderbei, R.J.: Toward a Stochastic Calculus for Several Markov Processes, PhD. Thesis, Cornell University, May 1981.
  2. ↑ Vanderbei, R.J.; Meketon, M.S.; Freedman, B.A.: A modification of Karmarkar's linear programming algorithm, Algorithmica, 1:395–407, 1986.
  3. ↑ Dikin, I.I.: Iterative solution of problems of linear and quadratic programming, Soviet Mathematics - Doklady, 8:674–675, 1967.
  4. ↑ Vanderbei, R.J.: Methods and Apparatus for Efficient Resource Allocation, U.S. Patent Number 4,744,026. Extension of Karmarkar algorithm to handle linear programming problems with free variables, May 1988.
  5. ↑ Vanderbei, R.J.: Methods and Apparatus for Efficient Resource Allocation, U.S. Patent Number 4,885,686. Extension of Karmarkar algorithm to handle linear programming problems with dense columns, December 1988.
  6. ↑ Freedman, B.A.; Meketon, M.S.; Vanderbei, R.J.: Methods and Apparatus for Efficient Resource Allocation, U.S. Patent Number 4,924,386. Extension of Karmarkar algorithm to handle linear programming problems with nonzero lower bounds and finite upper bounds, May 1990.
  7. ↑ Dantzig, G.B.; Goldfarb, D; Lawler, E; Monma, C; Robinson, S.M.: Report of the Committee on Algorithms and the Law, Optima, 33:1–19, June 1991.
  8. ↑ Helmberg, C; Rendl, F.; Vanderbei, R.J.; Wolkowicz, H.: An interior point method for semidefinite programming, SIAM Journal on Optimization, 6:342–361, 1996.
  9. ↑ Vanderbei, R.J.: LOQO: An interior point code for quadratic programming, Optimization Methods and Software, 12:451–484, 1999.
  10. ↑ Vanderbei, R.J.; Shanno, D.F.: An Interior-Point Algorithm for Nonconvex Nonlinear Programming, Computational Optimization and Applications, 13:231–252, 1999.
  11. ↑ Vanderbei, R.J.: Linear Programming: Foundations and Extensions, Kluwer Academic Publishers, 3rd edition, 2007.
  12. ↑ Fellows: Alphabetical List, Institute for Operations Research and the Management Sciences , retrieved 2019-10-09
  13. ↑ Society for Industrial and Applied Mathematics (SIAM)
  14. ↑ 2014 Class of the Fellows of the AMS, American Mathematical Society, retrieved 2014-08-12.
  15. ↑ Robert Vanderbei is selected as the winner of the 2017 INFORMS Optimization Society Khachiyan Prize
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.