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]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[2]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008
[3]

Charlene Kalle, Niels Langeveld, Marta Maggioni, Sara Munday. Matching for a family of infinite measure continued fraction transformations. Discrete & Continuous Dynamical Systems - A, 2020, 40 (11) : 6309-6330. doi: 10.3934/dcds.2020281
[4]

Seung-Yeal Ha, Myeongju Kang, Bora Moon. Collective behaviors of a Winfree ensemble on an infinite cylinder. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2749-2779. doi: 10.3934/dcdsb.2020204
[5]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[6]

Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781
[7]

Marcelo Messias. Periodic perturbation of quadratic systems with two infinite heteroclinic cycles. Discrete & Continuous Dynamical Systems - A, 2012, 32 (5) : 1881-1899. doi: 10.3934/dcds.2012.32.1881
[8]

Diana Keller. Optimal control of a linear stochastic Schrödinger equation. Conference Publications, 2013, 2013 (special) : 437-446. doi: 10.3934/proc.2013.2013.437
[9]

Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311
[10]

Nizami A. Gasilov. Solving a system of linear differential equations with interval coefficients. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2739-2747. doi: 10.3934/dcdsb.2020203
[11]

Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119
[12]

W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349
[13]

Arunima Bhattacharya, Micah Warren. $ C^{2, \alpha} $ estimates for solutions to almost Linear elliptic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021024
[14]

Misha Bialy, Andrey E. Mironov. Rich quasi-linear system for integrable geodesic flows on 2-torus. Discrete & Continuous Dynamical Systems - A, 2011, 29 (1) : 81-90. doi: 10.3934/dcds.2011.29.81
[15]

Fumihiko Nakamura. Asymptotic behavior of non-expanding piecewise linear maps in the presence of random noise. Discrete & Continuous Dynamical Systems - B, 2018, 23 (6) : 2457-2473. doi: 10.3934/dcdsb.2018055
[16]

Hirofumi Notsu, Masato Kimura. Symmetry and positive definiteness of the tensor-valued spring constant derived from P1-FEM for the equations of linear elasticity. Networks & Heterogeneous Media, 2014, 9 (4) : 617-634. doi: 10.3934/nhm.2014.9.617
[17]

Jong Yoon Hyun, Yoonjin Lee, Yansheng Wu. Connection of $ p $-ary $ t $-weight linear codes to Ramanujan Cayley graphs with $ t+1 $ eigenvalues. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020133

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences