2021 Faculty Courses School of Computing Undergraduate major in Mathematical and Computing Science

Mathematical Optimization

Academic unit or major: Undergraduate major in Mathematical and Computing Science
Instructor(s): Makoto Yamashita / / Tianxiang Liu
Class Format: Lecture/Exercise
Media-enhanced courses: -
Day of week/Period (Classrooms): 3-4 Mon (W935) / 7-8 Mon (W935) / 3-4 Thu (W641)
Class: -
Course Code: MCS.T302
Number of credits: 210
Course offered: 2021
Offered quarter: 1Q
Syllabus updated: Jul 10, 2025
Language: Japanese

Syllabus

Course overview and goals

This course is composed of lectures and exercises. The lecture part first introduces linear programming problem, the most fundamental mathematical optimization problem. Then the lecture part overviews the simplex method and theoretical aspects of linear programming. The topic for nonlinear optimization problems includes the optimality conditions, the steepest descent method, the interior-point method. In the exercise part, students apply the simplex method to linear programming problems for understanding the computational steps of the simplex method, and give some parts of mathematical proof on optimization methods.

Mathematical optimization is a mathematical approach to find an optimal candidate from the set of candidates that satisfy specific conditions. It is closely related to scientific problems and it is widely employed to solve practical problems. For example, a diet problem in which we want to find a food recipe that minimizes the calories satisfying enough nutrients can be considered as an example of mathematical optimization problems. In this course , students learn both theoretical and computational aspects of optimization methods.

Course description and aims

At the end of this course, students will be able to:

(1) Solve linear programming using the simplex method
(2) Understand theoretical properties of linear programming, for example, the duality theorem
(3) Understand the relation between optimal solutions and optimality conditions
(4) Explain the framework of numerical methods to solve nonlinear optimization problems, for example, the steepest decent method and the interior-point method

Keywords

Linear programming, Simplex methods, Duality theorem, Sensitive analysis, Shortest path problem, Maximum flow problem, Convex function, Optimality condition for nonlinear optimization methods, Karush-Kuhn-Tucker condition, Steepest descent method, Newton method, Successive quadratic method, Interior-point method.

Competencies

Specialist skills
Intercultural skills
Communication skills
Critical thinking skills
Practical and/or problem-solving skills

Class flow

The lecture part overviews numerical methods and theoretical aspects. In the exercise part, exercise problems are assigned. Students apply the simplex method to linear programming problems by hand, and give a proof of optimization methods. For each exercise class, students submit reports.

Course schedule/Objectives

	Course schedule	Objectives
Class 1	Overview of mathematical optimization, Linear programming	Formulate some problems using the standard form of linear programming
Class 2	Simplex method	Solve linear programming problems by the simplex method.
Class 3	Exercise: Linear programming and Simplex method	Solve exercise problems related to linear programming and the simplex method
Class 4	Bland's rule, Two-phase simplex method	Apply Bland's rule and/or two-phase simplex method to linear programming problems.
Class 5	Dual problem, Duality theorem	Derive a dual problem from a linear programming problem. Derive a theoretical properties from weak duality theorem.
Class 6	Exercise: Two-phase simplex method and Duality theorem	Solve exercise problems related to two-phase simplex method and duality theorem
Class 7	Complementary theorem, Sensitivity analysis	Derive an optimal solution using the complementary theorem. Apply the simplex method in a matrix style.
Class 8	Shortest path	Analyze the sensitive of linear programming problems. Apply Dikstra's method to obtain the shortest path.
Class 9	Exercise: Complementary theorem and Shortest path	Solve exercise problems related to the complementary problem and shortest path
Class 10	Maximum flow problem and question time	Apply the Ford-Fulkerson algorithm to solve the maximum flow.
Class 11	Exercise problems to evaluate achievements and review the first part of the course	Evaluate the understanding on the first part of the course.
Class 12	Exercise: Maximum flow problem	Solve exercise problems related to maximum flow problems
Class 13	Nonlinear optimization, Convex set, Convex function	Formulate some problems as nonlinear optimization problems. Understand the definitions of convex sets and convex functions.
Class 14	Steepest descent method	Derive a proof on the convergence of the steepest descent method
Class 15	Exercise: Convexity and Optimality conditions	Solve exercise problems related to convexity and optimality conditions
Class 16	Newton method, Karush-Kuhn-Tucker condition	Explain the framework of Newton method. Derive relations between the KKT condition and optimal solutions.
Class 17	Lagrange function, Duality theorem	Derive relations between Lagrange function and the KKT condition.
Class 18	Exercise: Steepest descent method and Karush-Kuhn-Tucker condition, Duality theorem	Solve exercise problems related to steepest descent method, Karush-Kuhn-Tucker condition and duality theorem
Class 19	Successive quadratic method	Explain the framework of the successive quadratic method
Class 20	Interior-point method	Explain the framework of the interior-point method.
Class 21	Exercise: Successive quadratic method	Solve exercise problems related to successive quadratic method
Class 22	A review of this course	Re-solve all the excercise problems

Study advice (preparation and review)

To enhance effective learning, students are encouraged to spend a certain length of time outside of class on preparation and review (including for assignments), as specified by the Tokyo Institute of Technology Rules on Undergraduate Learning (東京工業大学学修規程) and the Tokyo Institute of Technology Rules on Graduate Learning (東京工業大学大学院学修規程), for each class.
They should do so by referring to textbooks and other course material.

Textbook(s)

None required. Parts of the course materials are based on the reference books below.

Reference books, course materials, etc.

・ Mathematical optimizaiton, Takahito Kuno, Maiko Shigeno, Junnya Goto, Ohmsha, 2012 (in Japanese)
・ Optimization Methods, Akihisa Tamura, Masakazu Muramatsu, Kyouritsu-shuppan, 2002 (in Japanese)
・ Linear and Nonlinear Optimization," Igor Griva, Stephen G. Nash, Ariela Sofer, SIAM,
2009
・　Linear Programming, Vasek Chvatal, Freeman, 1983
・ Linear Optimization, Glenn H. Hurlbert, Springer, 2010
・ Introductory Lectures on Convex Optimizaiton, Yurii Nesterov, Kluwer Academic Publishers, 2004

Evaluation methods and criteria

Students will be assessed on their understanding on the simplex method for linear programming problems, duality theorem, network optimization problems, and numerical methods and optimality conditions for nonlinear optimization problems.
Students' course scores are based on the final exam (80%) and exercise reports (20%).
[In the case that the final exam is not available, a final report will be used instead.)

Related courses

MCS.T203 ： Linear Algebra and Its Applications
MCS.T322 ： Combinatorial Algorithms

Prerequisites

Students must have studied Linear Algebra and Its Applications (MCS.T203) or have equivalent knowledge.

Other

(FY2021) The final exam will be given in-person during the examination period. Depending on the situation of the new corona virus, it may be given as an online examination or a final report.