# American Institute of Mathematical Sciences

October  2019, 15(4): 1517-1534. doi: 10.3934/jimo.2018107

## An interior point continuous path-following trajectory for linear programming

 1 School of Science, Nanjing Audit University, Nanjing 211815, Jiangsu Province, China 2 Department of Mathematics, Hong Kong Baptist University, Kowloon Tong, Hong Kong SAR, China

* Corresponding author: Li-Zhi Liao

Received  January 2018 Revised  March 2018 Published  July 2018

Fund Project: The work of Liming Sun was supported in part by the National Natural Science Foundation of China (Grant No. 11701287) and the Natural Science Foundation of Jiangsu Province (Grant No. BK20171071). The work of Li-Zhi Liao was supported in part by grants from the General Research Fund (GRF) of Hong Kong and FRG of Hong Kong Baptist University.

In this paper, an interior point continuous path-following trajectory is proposed for linear programming. The descent direction in our continuous trajectory can be viewed as some combination of the affine scaling direction and the centering direction for linear programming. A key component in our interior point continuous path-following trajectory is an ordinary differential equation (ODE) system. Various properties including the convergence in the limit for the solution of this ODE system are analyzed and discussed in detail. Several illustrative examples are also provided to demonstrate the numerical behavior of this continuous trajectory.

Citation: Liming Sun, Li-Zhi Liao. An interior point continuous path-following trajectory for linear programming. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1517-1534. doi: 10.3934/jimo.2018107
##### References:

show all references

##### References:
Transient behaviors of the continuous path of $x(t)$ and the objective function $c^Tx$ in Example 4.1 with starting point $x_0$
Transient behaviors of the continuous path of $x(t)$ and the objective function $c^Tx$ in Example 4.1 with starting point $x_0^{'}$
Transient behaviors of the continuous path of $x(t)$ and the objective function $c^Tx$ in Example 4.2 with starting point $x_0$
Transient behaviors of the continuous path of $x(t)$ and the objective function $c^Tx$ in Example 4.2 with starting point $x_0^{'}$
 [1] Behrouz Kheirfam. A weighted-path-following method for symmetric cone linear complementarity problems. Numerical Algebra, Control & Optimization, 2014, 4 (2) : 141-150. doi: 10.3934/naco.2014.4.141 [2] Yanqun Liu. An exterior point linear programming method based on inclusive normal cones. Journal of Industrial & Management Optimization, 2010, 6 (4) : 825-846. doi: 10.3934/jimo.2010.6.825 [3] Yanqin Bai, Pengfei Ma, Jing Zhang. A polynomial-time interior-point method for circular cone programming based on kernel functions. Journal of Industrial & Management Optimization, 2016, 12 (2) : 739-756. doi: 10.3934/jimo.2016.12.739 [4] Yibing Lv, Tiesong Hu, Jianlin Jiang. Penalty method-based equilibrium point approach for solving the linear bilevel multiobjective programming problem. Discrete & Continuous Dynamical Systems - S, 2020, 13 (6) : 1743-1755. doi: 10.3934/dcdss.2020102 [5] Andrew E.B. Lim, John B. Moore. A path following algorithm for infinite quadratic programming on a Hilbert space. Discrete & Continuous Dynamical Systems - A, 1998, 4 (4) : 653-670. doi: 10.3934/dcds.1998.4.653 [6] Behrouz Kheirfam, Guoqiang Wang. An infeasible full NT-step interior point method for circular optimization. Numerical Algebra, Control & Optimization, 2017, 7 (2) : 171-184. doi: 10.3934/naco.2017011 [7] Yanqun Liu, Ming-Fang Ding. A ladder method for linear semi-infinite programming. Journal of Industrial & Management Optimization, 2014, 10 (2) : 397-412. doi: 10.3934/jimo.2014.10.397 [8] Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193 [9] Soodabeh Asadi, Hossein Mansouri. A Mehrotra type predictor-corrector interior-point algorithm for linear programming. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 147-156. doi: 10.3934/naco.2019011 [10] Yue Zheng, Zhongping Wan, Shihui Jia, Guangmin Wang. A new method for strong-weak linear bilevel programming problem. Journal of Industrial & Management Optimization, 2015, 11 (2) : 529-547. doi: 10.3934/jimo.2015.11.529 [11] Boshi Tian, Xiaoqi Yang, Kaiwen Meng. An interior-point $l_{\frac{1}{2}}$-penalty method for inequality constrained nonlinear optimization. Journal of Industrial & Management Optimization, 2016, 12 (3) : 949-973. doi: 10.3934/jimo.2016.12.949 [12] Yu-Hong Dai, Xin-Wei Liu, Jie Sun. A primal-dual interior-point method capable of rapidly detecting infeasibility for nonlinear programs. Journal of Industrial & Management Optimization, 2020, 16 (2) : 1009-1035. doi: 10.3934/jimo.2018190 [13] Dale McDonald. Sensitivity based trajectory following control damping methods. Numerical Algebra, Control & Optimization, 2013, 3 (1) : 127-143. doi: 10.3934/naco.2013.3.127 [14] Fang Zeng, Pablo Suarez, Jiguang Sun. A decomposition method for an interior inverse scattering problem. Inverse Problems & Imaging, 2013, 7 (1) : 291-303. doi: 10.3934/ipi.2013.7.291 [15] Fang Zeng. Extended sampling method for interior inverse scattering problems. Inverse Problems & Imaging, 2020, 14 (4) : 719-731. doi: 10.3934/ipi.2020033 [16] Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353 [17] Rongjie Lai, Jiang Liang, Hong-Kai Zhao. A local mesh method for solving PDEs on point clouds. Inverse Problems & Imaging, 2013, 7 (3) : 737-755. doi: 10.3934/ipi.2013.7.737 [18] Zhongyi Huang. Tailored finite point method for the interface problem. Networks & Heterogeneous Media, 2009, 4 (1) : 91-106. doi: 10.3934/nhm.2009.4.91 [19] Igor Griva, Roman A. Polyak. Proximal point nonlinear rescaling method for convex optimization. Numerical Algebra, Control & Optimization, 2011, 1 (2) : 283-299. doi: 10.3934/naco.2011.1.283 [20] Huan Gao, Zhibao Li, Haibin Zhang. A fast continuous method for the extreme eigenvalue problem. Journal of Industrial & Management Optimization, 2017, 13 (3) : 1587-1599. doi: 10.3934/jimo.2017008

2018 Impact Factor: 1.025