凸最適化の概要と主双対内点法のアルゴリズムの解説 - Qiita

はじめに 凸最適化問題に使われている主双対内点法の解説を目標に、凸最適化の概要を説明します。二次計画がメインターゲットです。 この記事は ソルバーは使ったことあるけど、もう少しアルゴリズムの中身が知りたい 凸最適を学びたいけど、最適化の章までの道のりが長すぎてつらい な方が対象です。いまどき1から凸最適アルゴリズム実装しようなんて物好きは稀だと思いますが、この記事の目的は主双対内点法を実装するための知識を全体的にふわっと理解することです。 二次計画でよく使われる 主双対内点法 と 有効制約法 を以下に可視化しました。解の求め方が全く異なることが分かります。コードはpythonです。 主双対内点法（primal dual interpoint） 内点法の系譜（有効領域の内部を進む） 徐々に相補性残差を減少させて最適解を得る 線形計画、二次計画、非線形計画まで幅広く対応可能 高次元の問題が得意

[sh19910711]

"もう少し複雑な問題が解きたいと勉強し始めると、双対定理、制約想定、実行可能解、スラック変数、ラグランジアン、などなど / KKT条件の論文が公開されたのは1951年であり、ラグランジュの未定乗数法の発見から200年"