本稿は [1] の p115 手続き 4.1 として紹介されている歪対称行列を用いた線形計画問題が内点 を含むようにする手順について考察を行うものです。 [1] 並木誠 線形計画法(朝倉書店, 2008) drive.google.com

Solver (May 22, 2020) [S] Solver (問題を解くアルゴリズムを内包し, それを実行して解を探索するアプリケーション) [M] Modeler (解く問題をプログラムで作成するためのアプリケーション) Nonlinear or Linear Programming NLP (Nonlinear Programming) MI…

グラフィカルモデル （機械学習プロフェッショナルシリーズ） [ 渡辺 有祐 ]価格：3024円（税込、送料無料) (2019/2/7時点)楽天で購入

Qiitaに記事を投稿しました。 一階の常微分方程式は, 一般に の形で記述されます。 は独立な変数, は既知の二変数関数であり, は求める未知関数です。 (中略) まずは, 1つの一階の常微分方程式の解軌跡を求める方法を紹介します。 また, この解法は高階の微…

さて, 求根アルゴリズム最終回はデッカー法とそれを改良したブレント法を紹介します。 ブレント法はMATLABの非線形関数の根をみつける関数fzeroにも用いられている有用なアルゴリズムになっています。 デッカー法(Dekker method) ブレント法(Brent method) …

求根アルゴリズム第2回です。今回は挟み撃ち法と, その応用形である イリノイ法とアンダーソンビューク法を紹介します。 挟み撃ち法(False position method) イリノイ法(Illinois method) アンダーソン・ビョーク法(Anderson & Björk's method) 挟み撃ち法(F…

本稿から3回に分けて様々な求根アルゴリズムを紹介したいと思います。 求根とは、ある関数 の根, すなわち を満たす を求めることです。 もし が微分可能であれば微積分の知見を用いて根を見つけることは容易な場合も多いですが、今回は関数 が微分不可能、…

「劣モジュラ最適化と機械学習」(講談社) 5.1.2節 双対ノルムとフェンシエル共役 の中に以下のような記述があります。 劣モジュラ最適化と機械学習 （機械学習プロフェッショナルシリーズ） [ 河原吉伸 ]価格：3024円（税込、送料無料) (2018/12/2時点)楽天…

この記事の続きです。 今回やりたいのは, ある画像を元にノイズを付加した画像を数枚用意します。 そのノイズが付加した数枚の画像から元の画像を復元することを考えます。 前回の記事のを事後確率を用いて以下のように決定します。 ということで, 上記の考…

この記事の応用です。 商品とビンに順序をつけた場合のビンパッキング問題になります。 ソースコード 実行結果 入力 うさぎ0が食べるりんごの量は1.2 うさぎ1が食べるりんごの量は2.2 うさぎ2が食べるりんごの量は1.0 うさぎ3が食べるりんごの量は0.7 うさぎ…

離散数学の組合せ論の代表的な問題としてビンパッキング問題というのがあります。 十分に用意された品物を、複数個のビン(容器)に詰めるときの最大利益を求める問題です。 このときビンの個数が1つであればナップサック問題と呼ばれる問題になります。 この…

ダブリングという計算手法に感動したので、No.572 妖精の演奏 - yukicoderこの問題の解説を書こうと思います。 問題文を読むと、なるほどいかにも動的計画法チックな問題ですね、 ということで、最初は普通に以下のような定式化を行いました。 gist.github.c…

上の記事で紹介したMATLABのcsapiはdeBoorの公式を用いて双3次スプラインを行っています。 この記事ではそのdeBoorの公式を自作してみたいと思います。 アルゴリズム さて、ここでどのようにfxやfyを計算するかというと、 この記事の方法を用います。スプラ…

csapi関数を用いて双3次スプライン関数の生成と復元を行います。 双スプラインとは2変数のスプライン関数のことです。 言い換えれば平面の補間関数になります。 まずはソースコードから。 peaksというMatlabのサンプル関数からいくつかを標本点を取り出して…

問題設定 一次近似 二次近似 三次近似 この三次近似について、幾何的にどう捉えられるのかを考えてみました。 (面積で議論することもできると思います) 四次近似については’Runge-Kutta法’という方法が知られています。 それについては、こちらをどうぞ ルン…

有理スプライン補間をMatlabで実装してみました。 有理スプライン補間とは3次スプライン補間の3次の項を双曲線関数に置き換えたものです。 有理スプラインはパラーメータをうまく調節することで、 3次スプライン補間(参考: 3 次スプライン データ内挿 - MATL…

Cbcとはオープンソースの混合整数線形計画(mixed integer liner program)ソルバーです。混合整数線形計画問題とは線形計画問題の中に連続変数と、整数変数が混合している問題のことになります。 そのCbcソルバーで並列処理を行えるようにするには、下記のよ…

これの後編です。 実際に簡単な関数でいくつか補間による近似を行なってみたいと思います。 fが近似したい関数、gがデータ点(0, 0) (1, 1) (2, 2)から構成した差分商補間になります。 fは2次式でかつ、前編の最後の定理「剰余なしのn項からなるNewtonの差分…

Newtonの差分商補間の理論についてです。内容は高校レベルでしょうか。 最後の定理は強力ですね。 補間といえば、他にはLagrange補間が有名ですが、 Lagrange補間よりも計算量が少ないことが特徴です。 一番最後の証明は、「n点を補間するn-1次の多項式はLag…

最近、線形計画問題に取り組んでいまして、以下のようなバイナリ変数xを定義する必要が出てきました。 バイナリ変数とは0と1の2値のみをとり得る変数のことです。 これがなかなか難しくて、いろいろ調べてみて、 2通りの定式化を行いました。 1つ目は以下の…

グラフの最短路問題はダイクストラ法等で解くのが普通ですが、 今回も線形計画法で解いてみたいと思います。(あえてね) ↓その1です。 inarizuuuushi.hatenablog.com が定式化となります。(とするとが続いているところは無視してください) 路の制約として、フ…

グラフの最短路問題はダイクストラ法等で解くのが普通ですが、 今回は線形計画法で解いてみたいと思います。(あえてね) 定式化は こうなります。 最短路を解く問題なのに目的関数が最大化になっているところが面白いですね。 ad(j)については、jの隣接ノード…

上記のグラフのstartからgoalまでの最短路を求めたいとします。 (グラフの枝の重みは枝の長さ) 直感的には、startとgoalから離れた点や枝を考える必要はない(i.e.最短路にそれらの点や枝が含まれることがない)ように思えますが、それをどう厳密に表現するか?…

newton法とは、目的関数の最小化元(或いは最大化元)を求める問題に対する反復法と呼ばれる解法の一つです。 関数fと勾配、初期点を問題に合わせて入力する必要があります。

最急降下法とは、目的関数の最小化元(或いは最大化元)を求める問題に対する反復法と呼ばれる解法の一つです。 目的関数fと勾配、初期点を問題に合わせて入力する必要があります。

ある二つの三角形について、その形と大きさが等しいとき、それらは「合同である」と言います。 この合同についてみなさん、中学校で以下の三つの合同条件を習ったと思います。 ・三辺相等 ・二辺狭角相等 ・二角狭辺相等 例えば三辺相等について、 三角形の…

完全マッチングについて面白い定理を見つけたので、ご紹介します。 まず、完全マッチングについて、 グラフ理論においてマッチングとは、グラフ中の枝集合で、互いに端点を共有しないもののこと。特に、これ以上枝を追加できないもののことを極大マッチング…

今回は Chapter2 劣モジュラ最適化の基礎 2.4 列もジュラ最適化と多様体の 貪欲解の最適性についてです。 ラグランジュ緩和については以下のPDFが分かりやすくまとまっていると思います。 http://www.bunkyo.ac.jp/~nemoto/lecture/opt-model/2008/duality1-…

「劣モジュラ最適化と機械学習」という河原先生と永野先生が書かれた本を最近勉強しています。 https://www.amazon.co.jp/劣モジュラ最適化と機械学習-機械学習プロフェッショナルシリーズ-河原-吉伸/dp/4061529099/ref=sr_1_fkmr0_1?ie=UTF8&qid=1492411085…