The Convergent Generalized Central Paths for Linearly Constrained Convex Programming
MetadataShow full item record
The convergence of central paths has been a focal point of research on interior point methods. Quite detailed analyses have been made for the linear case. However, when it comes to the convex case, even if the constraints remain linear, the problem is unsettled. In [Math. Program., 103 (2005), pp. 63–94], Gilbert, Gonzaga, and Karas presented some examples in convex optimization, where the central path fails to converge. In this paper, we aim at finding some continuous trajectories which can converge for all linearly constrained convex optimization problems under some mild assumptions. We design and analyze a class of continuous trajectories, which are the solutions of certain ordinary differential equation (ODE) systems for solving linearly constrained smooth convex programming. The solutions of these ODE systems are named generalized central paths. By only assuming the existence of a finite optimal solution, we are able to show that, starting from any interior feasible point, (i) all of the generalized central paths are convergent, and (ii) the limit point(s) are indeed the optimal solution(s) of the original optimization problem. Furthermore, we illustrate that for the key example of Gilbert, Gonzaga, and Karas, our generalized central paths converge to the optimal solutions.
Showing items related by title, author, creator and subject.
A strategy of global convergence for the affine scaling algorithm for convex semidefinite programmingQian, X.; Liao, L.; Sun, Jie (2018)The affine scaling algorithm is one of the earliest interior point methods developed for linear programming. This algorithm is simple and elegant in terms of its geometric interpretation, but it is notoriously difficult ...
Qian, X.; Liao, L.; Sun, Jie (2017)In this paper, we analyse three interior point continuous trajectories for convex programming with general linear constraints. The three continuous trajectories are derived from the primal–dual path-following method, the ...
Tseng, Chien H. (1999)The design of envelope-constrained (EC) filters is considered for the time-domain synthesis of filters for signal processing problems. The objective is to achieve minimal noise enhancement where the shape of the filter ...