A ladder method for linear semi-infinite programming

Yanqun Liu; Ming-Fang Ding

doi:10.3934/jimo.2014.10.397

Article Contents

2014, Volume 10, Issue 2: 397-412. Doi: 10.3934/jimo.2014.10.397

This issue Previous Article Optimizing system-on-chip verifications with multi-objective genetic evolutionary algorithms Next Article Theory and applications of optimal control problems with multiple time-delays

A ladder method for linear semi-infinite programming

Yanqun Liu^1, and
Ming-Fang Ding^1,

1.
School of Mathematical and Geospatial Sciences, RMIT University, GPO Box 2476, Melbourne, Victoria 3001

Received: October 31, 2012

Revised: June 30, 2013

Published: March 2014

Abstract Related Papers Cited by

Abstract

This paper presents a new method for linear semi-infinite programming. With the introduction of the so-called generalized ladder point, a ladder method for linear semi-infinite programming is developed. This work includes the generalization of the inclusive cone version of the fundamental theorem of linear programming and the extension of a linear programming ladder algorithm. The extended ladder algorithm finds a generalized ladder point optimal solution of the linear semi-infinite programming problem, which is approximated by a sequence of ladder points. Simple convergence properties are provided. The algorithm is tested by solving a number of linear semi-infinite programming examples. These numerical results indicate that the algorithm is very efficient when compared with other methods.

Keywords:

Mathematics Subject Classification: Primary: 90C34, 90C46.

Citation:

Related Papers

Cited by

References

[1]	E. J. Anderson and A. S. Lewis, An extension of the simplex algorithm for semi-infinite linear programming, Mathematical Programming, 44 (1989), 247-269.doi: 10.1007/BF01587092.
[2]	B. Betrò, An accelerated central cutting plane algorithm for semi-infinite linear programming, Mathematical Programming, 101 (2004), 479-495.doi: 10.1007/s10107-003-0492-5.
[3]	D. den Hertog, J. Kaliski, C. Roos and T. Terlaky, A logarithmic barrier cutting plane method for convex programming, Annals of Operations Research, 58 (1995), 69-98.doi: 10.1007/BF02032162.
[4]	M. C. Ferris and A. B. Philpott, An interior point algorithm for semi-infinite linear programming, Mathematical Programming, 43 (1989), 257-276.doi: 10.1007/BF01582293.
[5]	M. A. Goberna and M. A. López, Linear Semi-infinite Optimization, Wiley Series in Mathematical Methods in Practice, 2, John Wiley & Sons, Ltd., Chichester, 1998.
[6]	M. A. Goberna, Linear semi-infinite optimization: Recent advances, in Continuous Optimization (eds. V. Jeyakumar and A. M. Rubinov), Appl. Optim., 99, Springer, New York, 2005, 3-22.doi: 10.1007/0-387-26771-9_1.
[7]	R. Hettich, A review of numerical methods for semi-infinite optimization, in Semi-infinite Programming and Applications (eds. A. V. Fiacco and K. O. Kortanek), Lecture Notes in Econom. and Math. Systems, 215, Springer, Berlin, 1983, 158-178.doi: 10.1007/978-3-642-46477-5_11.
[8]	R. Hettich, An implementation of a discretization method for semi-infinite programming, Mathematical Programming, 34 (1986), 354-361.doi: 10.1007/BF01582235.
[9]	R. Hettich and K. O. Kortanek, Semi-infinite programming: Theory, methods, and applications, SIAM Rev., 35 (1993), 380-429.doi: 10.1137/1035089.
[10]	S. Ito, Y. Liu and K. L. Teo, A dual parametrization method for convex semi-infinite programming, Ann. Oper. Res., 98 (2000), 189-213.doi: 10.1023/A:1019208524259.
[11]	A. Kaplan and R. Tichatschke, Proximal interior point method for convex semi-infinite programming, Optim. Methods Softw., 15 (2001), 87-119.doi: 10.1080/10556780108805813.
[12]	Y. Liu, An exterior point method for linear programming based on inclusive normal cones, J. Ind. Manag. Optim., 6 (2010), 825-846.doi: 10.3934/jimo.2010.6.825.
[13]	Y. Liu, Duality theorem in linear programming: From trichotomy to quadrichotomy, J. Ind. Manag. Optim., 7 (2011), 1003-1011.doi: 10.3934/jimo.2011.7.1003.
[14]	Y. Liu and K. L. Teo, A bridging method for global optimization, J. Austral. Math. Soc. Ser. B, 41 (1999), 41-57.doi: 10.1017/S0334270000011024.
[15]	Y. Liu, K. L. Teo and S. Y. Wu, A New quadratic semi-infinite programming algorithm based on dual parametrization, J. Global Optim., 29 (2004), 401-413.doi: 10.1023/B:JOGO.0000047910.80739.95.
[16]	R. Reemtsen, Discretization methods for the solution of semi-infinite programming problems, J. Optim. Theory Appl., 71 (1991), 85-103.doi: 10.1007/BF00940041.
[17]	G. A. Watson, Lagrangian methods for semi-infinite programming problems, in Infinite Programming, Lecture Notes in Economics and Mathematical Systems (eds. E. J. Anderson and A. B. Philpott), Lecture Notes in Econom. and Math. Systems, 259, Springer, Berlin, 1985, 90-107.doi: 10.1007/978-3-642-46564-2_8.
[18]	S. Y. Wu, S. C. Fang and C. J. Lin, Relaxed cutting plane method for solving linear semi-infinite programming problems, J. Optim. Theory Appl., 99 (1998), 759-779.doi: 10.1023/A:1021763419562.