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 があるので、それをうまく解けるといいなぁ、と思っている。



2017年12月2日土曜日

Adobe は、なぜ学習しないのか?

Adobe Acrobat Reader DC の注釈で書いていると気になるのだが、漢字変換の学習機能が効かない。

例えば、「この節では」と Windows で何回も入力していても、「この説では」と変換される。Adobe Acrobat Reader DC でも注釈で「この節では」と何回入力しても、学習されないようだ。

Adobe だと、なぜ学習しないのか、不思議だ。
ひょっとしたら変換辞書が別にあるのか?


ちなみに、普段はAdobeではない別の PDF リーダーを使っていて、そっちでは快適に漢字変換ができている。


PowerPoint の数式が思い

プレゼンテーションのファイルを作るのに、以前は Beamer を使っていたこともあるけど、PowerPoint + IguanaTeX の自由度の高さに気がついてからは Beamer には戻れなくなってしまった。
(個人的に思うところでは、Beamer を使い慣れている人には、PowerPoint + IguanaTeX をあまり勧めない。まぁ、Beamer と PowerPoint + IguanaTeX を比較しても大きな差はなく、例えていえば Beamer が普通の黒電話ぐらいで PowerPoint + IguanaTeX がスマートフォンぐらいという差の程度でしかない。無理して乗り換える必要もない。)

今回は、IguanaTeX を使わずにPowerPoint の数式だけでプレゼンテーションファイルを作ったらどうなるか、ということも試してみたくてやってみることにしてみた。
そもそも IguanaTeX だと TeX 環境をインストールしないといけないので、TeX がインストールされてないところでは編集ができない。そこで PowerPoint の数式だけでできるかを知っておくことも有益だろうと思ってやってみた。

結果として、PowerPoint の数式は、思っていた以上にスマート。入力に多少の癖はあるけど、TeX の数式を入力する知識がだいぶ役に立つので、Beamer を使っている人にもPowerPoint の数式は使いやすいと思う。

逆に困っているところは、以下の2つ。
(1) 行列を書こうとすると Unicode が入り込んでしまって、行形式での編集が極めて困難。
(2) 数式が多くなると、PowerPoint の処理が極端に遅くなる。例えば、"PowerPoint" という文字列を入力するだけでも 10 秒以上かかる。


まぁ、自分のところでは試していないけど、Office365 では LaTeX で数式を書けるようになるということなので、このあたりが解決するのは時間の問題かもしれない。
やはり LaTeX の数式はキーボードだけで書けるというメリットが大きいので、できれば Google スライドとか Office Online とかでも使えるようになるといいなぁ、とは思う。

2017年11月22日水曜日

IguanaTeX のバグを回避する

IguanaTeX は非常によくできているので、よく利用させてもらっているが、たまにバグがある。
例えば、一時ファイルを置く場所を Main Setting に入力しても、これが環境変数として ghostscript に渡らないため、TeX2imgc.exe などを使おうとしても途中の ghostscript で Unable to open the initial device, quittingとなって終了してしまう。

これを回避するには、TeX2imgc.exe を呼び出す bat ファイルを以下のように作って、TeX2imgc.exe の代わりに Main Setting で設定する。

%%%%%%%%%%%
set TEMP=[一時ファイルの場所]
set TMP=[一時ファイルの場所]
"[TeX2imgc.exeへのパス]\TeX2imgc.exe" %*
%%%%%%%%%%%
つまり、環境変数 TEMP, TMP を設定して、あとは TeX2imgc.exe にすべての引数を渡して実行する。