論文 / 著書情報
Article / Book Information
題目(和文)
Title(English)

Study on Cutting-plane Algorithms for Mixed-integer Semidefinite
Optimization

著者(和文)

小林健

Author(English)

Ken Kobayashi

出典(和文)

学位:博士(工学),学位授与機関:東京工業大学,
報告番号:甲第11762号,
授与年月日:2022年3月26日,
学位の種別:課程博士,
審査員:中田 和秀,水野 眞治,松井 知己,塩浦 昭義,梅室 博行

Citation(English)

Degree:Doctor (Engineering),
Conferring organization: Tokyo Institute of Technology,
Report number:甲第11762号,
Conferred date:2022/3/26,
Degree Type:Course doctor,Examiner:,,,,

学位種別(和文)

博士論文

Category(English)

Doctoral Thesis

種別(和文)

論文要旨

Type(English)

Summary

Powered by T2R2 (Tokyo Institute Research Repository)

（博士課程）Doctoral Program論 文 要 旨ＴＨＥＳＩＳ ＳＵＭＭＡＲＹ

系・コース：
Department of, Graduate major in

経営工学
経営工学

学生氏名：
Student’s Name系コース

小林健

申請学位（専攻分野）： 博士
Academic Degree Requested

指導教員（主）：Academic Supervisor(main)

Doctor of（工学）中田和秀

指導教員（副）：Academic Supervisor(sub)要旨（和文 2000 字程度）
Thesis Summary （approx.2000 Japanese Characters ）本論文は「Study on Cutting-plane Algorithms for Mixed-integer Semidefinite Optimization」(混合整数半正定値最適化問題に対する切除平面法の研究)と題するもので，混合整数半正定値最適化問題を解く切除平面法に関連する研究をまとめたものである．混合整数半正定値最適化問題とは，半正定値制約と整数制約のもとで線形目的関数を最小化する最適化問題である．この問題は非線形性と離散性をもつ最適化問題であり，工学の諸分野で現れる多くの最適化問題は混合整数半正定値最適化問題として定式化される． このような背景から，混合整数半正定値最適化問題に対する高速な解法を設計することは工学的に重要な価値を持つ．本論文は以下の６章で構成される．
第１章：「Introduction」（はじめに）では，混合整数半正定値最適化問題の重要性と，切除平面法に着目する本論文の動機と位置づけについて述べている．これまで混合整数線形最適化問題の解法には分枝限定法が一般的に用いられるが，混合整数半正定値最適化問題の場合，線形の最適化問題で使えるウォームスタート戦略が活用できず，大規模な問題を現実的な時間で解くことは難しい．このような背景から、本論文では混合整数半正定値最適化問題に対する新しいアプローチとして切除平面法に着目する．切除平面法は、複雑な制約条件や目的関数を扱う最適化手法であり，その拡張性と実装の容易さから、問題構造を利用して混合整数半正定値最適化問題を解く可能性を秘めている
第２章：「Branch-and-cut Algorithm for Mixed-integer Semidefinite Optimization」(混合整数半正最適化問題に対する分枝切除法)では，混合整数半正定値最適化問題の標準形に対する切除平面法ベースの解法を述べている．本章でははじめに半正定値最適化問題に対する切除平面法を拡張した解法を提案し，その収束性を議論している．また計算をより効率化するため，提案した切除平面法と分枝限定法を組み合わせた分枝切除法による解法もあわせて提案している．
第３章：「Cutting-plane Algorithm for Best Subset Selection for Eliminating Multicollinearity」(多重共線性を除去するための最良部分集合選択問題に対する切除平面法)では，線形回帰モデルから多重共線性を除去するための最良部分集合選択問題に注目する．線形回帰モデルを用いた分析では，説明変数間に一次従属の関係があると推定量の信頼性が損なわれる多重共線性という問題がある．本章では，多重共線性を検出する指標として説明変数の相関係数行列の条件数に着目し，相関係数行列の条件数に制約を与えたもとで最小二乗推定を行う変数選択問題を混合整数半正定値最適化問題として定式化した．また，条件数の制約に関する性質を活用した切除平面法を提案して，その有効性を数値実験により検証している．
第４章：「Cutting-plane Algorithm for Cardinality-constrained Distributionally Robust PortfolioOptimization」(基数制約つき分布ロバストポートフォリオ最適化問題に対する切除平面法)では，基数制約つき分布ロバストポートフォリオ最適化問題に注目する．この問題は基数制約によって生じる離散性と不確実性集合を表現するための半正定値制約から混合整数半正定値最適化問題として定式化される．本章では，この問題を２段階最適化問題として再定式化し，劣勾配を用いて上位問題を解く切除平面法を設計した．また下位問題に表れる問題の構造を活用して，劣勾配の算出に必要な計算量を削減した．
第５章：「Bilevel Cutting-plane Algorithm for Cardinality-constrained Mean-CVaR Portfolio Optimization」(基数制約つき平均-CVaR モデルに対する切除平面法)では，第４章で提案した切除平面法の枠組みを拡張し，条件付きバリュー・アット・リスクを最小化する基数制約つきポートフォリオ最適化問題に対する効率的解法を提案する．この問題は混合整数半正定値最適化問題の特殊ケースである混合整数線形最適化問題として定式化されるが，問題の規模が条件付きバリュー・アット・リスクの近似に用いるシナリオ数に依存するという問題がある．
そこで，第４章で述べた切除平面法に，条件付きバリュー・アット・リスクを効率的に最小化する別の切断面法をサブルーチンに組み込み，多数シナリオでも高速に動作する解法を設計した．
第６章：「Conclusion and Prospects」(結論と今後の展望)では，本論文で取り上げた研究成果をまとめ，混合整数半正定値最適化における切除平面法の可能性を議論するとともに，今後の展望について述べている．
備考：論文要旨は、和文 2000 字と英文 300 語を 1 部ずつ提出するか、もしくは英文 800 語を 1 部提出してください。
注意：論文要旨は、東工大リサーチリポジトリ（T2R2）にてインターネット公表されますので、公表可能な範囲の内容で作成してください。

（博士課程）Doctoral Program論 文 要 旨ＴＨＥＳＩＳ ＳＵＭＭＡＲＹ

系・コース：

経営工学

Department of, Graduate major in

学生氏名：
Student’s Name

小林健

系
コース

申請学位（専攻分野）： 博士
Academic Degree Requested

指導教員（主）：Academic Supervisor(main)

Doctor of（工学）中田和秀

指導教員（副）：Academic Supervisor(sub)要旨（英文 300 語程度）
Thesis Summary （approx.300 English Words ）This thesis focuses on mixed-integer semidefinite optimization problems, which minimize or maximize
a linear objective function subject to constraints wherein a given matrix formed from the decision variables
is positive semidefinite, and some of the variables are integer-valued. Since this problem includes
nonlinearity and discreteness, various practical optimization problems can be formulated as amixed-integer optimization problem. However, studies on algorithms for mixed-integer semidefinite
optimization problems are relatively few, and solving large-sized mixed-integer semidefinite optimization
problems has been difficult in practice. With this background in mind, this thesis reviews some
cutting-plane algorithms for efficiently solving mixed-integer semidefinite optimization problems.
Cutting-plane algorithms are optimization techniques to handle complex constraints or an objectivefunction. Because of the extendability and ease of implementation, the cutting-plane algorithms have thepotential to efficiently solve mixed-integer semidefinite optimization problems by exploiting thestructure of the individual problems.
First, we consider the standard form of the mixed-integer semidefinite optimization problems and propose
a general-purpose cutting-plane algorithm for solving it. We also devise a branch-and-cut algorithm toimprove computational efficiency, which integrates the cutting-plane algorithm and a branch-and-boundalgorithm.
Second, we focus on the best subset selection problem for eliminating multicollinearity from linear
regression models. We give a mixed-integer semidefinite optimization formulation of the problem, in which
a subset of explanatory variables is selected under an upper bound on the condition number of the correlation
matrix of the selected variables. Then, we propose a specialized cutting-plane algorithm that exploits
the structure of the condition number constraint.
Finally, we focus on portfolio selection problems formulated as a mixed-integer semidefiniteoptimization problem. Specifically, we consider a distributionally robust portfolio optimization problem
with limiting the number of invested assets. By exploiting the problem structure, we develop a scalable
cutting-plane algorithm for solving the model with the technique of positive semidefinite matrixcompletion. In addition, we extend the cutting-plane algorithm for the cardinality-constrained
distributionally robust portfolio optimization so as to deal with another portfolio optimization problem
that minimizes the conditional value-at-risk under a cardinality constraint.
For this problem, we propose a cutting-plane method that incorporates into its subroutine anothercutting-plane algorithm that efficiently minimizes the conditional value-at-risk. From these results,
we discuss the potential of cutting-plane algorithms for mixed-integer semidefinite optimization.

備考 : 論文要旨は、和文 2000 字と英文 300 語を 1 部ずつ提出するか、もしくは英文 800 語を 1 部提出してください。
注意：論文要旨は、東工大リサーチリポジトリ（T2R2）にてインターネット公表されますので、公表可能な範囲の内容で作成してください。