2017年6月17日土曜日

TeX のソースコードをテキストに変換

TeX のソースコードをテキストに変換するスクリプトが
https://github.com/subbyte/tex2text/blob/master/tex2text.sh
にあった。

これを使うと、あとで英語の文法チェックのソフトなどにある程度一括でかけることができるので、だいぶ便利になる。

2017年6月16日金曜日

研究ネタになりそうなこと (SIAM Optimization 2017から)

先月参加してきた SIAM Conference on Optimization 2017 で、今後の内容になりそうな内容をメモとして残しておく。

ちなみに、セッション情報などは
http://meetings.siam.org/program.cfm?CONFCODE=OP17
で見ると分かる。
例えば、[MS1-2] はセッション MS1 の中の2番目の発表。

なお、ここにある情報は一部を取り除いてあって、完全版は別途あり。


== 2017/05/22 ==

[MS1-2] The Conic Optimizer in Mosek: A Status Report
Mosek が Ver 8 になって、40% 程度高速になったとのこと。
やはり、問題の再定式化などが要綱。
テスト問題として、以下の論文のものを用いていて、
Reduced-Complexity Semidefinite Relaxation of Optmial Power Flow Problems
http://ieeexplore.ieee.org/document/6692873/
データを作るプログラムがgithubで公開されている。
https://github.com/martinandersen/opfsdr

[MS1-3]
de Klerk の話で、First-order method で最もパフォーマンスが出ないのがどういう
状況なのかを解析するのに SDP を使うっていう話。
基本的には、内積は内積であればどの内積を使ってもよく、重要な情報は Gram 行列に集約される。
思うに、kernel trick のようなものなので、再生ヒルベルト空間の性質が聞いているのでは?
解析では、SDP を解くのではなく、特定のLagrange 乗数を使って KKT 条件を満たしている。
この Lagrange 乗数は、まだ幾何学的な解釈がないようなので、そのあたりも調べたら面白そう。
self-concordant にも似たように拡張していて、現在は内点法について拡張中。
たぶん、inexact Newton だったり、quasi Newton だったりで亜種を作れそう。
論文は Optimization Letter に To appear で、ドラフトとしては、
arXiv:1606.09365

[MS25-2]
SCIP-SDP の話。
SDPA も SDP ソルバーの一つに入れてもらっているけど、
最近の性能向上をさぼっていたためか、ちょっとダメな感じ。
もっと性能を上げるようにしないと。

[MS25-4]
Mixed-Integer Sum of Squares を Julia のパッケージで解く、という話。
Julia のパッケージとしては、MultivariatePolynomial.jl, PolyJuMP.jl,
SumofSquares.jl などがあって、これらを使うと、多項式最適化問題から
SDP 緩和を作るのがとても簡単にできる、ということ。
また、Steering a quadcopter through obstacles では、
Mixed-Integer Sum of Squares で
「障害物を避けながら進む」っていう計算ができていて、
これは計算結果をグラフィック表示で楽しむことができるので、
デモンストレーションなどにいいかもしれない。
(ただ、このデモンストレーションの計算については、論文などにはまだなっていない様子。)

[CP8-4]
サプライチェーンのロバスト版を考えることで SOCP が出てくる、ということ。
また、KKT 条件などから、均衡状態が示されている、ということなので、
SOCP の応用として覚えておくと面白そう。
というか、あっちの応用に組み合わせたら面白い。

== 2017/05/23 ==

[IP-3] Tom Luo の通信に関係する最適化問題の話。
interference の計算に WMMSE という座標降下法の一種を用いていて、
WMMSE はデファクトスタンダードとして用いられている、とのこと。
このときの目的関数はなかなかに複雑になっているので、
あとで細かいところを確認したら面白いかもしれない。

[MS39-1] min c^T x s.t. x in P \cap S で、
P は Ax <= b で S は closed set。
Disjunctive cut を outer-product-free という考えを用いて作られている。
テスト問題には GLOBALLib からとっている。
このGLOBALlib には多項式最適化のベンチマークも含まれるようなので、
いろいろとチェックしたら面白そうだ。

[MS41-2]
arXiv:1702.00526 https://arxiv.org/abs/1702.00526
問題は、min{f(x) | Qx = z, x in Conv(X), z in Z}
Subgradient, Proximal Point Method, Augmented Lagrangian Method,
Bundle Method との関係を調べることで、新しいアルゴリズムを作る。
Proximal SDM (Simplical decomposition method) では、
proximal point method の探索方向の近似を計算していて
column generation と同じ感じで探索領域が広がっていくようだ。
nonlinear SDM-GS (Gauss-Seidel) -ALM の方法を提案していて、
収束などを示しているようだ。
column geration が関係しているから、ほかのところにも使えるかも。

[MS41-3]
内点法ベースで Boyd らが作っているのが Forces というソフトウェア。
Augmented Lagrangian Filter という手法の大域的収束性を示している。
メモリが少ないような組み込み環境でも問題が解ける、ということなので、
に適したアルゴリズムとして考えれば、これは化けるかもしれない。
この話では、空冷システムのようなものの最適化計算を組み込み環境で計算していた。
http://ieeexplore.ieee.org/document/7902123/

[MS40-4]
Monte Carlo ので Adaptive Sampling Method を計算している。

[MS56-1]
Stochastic Mixed Integer Programming の計算を PIPS-SBB という
分子限定法の並列計算で行っている。
大まかに各ノードに割りあてする Coarse-grained と、もっと細かい制御で
並列計算する Fine-grained の2段階割り当てを行う。
ただ、200台ぐらいでパフォーマンスに限度が来る様子。
思うに、何台で最大パフォーマンスになるか、っていう予測があれば役に立ちそう。

[MS56-3]
並列計算の評価基準をどうするべきか、っていう話。
計算時間が遅くても、スケーラビリティーだと高く表示されてしまう危険性がある。

[MS57-3]
Birgin の発表。
ARC (adaptive regularization with cubics)
TRACE (a non-standard trust-region method that uses cubic descent)

f(x+s) <= f(x) - alpha*||s||^3
と最後が3乗になっているのがポイント。
これにより、2乗のときよりも全体の反復回数は抑えられる。
その一方で各反復の計算は2次計画問題を解く必要があって、コストが高い。
思うに、ニュートン法でも反復回数がかかるような問題に有効なのでは?
つまり、first-order < ニュートン法 < cubics のような感じ。

今後の研究では、min f(x) s.t. l <= x <= u のように
上限下限など制約を入れていったときにどうなるか、ということ。

The use of quadratic regularization with a cubic descent condition
for unconstrained optimization
(To appear SIAM J. Optim)
https://www.ime.usp.br/~egbirgin/publications/bmregu.pdf
https://www.ime.usp.br/~egbirgin/sources/bmregu/

[MS57-4]
問題の制約が線形制約な問題に対して、
Gradient Projection Algorithm (GPA) と
Linear Constrained Optimizer (LCO) を繰り返していく
PASA (Polyhedral Active Set Algorithm) というのを作った。
また、 Strong second-order assumption という仮定を導入して、
よりいろんなことを証明している。
Polyhedron への射影は PPPOJ という Hager/Zhang の方法を使う。
また、Dual Active Set Algorithm とも関係があり、
計算の途中で preconditined CG などを使ったりする。
あとは、Grippo のような Non-monotone なども使う。

テスト問題は、Cutest から持ってきている。
結果の比較は IPOPT (デフォルトパラメータ使用)と比較している。
あと、BIGBANK というテスト問題集があり、これには条件数が 10^8 などの
テスト問題が含まれている。
今回の結果は、いかに掲載されている、ということ。
An active set algorithm for nonlinear optimization with polyhedral constraints
https://link.springer.com/article/10.1007/s11425-016-0300-6

=== 2017-05-24===

[IP-4] Renegar の subgradient の話。
Plenary にもかかわらず、概要とか短めに切り上げて、思いっきりコアな数式に突入するあたりが、
うっとりするほど素敵。
通常の subgradient とは違った内容の subgradient なわけだけど、
自己双対錐の性質を使って単位ベクトルに移動してから計算するあたりが面白い。
話の内容としては、Optimization Online に乗っていたのがベース。

[CP12-1]
graph-valued version of total variation っていう話。
全てのラグランジュ乗数が定数になる場合には、実は制約なし最適化問題を解けば十分、
というのがとても面白い性質だった。
ちなみに、出てきている問題は2次計画問題に帰着していたけど、これが凸ではないので、
そう簡単には解けないはず。

[CP15-5]
カラテオドリの一般化の話。
このあたりは、理論的な枠組みと実際の数値計算がずれるかもしれないので、
もしずれるのであれば、それをどうやって修正するか、とか考えたら実用に使えるかも。

[CP15-6]
Conic Programming の実行可能でないとかいろいろと分岐するのを
ADMM  の計算過程に基づいて判別している。
このあたりは、SDPA の判別基準とも似たようなことになっているので、
その二つの論文を突き合わせて比較すると、もう少し詳細に踏み込めるはず。
(たぶん、SDPA のパラメータの omega についての考察とか。)
そういった情報をうまく取り入れていくと、面白いことがわかるかも。