投稿
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日日曜日
３次元以上のSDP の錐は、SOCP では表現できない
２次元の半正定値行列の成す錐が SOCP で書けることは良く知られている事実だけど、３次元以上の場合に 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で任意精度で近似するっていうのは出来るんだろうか？
それが今後の展開なんだろうか？
詳しくは、
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 を使っている。
論文のモデルは結構面白いかと思うが、この論文をベースに何かするとしたらベンチマーク問題のようなものがないとちょっと難しいかと思う。
やはり、データが整理されている、というのは重要な点なのかもしれない。
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 に対する内点法を今までよりも高速に計算できるアルゴリズムを作れるかも、と思ったりしている。
（どうやってアルゴリズムを作ればいいか、という全体の枠組みは分かりつつあるので、それぞれのステップをきちんと作る方法を調べている、というところ。）
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 と入っているものを網羅的に並べてある。ただ、人力でやっているので、１つや２つは見落としがあるかもしれない。
つまり、
https://www.siam.org/meetings/op17/op17_abstracts.pdf
で semidefinite と検索したということ。
タイトルの数としては６０個ぐらいで、多いのは 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
基本的にはタイトルだけだけど、タイトルかアブストラクトに semidefinite と入っているものを網羅的に並べてある。ただ、人力でやっているので、１つや２つは見落としがあるかもしれない。
つまり、
https://www.siam.org/meetings/op17/op17_abstracts.pdf
で semidefinite と検索したということ。
タイトルの数としては６０個ぐらいで、多いのは 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 があるので、それをうまく解けるといいなぁ、と思っている。
今回は、
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 リーダーを使っていて、そっちでは快適に漢字変換ができている。
例えば、「この節では」と Windows で何回も入力していても、「この説では」と変換される。Adobe Acrobat Reader DC でも注釈で「この節では」と何回入力しても、学習されないようだ。
Adobe だと、なぜ学習しないのか、不思議だ。
ひょっとしたら変換辞書が別にあるのか？
ちなみに、普段はAdobeではない別の PDF リーダーを使っていて、そっちでは快適に漢字変換ができている。
登録:
投稿 (Atom)