Recent developments of optimization algorithms

This paper surveys recent developments of algorithms for solving various optimization problems. (1) Linear Programming: Three types of interior point algorithms, i.e., affine scaling methods, potential reduction methods and path-following methods, are discussed. Some recent attempts to apply the simplex method to real-world problems are also mentioned. (2) Nonlinear Programming: Quasi-Newton methods for unconstrained optimization and successive quadratic programming methods for constrained optimization are discussed. The proximal point algorithm for monotone operators is also discussed. (3) Network Optimization: Various algorithms for shortest path problems, max flow problems and min cost flow problems are mentioned, with particular emphasis on strongly polynomial algorithms. (4) Combinatorial Optimization: The polyhedral approach to combinatorial optimization problems is discussed using a travelling salesman problem as an example. [In Japanese.]