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]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008
[2]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[3]

Vakhtang Putkaradze, Stuart Rogers. Numerical simulations of a rolling ball robot actuated by internal point masses. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 143-207. doi: 10.3934/naco.2020021
[4]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[5]

Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781
[6]

Fernando P. da Costa, João T. Pinto, Rafael Sasportes. On the convergence to critical scaling profiles in submonolayer deposition models. Kinetic & Related Models, 2018, 11 (6) : 1359-1376. doi: 10.3934/krm.2018053
[7]

Alberto Bressan, Carlotta Donadello. On the convergence of viscous approximations after shock interactions. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 29-48. doi: 10.3934/dcds.2009.23.29
[8]

Caifang Wang, Tie Zhou. The order of convergence for Landweber Scheme with $\alpha,\beta$-rule. Inverse Problems & Imaging, 2012, 6 (1) : 133-146. doi: 10.3934/ipi.2012.6.133
[9]

Jiangxing Wang. Convergence analysis of an accurate and efficient method for nonlinear Maxwell's equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2429-2440. doi: 10.3934/dcdsb.2020185
[10]

Diana Keller. Optimal control of a linear stochastic Schrödinger equation. Conference Publications, 2013, 2013 (special) : 437-446. doi: 10.3934/proc.2013.2013.437
[11]

Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311
[12]

Nizami A. Gasilov. Solving a system of linear differential equations with interval coefficients. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2739-2747. doi: 10.3934/dcdsb.2020203
[13]

Bin Pei, Yong Xu, Yuzhen Bai. Convergence of p-th mean in an averaging principle for stochastic partial differential equations driven by fractional Brownian motion. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1141-1158. doi: 10.3934/dcdsb.2019213
[14]

Haibo Cui, Haiyan Yin. Convergence rate of solutions toward stationary solutions to the isentropic micropolar fluid model in a half line. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020210
[15]

Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119
[16]

W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349
[17]

Arunima Bhattacharya, Micah Warren. $ C^{2, \alpha} $ estimates for solutions to almost Linear elliptic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021024
[18]

Misha Bialy, Andrey E. Mironov. Rich quasi-linear system for integrable geodesic flows on 2-torus. Discrete & Continuous Dynamical Systems - A, 2011, 29 (1) : 81-90. doi: 10.3934/dcds.2011.29.81
[19]

Fumihiko Nakamura. Asymptotic behavior of non-expanding piecewise linear maps in the presence of random noise. Discrete & Continuous Dynamical Systems - B, 2018, 23 (6) : 2457-2473. doi: 10.3934/dcdsb.2018055
[20]

Christophe Zhang. Internal rapid stabilization of a 1-D linear transport equation with a scalar feedback. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021006

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences