4. Potential-Reduction Methods

Stephen J. WrightSociety 1997 · DOI · OpenAlex

Abstract

Potential functions have always played a central role in the development of interior-point algorithms. Karmarkar's algorithm [57], when adapted for the standard-form linear program (1.1), makes use of a logarithmic potential function of the formρlog(cTx−Z)−∑i=1nlogxi,4.1where ρ=n+1 and Z is a lower bound on the optimal objective value. Karmarkar proved convergence and complexity results by showing that this function is decreased by at least a constant at each step. In subsequent work, researchers devised algorithms based on variants of this potential function, and also the log barrier function (2.33) and the logarithmic function (2.36) used by Renegar [112], none of which depend explicitly on the dual variables. The complexity analysis of these algorithms depends crucially on the clever devices used to update their parameters (the barrier parameter μ in (2.33) and the bound Z in (4.1) and (2.36)). See, for example, the Newton-log-barrier algorithm discussed by Gill et al. [40] and Renegar's algorithm [112] discussed in Chapter 2. In some cases, the parameter update makes use of information from the dual problem, as in the algorithms of Todd and Burrell [129] and Gonzaga [45], but most of the action takes place in the space of primal variables.
BibTeX
@inproceedings{wright1997potential,
  author = {Stephen J. Wright},
  title = {{4. Potential-Reduction Methods}},
  booktitle = {Society},
  year = {1997},
  doi = {10.1137/1.9781611971453.ch4},
}

Loading related content...

Figure