An exterior point linear programming method based on inclusive normal cones

Previous Article
A method for optimizing over the integer efficient set
JIMO Home
This Issue
Next Article
Two-person knapsack game

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

An exterior point linear programming method based on inclusive normal cones

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

Received December 2009 Revised June 2010 Published September 2010

Abstract
Related Papers

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, (2006).
[2]	G. B. Dantzig, Maximization of a linear function of variables subject to linear inequalities,, Activity Analysis of Production and Allocation, (1951), 339.
[3]	N. Karmarkar, A new polynomial-time algorithm for linear programming,, Combinatorica, 4 (1984), 373. doi: 10.1007/BF02579150.
[4]	L. G. Khachiyan, A polynomial algorithm in linear programming,, Doklady Akademii Nauk SSSR-S, 244 (1979), 1093.
[5]	T. Terlaky and S. Zhang, Pivot rules for linear programming: A survey on recent theoretical developments,, Annals of Operations Research, 46 (1993), 203. doi: 10.1007/BF02096264.
[6]	R. J. Vanderbei, "Linear Programming - Foundations and Extensions,", 3rd Ed., (2008).

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, (2006).
[2]	G. B. Dantzig, Maximization of a linear function of variables subject to linear inequalities,, Activity Analysis of Production and Allocation, (1951), 339.
[3]	N. Karmarkar, A new polynomial-time algorithm for linear programming,, Combinatorica, 4 (1984), 373. doi: 10.1007/BF02579150.
[4]	L. G. Khachiyan, A polynomial algorithm in linear programming,, Doklady Akademii Nauk SSSR-S, 244 (1979), 1093.
[5]	T. Terlaky and S. Zhang, Pivot rules for linear programming: A survey on recent theoretical developments,, Annals of Operations Research, 46 (1993), 203. doi: 10.1007/BF02096264.
[6]	R. J. Vanderbei, "Linear Programming - Foundations and Extensions,", 3rd Ed., (2008).

[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 PNCP. 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, 2018, 13 (5) : 1-18. 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]	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
[7]	Mansoureh Alavi Hejazi, Soghra Nobakhtian. Optimality conditions for multiobjective fractional programming, via convexificators. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-9. doi: 10.3934/jimo.2018170
[8]	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
[9]	Victoriano Carmona, Emilio Freire, Soledad Fernández-García. Periodic orbits and invariant cones in three-dimensional piecewise linear systems. Discrete & Continuous Dynamical Systems - A, 2015, 35 (1) : 59-72. doi: 10.3934/dcds.2015.35.59
[10]	Charles Fefferman. Interpolation by linear programming I. Discrete & Continuous Dynamical Systems - A, 2011, 30 (2) : 477-492. doi: 10.3934/dcds.2011.30.477
[11]	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
[12]	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
[13]	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
[14]	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
[15]	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
[16]	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
[17]	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
[18]	Chuanhao Guo, Erfang Shan, Wenli Yan. A superlinearly convergent hybrid algorithm for solving nonlinear programming. Journal of Industrial & Management Optimization, 2017, 13 (2) : 1009-1024. doi: 10.3934/jimo.2016059
[19]	Wenqing Hu, Chris Junchi Li. A convergence analysis of the perturbed compositional gradient flow: Averaging principle and normal deviations. Discrete & Continuous Dynamical Systems - A, 2018, 38 (10) : 4951-4977. doi: 10.3934/dcds.2018216
[20]	Pilar Bayer, Dionís Remón. A reduction point algorithm for cocompact Fuchsian groups and applications. Advances in Mathematics of Communications, 2014, 8 (2) : 223-239. doi: 10.3934/amc.2014.8.223

2017 Impact Factor: 0.994

American Institute of Mathematical Sciences