Direct solution of the normal equations in interior point methods for convex transportation problems

被引：3

作者：

Wright, Stephen E. ^{[1
]}

机构：

[1] Miami Univ, Dept Stat, Oxford, OH 45056 USA

来源：

OPERATIONS RESEARCH LETTERS | 2023年 / 51卷 / 05期

关键词：

Convex programming; Interior point methods; Network constraints; ALGORITHM; FLOW;

D O I：

10.1016/j.orl.2023.07.001

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

Recent research has shown that very large convex transportation problems can be solved efficiently with interior point methods by finding a good pre-conditioner for an iterative linear-equation solver. In this article, it is demonstrated that the specific structure of the constraints allows use of a direct method for solving those linear equations with the same order of worst-case time complexity.& COPY; 2023 Elsevier B.V. All rights reserved.

引用

页码：469 / 472

页数：4

共 5 条

[1] A specialized interior-point algorithm for huge minimum convex cost flows in bipartite networks [J].