none

The purpose of this thesis is to present some results on linear programming on measure spaces (LPM). We shall discuss the conditions under which LPM is solvable and the optimal value of an LPM is equal to the optimal value of the dual problem;moreover, we present two algorithms for solving various LPM problems. Essentially, our approach extends the method introduced in cite{LaiWu94}. Besides, we use some examples to show that the proposed methods work for real. We also propose another approximation scheme to solve LPM.This scheme is a discretization method which finds a sequence of optimal solutions of corresponding linear semi-infinite programs, and which shows that the sequence of optimal solutions converges to an optimal solution of LPM. Finally, we implement these methods with providing some examples in the final section.

[1] E. J. Anderson (1983), A review of duality theory for linear programming
over topological vector spaces, J. Math. Anal. Appl. , 97, 380--392.

[2] E. J. Anderson (1985), A new primal algorithm for semi-infinite linear programming.
In E. J. Anderson and A. B. Philpott, editors, Infinite programming, Lecture Notes in
Econom. and Math. Systems 259, pages 108--122, Springer, Berlin-Heidelberg-New York-Tokyo.

[3] E. J. Anderson and A. S. Lewis (1989). An extension of the simplex algorithm for semi-infinite linear
programming. Math. programming , 44, 247--269.

[4] E. J. Anderson, A. S. Lewis and S.-Y. Wu (1989). The capacity problem. Optimization, 20, 725--742.

[5] E. J. Anderson and P. Nash (1987). Linear Programming in Infinite Dimensional Spaces .
John Wiley & Sons, Chichester-New York-Brisbane-Toronto-Singapore.

[6] E. J. Anderson and A. B. Philpott, editors (1985). Infinite programming, Lecture Notes in
Econom. and Math. Systems 259. Springer, Berlin-Heidelberg-New York-Tokyo.

[7] R. G. Bartle (1976). The Elements of Real Analysis . John Wiley & Sons., New York.

[8] R. Bellman (1957). Dynamic Programming . Princeton University Press, Princeton, N. J.

[9] L. Bittner. (1961). Das Austauschverfahren der linearen, Tschebyscheff-Approximation bei nicht
erfullter Haarscher Bedingung. Z. Angew. Math. Mech. , 41, 238--256.

[10] H.-P. Blatt, U. Kaiser, and B. Ruffer-Beedgen (1983). A multiple exchange algorithm in convex
programming. In J.-B. Hiriart-Urruty, W. Oettli, and J. Stoer, editors, Optimization:
Theory and Applications pages 113-130. Marcel Dekker, New York-Basel.

[11] J. W. Blankenship and J. E. Falk (1976). Infinitely constrained optimization problems.
J. Optim. Theory Appl. , 19, 261--281.

[12] C. Carasso and P. J. Laurent (1978). Un algorithme de minimisation en chaine en optimisation convexe.
SIAM J. Control Optim. , 16, 209--235.

[13] A. Charnes, W. W. Cooper, and K. O. Kortanek (1962). Duality, Haar programs and finite sequences
spaces. Proc. Nat. Acad. Sci. USA , 48, 783--786.

[14] A. Charnes, W. W. Cooper, and K. O. Kortanek (1963). Duality in semi-infinite programs and some works
of Haar and Caratheodory. Management Sci. , 9, 209--228.

[15] A. Charnes, W. W. Cooper, and K. O. Kortanek (1965). On representation of semi-infinite programms
which have no duality gaps. Management Sci. , 12, 113--121.

[16] E. W. Cheney and A. A. Goldstein (1959). Newton's method for convex programming and Tchebycheff approximation.
Numer. Math. , 1, 253--268.

[17] G. Choquet (1954). Theory of capacity. Annales de l'Institut Fourier , 131--295.

[18] I. D. Coope and G. A. Watson (1985). A projected Lagrangian algorithm for semi-infinite programming.
Math. Programming , 32, 337--356.

[19] R. J. Duffin (1956). Infinite programs, in "Linear Inequalities and Related Systems" (H. W. Kuhn and
A. W. Tucker, Eds.), Princeton Univ. Press, Princeton, N. J..

[20] S.-C. Fang and S. Puthenpura (1993). Linear Optimization and Extensions: Theory and Algorithms .
Prentice Hall, Englewood Cliffs, New Jersey.

[21] S.-C. Fang and H. S. J. Tsao (1993). Linear programming with entropic perturbation. ZOR ,
37, 171--186.

[22] S.-C. Fang and S.-Y. Wu (1994). An entropic path-following approach for linear semi-infinite programming
problems. In Mathematics Today Vol. XII-A , pages 1--16.

[23] S.-C. Fang and S.-Y. Wu (1994). An inexact approach to solving linear semi-infinite programming
problems. Optimization , 28, 291--299.

[24] A. V. Fiacco and K. O. Kortanek, editors (1983). Semi-Infinite Programming and Applications ,
Lecture Notes in Econom. and Math. Systems 215. Springer, Berlin-Heidelberg-New York-Tokyo.

[25] B. Fugled (1960). On the theory of potentials in locally compact spaces.
Acta Mathematica , 103, 139--215.

[26] J. Fulop (1992). A semi-infinite programming method for approximating load duration
curves by polynomials. Computing , 49, 201--212.

[27] K. Glashoff, and S.-A. Gustafson (1983). Linear Optimization and Approximation .
Springer, New York-Heidelberg-Berlin.

[28] M. A. Goberna and V. Jornet (1988). Geometric fundamentals of the simplex method in semi-infinite
programming. OR Spektrum , 10, 145--152.

[29] M. A. Goberna and M. A. Lopez (1987). Reduction and discrete approximation in linear
semi-infinite programming. Optimization , 18, 643--658.

[30] M. A. Goberna and M. A. Lopez (1988). Optimal value function in semi-infinite programming.
J. Optim. Theory Appl. , 59, 261--279.

[31] M. A. Goberna and M. A. Lopez (1998). Linear Semi-Infinite Optimization . John Wiley
& Sons, Chichester-New York-Brisbane-Toronto-Singapore.

[32] C. Gonzaga and E. Polark (1979). On constraint dropping schemes and optimality functions for a class
of outer approximations algorithms. SIAM J. Control Optim. , 17, 477--493.

[33] R. Grigorieff and R. Reemtsen (1990). Discrete approximations of minimization problems. II. Applications.
Numer. Funct. Anal. Optim. , 11, 721--761.

[34] R. C. Grinold (1969). Continuous programming. I. Linear objectives., J. Math. Anal. Appl. , 28, 32--51.

[35] S.-A. Gustafson (1979). On numerical analysis in semi-infinite programming.
In R. Hettich, editor, Semi-Infinite Programming , Lecture Notes in Contr.
and Inform. Sci. 15, pages 51--65, Springer, Berlin-Heidelberg-New York.

[36] S.-A. Gustafson (1983). A three-phase algorithm for semi-infinite programs.
In A. V. Fiacco and K. O. Kortanek, editors, Semi-Infinite Programming and Applications ,
Lecture Notes in Econom. and Math. Systems 215, pages 138--157, Springer, Berlin-Heidelberg-New York-Tokyo.

[37] S.-A. Gustafson and K. O. Kortanek (1973). Numerical treatment of a class of semi-infinite programming problems.
Nav. Res. Log. Quart. , 20, 477--504.

[38] S.-A. Gustafson and K. O. Kortanek (1982). Semi-infinite programming and applicications. In A. Bachem,
M. Gro tschel, and B. Korte, editors, Mathematical Programming. The State of the Art , pages
132--57. Springer, Berlin-Heidelberg-New York.

[39] O. Hernandez-Lerma and J. B. Lasserre (1996). Discrete-Time Markov Control Processes: Basic Optimality
Criteria . Springer-Verlag, New York.

[40] O. Hernandez-Lerma and J. B. Lasserre (1998). Approximation schemes for infinite linear programs.
SIAM J. Optim. , 32, 973--988.

[41] R. Hettich, editor (1979), Semi-Infinite Programming , Lecture Notes in Contr. and Inform. Sci.
15. Springer, Berlin-Heidelberg-New York.

[42] R. Hettich (1986). An implementation of a discretization method for semi-infinite programming.
Math. Programming , 34, 354--361.

[43] R. Hettich and K. O. Kortanek (1993). Semi--infinite programming:
theory, methods and applications. SIAM Review , 35, 380--429.

[44] R. Hettich and P. Zencke (1982). Numerische Methoden der Approximation und semi-infiniten Optimierung .
Teubner, Stuttgart.

[45] K.-H. Hoffmann and A. Klostermair (1976). A semi-infinite linear programming procedure and application to approximation
problems in optimal control. In G. G. Lorentz et al., editors, Approximation Theory II , pages
379--389. Academic Press, New York-San Francisco-London.

[46] H. Hu (1990). A one-phase algorithm for semi-infinite linear programming. Math. Programming ,
46: 85--103.

[47] H. G. Huser (1982). Functional Analysis . Wiley, Chichester.

[48] K. Jacobs and G. Seiffert (1983). A measure-theoretical max-flow problem. Bull. Inst. Math. Acad.
Sinica , 11, 261--280.

[49] C. Kallina and A. C. Williams (1971). Linear programming in reflexive spaces. SIAM Rev. , 13, 350--376.

[50] L. V. Kantorovich (1942). On the translocation of masses. Dokl. Akad. Nauk. SSSR , 37, 220--231.

[51] N. Karmarkar (1984). A new polynomial time algorithm for linear programming. Combinatorica , 4,
373--395.

[52] A. Kaplan and R. Tichatschke (1993). Iterative processes for solving incorrect convex variational problem.
J. Global Optim. , 3, 243--255.

[53] A. Kaplan and R. Tichatschke (1994). Stable Methods for Ill-posed Variational Problems .
Akademie Verlag, Berlin.

[54] J. E. Kelley (1960). The cutting-plane method for solving convex programs. J. Soc. Industr. Appl.
Math. , 8, 703--712.

[55] H. G. Kellerer (1988). Measure theoretic versions of linear
programming. Math. Zeitschrift , 198, 367--400.

[56] L. G. Khachian (1979). A polynomial algorithm in linear programming (in Russian). Doklady Akademiia
Nauk SSSR , 224, 1093--1096, (English translation) Soviet Mathematics Doklady , 20, 191--194.

[57] M. Kojima, N. Meggido, and S. Mizuno (1991). A primal-dual infeasible-interior-point algorithm
algorithm for linear programming. Math. programming , 61, 263--280.

[58] W. Krabs (1979). Optimization and Approximation . Wiley, New York.

[59] K. S. Kretschmer (1961). Programmes in paired spaces.
Canad. J. Math. , 13, 221--238.

[60] H.-C. Lai, and S.-Y. Wu (1992). Extremal points and optimal solutions for
general capacity problems. Math. Programming (series A) , 54, 87--113.

[61] H.-C. Lai, and S.-Y. Wu (1992). On linear semi--infinite programming problems:
An algorithm. Numer. Funct. Anal. and Optim. , 13, 287--304.

[62] H.-C. Lai, and S.-Y. Wu (1994). Linear programming in measure spaces.
Optimization , 29, 141--156.

[63] P. J. Laurent and C. Carasso (1978). An algorithm of successive minimization in convex programming.
R.A.I.R.O. Numer. Anal. , 12, 377--400.

[64] T. Leon and E. Vercher (1992). A purification algorithm for semi-infinite programming.
Europ. J. Oper. Res. , 57, 412--420.

[65] T. Leon and E. Vercher (1994). New descent rules for solving the linear semi-infinite programming
problem. Oper. Res. Letters , 15, 105--114.

[66] V. L. Levin and A. A. Milyutin (1978). The problem of mass transfer with a discontinuous cost function
and a mass statement of the duality problem for convex extremal problems. Russian Math. Surveys ,
34, 1--78.

[67] C.-J. Lin, S.-C. Fang, and S.-Y. Wu . An unconstrained convex programming approach for linear
semi-infinite programming. SIAM J. Optim. (in print).

[68] C.-J. Lin, S.-C. Fang, and S.-Y. Wu (1994). A dual affine scaling based algorithm for solving linear
semi-infinite programming problems. In D.-Z. Du and J. Sun, editors, Advances in Optimization
and Approximation , pages 217--233, Kluwer, Dordrecht-Boston-London.

[69] C.-J. Lin, E. K. Yang, S.-C. Fang, and S.-Y. Wu (1995). Implementation of an inexact approach to
solving linear semi-infinite programming problems. J. Comp. Appl. Math. , 61, 87--103.

[70] D. G. Luenberger (1989). Linear and Nonlinear programming . Addison-Wesley, Reading, Massachusetts,
2nd edition.

[71] D. Q. Mayne, E. Polark, and R. Trahan (1979). An outer approximation algorithm for computer-aided
design problems. J. Optim. Theory Appl. , 28, 331--352.

[72] L. Narici and E. Beckenstein (1985). Topological vector spaces .
Marcel Dekker, New York.

[73] T. Nakamura and M. Yamasaki (1979). Sufficient conditions for duality theorems in infinite linear
programming problems. Hiroshima Math. J. , 9, 323--334.

[74] P. Nash (1985). Algebraic fundamentals of linear programming. In E. J. Anderson and
A. B. Philpott, editors, Infinite programming , Lecture Notes in
Econom. and Math. Systems 259, pages 37--52, Springer, Berlin-Heidelberg-New York-Tokyo.

[75] M. Ohtsuka (1966). Generalized capacity and duality theorem in linear programming. J. Sci. Hiroshima
Univ. Ser. A-I , 30, 45--46.

[76] M. Ohtsuka (1966). A generalization of duality theorem in linear programming.
J. Sci. Hiroshima Univ. Ser. A-I , 30, 57--73.

[77] E. Polak (1997). Optimization. Algorithms and Consistent Approximations . Springer, Berlin-Heidelberg-New York.

[78] R. Reemtsen (1991). Discretization methods for the solution of semi-infinite programming problems.
J. Optim. Theory Appl. , 71, 85--103.

[79] R. Reemtsen (1994). Some outer approximation methods for semi-infinite optimization problems.
J. Comp. Appl. Math. , 53, 87--108.

[80] R. Reemtsen and S. Gorner (1998). Numerical methods for semi--infinite
programming; a survey. In R. Reemtsen and J--J. Ruckmann, editors,
Semi--Infinite programming , pages 195--275, Kluwer Academic Publishers,
Boston.

[81] A. P. Robertson and W. J. Robertson (1973). Topological Vector Spaces . Cambridge
University Press, Cambridge.

[82] K. Roleff (1979). A stable multiple exchange algorithm for linear SIP.
In R. Hettich, editor, Semi-Infinite Programming , Lecture Notes in Contr. and Inform. Sci. 15,
pages 83--96, Springer, Berlin-Heidelberg-New York.

[83] C. Roos, T. Terlaky, and J.-P. Vial (1997). Theory and Algorithms for Linear Optimization .
John Wiley & Sons, Chichester.

[84] W. Rudin (1987). Real and complex analysis . McGraw-Hill.

[85] W. Rudin (1991). Functional analysis . McGraw-Hill.

[86] H. Rudolph (1987). Der Simplex algorithmus der semiinfiniten linearen Optimierung. Wiss. Z. TH
Leuna-Merseburg , 29, 782--806.

[87] R. Schaback and D. Braess (1970). Eine Losungsmethode fur die lineare Tshebyscheff-Approximation
bei nicht erfu llter Haarscher Bedingung. Computing , 6, 289--294.

[88] H. H. Schaefer (1971). Topological Vector Spaces . Springer-verlag, New York.

[89] E. Scha fer (1971). Ein Konstruktionsverfahren bie allgemeiner linearer Approximation.
Numer. Math. , 18, 113--126.

[90] M. Schechter (1972). Linear programs in topological vector spaces. J. Math. Anal. Appl. , 37, 492--500.

[91] R.-L. Sheu, S.-Y. Wu, and S.-C. Fang (1995). A primal-dual infeasible-interior-point algorithm for
linear semi-infinite programming. Computers Math. Applic. , 29, 7--18.

[92] T. Terlaky, editor (1996). Interior Point Methods of Mathematical programming . Kluwer,
Dordrecht-Boston-London.

[93] R. Tichatschke (1979). Stetigkeitseigenschaften und Konvergenz von Folgen diskretisierter semi-infinite
konvexer Optimierungsaufgaben. Wiss. Z. TH Karl-Marx-Stadt , 21, 577--586.

[94] H.-J. Topfer (1967). Tschebyscheff-Approximation und Austauschverfahren bei nicht erfullter
Haarscher Bedingung. In L. Collatz, G. Meinardus, and H. Unger, editors, Funktionalanalysis,
Approximationstheorie, Numerische Mathematik , page 71--89. Birkhauser, Basel-Stuttgart.

[95] W. F. Tyndall (1965). A duality theorem for a class of continuous linear programming problems. SIAM J.
Appl. Math. , 13, 644--666.

[96] R. J. Vanderbei (1997). Linear Programming: Fundations and Extensions . Kluwer,
Dordrecht-Boston-London.

[97] G. A. Watson (1975). A multiple exchange algorithm for multivariate Chebyshev approximation.
SIAM J. Numer. Anal. , 12, 46--52.

[98] C.-F. Wen and S.-Y. Wu (2001). Duality theorems and algorithms for linear
programming in measure spaces, to appear in Journal of Global Optimization .

[99] S. J. Wright (1997). Primal-Dual Interior-Point Methods . SIAM, philadelphia.

[100] S.-Y. Wu (1985). The general capacity problem. In: W. Oettli et al., eds., Methods of
Operations Reasearch (Oelgeschlager, Gunn and Hain, Cambridge, Ma), 49, 329--344.

[101] S.-Y. Wu, S.-C. Fang and C.-J. Lin (1998). Relaxed cutting plane method for solving
linear semi--infinite programming problems.
Journal of Optimization Theory and Applications , 99, 759--779.

[102] S.-Y. Wu, C.-J. Lin and S.-C. Fang (2001). Relaxed cutting plane method for
solving general capacity programming problems, to appear in
Ann of Operations Research .

[103] M. Yamasaki (1966). On a capacity problem raised in connection with linear programming.
J. Sci. Hiroshima Univ. Ser. A-I , 30, 57--73.

[104] M. Yamasaki (1968). Duality theorems in mathematical programmings
and their applications. J. Sci. Hiroshima Univ. Ser. A-I , 32,
331--356.

[105] M. Yosida (1966). Some examples related to duality theorem in linear programming.
J. Sci. Hiroshima Univ. Ser. A--I , 30, 41--43.

[106] Y. Z. Zhu (1966). Generalizations of some fundamental theorems on linear inequalities.
Acta Math. Sinica , 16, 25--40.