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  October 2019 Early access  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 and Management Optimization, 2019, 15 (4) : 1517-1534. doi: 10.3934/jimo.2018107
References:
[1]

P.-A. AbsilR. Mahony and B. Andrews, Convergence of the iterates of descent methods for analytic cost functions, SIAM J. Optim., 16 (2005), 531-547.  doi: 10.1137/040605266.

[2]

I. AdlerN. KarmarkarM. G. C. Resend and G. Veiga, An implementation of Karmarkar's algorithm for linear programming, Math. Program., 44 (1989), 297-335.  doi: 10.1007/BF01587095.

[3]

N. Andrei, Gradient Flow Algorithm for Unconstrained Optimization, ICI Technical Report, April, 2004.

[4]

E. R. Barnes, A variation on Karmarkar's algorithm for solving linear programming problems, Math. Program., 36 (1986), 174-182.  doi: 10.1007/BF02592024.

[5]

D. A. Bayer and J. C. Lagarias, The nonlinear geometry of linear programming. I Affine and projective scaling trajectories, Trans. Amer. Math. Soc., 314 (1989), 499-526.  doi: 10.2307/2001396.

[6]

D. A. Bayer and J. C. Lagarias, The nonlinear geometry of linear programming. Ⅱ Legendre transform coordinates and central trajectories, Trans. Amer. Math. Soc., 314 (1989), 527-581.  doi: 10.2307/2001397.

[7]

C. A. Botsaris, Differential gradient methods, J. Math. Anal. Appl., 63 (1978), 177-198.  doi: 10.1016/0022-247X(78)90114-2.

[8]

F. H. Branin, A widely convergent method for finding multiple solutions of simultaneous nonlinear equations, IBM J. Res. Devel., 16 (1972), 504-522.  doi: 10.1147/rd.165.0504.

[9]

F. H. Branin and S. K. Hoo, A method for finding multiple extrema of a function of N variables, Numerical Methods for Non-Linear Optimization (Conf., Univ. Dundee, Dundee, 1971), Academic Press, London, (1972), 231-237.

[10]

A. A. Brown and M. C. Bartholomew-Biggs, Some effective methods for unconstrained optimization based on the solution of systems of ordinary differential equations, J. Optim. Theory Appl., 62 (1989), 211-224.  doi: 10.1007/BF00941054.

[11]

R. Courant, Variational methods for the solution of problems of equilibrium and vibration, Bull. Amer. Math. Soc., 49 (1943), 1-23.  doi: 10.1090/S0002-9904-1943-07818-4.

[12]

J. E. Dennis, Jr. and R. B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, SIAM, 1996. doi: 10.1137/1.9781611971200.

[13]

I. Diener, On the global convergence of path-following methods to determine all solutions to a system of nonlinear equations, Math. Program., 39 (1987), 181-188.  doi: 10.1007/BF02592951.

[14]

I. Diener, Trajectory nets connecting all critical points of a smooth function, Math. Program., 36 (1986), 340-352.  doi: 10.1007/BF02592065.

[15]

I. I. Dikin, Iterative solution of problems of linear and qudartic programming, Doklady Akademiia Nauk SSSR, 174 (1967), 747-748. 

[16]

R. M. Freund, Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function, Math. Program., 51 (1991), 203-222.  doi: 10.1007/BF01586933.

[17]

P. E. GillW. MurrayM. A. SaundersJ. A. Tomlin and M. H. Wright, On projected Newton barrier methods for linear programming and an equivalence to Karmarkar's projective method, Math. Program., 36 (1986), 183-209.  doi: 10.1007/BF02592025.

[18]

C. C. Gonzaga, Polynomial affine algorithms for linear programming, Math. Program., 49 (1990/91), 7-21.  doi: 10.1007/BF01588776.

[19]

C. C. Gonzaga, Large step path-following methods for linear programming. Ⅱ. Potential reduction method, SIAM J. Optim., 1 (1991), 280-292.  doi: 10.1137/0801019.

[20]

C. C. Gonzaga, Path-following methods for linear programming, SIAM Rev., 34 (1992), 167-224.  doi: 10.1137/1034048.

[21]

N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, 4 (1984), 373-395.  doi: 10.1007/BF02579150.

[22]

L.-Z. LiaoH. D. Qi and L. Q. Qi, Neurodynamical optimization, J. Global Optim, 28 (2004), 175-195.  doi: 10.1023/B:JOGO.0000015310.27011.02.

[23]

L.-Z. Liao, A study of the dual affine scaling continuous trajectories for linear programming, J. Optim. Theory and Appl., 163 (2014), 548-568.  doi: 10.1007/s10957-013-0495-1.

[24]

N. Megiddo and M. Shub, Boundary behavior of interior point algorihms for linear programming, Math. Oper. Res., 14 (1989), 97-146.  doi: 10.1287/moor.14.1.97.

[25]

C. L. Monma and J. Morton, Computational experience with a dual affine variant of Karmarkar's method for linear programming, Oper. Res. Lett., 6 (1987), 261-267.  doi: 10.1016/0167-6377(87)90040-X.

[26]

R. D. C. Monteiro and I. Adler, Interior path following primal-dual algorithms. I. Linear programming, Math. Program., 44 (1989), 27-41.  doi: 10.1007/BF01587075.

[27]

R. D. C. MonteiroI. Adler and M. G. C. Resende, A polynomial-time primal-dual affine scaling algorithm for linear and convex quadratic programming and its power series extension, Math. Oper. Res., 15 (1990), 191-214.  doi: 10.1287/moor.15.2.191.

[28]

R. D. C. Monteiro and I. Adler, Limiting behavior of the affine scaling continuous trajectories for linear programming problems, Math. Program., 50 (1991), 29-51.  doi: 10.1007/BF01594923.

[29]

R. D. C. Monteiro, On the continuous trajectories for a potential reduction algorithm for linear programming, Math. Oper. Res., 17 (1992), 225-253.  doi: 10.1287/moor.17.1.225.

[30]

X. Qian and L.-Z. Liao, Analysis of the primal affine scaling continuous trajectory for convex programming, Pacific J. Optimi., (to appear).

[31]

C. Roos, New trajectory-following polynomial-time algorithm for linear programming problems, J. Optim. Theory Appl., 63 (1989), 433-458.  doi: 10.1007/BF00939806.

[32]

C. Roos and J.-Ph. Vial, A polynomial method of approximate centers for linear programming, Math. Program., 54 (1992), 295-305.  doi: 10.1007/BF01586056.

[33]

J. J. E. Slotine and W. Li, Applied Nonlinear Control, Prentice Hall, New Jersey, 1991.

[34]

G. W. Stewart, On scaled projections and pseudoinverses, Linear Alg. Appl., 112 (1989), 189-193.  doi: 10.1016/0024-3795(89)90594-6.

[35]

J. Sun, A convergence proof for an affine scaling algorithm for convex quadratic programming without nondegeneracy assumptions, Math. Program., 60 (1993), 69-79.  doi: 10.1007/BF01580601.

[36]

J. Sun, A convergence analysis for a convex version of Dikin's algorithm, Annals Oper. Res., 62 (1996), 357-374.  doi: 10.1007/BF02206823.

[37]

M. J. Todd, A Dantzig-Wolfe-like variant of Karmarkar's interior-point linear programming algorithm, Oper. Res., 38 (1990), 1006-1018.  doi: 10.1287/opre.38.6.1006.

[38]

P. Tseng and Z.-Q. Luo, On the convergence of the affine-scaling algorithm, Math. Program., 56 (1992), 301-319.  doi: 10.1007/BF01580904.

[39]

T. Tsuchiya, Affine scaling algorithm, Interior Point Methods of Mathematical Programming, Kluwer Academic Pub., Netherlands, 5 (1996), 35-82. doi: 10.1007/978-1-4613-3449-1_2.

[40]

R. J. VanderbeiM. S. Meketon and B. A. Freedman, A modification of Karmarkar's linear programming algorithm, Algorithmica, 1 (1986), 395-407.  doi: 10.1007/BF01840454.

[41]

C. Witzgall, P. T. Boggs and P. D. Domich, On the convergence behavior of trajectories for linear programming, Mathematical Developments Arising from Linear Programming (Brunswick, ME, 1988), 161-187, Contemp. Math., 114, Amer. Math. Soc., Providence, RI, 1990. doi: 10.1090/conm/114/1097873.

show all references

References:
[1]

P.-A. AbsilR. Mahony and B. Andrews, Convergence of the iterates of descent methods for analytic cost functions, SIAM J. Optim., 16 (2005), 531-547.  doi: 10.1137/040605266.

[2]

I. AdlerN. KarmarkarM. G. C. Resend and G. Veiga, An implementation of Karmarkar's algorithm for linear programming, Math. Program., 44 (1989), 297-335.  doi: 10.1007/BF01587095.

[3]

N. Andrei, Gradient Flow Algorithm for Unconstrained Optimization, ICI Technical Report, April, 2004.

[4]

E. R. Barnes, A variation on Karmarkar's algorithm for solving linear programming problems, Math. Program., 36 (1986), 174-182.  doi: 10.1007/BF02592024.

[5]

D. A. Bayer and J. C. Lagarias, The nonlinear geometry of linear programming. I Affine and projective scaling trajectories, Trans. Amer. Math. Soc., 314 (1989), 499-526.  doi: 10.2307/2001396.

[6]

D. A. Bayer and J. C. Lagarias, The nonlinear geometry of linear programming. Ⅱ Legendre transform coordinates and central trajectories, Trans. Amer. Math. Soc., 314 (1989), 527-581.  doi: 10.2307/2001397.

[7]

C. A. Botsaris, Differential gradient methods, J. Math. Anal. Appl., 63 (1978), 177-198.  doi: 10.1016/0022-247X(78)90114-2.

[8]

F. H. Branin, A widely convergent method for finding multiple solutions of simultaneous nonlinear equations, IBM J. Res. Devel., 16 (1972), 504-522.  doi: 10.1147/rd.165.0504.

[9]

F. H. Branin and S. K. Hoo, A method for finding multiple extrema of a function of N variables, Numerical Methods for Non-Linear Optimization (Conf., Univ. Dundee, Dundee, 1971), Academic Press, London, (1972), 231-237.

[10]

A. A. Brown and M. C. Bartholomew-Biggs, Some effective methods for unconstrained optimization based on the solution of systems of ordinary differential equations, J. Optim. Theory Appl., 62 (1989), 211-224.  doi: 10.1007/BF00941054.

[11]

R. Courant, Variational methods for the solution of problems of equilibrium and vibration, Bull. Amer. Math. Soc., 49 (1943), 1-23.  doi: 10.1090/S0002-9904-1943-07818-4.

[12]

J. E. Dennis, Jr. and R. B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, SIAM, 1996. doi: 10.1137/1.9781611971200.

[13]

I. Diener, On the global convergence of path-following methods to determine all solutions to a system of nonlinear equations, Math. Program., 39 (1987), 181-188.  doi: 10.1007/BF02592951.

[14]

I. Diener, Trajectory nets connecting all critical points of a smooth function, Math. Program., 36 (1986), 340-352.  doi: 10.1007/BF02592065.

[15]

I. I. Dikin, Iterative solution of problems of linear and qudartic programming, Doklady Akademiia Nauk SSSR, 174 (1967), 747-748. 

[16]

R. M. Freund, Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function, Math. Program., 51 (1991), 203-222.  doi: 10.1007/BF01586933.

[17]

P. E. GillW. MurrayM. A. SaundersJ. A. Tomlin and M. H. Wright, On projected Newton barrier methods for linear programming and an equivalence to Karmarkar's projective method, Math. Program., 36 (1986), 183-209.  doi: 10.1007/BF02592025.

[18]

C. C. Gonzaga, Polynomial affine algorithms for linear programming, Math. Program., 49 (1990/91), 7-21.  doi: 10.1007/BF01588776.

[19]

C. C. Gonzaga, Large step path-following methods for linear programming. Ⅱ. Potential reduction method, SIAM J. Optim., 1 (1991), 280-292.  doi: 10.1137/0801019.

[20]

C. C. Gonzaga, Path-following methods for linear programming, SIAM Rev., 34 (1992), 167-224.  doi: 10.1137/1034048.

[21]

N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, 4 (1984), 373-395.  doi: 10.1007/BF02579150.

[22]

L.-Z. LiaoH. D. Qi and L. Q. Qi, Neurodynamical optimization, J. Global Optim, 28 (2004), 175-195.  doi: 10.1023/B:JOGO.0000015310.27011.02.

[23]

L.-Z. Liao, A study of the dual affine scaling continuous trajectories for linear programming, J. Optim. Theory and Appl., 163 (2014), 548-568.  doi: 10.1007/s10957-013-0495-1.

[24]

N. Megiddo and M. Shub, Boundary behavior of interior point algorihms for linear programming, Math. Oper. Res., 14 (1989), 97-146.  doi: 10.1287/moor.14.1.97.

[25]

C. L. Monma and J. Morton, Computational experience with a dual affine variant of Karmarkar's method for linear programming, Oper. Res. Lett., 6 (1987), 261-267.  doi: 10.1016/0167-6377(87)90040-X.

[26]

R. D. C. Monteiro and I. Adler, Interior path following primal-dual algorithms. I. Linear programming, Math. Program., 44 (1989), 27-41.  doi: 10.1007/BF01587075.

[27]

R. D. C. MonteiroI. Adler and M. G. C. Resende, A polynomial-time primal-dual affine scaling algorithm for linear and convex quadratic programming and its power series extension, Math. Oper. Res., 15 (1990), 191-214.  doi: 10.1287/moor.15.2.191.

[28]

R. D. C. Monteiro and I. Adler, Limiting behavior of the affine scaling continuous trajectories for linear programming problems, Math. Program., 50 (1991), 29-51.  doi: 10.1007/BF01594923.

[29]

R. D. C. Monteiro, On the continuous trajectories for a potential reduction algorithm for linear programming, Math. Oper. Res., 17 (1992), 225-253.  doi: 10.1287/moor.17.1.225.

[30]

X. Qian and L.-Z. Liao, Analysis of the primal affine scaling continuous trajectory for convex programming, Pacific J. Optimi., (to appear).

[31]

C. Roos, New trajectory-following polynomial-time algorithm for linear programming problems, J. Optim. Theory Appl., 63 (1989), 433-458.  doi: 10.1007/BF00939806.

[32]

C. Roos and J.-Ph. Vial, A polynomial method of approximate centers for linear programming, Math. Program., 54 (1992), 295-305.  doi: 10.1007/BF01586056.

[33]

J. J. E. Slotine and W. Li, Applied Nonlinear Control, Prentice Hall, New Jersey, 1991.

[34]

G. W. Stewart, On scaled projections and pseudoinverses, Linear Alg. Appl., 112 (1989), 189-193.  doi: 10.1016/0024-3795(89)90594-6.

[35]

J. Sun, A convergence proof for an affine scaling algorithm for convex quadratic programming without nondegeneracy assumptions, Math. Program., 60 (1993), 69-79.  doi: 10.1007/BF01580601.

[36]

J. Sun, A convergence analysis for a convex version of Dikin's algorithm, Annals Oper. Res., 62 (1996), 357-374.  doi: 10.1007/BF02206823.

[37]

M. J. Todd, A Dantzig-Wolfe-like variant of Karmarkar's interior-point linear programming algorithm, Oper. Res., 38 (1990), 1006-1018.  doi: 10.1287/opre.38.6.1006.

[38]

P. Tseng and Z.-Q. Luo, On the convergence of the affine-scaling algorithm, Math. Program., 56 (1992), 301-319.  doi: 10.1007/BF01580904.

[39]

T. Tsuchiya, Affine scaling algorithm, Interior Point Methods of Mathematical Programming, Kluwer Academic Pub., Netherlands, 5 (1996), 35-82. doi: 10.1007/978-1-4613-3449-1_2.

[40]

R. J. VanderbeiM. S. Meketon and B. A. Freedman, A modification of Karmarkar's linear programming algorithm, Algorithmica, 1 (1986), 395-407.  doi: 10.1007/BF01840454.

[41]

C. Witzgall, P. T. Boggs and P. D. Domich, On the convergence behavior of trajectories for linear programming, Mathematical Developments Arising from Linear Programming (Brunswick, ME, 1988), 161-187, Contemp. Math., 114, Amer. Math. Soc., Providence, RI, 1990. doi: 10.1090/conm/114/1097873.

Figure 1.  Transient behaviors of the continuous path of $x(t)$ and the objective function $c^Tx$ in Example 4.1 with starting point $x_0$
Figure 2.  Transient behaviors of the continuous path of $x(t)$ and the objective function $c^Tx$ in Example 4.1 with starting point $x_0^{'}$
Figure 3.  Transient behaviors of the continuous path of $x(t)$ and the objective function $c^Tx$ in Example 4.2 with starting point $x_0$
Figure 4.  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 and 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 and 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 and Management Optimization, 2016, 12 (2) : 739-756. doi: 10.3934/jimo.2016.12.739

[4]

Leonid Faybusovich, Cunlu Zhou. Long-step path-following algorithm for quantum information theory: Some numerical aspects and applications. Numerical Algebra, Control and Optimization, 2022, 12 (2) : 445-467. doi: 10.3934/naco.2021017

[5]

Yibing Lv, Tiesong Hu, Jianlin Jiang. Penalty method-based equilibrium point approach for solving the linear bilevel multiobjective programming problem. Discrete and Continuous Dynamical Systems - S, 2020, 13 (6) : 1743-1755. doi: 10.3934/dcdss.2020102

[6]

Andrew E.B. Lim, John B. Moore. A path following algorithm for infinite quadratic programming on a Hilbert space. Discrete and Continuous Dynamical Systems, 1998, 4 (4) : 653-670. doi: 10.3934/dcds.1998.4.653

[7]

Behrouz Kheirfam, Guoqiang Wang. An infeasible full NT-step interior point method for circular optimization. Numerical Algebra, Control and Optimization, 2017, 7 (2) : 171-184. doi: 10.3934/naco.2017011

[8]

Yanqun Liu, Ming-Fang Ding. A ladder method for linear semi-infinite programming. Journal of Industrial and Management Optimization, 2014, 10 (2) : 397-412. doi: 10.3934/jimo.2014.10.397

[9]

Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193

[10]

Soodabeh Asadi, Hossein Mansouri. A Mehrotra type predictor-corrector interior-point algorithm for linear programming. Numerical Algebra, Control and Optimization, 2019, 9 (2) : 147-156. doi: 10.3934/naco.2019011

[11]

Xiaoni Chi, Zhongping Wan, Zijun Hao. A full-modified-Newton step $ O(n) $ infeasible interior-point method for the special weighted linear complementarity problem. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021082

[12]

Yue Zheng, Zhongping Wan, Shihui Jia, Guangmin Wang. A new method for strong-weak linear bilevel programming problem. Journal of Industrial and Management Optimization, 2015, 11 (2) : 529-547. doi: 10.3934/jimo.2015.11.529

[13]

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 and Management Optimization, 2020, 16 (2) : 1009-1035. doi: 10.3934/jimo.2018190

[14]

Boshi Tian, Xiaoqi Yang, Kaiwen Meng. An interior-point $l_{\frac{1}{2}}$-penalty method for inequality constrained nonlinear optimization. Journal of Industrial and Management Optimization, 2016, 12 (3) : 949-973. doi: 10.3934/jimo.2016.12.949

[15]

Dale McDonald. Sensitivity based trajectory following control damping methods. Numerical Algebra, Control and Optimization, 2013, 3 (1) : 127-143. doi: 10.3934/naco.2013.3.127

[16]

Yi Cui, Xintong Fang, Gaoqi Liu, Bin Li. Trajectory optimization of UAV based on Hp-adaptive Radau pseudospectral method. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021201

[17]

Fang Zeng. Extended sampling method for interior inverse scattering problems. Inverse Problems and Imaging, 2020, 14 (4) : 719-731. doi: 10.3934/ipi.2020033

[18]

Fang Zeng, Pablo Suarez, Jiguang Sun. A decomposition method for an interior inverse scattering problem. Inverse Problems and Imaging, 2013, 7 (1) : 291-303. doi: 10.3934/ipi.2013.7.291

[19]

Jinlong Guo, Bin Li, Yuandong Ji. A control parametrization based path planning method for the quad-rotor uavs. Journal of Industrial and Management Optimization, 2022, 18 (2) : 1079-1100. doi: 10.3934/jimo.2021009

[20]

Nadia Hazzam, Zakia Kebbiche. A primal-dual interior point method for $ P_{\ast }\left( \kappa \right) $-HLCP based on a class of parametric kernel functions. Numerical Algebra, Control and Optimization, 2021, 11 (4) : 513-531. doi: 10.3934/naco.2020053

2020 Impact Factor: 1.801

Metrics

  • PDF downloads (511)
  • HTML views (1408)
  • Cited by (0)

Other articles
by authors

[Back to Top]