甲斐性なしのブログ

うどんくらいしか食べる気がしない

連続最適化

IIRフィルタの設計問題を焼きなまし法で解いてみる

これは数理最適化 Advent Calendar 2022 の 23 日目の記事です。 はじめに ディジタルフィルタとは、離散時間信号に対し所望の周波数帯域の成分だけを通過させて他は阻止する機能のことを言う。中でもIIR (Infinite Impulse Response) フィルタはフィードバ…

HTTFで超球面上の最適化を試してみた話

はじめに AtCoder上で開催されたフューチャー社主催のヒューリスティックコンテストHACK TO THE FUTURE2022(HTTF)に参加した*1。問題等詳細は以下を参照。 atcoder.jp この問題は大きく分けて各作業者のスキル推定と作業スケジューリングという2つの要素が…

数理最適化をしっかり学ぶために主双対内点法とそれを使ったSVMを実装

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

数理最適化をしっかり学ぶために準ニュートン法を実装

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

数理最適化をしっかり学ぶために2段階単体法を実装

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

交互方向乗数法による最適化と画像ノイズ除去への応用

はじめに これまでの記事で近接勾配法と、それによるスパース解や低ランク解に導く正則化項を付随した最適化問題の解法、そしてその応用を見てきました。正則化項に変数間の絡みがなく各変数が独立に扱える場合は、正則化項のproximal operatorが解析的に求…

近接勾配法応用編その3~トレースノルム正則化項付きロジスティック回帰による行列データの分類~

はじめに 前回の記事では、ベクトルデータの分類問題に対するスパースなロジスティック回帰を説明しましたが、今回はその拡張となる行列データに対するロジスティック回帰を見ていきます。この行列データ分類問題においても正則化項は重要な役割を持ちますが…

近接勾配法応用編その2 ~L1ノルム正則化項によるスパースなロジスティック回帰~

今回は前々回の記事で書いた近接勾配法の応用例第2段ということで、分類問題などで使われるロジスティック回帰の目的関数にL1ノルムの正則化項をつけて、スパースな解を導いてみます。スパースな解を導出するメリットとしては、クラス分類に寄与しない無駄…

近接勾配法応用編その1 ~スパースコーディング、辞書学習からの超解像~

はじめに 前回の記事で近接勾配法の基本と実装を見てきました。今回はこの近接勾配法を利用して、スパースコーディングの応用の1つである超解像技術を調べPythonで実装してみました*1。画像処理関係の実装はほぼ未経験だったので、その分野の人が見れば前処…

近接勾配法とproximal operator

はじめに 前回、前々回とl1ノルム正則化項をつけた離散フーリエ変換により、スパースな解が得られること、そして基底ベクトルを並べた行列がユニタリ行列(直交行列)のため解析的に解けることを見てきました。それでは、が一般の行列の場合どうするか?今度…