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 and 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-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.

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

[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 and 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 and 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 and Management Optimization, 2012, 8 (3) : 705-726. doi: 10.3934/jimo.2012.8.705
[4]

Ke Su, Yumeng Lin, Chun Xu. A new adaptive method to nonlinear semi-infinite programming. Journal of Industrial and Management Optimization, 2022, 18 (2) : 1133-1144. doi: 10.3934/jimo.2021012
[5]

Yanqun Liu. An exterior point linear programming method based on inclusive normal cones. Journal of Industrial and Management Optimization, 2010, 6 (4) : 825-846. doi: 10.3934/jimo.2010.6.825
[6]

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 and Continuous Dynamical Systems - B, 2019, 24 (4) : 1743-1767. doi: 10.3934/dcdsb.2018235
[7]

Jinchuan Zhou, Naihua Xiu, Jein-Shan Chen. Solution properties and error bounds for semi-infinite complementarity problems. Journal of Industrial and Management Optimization, 2013, 9 (1) : 99-115. doi: 10.3934/jimo.2013.9.99
[8]

Burcu Özçam, Hao Cheng. A discretization based smoothing method for solving semi-infinite variational inequalities. Journal of Industrial and Management Optimization, 2005, 1 (2) : 219-233. doi: 10.3934/jimo.2005.1.219
[9]

Gang Li, Yinghong Xu, Zhenhua Qin. Optimality conditions for composite DC infinite programming problems. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022064
[10]

Yi Zhang, Yong Jiang, Liwei Zhang, Jiangzhong Zhang. A perturbation approach for an inverse linear second-order cone programming. Journal of Industrial and Management Optimization, 2013, 9 (1) : 171-189. doi: 10.3934/jimo.2013.9.171
[11]

Shiyun Wang, Yong-Jin Liu, Yong Jiang. A majorized penalty approach to inverse linear second order cone programming problems. Journal of Industrial and Management Optimization, 2014, 10 (3) : 965-976. doi: 10.3934/jimo.2014.10.965
[12]

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 and Continuous Dynamical Systems - S, 2020, 13 (3) : 1007-1015. doi: 10.3934/dcdss.2020059
[13]

Xiaodong Fan, Tian Qin. Stability analysis for generalized semi-infinite optimization problems under functional perturbations. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1221-1233. doi: 10.3934/jimo.2018201
[14]

Rafael del Rio, Mikhail Kudryavtsev, Luis O. Silva. Inverse problems for Jacobi operators III: Mass-spring perturbations of semi-infinite systems. Inverse Problems and Imaging, 2012, 6 (4) : 599-621. doi: 10.3934/ipi.2012.6.599
[15]

Igor Chueshov. Remark on an elastic plate interacting with a gas in a semi-infinite tube: Periodic solutions. Evolution Equations and Control Theory, 2016, 5 (4) : 561-566. doi: 10.3934/eect.2016019
[16]

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 and Imaging, 2008, 2 (3) : 317-333. doi: 10.3934/ipi.2008.2.317
[17]

Meixia Li, Changyu Wang, Biao Qu. Non-convex semi-infinite min-max optimization with noncompact sets. Journal of Industrial and Management Optimization, 2017, 13 (4) : 1859-1881. doi: 10.3934/jimo.2017022
[18]

Andrew E.B. Lim, John B. Moore. A path following algorithm for infinite quadratic programming on a Hilbert space. Discrete and Continuous Dynamical Systems, 1998, 4 (4) : 653-670. doi: 10.3934/dcds.1998.4.653
[19]

Rong Hu, Ya-Ping Fang. A parametric simplex algorithm for biobjective piecewise linear programming problems. Journal of Industrial and Management Optimization, 2017, 13 (2) : 573-586. doi: 10.3934/jimo.2016032
[20]

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

2021 Impact Factor: 1.411

Tools

Metrics

  • PDF downloads (98)
  • HTML views (0)
  • Cited by (5)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy