2018年2月11日日曜日

Knuth 以上の天才なんじゃないだろうか

Knuth といえばアルゴリズムを勉強したことがあるような人なら誰でも知っている超有名研究者なわけだけど、TeX の基礎を創った開発者としても超有名。

その Knuth を超えるんじゃないか、と個人的に思うのが
http://www.kabipan.com/densan/article.html
の内容。
簡単にいうと、TeX の主要な機能である自動番号付けと相互参照を Java Script で作ってしまう、というもの。
しかも、世の中には Mathjax もあるし、Java Script で bibtex も処理できてしまうようだし、TeX で作られている論文の9割以上は TeX をインストールしなくても HTML + Mathjax + Java Script で、論文としての読むに堪えるものは再現できるのではないかと思ってしまう。(というか、オンラインで論文を読んでいるときには、最近ではほとんどの機能がそうやって再現されているみたいだし。)


まぁ、こういうのが気になっているのも、そもそも TeX が衰退してきているなぁ、と感じるところにある。
https://www.slideshare.net/iesli/20141108-senooken-tex
によると TeX, LaTeX などの検索回数は 1/3 程度に減ってきているようで、世界の研究者の数が1/3に減ったりしてはいないだろうから、TeX は新しい研究者には支持されていない、ということを示唆しているのではないかと思ったりする。

TeXLive はインストールすると 2.5 GB 以上の容量があるし、Android などのタブレットやスマホへの移植も進んでいない。
PC でのコンパイルも、PCそのものの性能は向上しているけど、TeX 処理系が遅くなっていて、10年前のほうが高速にコンパイルできたんじゃないか?って思ったりするほど。

それだったら、いっそのこと、HTML + Mathjax + Java Scriptで作ってしまった方がいいのではないかと思う。
これならブラウザが動いていれば CJK の問題もブラウザが吸収してくれるし、開発する部分は100MBもないだろうから(1MB でも主要な機能の9割はいけるのでは?)、少ない人数でも十分に開発できるかもしれない。
エディタとブラウザがあればいいから、Android や Chromebook などでも十分に論文を書けると思う。TeX の挫折理由の一つであるインストールも簡単になるだろうから、挫折する人は減るだろうし。



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 に対する内点法を今までよりも高速に計算できるアルゴリズムを作れるかも、と思ったりしている。
(どうやってアルゴリズムを作ればいいか、という全体の枠組みは分かりつつあるので、それぞれのステップをきちんと作る方法を調べている、というところ。)

2017年12月28日木曜日

SIAM Optimization 2017 での SDP 関係の発表を一覧にしてみた

SIAM Optimization 2017 での SDP 関係がどんなものがあるのかを調べてみたので、一覧を掲載しておく。
基本的にはタイトルだけだけど、タイトルかアブストラクトに semidefinite と入っているものを網羅的に並べてある。ただ、人力でやっているので、1つや2つは見落としがあるかもしれない。
つまり、
https://www.siam.org/meetings/op17/op17_abstracts.pdf
で semidefinite と検索したということ。

タイトルの数としては60個ぐらいで、多いのは SDP 緩和関係のお話。あと、最近の話題としては、量子計算と絡んでいるものが増えている傾向がある。


[1]  A Primal Majorized Newton-CG Augmented Lagrangian Method for Large-Scale Linearly Constrained Convex Programming
[2]  A Semidefinite Programming Approach for Energy Network Planning
[3]  Simultaneous Truss Topology - and Static Output Feedback Controller Design via Nonlinear Semidefinite Programming
[4] Copositive Optimization on Infinite Graphs
[5] The Cone of Positive Type Measures on a Compact Group
[6] Convergence Rates of the Moment-Sum-of-Squares Hierarchy for Volume Approximation of Semialgebraic Sets
[7] A Two-Phase Algorithm for Large-Scale Qplogdet Optimization Problem
[8] Convex Relaxations with Second Order Cone Constraints for Nonconvex Quadratically Constrained Quadratic Programming
[9] Completely Positive and Positive Semidefinite Tensor Relaxations for Polynomial Optimization
[10] Analysis of Newton’s Method via Semidefinite Programming Performance Estimation Problems
[11] Perturbation Analysis of Singular Semidefinite Programming via the Facial Reduction
[12] Polynomial Norms
[13] Inner and Outer Approximations of the Semidefinite Cone Using SD Bases and their Applications to Some NP-Hard Problems
[14] Tensor Eigenvalue Complementarity Problems
[15]  More NP-Hard Tensor Problems
[16] Real Eigenvalues of Nonsymmetric Tensors
[17] Pajarito: An Open-Source Mixed-Integer Conic Solver
[18] SCIP-SDP: A Framework for Solving Mixed-Integer Semidefinite Programs
[19] Sums of Squares and Matrix Completion
[20] Polynomial Optimization with Sum-of-Squares Interpolants
[21] Polynomials as Sums of Few Squares
[22] Relaxations and Convex Hull Results for the Intersection of Elementary Nonconvex Quadratics and General Regular Cones
[23] Semidefinite Approximations of Matrix Logarithm
[24] A Positivstellensatz for Sums of Nonnegative Circuit Polynomials
[25] Exploring the Second Order Sparsity in Large Scale Optimization
[26] Low-Rank Matrix Completion (LRMC) Using Nuclear Norm (NN) with Facial Reduction (FR)
[27] Lieb’s Concavity Theorem, Matrix Geometric Means, and Semidefinite Optimization
[28] Solving Generic Nonarchimedean Semidefinite Programs Using Stochastic Game Algorithms
[29] A Generalized Alternating Direction Method of Multipliers with Semi-Proximal Terms for Convex Composite Conic Programming
[30] Nonconvex Low-Rank Estimation: Robustness and Linear Convergence
[31] Dropping Convexity for Faster Semidefinite Optimization
[32] Automating the Analysis and Design of Large-Scale Optimization Algorithms
[33] A Lifted-Polyhedral-Programming Approach for Optimal Contribution Problems
[34] Conic Infimum and Supremum and Some Applications
[35] On Positive Duality Gaps in Semidefinite Programming
[36] Dimension Reduction for SDP
[37] Semidefinite Programming Relaxations and Multigrid Methods in Optimal Control
[38] A Copositive Approach for Two-Stage Adjustable Robust Optimization with Uncertain Right-Hand Sides
[39] Low-Complexity Relaxations and Convex Hulls of Disjunctions on the Positive Semidefinite Cone and Other Regular Cones
[40] Conic Programming Reformulations of Two-Stage Distributionally Robust Linear Programs over Wasserstein Balls
[41] Appointment Scheduling under Schedule-Dependent Patient No-Show Behavior
[42] A Data-Driven Distributionally Robust Bound on the Expected Optimal Value of Uncertain Mixed 0-1 Linear Programming
[43] On the Construction of Exact Augmented Lagrangian Functions for Nonlinear Semidefinite  Optimization
[44] An Extension of Chubanov’s Algorithm to Symmetric Cones
[45] Low-Order Complexity Results for SOS/SDP Methods in Real Algebra
[46] Convex Relaxation Without Lifting: Solving Large Semidefinite Programs without all the Pain
[47] Electronic Structure Calculation using Semidefinite Programs
[48] Estimation Performance and Convergence Rate of the Generalized Power Method for Phase Synchronization
[49] Computational Study of Some Valid Inequalities for k-Way Graph Partitioning
[50] Graph Bisection Revisited
[51] From Clifford Algebras and Rigidity Theory to Large Completely Positive Semidefinite Rank
[52] Quantum Correlations: Conic Formulations, Dimension Bounds and Matrix Factorizations
[53] Rank Minimization using a Complementarity Approach
[54] Quantum Bilinear Optimization
[55] Quantum Channels, Spectrahedra and a Tracial Hahn-Banach Theorem
[56] Using Noncommutative Polynomial Optimization for Matrix Factorization Ranks
[57] Optimization of Spatiotemporal Fractionation in Photon Radiotherapy with Optimality Bounds
[58] Finding Planted Graphs with Few Eigenvalues using the Schur-Horn Relaxation
[59] Semidefinite Programs with a Dash of Smoothness: Why and When the Low-Rank Approach Works
[60]  Gradient Descent for Rectangular Matrix Completion
[61] Analyzing Quantum Cryptographic Protocols using Semidefinite Programming
[62] Quantum Speed-Ups for Semidefinite Programming


2017年12月4日月曜日

論文読み:Efficient Convex Optimization for Linear MPC

今回も Optimization Online のところから、論文をチェックしてみた。
今回は、

Efficient Convex Optimization for Linear MPC
http://www.optimization-online.org/DB_HTML/2017/11/6353.html

基本的には、線形モデル予測制御の問題が、目的関数が凸2次、制約が線形制約になるので、それをどのように効率的に解くか、という話。立ち位置としては、サーベイに近いような感じだと思う。
解法としては、内点法と active-set methods が書かれていて、内点法は比較的スタンダードなものに線形制約に現れる帯構造を使って時間短縮を図るというもの。
あと、active-set methods は warm-start のほうでメリットが大きい、とのこと。


個人的には、active-set methods をあまり使ったことがなかったので、もうちょっと調べてみようと思う。手元にはたくさんの対角ブロックになるような SDP があるので、それをうまく解けるといいなぁ、と思っている。