The Convergent Generalized Central Paths for Linearly Constrained Convex Programming
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. 6...
| Main Authors: | , , , |
|---|---|
| Format: | Journal Article |
| Published: |
Society for Industrial and Applied Mathematics
2018
|
| Online Access: | http://purl.org/au-research/grants/arc/DP160102819 http://hdl.handle.net/20.500.11937/69781 |
| _version_ | 1848762132784480256 |
|---|---|
| author | Qian, X. Liao, L. Sun, Jie Zhu, H. |
| author_facet | Qian, X. Liao, L. Sun, Jie Zhu, H. |
| author_sort | Qian, X. |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T10:42:43Z |
| format | Journal Article |
| id | curtin-20.500.11937-69781 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T10:42:43Z |
| publishDate | 2018 |
| publisher | Society for Industrial and Applied Mathematics |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-697812022-10-27T04:47:58Z The Convergent Generalized Central Paths for Linearly Constrained Convex Programming Qian, X. Liao, L. Sun, Jie Zhu, H. 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. 2018 Journal Article http://hdl.handle.net/20.500.11937/69781 10.1137/16M1104172 http://purl.org/au-research/grants/arc/DP160102819 Society for Industrial and Applied Mathematics fulltext |
| spellingShingle | Qian, X. Liao, L. Sun, Jie Zhu, H. The Convergent Generalized Central Paths for Linearly Constrained Convex Programming |
| title | The Convergent Generalized Central Paths for Linearly Constrained Convex Programming |
| title_full | The Convergent Generalized Central Paths for Linearly Constrained Convex Programming |
| title_fullStr | The Convergent Generalized Central Paths for Linearly Constrained Convex Programming |
| title_full_unstemmed | The Convergent Generalized Central Paths for Linearly Constrained Convex Programming |
| title_short | The Convergent Generalized Central Paths for Linearly Constrained Convex Programming |
| title_sort | convergent generalized central paths for linearly constrained convex programming |
| url | http://purl.org/au-research/grants/arc/DP160102819 http://hdl.handle.net/20.500.11937/69781 |