American Institute of Mathematical Sciences

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

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, 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.
Keywords: optimality, ladder, inclusive cone, Linear semi-infinite programming, algorithm..
Mathematics Subject Classification: Primary: 90C34, 90C4.
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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[5]

M. A. Goberna and M. A. López, Linear Semi-infinite Optimization,, Wiley Series in Mathematical Methods in Practice, (1998). Google Scholar

[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. Google Scholar

[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. Google Scholar

[8]

R. Hettich, An implementation of a discretization method for semi-infinite programming,, Mathematical Programming, 34 (1986), 354. doi: 10.1007/BF01582235. Google Scholar

[9]

R. Hettich and K. O. Kortanek, Semi-infinite programming: Theory, methods, and applications,, SIAM Rev., 35 (1993), 380. doi: 10.1137/1035089. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[16]

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

[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. Google Scholar

[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. Google Scholar

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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[5]

M. A. Goberna and M. A. López, Linear Semi-infinite Optimization,, Wiley Series in Mathematical Methods in Practice, (1998). Google Scholar

[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. Google Scholar

[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. Google Scholar

[8]

R. Hettich, An implementation of a discretization method for semi-infinite programming,, Mathematical Programming, 34 (1986), 354. doi: 10.1007/BF01582235. Google Scholar

[9]

R. Hettich and K. O. Kortanek, Semi-infinite programming: Theory, methods, and applications,, SIAM Rev., 35 (1993), 380. doi: 10.1137/1035089. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[16]

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

[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. Google Scholar

[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. Google Scholar

[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

Tools

Metrics

  • PDF downloads (9)
  • HTML views (0)
  • Cited by (4)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences