
doi: 10.1137/0802005
The authors propose a large-step path following method for smooth convex programming problems satisfying the so-called relative Lipschtz condition. It is stated that the existing small-step path-following algorithms for smooth convex programming problems have the disadvantage that they are based on very small step sizes and hence remain in the vicinity of the central trajectory. The method discussed in this paper is a generalization of recent work of the authors [Linear Algebra Appl. 152, 43-68 (1991; Zbl 0734.65050)] and is also based on the work of \textit{F. Jarre} [Springer Lect. Notes Math. 1405, 69-85 (1989; Zbl 0684.90068)]. The authors present the following brief summary of the procedure. In this method line searches are performed along the Newton direction with respect to a strictly convex potential function. If one is close to the current analytic center, then the lower bound is updated somehow, whereafter line searches are performed aiming at getting close to the analytic center associated with the new lower bound. It is shown that after a line search the potential value reduces and this fact is used to establish that the number of iterations required by the algorithm to converge to an \(\varepsilon\)-optimal solution is bounded by a polynomial in \(|\ln\varepsilon|\), the dimension of the problem and the Lipschitz constant.
Convex programming, analytic center method, Newton method, large-step path following, Computational methods for problems pertaining to operations research and mathematical programming, smooth convex programming
Convex programming, analytic center method, Newton method, large-step path following, Computational methods for problems pertaining to operations research and mathematical programming, smooth convex programming
| 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). | 17 | |
| 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). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
