整数計画法(integer programming)とは、線形の条件のもとで線形の目的関数を最適にする問題に、変数が整数であるという条件を加えた問題を解く方法で、人の割当、施設の選択、作るか作らないかの決定の計算に使う。整数の条件を外した線形計画緩和は最大化の問題の上界を与え、これを場合分けと組み合わせた分枝限定法は、有界な問題を有限回で解く。行列が完全単模で右辺が整数なら緩和の頂点は整数で、線形計画だけで解ける。切除平面は整数解を残して緩和の解を切り落とす不等式である。
54分前に投稿
動的計画法と最適制御(dynamic programming and optimal control)とは、決定を何段にも重ねる問題を、ある状態から先の最適費用を表す価値関数の漸化式(Bellman 方程式)に直し、終わりの段から後ろ向きに解く計算の型である。最適な列の後半はそれ自身最適であるという Bellman の最適性原理が根拠で、状態と行動が有限なら表の計算になる。線形の系と 2 次の費用では Riccati 漸化式で最適なフィードバックの係数が求まり、割引のある無限期間の問題は価値反復で解ける。在庫管理、機械の保守、制御器の設計に使う。
56分前に投稿
ウェーブレット(wavelet)とは、1 つの関数 $\psi$ を 2 倍ずつ縮め整数ずつずらした関数 $\psi_{j,k}(x)=2^{j/2}\psi(2^jx-k)$ で信号を展開する方法である。多重解像度解析(閉部分空間の増加列 $V_j$ と、整数平行移動が $V_0$ の正規直交基底になる尺度関数 $\varphi$ で、和集合の稠密性・共通部分が $0$・2 倍の伸縮の条件を満たすもの)のウェーブレットについて、$\{\psi_{j,k}\}$ は $L^2(\mathbb{R})$ の正規直交基底になる。尺度方程式の有限なフィルタを使う高速ウェーブレット変換は、長さ $N$ の信号を $O(N)$ 回の掛け算で分解・再構成する。滑らかな部分の係数は速く小さくなるので、信号・画像の圧縮と雑音の除去に使う。
1時間前に投稿
変分推論(variational inference)とは、Bayes 統計で計算の難しい事後分布を、扱いやすい分布の族の中で Kullback–Leibler ダイバージェンスの意味で最も近い分布で近似する方法である。周辺尤度の対数は ELBO(evidence lower bound)とこの KL ダイバージェンスの和に等しいので、周辺尤度を計算せずに ELBO を最大にすればよい。分布を座標ごとの積に限る平均場近似では、因子を 1 つずつ最適にする座標上昇法で ELBO は減らず、最適な因子は他の因子による対数同時密度の期待値の指数で与えられる。正規分布の事後分布では平均は正しく求まるが、分散は小さく見積もられる。
1時間前に投稿
戸田格子(Toda lattice)とは、直線上の粒子が隣どうし指数関数のポテンシャルで作用し合う Hamilton 力学系である。位置と運動量を対称三重対角行列に組むと運動方程式は Lax 方程式になり、その固有値が保存量を与えて、系は完全可積分である。解は行列の指数関数の QR 分解で明示的に書け、時刻 $1$ の流れは行列の指数関数に施す QR 法の 1 段に一致する。長時間では粒子は遠くへ散らばって等速運動に近づき、衝突の前後で速度の組は順序を逆にして入れ替わるだけである。
1時間前に投稿
Temperley–Lieb代数(Temperley–Lieb algebra)とは、可換環 $R$ の元 $\delta$ について、生成元 $e_1,\dots,e_{n-1}$ と関係式 $e_i^2=\delta e_i$、$e_ie_{i\pm1}e_i=e_i$、離れた添字の可換性で定まる結合代数 $\mathrm{TL}_n(\delta)$ のことである。交わらない弧の図を重ねる積で実現され、階数 $C_n$ の自由加群である。Markov 型のトレース、Jones–Wenzl 射影子、$\delta=-A^2-A^{-2}$ での組紐群の表現をもち、Jones 多項式を与える。
1時間前に投稿
面積分(surface integral)とは、空間の曲面の上で関数やベクトル場を積分することで、曲面を $r(u,v)$ と表し $dS=\lvert r_u\times r_v\rvert\,du\,dv$ を代入して重積分で計算する。スカラー場の面積分は薄い板の質量・重心・平均値を与え、ベクトル場の面積分(流束)$\iint_SF\cdot n\,dS$ は面を通り抜ける量を与える。値は媒介変数によらず、流束だけは向きを逆にすると符号が変わる。流量や電場の流束の計算では、発散定理、同じ縁の面への張り替え、縁の線積分も使える。
1時間前に投稿
サポートベクターマシン(support vector machine)とは、2 つの類に分かれたデータ $(x_i,y_i)$($y_i=\pm1$)を超平面 $\langle w,x\rangle+b=0$ で分ける分類の方法で、超平面から最も近いデータ点までの距離(マージン)が最大のものを選ぶものである。マージンの最大化は $y_i(\langle w,x_i\rangle+b)\ge1$ のもとで $\frac12\|w\|^2$ を最小化する凸 2 次計画の問題で、その双対問題の解 $\alpha$ により $w=\sum_i\alpha_iy_ix_i$ と書け、$\alpha_i>0$ の点(サポートベクター)はマージンの境界の上にある。分離できないデータには条件の破れに罰を課すソフトマージンを使い、内積をカーネルに置き換えると非線形の境界が得られる。
1時間前に投稿
状態空間表現(state-space representation)とは、線形な系を、状態 $x$ の 1 階の連立微分方程式 $x'=Ax+Bu$ と出力の式 $y=Cx+Du$ の組で書く方法である。解は $e^{tA}$ を使った 1 つの公式で計算でき、伝達関数は $G(s)=C(sI-A)^{-1}B+D$ で得られ、逆にプロパーな有理関数は標準形で状態空間表現に直せる。1 入力 1 出力では、次数が最小の実現は可到達かつ可観測な実現と一致し、座標変換を除いてただ 1 つである。多入力多出力の系の解析、数値計算、制御の設計に使う。
1時間前に投稿
球面三角形の垂線(altitudes of a spherical triangle)とは、球面三角形の各頂点から向かいの辺の大円に垂直に引いた大円である。点を単位ベクトル、大円を法線で表すと、頂点 $A$ からの垂線の法線は $\vec a\times(\vec b\times\vec c)$ であり、3 本の法線の和は外積の Jacobi 恒等式により $\vec 0$ になる。このため、どの頂点も向かいの辺の大円の極でなければ、3 本の垂線はちょうど 1 組の対蹠点で交わり、この交点は極三角形の垂心とも一致する。
1時間前に投稿