A New Relation between Information Geometry and Convex Programming : Coincidence with the Gradient Vectors for the Divergence and a Modified Barrier Function(Special Section on Nonlinear Theory and its Applications)
スポンサーリンク
概要
- 論文の詳細を見る
We study a class of nonlinear dynamical systems to develop efficient algorithms. As an efficient algorithm, interior point method based on Newton's method is well-known for solving convex programming problems which include linear, quadratic, semidefinite and l_p-programming problems. On the other hand, the geodesic of information geometry is represented by a continuous Newton's method for minimizing a convex function called divergence. Thus, we discuss a relation between information geometry and convex programming in a related family of continuous Newton's method. In particular, we consider the α-projection problem from a given data onto an information geometric submanifold spanned with power-functions. In general, an information geometric structure can be induced from a standard convex programming problem. In contrast, the correspondence from information geometry to convex programming is slightly complicated. We first present there exists a same structure between the α-projection and semidefinite programming problems. The structure is based on the linearities or autoparallelisms in the function space and the space of matrices, respectively. However, the α-projection problem is not a form of convex programming. Thus, we reformulate it to a l_p-programming and the related ones. For the reformulated problems, we derive self-concordant barrier functions according to the values of α. The existence of a polynomial time algorithm is theoretically confirmed for the problem. Furthermore, we present the coincidence with the gradient vectors for the divergence and a modified barrier function. These results connect a part of nonlinear and algorithm theories by the discreteness of variables.
- 社団法人電子情報通信学会の論文
- 2001-09-01
著者
関連論文
- Direct Calculation Methods for Parameter Estimation in Statistical Manifolds of Finite Discrete Distributions
- A Review of Recent Studies of Geographical Scale-Free Networks(サーベイ,ネットワーク生態学〜生命現象から社会文化現象の新しいパースペクティブ〜)
- A New Relation between Information Geometry and Convex Programming : Coincidence with the Gradient Vectors for the Divergence and a Modified Barrier Function(Special Section on Nonlinear Theory and its Applications)
- Rate and Speed of Information Spread over a Web-Like Network
- A Review of Recent Studies of Geographical Scale-Free Networks