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, (2006).   Google Scholar

[2]

G. B. Dantzig, Maximization of a linear function of variables subject to linear inequalities,, Activity Analysis of Production and Allocation, (1951), 339.   Google Scholar

[3]

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

[4]

L. G. Khachiyan, A polynomial algorithm in linear programming,, Doklady Akademii Nauk SSSR-S, 244 (1979), 1093.   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.  doi: 10.1007/BF02096264.  Google Scholar

[6]

R. J. Vanderbei, "Linear Programming - Foundations and Extensions,", 3rd Ed., (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, (2006).   Google Scholar

[2]

G. B. Dantzig, Maximization of a linear function of variables subject to linear inequalities,, Activity Analysis of Production and Allocation, (1951), 339.   Google Scholar

[3]

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

[4]

L. G. Khachiyan, A polynomial algorithm in linear programming,, Doklady Akademii Nauk SSSR-S, 244 (1979), 1093.   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.  doi: 10.1007/BF02096264.  Google Scholar

[6]

R. J. Vanderbei, "Linear Programming - Foundations and Extensions,", 3rd Ed., (2008).   Google Scholar

[1]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077
[2]

Thierry Horsin, Mohamed Ali Jendoubi. On the convergence to equilibria of a sequence defined by an implicit scheme. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020465
[3]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054
[4]

Manil T. Mohan. First order necessary conditions of optimality for the two dimensional tidal dynamics system. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020045
[5]

Awais Younus, Zoubia Dastgeer, Nudrat Ishaq, Abdul Ghaffar, Kottakkaran Sooppy Nisar, Devendra Kumar. On the observability of conformable linear time-invariant control systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020444
[6]

Christian Beck, Lukas Gonon, Martin Hutzenthaler, Arnulf Jentzen. On existence and uniqueness properties for solutions of stochastic fixed point equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020320
[7]

Ahmad Z. Fino, Wenhui Chen. A global existence result for two-dimensional semilinear strongly damped wave equation with mixed nonlinearity in an exterior domain. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5387-5411. doi: 10.3934/cpaa.2020243
[8]

Yongge Tian, Pengyang Xie. Simultaneous optimal predictions under two seemingly unrelated linear random-effects models. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020168
[9]

Justin Holmer, Chang Liu. Blow-up for the 1D nonlinear Schrödinger equation with point nonlinearity II: Supercritical blow-up profiles. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020264

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences