
doi: 10.1137/0331074
Summary: Motivated by a recent work of \textit{R. Setiono} [`An interior dual proximal point algorithm for linear programs', Tech. report, Computer Sci. Dept., Univ. of Wisconsin, Madison, WI/USA (1989)], a path-following algorithm for linear programming using both logarithmic and quadratic penalty functions is proposed. In the algorithm, a logarithmic and a quadratic penalty is placed on, respectively, the nonnegativity constraints and an arbitrary subset of the equality constraints; Newton's method is applied to solve the penalized problem, and after each Newton step the penalty parameters are decreased. This algorithm maintains neither primal nor dual feasibility and does not require a Phase I. It is shown that if the initial iterate is chosen appropriately and the penalty parameters are decreased to zero in a particular way, then the algorithm is linearly convergent. Numerical results are also presented suggesting that the algorithm may be competitive with interior point algorithms in practice, requiring typically between 30-45 iterations to accurately solve each Netlib problem tested.
logarithmic and quadratic penalty functions, Linear programming, path-following, Newton step
logarithmic and quadratic penalty functions, Linear programming, path-following, Newton step
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
