An exterior point linear programming method based on inclusive normal cones

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

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 and 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.
[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.
[3]	N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, 4 (1984), 373-395 doi: 10.1007/BF02579150.
[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.
[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.
[6]	R. J. Vanderbei, "Linear Programming - Foundations and Extensions," 3rd Ed., International Series in Operations Research & Management Science, 114, Springer, New York, 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, 3. Springer, New York, 2006.
[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.
[3]	N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, 4 (1984), 373-395 doi: 10.1007/BF02579150.
[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.
[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.
[6]	R. J. Vanderbei, "Linear Programming - Foundations and Extensions," 3rd Ed., International Series in Operations Research & Management Science, 114, Springer, New York, 2008.

[1]	Guoyong Gu, Junfeng Yang. A unified and tight linear convergence analysis of the relaxed proximal point algorithm. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022107
[2]	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
[3]	Zheng-Hai Huang, Shang-Wen Xu. Convergence properties of a non-interior-point smoothing algorithm for the PNCP. Journal of Industrial and Management Optimization*, 2007, 3 (3) : 569-584. doi: 10.3934/jimo.2007.3.569
[4]	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
[5]	Rong Hu, Ya-Ping Fang. A parametric simplex algorithm for biobjective piecewise linear programming problems. Journal of Industrial and Management Optimization, 2017, 13 (2) : 573-586. doi: 10.3934/jimo.2016032
[6]	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 and Continuous Dynamical Systems - B, 2019, 24 (4) : 1743-1767. doi: 10.3934/dcdsb.2018235
[7]	Aleksandar Jović. Saddle-point type optimality criteria, duality and a new approach for solving nonsmooth fractional continuous-time programming problems. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022025
[8]	Kai Wang, Deren Han. On the linear convergence of the general first order primal-dual algorithm. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021134
[9]	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
[10]	Yinghong Xu, Lipu Zhang, Jing Zhang. A full-modified-Newton step infeasible interior-point algorithm for linear optimization. Journal of Industrial and Management Optimization, 2016, 12 (1) : 103-116. doi: 10.3934/jimo.2016.12.103
[11]	Ayache Benhadid, Fateh Merahi. Complexity analysis of an interior-point algorithm for linear optimization based on a new parametric kernel function with a double barrier term. Numerical Algebra, Control and Optimization, 2022 doi: 10.3934/naco.2022003
[12]	Mansoureh Alavi Hejazi, Soghra Nobakhtian. Optimality conditions for multiobjective fractional programming, via convexificators. Journal of Industrial and Management Optimization, 2020, 16 (2) : 623-631. doi: 10.3934/jimo.2018170
[13]	Tone-Yau Huang, Tamaki Tanaka. Optimality and duality for complex multi-objective programming. Numerical Algebra, Control and Optimization, 2022, 12 (1) : 121-134. doi: 10.3934/naco.2021055
[14]	Gang Li, Yinghong Xu, Zhenhua Qin. Optimality conditions for composite DC infinite programming problems. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022064
[15]	Zheng-Hai Huang, Nan Lu. Global and global linear convergence of smoothing algorithm for the Cartesian $P_(\kappa)$-SCLCP. Journal of Industrial and Management Optimization*, 2012, 8 (1) : 67-86. doi: 10.3934/jimo.2012.8.67
[16]	Victoriano Carmona, Emilio Freire, Soledad Fernández-García. Periodic orbits and invariant cones in three-dimensional piecewise linear systems. Discrete and Continuous Dynamical Systems, 2015, 35 (1) : 59-72. doi: 10.3934/dcds.2015.35.59
[17]	Charles Fefferman. Interpolation by linear programming I. Discrete and Continuous Dynamical Systems, 2011, 30 (2) : 477-492. doi: 10.3934/dcds.2011.30.477
[18]	Hadi Khatibzadeh, Vahid Mohebbi, Mohammad Hossein Alizadeh. On the cyclic pseudomonotonicity and the proximal point algorithm. Numerical Algebra, Control and Optimization, 2018, 8 (4) : 441-449. doi: 10.3934/naco.2018027
[19]	Giuseppe Marino, Hong-Kun Xu. Convergence of generalized proximal point algorithms. Communications on Pure and Applied Analysis, 2004, 3 (4) : 791-808. doi: 10.3934/cpaa.2004.3.791
[20]	Jing Quan, Zhiyou Wu, Guoquan Li. Global optimality conditions for some classes of polynomial integer programming problems. Journal of Industrial and Management Optimization, 2011, 7 (1) : 67-78. doi: 10.3934/jimo.2011.7.67

2021 Impact Factor: 1.411

Tools

Metrics

Other articles
by authors

on AIMS
Yanqun Liu
on Google Scholar
Yanqun Liu

[Back to Top]