论文标题
用于大规模线性程序的原始偶二大化最小化方法
A primal-dual majorization-minimization method for large-scale linear programs
论文作者
论文摘要
我们提出了一种用于求解大规模线性程序的原始偶二大化最小化方法。对于双线性程序，具有严格凸度的平滑屏障增强拉格朗日（SBAL）功能。自然引入了大型最小化方法，以发展SBAL功能的平滑度和凸度。我们的方法仅取决于与迭代无关的恒定矩阵的分解，并且不需要对阶梯尺寸的任何计算，因此可以期望特别适合大规模线性程序。该方法具有与线性程序的一阶方法相似的属性，但其收敛分析是在我们的SBAL功能的可不同性和凸度上建立的。分析全局收敛，而无需事先要求原始或双线性程序可行。在常规条件下，我们的方法被证明是全球线性收敛的，并给出了新的迭代复杂性结果。
We present a primal-dual majorization-minimization method for solving large-scale linear programs. A smooth barrier augmented Lagrangian (SBAL) function with strict convexity for the dual linear program is derived. The majorization-minimization approach is naturally introduced to develop the smoothness and convexity of the SBAL function. Our method only depends on a factorization of the constant matrix independent of iterations and does not need any computation on step sizes, thus can be expected to be particularly appropriate for large-scale linear programs. The method shares some similar properties to the first-order methods for linear programs, but its convergence analysis is established on the differentiability and convexity of our SBAL function. The global convergence is analyzed without prior requiring either the primal or dual linear program to be feasible. Under the regular conditions, our method is proved to be globally linearly convergent, and a new iteration complexity result is given.
