An active-set strategy in an interior point method for linear programming (Q687036)

The author presents a potential reduction method for linear programming, where only active constraints (i.e. constraints with relatively small dual slacks) are taken into account to form the ellipsoid constraint at each iteration of the process. It is proved that the algorithm converges to the optimal feasible solution in \(O(\sqrt n L)\) iterations with the same polynomial bound as in the full constraint case, where \(n\) is the number of variables and \(L\) is the data length. The advantage of the proposed active-set strategy is that the cost of each iteration may be reduced.