5. Path-Following Algorithms

Abstract

In Chapters 1 and 2, we described the central path C , a path of points (xτ,λτ,sτ) that leads to the set Ω of primal-dual solutions. Points in Ω satisfy the KKT conditions (2.4), whereas points in C are defined by conditions that differ from the KKT conditions only by the presence of a positive scalar parameter τ>0 , namely,ATλ+s=c,(5.1a)Ax=b,(5.1b)(x,s)≥0,(5.1c)xisi=τ,i=1,2,…,n.(5.1d)We showed in Chapter 2 that this system has a unique solution (xτ,λτ,sτ) for each τ>0 whenever the problem is feasible (although the KKT conditions, for which τ=0 in (5.1d), may have multiple solutions).