## Course Title : Optimization

Code 90790 3rd year 2nd term 2 No Restriction Lecture H. Nagamichi, N. Yamashita, L. Zhao, ,

### Course Description

Mathematical programming or optimization is a methodology for modeling a real-world problem as a mathematical problem with an objective function and constraints, and solving it by some suitable procedure (algorithm). This course consists of lectures on basic theory and methods in nonlinear optimization and combinatorial optimization.

Based on the score of the term examination.

### Course Goals

To understand basic theory and algorithms in continuous optimization and combinatorial optimization.

### Course Topics

Theme Class number of times Description
Fundamentals of nonlinear optimization 2 Basic notions in continuous optimization such as global and local minima, convex sets and functions, gradients and Hessian matrices of multivariate functions.
Method of unconstrained optimization 2 Basic unconstrained optimization methods such as steepest descent method, Newton's method, quasi-Newton methods, conjugate gradient method.
Optimality conditions and duality 2 Optimality conditions for constrained optimization problems, called Karush-Kuhn-Tucker conditions, as well as the second-order optimality conditions and Lagrangian duality theory.
Methods of constrained optimization 1 Basic methods of constrained optimization such as penalty methods and sequential quadratic programing methods.
Combinatorial optimization 1 Typical combinatorial optimization problems such as traveling salesman problem and knapsack problem, and their computational complexity.
Branch-and-bound method and dynamic programming 2 Basic exact solution strategies for combinatorial optimization such as branch-and-bound method and dynamic programming.
Approximation algorithms 3 Approximation algorithms for hard combinatorial optimization problems, and their theoretical performance guarantees.
Summary and review 1 Summary and review. Confirmation of achievement level.

### Textbook(supplemental)

M. Fukushima, Introduction to Mathematical Programming: New Edition (in Japanese), Asakura Shoten ;
M. Yagiura and T. Ibaraki, Combinatorial Optimization - Metaheuristic Algorithms (in Japanese), Asakura Shoten .

### Prerequisite(s)

Linear Programming (90690) recommended.