American Institute of Mathematical Sciences

Advanced
October  2010, 6(4): 825-846. doi: 10.3934/jimo.2010.6.825

An exterior point linear programming method based on inclusive normal cones

Yanqun Liu 1,

1. 

School of Mathematical & Geospatial Sciences, RMIT University, Melbourne, Australia

Received  December 2009 Revised  June 2010 Published  September 2010

In this paper, we present a geometrical exterior climbing method based on inclusive normal cones for solving general linear programming problems in canonical form. The method iteratively updates the inclusive cone by climbing within its associated inclusive region (also called a ladder), and eventually reaches an optimal solution. This method allows the development of a class of 'ladder algorithms' by using different climbing schemes. Some aspects of the current method are intrinsically related to the dual simplex method. However, it originates from different ideas and provides a new angle to look at the linear programming problem. It can be shown that the dual simplex algorithms are special ladder algorithms in this context. We present two climbing schemes leading to two finitely convergent ladder algorithms. The algorithms are tested by solving a number of linear programming examples. Some numerical results are provided.
Keywords: inclusive normal cones, optimality, Linear programming, exterior point algorithm, convergence..
Mathematics Subject Classification: Primary: 90C05, 65K0.
Citation: 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
References:
[1]

J. M. Borwein and A. S. Lewis, "Convex Analysis and Nonlinear Optimization. Theory and Examples," Second edition. CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, 3. Springer, New York, 2006.  Google Scholar

[2]

G. B. Dantzig, Maximization of a linear function of variables subject to linear inequalities, Activity Analysis of Production and Allocation, 339-347; Cowles Commission Monograph No. 13. John Wiley & Sons, Inc., New York, N. Y.; Chapman & Hall, Ltd., London, 1951.  Google Scholar

[3]

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

[4]

L. G. Khachiyan, A polynomial algorithm in linear programming, Doklady Akademii Nauk SSSR-S, 244 (1979), 1093-1096; translated in Soviet Mathematics Doklady, 20 (1979), 191-194.  Google Scholar

[5]

T. Terlaky and S. Zhang, Pivot rules for linear programming: A survey on recent theoretical developments, Annals of Operations Research, 46 (1993), 203-233 doi: 10.1007/BF02096264.  Google Scholar

[6]

R. J. Vanderbei, "Linear Programming - Foundations and Extensions," 3rd Ed., International Series in Operations Research & Management Science, 114, Springer, New York, 2008.  Google Scholar

show all references

References:
[1]

J. M. Borwein and A. S. Lewis, "Convex Analysis and Nonlinear Optimization. Theory and Examples," Second edition. CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, 3. Springer, New York, 2006.  Google Scholar

[2]

G. B. Dantzig, Maximization of a linear function of variables subject to linear inequalities, Activity Analysis of Production and Allocation, 339-347; Cowles Commission Monograph No. 13. John Wiley & Sons, Inc., New York, N. Y.; Chapman & Hall, Ltd., London, 1951.  Google Scholar

[3]

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

[4]

L. G. Khachiyan, A polynomial algorithm in linear programming, Doklady Akademii Nauk SSSR-S, 244 (1979), 1093-1096; translated in Soviet Mathematics Doklady, 20 (1979), 191-194.  Google Scholar

[5]

T. Terlaky and S. Zhang, Pivot rules for linear programming: A survey on recent theoretical developments, Annals of Operations Research, 46 (1993), 203-233 doi: 10.1007/BF02096264.  Google Scholar

[6]

R. J. Vanderbei, "Linear Programming - Foundations and Extensions," 3rd Ed., International Series in Operations Research & Management Science, 114, Springer, New York, 2008.  Google Scholar

[1]

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
[2]

Zheng-Hai Huang, Shang-Wen Xu. Convergence properties of a non-interior-point smoothing algorithm for the P*NCP. Journal of Industrial & Management Optimization, 2007, 3 (3) : 569-584. doi: 10.3934/jimo.2007.3.569
[3]

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
[4]

Rong Hu, Ya-Ping Fang. A parametric simplex algorithm for biobjective piecewise linear programming problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 573-586. doi: 10.3934/jimo.2016032
[5]

Vladimir Gaitsgory, Alex Parkinson, Ilya Shvartsman. Linear programming based optimality conditions and approximate solution of a deterministic infinite horizon discounted optimal control problem in discrete time. Discrete & Continuous Dynamical Systems - B, 2019, 24 (4) : 1743-1767. doi: 10.3934/dcdsb.2018235
[6]

Kai Wang, Deren Han. On the linear convergence of the general first order primal-dual algorithm. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021134
[7]

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
[8]

Yinghong Xu, Lipu Zhang, Jing Zhang. A full-modified-Newton step infeasible interior-point algorithm for linear optimization. Journal of Industrial & Management Optimization, 2016, 12 (1) : 103-116. doi: 10.3934/jimo.2016.12.103
[9]

Mansoureh Alavi Hejazi, Soghra Nobakhtian. Optimality conditions for multiobjective fractional programming, via convexificators. Journal of Industrial & Management Optimization, 2020, 16 (2) : 623-631. doi: 10.3934/jimo.2018170
[10]

Zheng-Hai Huang, Nan Lu. Global and global linear convergence of smoothing algorithm for the Cartesian $P_*(\kappa)$-SCLCP. Journal of Industrial & Management Optimization, 2012, 8 (1) : 67-86. doi: 10.3934/jimo.2012.8.67
[11]

Victoriano Carmona, Emilio Freire, Soledad Fernández-García. Periodic orbits and invariant cones in three-dimensional piecewise linear systems. Discrete & Continuous Dynamical Systems, 2015, 35 (1) : 59-72. doi: 10.3934/dcds.2015.35.59
[12]

Charles Fefferman. Interpolation by linear programming I. Discrete & Continuous Dynamical Systems, 2011, 30 (2) : 477-492. doi: 10.3934/dcds.2011.30.477
[13]

Hadi Khatibzadeh, Vahid Mohebbi, Mohammad Hossein Alizadeh. On the cyclic pseudomonotonicity and the proximal point algorithm. Numerical Algebra, Control & Optimization, 2018, 8 (4) : 441-449. doi: 10.3934/naco.2018027
[14]

Giuseppe Marino, Hong-Kun Xu. Convergence of generalized proximal point algorithms. Communications on Pure & Applied Analysis, 2004, 3 (4) : 791-808. doi: 10.3934/cpaa.2004.3.791
[15]

Jing Quan, Zhiyou Wu, Guoquan Li. Global optimality conditions for some classes of polynomial integer programming problems. Journal of Industrial & Management Optimization, 2011, 7 (1) : 67-78. doi: 10.3934/jimo.2011.7.67
[16]

Yuhua Sun, Laisheng Wang. Optimality conditions and duality in nondifferentiable interval-valued programming. Journal of Industrial & Management Optimization, 2013, 9 (1) : 131-142. doi: 10.3934/jimo.2013.9.131
[17]

Xian-Jun Long, Jing Quan. Optimality conditions and duality for minimax fractional programming involving nonsmooth generalized univexity. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 361-370. doi: 10.3934/naco.2011.1.361
[18]

Xiao-Bing Li, Qi-Lin Wang, Zhi Lin. Optimality conditions and duality for minimax fractional programming problems with data uncertainty. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1133-1151. doi: 10.3934/jimo.2018089
[19]

Bhawna Kohli. Sufficient optimality conditions using convexifactors for optimistic bilevel programming problem. Journal of Industrial & Management Optimization, 2021, 17 (6) : 3209-3221. doi: 10.3934/jimo.2020114
[20]

Jean Creignou, Hervé Diet. Linear programming bounds for unitary codes. Advances in Mathematics of Communications, 2010, 4 (3) : 323-344. doi: 10.3934/amc.2010.4.323

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (66)
  • HTML views (0)
  • Cited by (8)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences