はじめに シリーズ第3弾で今回は制約付き非線形計画問題を解く主双対内点法を実装した*1。前回の準ニュートン法の記事はこちら。 yamagensakam.hatenablog.com 制約付き非線形計画問題を式で表すと、以下のような最適化問題になる。 なお今回取り上げる主双…

はじめに 以前、以下の単体法の記事を書いた。 yamagensakam.hatenablog.com 今回はこのシリーズ第2弾で、以下の制約なし非線形計画問題を準ニュートン法で解くプログラムを実装する。 手法 制約なし非線形計画問題の解き方 非線形計画問題を解く際よく行わ…

はじめに 数理最適化には興味があってこのブログでもいくつか記事を書いてきたが、つまみ食いばかりして理解があいまいな部分もあるので、もう少しちゃんと基本から学ぶため以下の書籍を読み進めている。 しっかり学ぶ数理最適化 モデルからアルゴリズムまで…

はじめに 以前の記事にて最短経路問題を解くアルゴリズムの実装を書きましたが、今回はその続きとしてグラフアルゴリズムの中でも幅優先探索、深さ優先探索、union-find、最小全域木問題を解くアルゴリズム2種について実装を書いていきます。 例によって、自…

はじめに ここ１年くらい、ちまちまとatcoder中心に競技プログラミングに参加してたりします。ABCのD問題を解くのがやっとなのにAGCに突撃して爆死するってことを繰り返し続け、未だに緑コーダーです（パフォーマンスも1200前後がやっと）。こりゃまずいとい…

いやいや、お久しぶりです。 実に半年以上も更新が滞ってました。 ちゃんと生きてます。以前、動的計画法によるシーケンシャルデータのセグメンテーションという記事を書きましたが、 今回はそれを応用して、テキストセグメンテーションを行おうと思います。…

学生の頃、表題のアルゴリズムを研究に応用しようとしていましたが、すっかり忘れているので、思い出すために改めてPythonで実装してみました。当時は、matlabでfor文を回して実現していましたが、今回は、勉強がてらラムダ式やら再帰呼び出しやらを駆使して…