A pivoting algorithm for linear programming with linear complementarity constraints
A pivoting algorithm for linear programming with linear complementarity constraints
复制标题
具有线性互补约束的线性规划的旋转算法
DOI：
10.1080/10556788.2010.512956
复制
发表时间：
2012
影响因子：
2.2
通讯作者：
T. Munson
中科院分区：
文献类型：
--
作者：
Haw;S. Leyffer;T. Munson
我们提出了一种用于求解具有线性互补约束的线性程序的旋转算法。我们的方法概括了线性规划的单纯形方法来处理互补条件。我们开发了一种可以验证 Bouligand 平稳性的反循环方案。我们还给出了一种基于优化的技术来找到初始可行顶点。从可行顶点开始，我们的算法总是在有限数量的旋转步骤中找到最小化器或无界下降搜索方向。
We present a pivoting algorithm for solving linear programs with linear complementarity constraints. Our method generalizes the simplex method for linear programming to deal with complementarity conditions. We develop an anticycling scheme that can verify Bouligand stationarity. We also give an optimization-based technique to find an initial feasible vertex. Starting with a feasible vertex, our algorithm always finds a minimizer or an unbounded descent search direction in a finite number of pivoting steps.