学部・大学院区分
Undergraduate / Graduate

理学部

時間割コード
Registration Code

0619100

科目区分
Course Category

専門科目
Specialized Courses

科目名　【日本語】
Course Title

数理解析・計算機数学Ⅲ

科目名　【英語】
Course Title

Computational Mathematics and Computer Science Ⅲ

コースナンバリングコード
Course Numbering Code

担当教員　【日本語】
Instructor

平井広志 ○

担当教員　【英語】
Instructor

HIRAI Hiroshi ○

単位数
Credits

開講期・開講時間帯
Term / Day / Period

秋水曜日１時限
秋水曜日２時限
Fall Wed 1
Fall Wed 2

授業形態
Course style

講義
Lecture

学科・専攻
Department / Program

多元数理科学研究科

必修・選択
Compulsory / Selected

選択

授業の目的　【日本語】
Goals of the Course(JPN)

テーマ：数理最適化入門
与えられた条件のもとで，ある関数を最小にする解（または最大にする解）を求めることを最適化という．最適化は現代情報社会の様々な意思決定を基盤から支える技術である．本講義では，最適化の基礎となる数学理論と最適化のアルゴリズムについて解説する．社会に出てから最適化を使う際に役立つ知識・技能の習得を目指すとともに，最適化で使われる数学（凸解析，線形不等式・多面体論など）の面白さに触れる．これらは，他分野の数学研究においてもしばしば有用である．例えば，離散最適化における効率的アルゴリズムの設計は，理論計算機科学のみならず，離散数学・グラフ理論と密接に関わっている．

授業の目的　【英語】
Goals of the Course

Theme: Introduction to Mathematical Optimization
Finding a solution that minimizes (or maximizes) a function under given conditions is called optimization. Optimization is a technology that supports various decision-making processes in the modern information society. In this lecture, the mathematical theory underlying optimization and optimization algorithms will be explained. The course aims to provide students with knowledge and skills that will be useful when they use optimization in the real world, and to introduce them to the fascinating aspects of mathematics used in optimization (convex analysis, linear inequalities, polytope theory, etc.). These are often useful in other areas of mathematical research as well. For example, the design of efficient algorithms in discrete optimization is closely related to discrete mathematics and graph theory as well as theoretical computer science.

到達目標　【日本語】
Objectives of the Course(JPN))

最適化で使われる数学を理解すること．解きたい具体的な問題を最適化問題へと定式化する能力，そして，その最適化問題がどの問題クラスに属するか見極める能力，そして，適切な解法アルゴリズムを選択する・設計する能力，そして，既存のソフトウェアやライブラリを使いこなす能力を習得する．

到達目標　【英語】
Objectives of the Course

To understand mathematics used in optimization. To acquire the ability to formulate a specific problem to be solved into an optimization problem, to determine which problem class the optimization problem belongs to, to select and design an appropriate algorithm, and to master the use of existing software and libraries.

授業の内容や構成
Course Content / Plan

凸最適化を中心にその数理や解法アルゴリズムについて講義する．
また，最適化のソフトウェアやライブラリを用いた実習を行う．

1. 線形計画
線形不等式系の一般論，双対定理，相補性条件，単体法，楕円体法，内点法．

２. 非線形計画・凸計画
凸解析の基礎，KKT条件，勾配法，ニュートン法，錐計画・半正定値計画．

3. 離散最適化
計算複雑度（PとNP）, 多項式時間アルゴリズム, 整数計画法，LP緩和・多面体的手法，
ネットワーク最適化，近似アルゴリズム．

より詳しい講義内容は初回に説明する．

履修条件
Course Prerequisites

線形代数，微分積分，位相の初歩