2018年1月30日火曜日

論文読み:An improved version of Chubanov’s method for solving a homogeneous feasibility problem



An improved version of Chubanov’s method for solving a homogeneous feasibility problem
http://www.tandfonline.com/doi/full/10.1080/10556788.2017.1368509

をざっと読んでみた。Chubanov の方法を改良して性能を上げるっていうものだった。

この論文を読んでいて気が付いたけど、Chubanov の方法は norm の取り方が結構重要なので、双対 norm を入れると dual の方法が作れるのかー。
数値結果については Gurobi よりも良いということになっているけど、問題が小さいので何とも言い難いところかと。数値実験はオマケのような立ち位置なのかもしれない。

2018年1月28日日曜日

3次元以上のSDP の錐は、SOCP では表現できない

2次元の半正定値行列の成す錐が SOCP で書けることは良く知られている事実だけど、3次元以上の場合に SOCP では書けない、ということが証明されていた。
詳しくは、
On representing the positive semidefinite cone using the second-order cone
https://link.springer.com/article/10.1007%2Fs10107-018-1233-0
に載っていた。

そういえば、SOCP を LP で任意精度で近似するのは LPP を使えばできるけど、SDP を SOCPで任意精度で近似するっていうのは出来るんだろうか?
それが今後の展開なんだろうか?


2018年1月18日木曜日

論文読み:A Network Flow Model for Irrigation Water Management

灌漑施設についてネットワーク最適化問題として定式化して解く、という論文があったので目を通してみた。

A Network Flow Model for Irrigation Water Management
https://journals.lib.unb.ca/index.php/AOR/article/view/20397

解く手法は、min cost flow を使っている。
論文のモデルは結構面白いかと思うが、この論文をベースに何かするとしたらベンチマーク問題のようなものがないとちょっと難しいかと思う。
やはり、データが整理されている、というのは重要な点なのかもしれない。


2018年1月10日水曜日

論文読み:Augmented Lagrangian functions for cone constrained optimization: the existence of global saddle points and exact penalty property

今回は、Journal of Global Optimization に掲載されていた
Augmented Lagrangian functions for cone constrained optimization: the existence of global saddle points and exact penalty property
をチェックしてみた。

基本的には、タイトルが示す通り、錐最適化問題についての augmented Lagrangian についての理論的性質を調べている、というものだった。
数値解法については特に触れてなくて、解の性質などを中心に解析している感じだった。


この論文とはちょっと離れるが、最近はinexact な Newton 法、内点法、augmented Lagrangian については調べるようにしていて、こういったものを使うと SDP に対する内点法を今までよりも高速に計算できるアルゴリズムを作れるかも、と思ったりしている。
(どうやってアルゴリズムを作ればいいか、という全体の枠組みは分かりつつあるので、それぞれのステップをきちんと作る方法を調べている、というところ。)