The search functionality is under construction.

The search functionality is under construction.

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.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E84-A No.9 pp.2238-2246

- Publication Date
- 2001/09/01

- Publicized

- Online ISSN

- DOI

- Type of Manuscript
- Special Section PAPER (Special Section on Nonlinear Theory and its Applications)

- Category
- Numerical Method & Optimization

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Yukio HAYASHI, "A New Relation between Information Geometry and Convex Programming--Coincidence with the Gradient Vectors for the Divergence and a Modified Barrier Function" in IEICE TRANSACTIONS on Fundamentals,
vol. E84-A, no. 9, pp. 2238-2246, September 2001, doi: .

Abstract: 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.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e84-a_9_2238/_p

Copy

@ARTICLE{e84-a_9_2238,

author={Yukio HAYASHI, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={A New Relation between Information Geometry and Convex Programming--Coincidence with the Gradient Vectors for the Divergence and a Modified Barrier Function},

year={2001},

volume={E84-A},

number={9},

pages={2238-2246},

abstract={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.},

keywords={},

doi={},

ISSN={},

month={September},}

Copy

TY - JOUR

TI - A New Relation between Information Geometry and Convex Programming--Coincidence with the Gradient Vectors for the Divergence and a Modified Barrier Function

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 2238

EP - 2246

AU - Yukio HAYASHI

PY - 2001

DO -

JO - IEICE TRANSACTIONS on Fundamentals

SN -

VL - E84-A

IS - 9

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - September 2001

AB - 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.

ER -