American Institute of Mathematical Sciences

April  2014, 10(2): 397-412. doi: 10.3934/jimo.2014.10.397

A ladder method for linear semi-infinite programming

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

Received  November 2012 Revised  July 2013 Published  October 2013

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.
Citation: Yanqun Liu, Ming-Fang Ding. A ladder method for linear semi-infinite programming. Journal of Industrial & Management Optimization, 2014, 10 (2) : 397-412. doi: 10.3934/jimo.2014.10.397
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. doi: 10.1007/BF01587092. [2] B. Betrò, An accelerated central cutting plane algorithm for semi-infinite linear programming,, Mathematical Programming, 101 (2004), 479. 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. 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. doi: 10.1007/BF01582293. [5] M. A. Goberna and M. A. López, Linear Semi-infinite Optimization,, Wiley Series in Mathematical Methods in Practice, (1998). [6] M. A. Goberna, Linear semi-infinite optimization: Recent advances,, in Continuous Optimization (eds. V. Jeyakumar and A. M. Rubinov), (2005), 3. 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), (1983), 158. 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. doi: 10.1007/BF01582235. [9] R. Hettich and K. O. Kortanek, Semi-infinite programming: Theory, methods, and applications,, SIAM Rev., 35 (1993), 380. 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. 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. 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. 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. 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. 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. 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. doi: 10.1007/BF00940041. [17] G. A. Watson, Lagrangian methods for semi-infinite programming problems,, in Infinite Programming, (1985), 90. 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. doi: 10.1023/A:1021763419562.

show all references

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. doi: 10.1007/BF01587092. [2] B. Betrò, An accelerated central cutting plane algorithm for semi-infinite linear programming,, Mathematical Programming, 101 (2004), 479. 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. 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. doi: 10.1007/BF01582293. [5] M. A. Goberna and M. A. López, Linear Semi-infinite Optimization,, Wiley Series in Mathematical Methods in Practice, (1998). [6] M. A. Goberna, Linear semi-infinite optimization: Recent advances,, in Continuous Optimization (eds. V. Jeyakumar and A. M. Rubinov), (2005), 3. 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), (1983), 158. 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. doi: 10.1007/BF01582235. [9] R. Hettich and K. O. Kortanek, Semi-infinite programming: Theory, methods, and applications,, SIAM Rev., 35 (1993), 380. 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. 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. 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. 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. 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. 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. 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. doi: 10.1007/BF00940041. [17] G. A. Watson, Lagrangian methods for semi-infinite programming problems,, in Infinite Programming, (1985), 90. 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. doi: 10.1023/A:1021763419562.
 [1] Jinchuan Zhou, Changyu Wang, Naihua Xiu, Soonyi Wu. First-order optimality conditions for convex semi-infinite min-max programming with noncompact sets. Journal of Industrial & Management Optimization, 2009, 5 (4) : 851-866. doi: 10.3934/jimo.2009.5.851 [2] Zhi Guo Feng, Kok Lay Teo, Volker Rehbock. A smoothing approach for semi-infinite programming with projected Newton-type algorithm. Journal of Industrial & Management Optimization, 2009, 5 (1) : 141-151. doi: 10.3934/jimo.2009.5.141 [3] Cheng Ma, Xun Li, Ka-Fai Cedric Yiu, Yongjian Yang, Liansheng Zhang. On an exact penalty function method for semi-infinite programming problems. Journal of Industrial & Management Optimization, 2012, 8 (3) : 705-726. doi: 10.3934/jimo.2012.8.705 [4] 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 [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] Jinchuan Zhou, Naihua Xiu, Jein-Shan Chen. Solution properties and error bounds for semi-infinite complementarity problems. Journal of Industrial & Management Optimization, 2013, 9 (1) : 99-115. doi: 10.3934/jimo.2013.9.99 [7] Burcu Özçam, Hao Cheng. A discretization based smoothing method for solving semi-infinite variational inequalities. Journal of Industrial & Management Optimization, 2005, 1 (2) : 219-233. doi: 10.3934/jimo.2005.1.219 [8] Rafael del Rio, Mikhail Kudryavtsev, Luis O. Silva. Inverse problems for Jacobi operators III: Mass-spring perturbations of semi-infinite systems. Inverse Problems & Imaging, 2012, 6 (4) : 599-621. doi: 10.3934/ipi.2012.6.599 [9] Igor Chueshov. Remark on an elastic plate interacting with a gas in a semi-infinite tube: Periodic solutions. Evolution Equations & Control Theory, 2016, 5 (4) : 561-566. doi: 10.3934/eect.2016019 [10] Roman Chapko, B. Tomas Johansson. An alternating boundary integral based method for a Cauchy problem for the Laplace equation in semi-infinite regions. Inverse Problems & Imaging, 2008, 2 (3) : 317-333. doi: 10.3934/ipi.2008.2.317 [11] Meixia Li, Changyu Wang, Biao Qu. Non-convex semi-infinite min-max optimization with noncompact sets. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1859-1881. doi: 10.3934/jimo.2017022 [12] Xiaodong Fan, Tian Qin. Stability analysis for generalized semi-infinite optimization problems under functional perturbations. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-13. doi: 10.3934/jimo.2018201 [13] Azhar Ali Zafar, Khurram Shabbir, Asim Naseem, Muhammad Waqas Ashraf. MHD natural convection boundary-layer flow over a semi-infinite heated plate with arbitrary inclination. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 1007-1015. doi: 10.3934/dcdss.2020059 [14] Yi Zhang, Yong Jiang, Liwei Zhang, Jiangzhong Zhang. A perturbation approach for an inverse linear second-order cone programming. Journal of Industrial & Management Optimization, 2013, 9 (1) : 171-189. doi: 10.3934/jimo.2013.9.171 [15] Shiyun Wang, Yong-Jin Liu, Yong Jiang. A majorized penalty approach to inverse linear second order cone programming problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 965-976. doi: 10.3934/jimo.2014.10.965 [16] Andrew E.B. Lim, John B. Moore. A path following algorithm for infinite quadratic programming on a Hilbert space. Discrete & Continuous Dynamical Systems - A, 1998, 4 (4) : 653-670. doi: 10.3934/dcds.1998.4.653 [17] 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 [18] Atul Kumar, R. R. Yadav. Analytical approach of one-dimensional solute transport through inhomogeneous semi-infinite porous domain for unsteady flow: Dispersion being proportional to square of velocity. Conference Publications, 2013, 2013 (special) : 457-466. doi: 10.3934/proc.2013.2013.457 [19] Satoshi Ito, Soon-Yi Wu, Ting-Jang Shiu, Kok Lay Teo. A numerical approach to infinite-dimensional linear programming in $L_1$ spaces. Journal of Industrial & Management Optimization, 2010, 6 (1) : 15-28. doi: 10.3934/jimo.2010.6.15 [20] Vladimir Gaitsgory, Alex Parkinson, Ilya Shvartsman. Linear programming formulations of deterministic infinite horizon optimal control problems in discrete time. Discrete & Continuous Dynamical Systems - B, 2017, 22 (10) : 3821-3838. doi: 10.3934/dcdsb.2017192

2018 Impact Factor: 1.025