    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:
  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.  Google Scholar  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.  Google Scholar  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.  Google Scholar  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.  Google Scholar  M. A. Goberna and M. A. López, Linear Semi-infinite Optimization,, Wiley Series in Mathematical Methods in Practice, (1998). Google Scholar  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.  Google Scholar  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.  Google Scholar  R. Hettich, An implementation of a discretization method for semi-infinite programming,, Mathematical Programming, 34 (1986), 354.  doi: 10.1007/BF01582235.  Google Scholar  R. Hettich and K. O. Kortanek, Semi-infinite programming: Theory, methods, and applications,, SIAM Rev., 35 (1993), 380.  doi: 10.1137/1035089.  Google Scholar  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.  Google Scholar  A. Kaplan and R. Tichatschke, Proximal interior point method for convex semi-infinite programming,, Optim. Methods Softw., 15 (2001), 87.  doi: 10.1080/10556780108805813.  Google Scholar  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.  Google Scholar  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.  Google Scholar  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.  Google Scholar  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.  Google Scholar  R. Reemtsen, Discretization methods for the solution of semi-infinite programming problems,, J. Optim. Theory Appl., 71 (1991), 85.  doi: 10.1007/BF00940041.  Google Scholar  G. A. Watson, Lagrangian methods for semi-infinite programming problems,, in Infinite Programming, (1985), 90.  doi: 10.1007/978-3-642-46564-2_8.  Google Scholar  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.  Google Scholar

show all references

##### References:
  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.  Google Scholar  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.  Google Scholar  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.  Google Scholar  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.  Google Scholar  M. A. Goberna and M. A. López, Linear Semi-infinite Optimization,, Wiley Series in Mathematical Methods in Practice, (1998). Google Scholar  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.  Google Scholar  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.  Google Scholar  R. Hettich, An implementation of a discretization method for semi-infinite programming,, Mathematical Programming, 34 (1986), 354.  doi: 10.1007/BF01582235.  Google Scholar  R. Hettich and K. O. Kortanek, Semi-infinite programming: Theory, methods, and applications,, SIAM Rev., 35 (1993), 380.  doi: 10.1137/1035089.  Google Scholar  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.  Google Scholar  A. Kaplan and R. Tichatschke, Proximal interior point method for convex semi-infinite programming,, Optim. Methods Softw., 15 (2001), 87.  doi: 10.1080/10556780108805813.  Google Scholar  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.  Google Scholar  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.  Google Scholar  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.  Google Scholar  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.  Google Scholar  R. Reemtsen, Discretization methods for the solution of semi-infinite programming problems,, J. Optim. Theory Appl., 71 (1991), 85.  doi: 10.1007/BF00940041.  Google Scholar  G. A. Watson, Lagrangian methods for semi-infinite programming problems,, in Infinite Programming, (1985), 90.  doi: 10.1007/978-3-642-46564-2_8.  Google Scholar  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.  Google Scholar
  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  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  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  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  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  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  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  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  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  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, 2020, 13 (3) : 1007-1015. doi: 10.3934/dcdss.2020059  Xiaodong Fan, Tian Qin. Stability analysis for generalized semi-infinite optimization problems under functional perturbations. Journal of Industrial & Management Optimization, 2020, 16 (3) : 1221-1233. doi: 10.3934/jimo.2018201  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  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  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  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  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  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  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  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  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

2019 Impact Factor: 1.366