主双対内点法に現れる直交行列

機関リポジトリ HANDLE

書誌事項

タイトル別名
  • Orthogonal matrics in a priminal-dual method of linear program

説明

In this paper, we consider orthogonal matrices appearing in a primal-dual method (or algorithm) of linear program. The program is important from theoretical and practical aspects after simplex and Karmarkar methods. In the simplex method, we make a better feasible solution choosing several rows of a given matrix. In the Karmarkar method, we use a projection matrix to improve a feasible solution. The primal-dual method clarifies a meaning of Karmarkar's projection matrix and then rewrites the matrix in terms of primal and dual linear programs. In the primal-dual method, we have two projection matrices which play important roles. Karmarkar method uses a single projection matrix in each step. Projection matrices in both Karmarkar method and primal-dual method are related to generalized inverse matrices. We analyze those matrices and have several properties concerning projection matrices in primal-dual method. The properties include relevant factors to compute the projection matries. In particular, we have new computational method of the projection matrices, which makes a computation of a feasible solution easy. Furthermore, we have a single orthogonal matrix derived from two projection matrices. We do not yet have new method of linear program using our orthogonal matrix. But we hope that future research of the orthogonal matrix induces a new method.

収録刊行物

詳細情報 詳細情報について

問題の指摘

ページトップへ