投稿
グラフ理論の関係の論文をチェックしている。
このあたりは、NPな問題が多いため、今回読んだ論文にあった手法としては
(1) 分枝限定法
(2) 近似アルゴリズム
(3) 貪欲アルゴリズム
(4) 遺伝的アルゴリズム
が載っていた。
遺伝的アルゴリズムは最適化では最強のアルゴリズムであるので、ここには触れないことにして、(1) & (2) の組み合わせなどでどうなるか、というのをもう少し調べてみようかとも思っている。
今日の作業内容：論文読み込み(2h) + 論文推敲(2h)
明日の予測作業時間：4h
2014年10月21日火曜日
Matlab のバージョンアップとファイアウォール設定
Matlab のバージョンアップは半年ごとであるが、そのたびにライセンスサーバー上でファイアウォールを通すための設定をしなおす必要がある。
基本的には、license.dat の
DAEMON MLM "/usr/local/MATLAB/R2014b/etc/MLM"
の行で最後にポート番号を指定する必要があって、前バージョンの情報を自動的に引き継げるわけではないので、手作業での作業となる。
そういえば、手作業といえば、Matlab のインストールも、インストーラーでアカウント確認をするにもかかわらず、別途ブラウザからlicense.datをダウンロードしてこないとインストールできない。
Matlab は半年ごとのバージョンアップでは性能差がほとんどないので Windows や Linux ならバージョンアップをする必要性は特にないのだが、Mac の場合は OS X であってもバージョンの差が大きいので（OSとして上位互換性が維持されない場合がそれなりにある）、Matlab をバージョンアップしないと上手く動かないことがある。
今日の作業内容：Matlab バージョンアップ, グラフ理論の論文読み込み
明日の予測作業内容：論文推敲の続き
基本的には、license.dat の
DAEMON MLM "/usr/local/MATLAB/R2014b/etc/MLM"
の行で最後にポート番号を指定する必要があって、前バージョンの情報を自動的に引き継げるわけではないので、手作業での作業となる。
そういえば、手作業といえば、Matlab のインストールも、インストーラーでアカウント確認をするにもかかわらず、別途ブラウザからlicense.datをダウンロードしてこないとインストールできない。
Matlab は半年ごとのバージョンアップでは性能差がほとんどないので Windows や Linux ならバージョンアップをする必要性は特にないのだが、Mac の場合は OS X であってもバージョンの差が大きいので（OSとして上位互換性が維持されない場合がそれなりにある）、Matlab をバージョンアップしないと上手く動かないことがある。
今日の作業内容：Matlab バージョンアップ, グラフ理論の論文読み込み
明日の予測作業内容：論文推敲の続き
2014年10月20日月曜日
久しぶりに再開
最近、このブログの更新が止まっていたので、久しぶりに再開することにする。
止まっていた理由の一つとして、そのときに考えている内容が証明であっただけでなく、相当な紆余曲折が多かったことがある。
そのまま書いていたとすると、
○月１日：証明の方法Ａ⇒失敗
止まっていた理由の一つとして、そのときに考えている内容が証明であっただけでなく、相当な紆余曲折が多かったことがある。
そのまま書いていたとすると、
○月１日：証明の方法Ａ⇒失敗
○月２日：証明の方法Ｂ⇒失敗
...
...
○月２６日：証明の方法Ｚ⇒失敗
という感じになっている。
ちなみに、この証明は３か月か４か月ぐらい考えたところで、あるとき証明の方針がわかって、そこからは１０日ほどで証明ができている。
数学の証明は、詳細などを詰めていなくても、「これで証明できる」ということがフィーリングがあると、詳細などもなんとかなる、というあたりが不思議でもある。
今日の作業内容：論文の推敲
明日の予測作業内容：論文の推敲の続き
2014年5月28日水曜日
英語で書くときの注意点
英語を書く上で指摘された部分で、今の自分が特に気をつけておくべき点などをいくつか列挙しておく。
１：$(i,j)$ element -> the $(i,j$th element が正しい
２：memory space という表現は、memory だけで十分
１：$(i,j)$ element -> the $(i,j$th element が正しい
２：memory space という表現は、memory だけで十分
３：in, of , on などの違いをしる (the right-hand side の前置詞は on the right-hand sideが多いっぽい)
４：compared to と compared with は意味が違う
５：On the contray と In constrast は意味が違う
６：since と because は意味や使い方が違う
７：fully-dense は、正しくは fully dense
８：Section 名は The から始めない
９：表に書くときの「時間の単位は秒」という表現は (time in seconds)
１０：計算時間の各パートごとなど詳細は its detail でなくて its breakdown
また気がついた点があったら、このリストを順次書き足すことにする。
2014年5月26日月曜日
SIAM Optimization 2014 で聞いてきたことのメモ
先週一週間で San Diego で行われた SIAM Optimization 2014 に参加してきたので、
その中で面白そうな発表をメモとして残しておく。
なお、他のセッションなども手書きメモはあるが、ここにはあとで再度調べたいものなどを中心にまとめている。
==============================================================
SIAM Optimization 発表メモ
2014/05/19
** MS16[3]
Sampling with in Algorithmic Recursions
Raghu Pasupathy, Virginia Tech, USA
Sampling Controlled Stochastic Recursions (SCSR)
最適化で探索する点を乱数を用いてサンプリングして構成するが、
サンプリングする領域を制御することで収束速度を向上させる。
（信頼領域法なイメージ？）
SCSR の論文は Dupuis & Shimha 1991 で、Dupuis のページを見ると
最適停止問題の論文もあるので、そのあたりに近い可能性あり。
On sampling-controlled stochastic approximation, (with R. Simha),
IEEE Trans. on Auto. Control 35 (1991), pp. 915—925.
** CP7[6]
A Numerical Method for Design Optimal Experiments for
Model Discrimination under Model and Data Uncertainities
Hilke Stibble et al, University of Marburg, Germany
Differential Algebraic Equation というのを対象にしている。
Robust などとも関連性あり。
2014/05/20
** MS27[3]
A Sequential Linear-Quadratic Programming Method
for the Online Solution of Mixed-Integer Optimial Control Problems
Christian Kirches, University of Heidelberg, Germany
目的関数に積分が入っていて、制約式には微分方程式が入っている最適化問題。
Mixed Integer Opimial Control Problem を反復法で解く感じか。
コンセプトとしては、Discrete first, then treat combination。
ソフトとしては、Baron や Minotaur のようなところに近いらしい。
発表を聞く限り、今回の発表は
F. Logist, S. Sager, C. Kirches, J.F. van Impe.
Efficient multi objective optimal control of dynamic systems with integer controls.
Journal of Process Control, 20(7), pp. 810-822, August 2010.
をベースにしている研究のようなので、こちらを読むと概要がもう少しわかるか？
** MS42[1]
Optimal Fractionation in Radiotherapy
Minsun Kim et al, University of Washington, USA
がんなどの治療に放射線をあてるときに、どのようにすれば
がんを取り除きしつつ、健康な細胞を維持できるのか、という研究。
特に、体のどちらから放射線を当てるか、という物理的な内容というよりも、
どのような時間間隔であてるのか、という点に注目している。
目的関数は、線形項と２次項からできている、とのこと。
また、今回の提案手法だと有限反復で解が得られるとのこと。
参考になりそうな文献は、
Optimization of Radiation Therapy Fractionation Schedules in the Presence of Tumor Repopulation
Thomas Bortfeld, Jagdish Ramakrishnan, John N. Tsitsiklis, Jan Unkelbach
http://arxiv.org/abs/1312.1332
このあたりの研究では、どのようにして数値実験のデータを入手しているのか、
自分で調べる必要がありそう。
** MS42[2]
A Mathematicla Optimization Approach to the Fractionation Problem in Chemoradiotherapy
Ehsan Salari et al, Wichita State University
こちらは、がんの治療などの研究を Fracitionation Problem に定式化しており、
Dynamic Programming で解を得ている。
今回の発表は、同じタイトルで arxiv にすでに掲載されている。
http://arxiv.org/abs/1312.5657
** MS59[2]
On the convergence of the self-consistent field iteration
in Kohn-Sham Density Functional Theory
Xin Liu et al, Chinese Academy of Sciences
量子化学での電子構造計算の基本である SCF 法は収束が保証されていなかったかと
自分は記憶しているが、この発表では、ある程度の仮定の範囲では収束を
示せるとのこと。
細かい内容は、arxiv にある論文で確認できそう。
http://arxiv.org/pdf/1302.6022v2.pdf
** MS65[4]
SDPNAL+: A Majorized Semismooth Newton-CG Augmented Lagrangian Method for
Semidefinite Programming with Nonnegative Constraints
Liuqin Yang et al, National University of Singapore
今回は他の発表を聞いていて、こちらを聞けなかったので、あとで
メールなどでコンタクトを取ってみることにする。
2014/05/21
** MS12[1]
Disjuctive Conic Cuts for Mixed Integer Second Order Cone Optimization
Julio C. Goez et al, Lehigh University, USA
整数混合２次錘計画問題を解くのに、線形カットだけでなくて、
もっと複雑なカットを入れられることを提唱している。
理論的な性質はいいものの、計算量が大きく実用的かは疑問、とのこと。
http://phd.ie.lehigh.edu/~jgoez/wp-content/uploads/thesisJCGoez.pdf
に博士論文があり、これに細かく書かれている。
また、
http://www.optimization-online.org/DB_FILE/2012/06/3494.pdf
にも内容がまとめられている。
http://www.lehigh.edu/ise/documents/11t_007.pdf
も参考になりそう。
** CP24[6]
Robust Optimization Reduces the Risks Occuring from Delineation Uncertanities
in HDR Brachytherapy for Prostate Cancer
Marleen Balvert et al, Tilburg, the Netherlands
以下の２つの互いに反するものをどう扱うか。
1. Deliver prescribed dose to target
2. Spare sorrounding organs
ロバスト最適化にも触れており、以下の論文が参考になりそう。
Effcient Schemes for Robust IMRT Treatment Planning,
A Olafsson and S J Wright
http://pages.cs.wisc.edu/~swright/papers/uwopt-0601.pdf
Linear programing formulations and algorithms for radiotherapy treatment planning
http://pages.cs.wisc.edu/~swright/papers/goms113455.pdf
** CP26[2]
Approximating the Minimum Hum Cover Problem on Planar Graphs
and Its Application to Query Optimization
Belma Yelbay et al, Sabanci University, Turkey
Minimum-Hub-Cover Problem は NP 困難で、Approximation Algorithm などを
考えている、とのこと。
Graph-Query-Processing は、ビジュアルとして面白そうな内容になりそう。
内容としては、arxiv にすでに掲載されていて、
http://arxiv.org/abs/1311.1626
2014/05/22
** MS107[3]
Mutli Stage Convex Relaxation Approach for Low Rank Structured PSD Optimal Problems
Defeng Sun, National University of Singapore
Rank 最小化に帰着される Matrix Recovery の問題を、目的関数に
Lowner operator という関数を取り入れることで、等価な別表現に変更。
ここで complementality condition がやっかいなので、これを
目的関数にペナルティ項として移動するが、ペナルティの重さが一定以上なら
最適解が得られることを示している。
Lowner operator のあたりを理解すると、他のことにも応用が利きそう。
発表資料は、すでに PDF でもらってある。
その中で面白そうな発表をメモとして残しておく。
なお、他のセッションなども手書きメモはあるが、ここにはあとで再度調べたいものなどを中心にまとめている。
==============================================================
SIAM Optimization 発表メモ
2014/05/19
** MS16[3]
Sampling with in Algorithmic Recursions
Raghu Pasupathy, Virginia Tech, USA
Sampling Controlled Stochastic Recursions (SCSR)
最適化で探索する点を乱数を用いてサンプリングして構成するが、
サンプリングする領域を制御することで収束速度を向上させる。
（信頼領域法なイメージ？）
SCSR の論文は Dupuis & Shimha 1991 で、Dupuis のページを見ると
最適停止問題の論文もあるので、そのあたりに近い可能性あり。
On sampling-controlled stochastic approximation, (with R. Simha),
IEEE Trans. on Auto. Control 35 (1991), pp. 915—925.
** CP7[6]
A Numerical Method for Design Optimal Experiments for
Model Discrimination under Model and Data Uncertainities
Hilke Stibble et al, University of Marburg, Germany
Differential Algebraic Equation というのを対象にしている。
Robust などとも関連性あり。
2014/05/20
** MS27[3]
A Sequential Linear-Quadratic Programming Method
for the Online Solution of Mixed-Integer Optimial Control Problems
Christian Kirches, University of Heidelberg, Germany
目的関数に積分が入っていて、制約式には微分方程式が入っている最適化問題。
Mixed Integer Opimial Control Problem を反復法で解く感じか。
コンセプトとしては、Discrete first, then treat combination。
ソフトとしては、Baron や Minotaur のようなところに近いらしい。
発表を聞く限り、今回の発表は
F. Logist, S. Sager, C. Kirches, J.F. van Impe.
Efficient multi objective optimal control of dynamic systems with integer controls.
Journal of Process Control, 20(7), pp. 810-822, August 2010.
をベースにしている研究のようなので、こちらを読むと概要がもう少しわかるか？
** MS42[1]
Optimal Fractionation in Radiotherapy
Minsun Kim et al, University of Washington, USA
がんなどの治療に放射線をあてるときに、どのようにすれば
がんを取り除きしつつ、健康な細胞を維持できるのか、という研究。
特に、体のどちらから放射線を当てるか、という物理的な内容というよりも、
どのような時間間隔であてるのか、という点に注目している。
目的関数は、線形項と２次項からできている、とのこと。
また、今回の提案手法だと有限反復で解が得られるとのこと。
参考になりそうな文献は、
Optimization of Radiation Therapy Fractionation Schedules in the Presence of Tumor Repopulation
Thomas Bortfeld, Jagdish Ramakrishnan, John N. Tsitsiklis, Jan Unkelbach
http://arxiv.org/abs/1312.1332
このあたりの研究では、どのようにして数値実験のデータを入手しているのか、
自分で調べる必要がありそう。
** MS42[2]
A Mathematicla Optimization Approach to the Fractionation Problem in Chemoradiotherapy
Ehsan Salari et al, Wichita State University
こちらは、がんの治療などの研究を Fracitionation Problem に定式化しており、
Dynamic Programming で解を得ている。
今回の発表は、同じタイトルで arxiv にすでに掲載されている。
http://arxiv.org/abs/1312.5657
** MS59[2]
On the convergence of the self-consistent field iteration
in Kohn-Sham Density Functional Theory
Xin Liu et al, Chinese Academy of Sciences
量子化学での電子構造計算の基本である SCF 法は収束が保証されていなかったかと
自分は記憶しているが、この発表では、ある程度の仮定の範囲では収束を
示せるとのこと。
細かい内容は、arxiv にある論文で確認できそう。
http://arxiv.org/pdf/1302.6022v2.pdf
** MS65[4]
SDPNAL+: A Majorized Semismooth Newton-CG Augmented Lagrangian Method for
Semidefinite Programming with Nonnegative Constraints
Liuqin Yang et al, National University of Singapore
今回は他の発表を聞いていて、こちらを聞けなかったので、あとで
メールなどでコンタクトを取ってみることにする。
2014/05/21
** MS12[1]
Disjuctive Conic Cuts for Mixed Integer Second Order Cone Optimization
Julio C. Goez et al, Lehigh University, USA
整数混合２次錘計画問題を解くのに、線形カットだけでなくて、
もっと複雑なカットを入れられることを提唱している。
理論的な性質はいいものの、計算量が大きく実用的かは疑問、とのこと。
http://phd.ie.lehigh.edu/~jgoez/wp-content/uploads/thesisJCGoez.pdf
に博士論文があり、これに細かく書かれている。
また、
http://www.optimization-online.org/DB_FILE/2012/06/3494.pdf
にも内容がまとめられている。
http://www.lehigh.edu/ise/documents/11t_007.pdf
も参考になりそう。
** CP24[6]
Robust Optimization Reduces the Risks Occuring from Delineation Uncertanities
in HDR Brachytherapy for Prostate Cancer
Marleen Balvert et al, Tilburg, the Netherlands
以下の２つの互いに反するものをどう扱うか。
1. Deliver prescribed dose to target
2. Spare sorrounding organs
ロバスト最適化にも触れており、以下の論文が参考になりそう。
Effcient Schemes for Robust IMRT Treatment Planning,
A Olafsson and S J Wright
http://pages.cs.wisc.edu/~swright/papers/uwopt-0601.pdf
Linear programing formulations and algorithms for radiotherapy treatment planning
http://pages.cs.wisc.edu/~swright/papers/goms113455.pdf
** CP26[2]
Approximating the Minimum Hum Cover Problem on Planar Graphs
and Its Application to Query Optimization
Belma Yelbay et al, Sabanci University, Turkey
Minimum-Hub-Cover Problem は NP 困難で、Approximation Algorithm などを
考えている、とのこと。
Graph-Query-Processing は、ビジュアルとして面白そうな内容になりそう。
内容としては、arxiv にすでに掲載されていて、
http://arxiv.org/abs/1311.1626
2014/05/22
** MS107[3]
Mutli Stage Convex Relaxation Approach for Low Rank Structured PSD Optimal Problems
Defeng Sun, National University of Singapore
Rank 最小化に帰着される Matrix Recovery の問題を、目的関数に
Lowner operator という関数を取り入れることで、等価な別表現に変更。
ここで complementality condition がやっかいなので、これを
目的関数にペナルティ項として移動するが、ペナルティの重さが一定以上なら
最適解が得られることを示している。
Lowner operator のあたりを理解すると、他のことにも応用が利きそう。
発表資料は、すでに PDF でもらってある。
2014年4月21日月曜日
サクラエディタで Aspell のマクロを作ってみる（不完全版）
サクラエディタを最近試してみており、そのなかからスペルチェックの Aspell を呼び出そうと考えている。
ただ、TeX Wiki の情報
http://oku.edu.mie-u.ac.jp/~okumura/texwiki/?%E3%82%B5%E3%82%AF%E3%83%A9%E3%82%A8%E3%83%87%E3%82%A3%E3%82%BF%2F%E3%83%9E%E3%82%AF%E3%83%AD
からたどれる情報は更新されていないようで、現在のサクラエディタだとうまく利用できなかった。
少しマクロなどを修正して、現状としては以下のようにしている。
--- aspell.js ----
(function () {
var c = Editor.ExpandParameter("$e");
var b = Editor.GetFilename();
var cd = "cd /d " + ["\"", c, "\""].join("");
var aspellcmd = "\"c:\\Program\ Files\ \(x86\)\\Aspell\\bin\\aspell.exe\" --lang=en -c -t" + " " + ["\"", b, "\""].join("");
var cmd = "cmd /c " + cd + " && chcp 65001 && " + aspellcmd;
Editor.FileSave();
var objShell = new ActiveXObject("WScript.Shell");
objShell.Run(cmd,1,1);
Editor.FileClose();
var movecmd = "cmd /c " + cd + " && " + "move " + b + ".new " + b;
objShell.Run(movecmd,1,1);
}.call(this));
ただ、TeX Wiki の情報
http://oku.edu.mie-u.ac.jp/~okumura/texwiki/?%E3%82%B5%E3%82%AF%E3%83%A9%E3%82%A8%E3%83%87%E3%82%A3%E3%82%BF%2F%E3%83%9E%E3%82%AF%E3%83%AD
からたどれる情報は更新されていないようで、現在のサクラエディタだとうまく利用できなかった。
少しマクロなどを修正して、現状としては以下のようにしている。
--- aspell.js ----
(function () {
var c = Editor.ExpandParameter("$e");
var b = Editor.GetFilename();
var cd = "cd /d " + ["\"", c, "\""].join("");
var aspellcmd = "\"c:\\Program\ Files\ \(x86\)\\Aspell\\bin\\aspell.exe\" --lang=en -c -t" + " " + ["\"", b, "\""].join("");
var cmd = "cmd /c " + cd + " && chcp 65001 && " + aspellcmd;
Editor.FileSave();
var objShell = new ActiveXObject("WScript.Shell");
objShell.Run(cmd,1,1);
Editor.FileClose();
var movecmd = "cmd /c " + cd + " && " + "move " + b + ".new " + b;
objShell.Run(movecmd,1,1);
}.call(this));
--- ここまで ---
これを設定フォルダ（サクラエディタの「設定」->「共通設定」として出てくるダイアログの左下にある「設定フォルダ」を押すと表示されるフォルダ）において、「共通設定」の「マクロ」タブで登録すると利用できるようにはなる。
ただ、まだ機能面で不足があって、
(1) a.txt を Aspell にかけると a.txt.new というファイルに結果が保存されて、a.txt.new を a.txt に移動している。このあとで、 Editor.FileReopen() をかけると空の状態でエディタに表示されてしまう（ファイルが「無題.txt」になる）。「X」ボタンでファイルを一度閉じた後に、もう一度開けると、Aspell のかかった結果を表示できる。
(2) ファイルが UTF-8 の場合、コマンドプロンプトのコードを chcp 65001 で UTF-8 に変換しているが、フォントが合わないため日本語部分が誤って表示される。Aspell 自身は日本語部分を飛ばして処理するようで処理自体は問題ないのだが、フォントを変更するにはレジストリを regedit で修正する方法がある。regedit ではなく、コマンドプロンプトからのコマンドで修正できるかどうか、がよく分かっていない。
となっている。
2014年4月10日木曜日
要約メモ：Math Prog A, Vol 144, No. 1-2
だいたいどんなことが研究されているか、一部の論文を抜粋して簡単にメモしておく。
[1] Iteration complexity of randomized block-coordinate descent methods for minimizing composite function
Richtarik and Takac
Nesterov の一次法のあたりでよく見かける
min : F(x) = f(x) + Psi(x)
の形式の問題を解いている。ベースになっているのは、Nesterov の 2012 の SIAM J. Optim の論文だが、ここでは、ベクトル x をいくつかのブロックに分解して、それぞれのブロックごとに手法を適用している。これは、例えば、 x のうちのx_1 から x_100 まで、などブロック単位で区切って処理しないとならないほど大きな問題などを想定できる。
解析の中では、Lipsitz 連続や strong convexity などを利用するタイプ。
また、完全に最適解に収束させるわけではなくて、確率的に収束させるタイプ。（99% 以上の確率で最適値とのずれが 0.01 以内、といった感じ。）
[2] On the complexity of finding first-order critical points in constrained nonlinear optimization
Cartis, Gould and Toint
min: f(x) such that c(x) = 0
という制約付き最適化問題に対する KKT 条件の近似解を求めるのに必要な計算量は、
min: fbar(x)
のように制約なしの場合から本質的には増えたりしない、ということを言っている。
解析の道具としては、信頼領域法のアルゴリズムを利用している。
[3] An introduction to a class of matrix cone programming
Ding, Sun and Toh
この論文のMatrix cone programming は、
min { c^T x | A x \in b + Q \times K}
の形で定式化されている。ここで、Qは基本的には対称錘なので、second-order cone や SDP などを含む。また、 K は epigraph による錘で、
epi (f) = {(t,X) : t \ge f(X)}
といったもの。
このような定式化に含まれるのは、Matrix completion, Robust PCA, 低ランク行列近似などがある。
アルゴリズムの基本要素は、錘などへの射影計算。
[4] A unified approach for minimizing composite norms
Aybat and Iyengar
この論文も composite の関数の最小化で
min mu_1 || F(X) -G ||_{alpha} + mu_2 || C(X) -d ||_{beta}
subject to A(X) - b \in Q.
という問題が対象。ここで、alpha と beta のノルムは 1-norm, 2-norm などがある。
解法としては、augmented Lagrangian がベース。
[1] Iteration complexity of randomized block-coordinate descent methods for minimizing composite function
Richtarik and Takac
Nesterov の一次法のあたりでよく見かける
min : F(x) = f(x) + Psi(x)
の形式の問題を解いている。ベースになっているのは、Nesterov の 2012 の SIAM J. Optim の論文だが、ここでは、ベクトル x をいくつかのブロックに分解して、それぞれのブロックごとに手法を適用している。これは、例えば、 x のうちのx_1 から x_100 まで、などブロック単位で区切って処理しないとならないほど大きな問題などを想定できる。
解析の中では、Lipsitz 連続や strong convexity などを利用するタイプ。
また、完全に最適解に収束させるわけではなくて、確率的に収束させるタイプ。（99% 以上の確率で最適値とのずれが 0.01 以内、といった感じ。）
[2] On the complexity of finding first-order critical points in constrained nonlinear optimization
Cartis, Gould and Toint
min: f(x) such that c(x) = 0
という制約付き最適化問題に対する KKT 条件の近似解を求めるのに必要な計算量は、
min: fbar(x)
のように制約なしの場合から本質的には増えたりしない、ということを言っている。
解析の道具としては、信頼領域法のアルゴリズムを利用している。
[3] An introduction to a class of matrix cone programming
Ding, Sun and Toh
この論文のMatrix cone programming は、
min { c^T x | A x \in b + Q \times K}
の形で定式化されている。ここで、Qは基本的には対称錘なので、second-order cone や SDP などを含む。また、 K は epigraph による錘で、
epi (f) = {(t,X) : t \ge f(X)}
といったもの。
このような定式化に含まれるのは、Matrix completion, Robust PCA, 低ランク行列近似などがある。
アルゴリズムの基本要素は、錘などへの射影計算。
[4] A unified approach for minimizing composite norms
Aybat and Iyengar
この論文も composite の関数の最小化で
min mu_1 || F(X) -G ||_{alpha} + mu_2 || C(X) -d ||_{beta}
subject to A(X) - b \in Q.
という問題が対象。ここで、alpha と beta のノルムは 1-norm, 2-norm などがある。
解法としては、augmented Lagrangian がベース。
登録:
投稿 (Atom)