Numerical method for solving the continuous-time linear programming problems with time-dependent matrices and piecewise continuous functions

Hsien-Chung Wu; Hsien-Chung Wu

doi:10.3934/math.2020358

AIMS Mathematics

2020, Volume 5, Issue 6: 5572-5627. doi: 10.3934/math.2020358

Previous Article Next Article

Research article

Numerical method for solving the continuous-time linear programming problems with time-dependent matrices and piecewise continuous functions

Hsien-Chung Wu ^,

Department of Mathematics, National Kaohsiung Normal University, Kaohsiung 802, Taiwan

Received: 20 April 2020 Accepted: 19 May 2020 Published: 01 July 2020
MSC : 90C05, 90C46, 90C90

The numerical method is proposed in this paper to solve a general class of continuous-time linear programming problems in which the functions appeared in the coefficients and the time-dependent matrices are assumed to be piecewise continuous. In order to make sure that all the subintervals of time interval will not contain the discontinuities of the involved functions, a methodology for not equally partitioning the time interval is proposed. The main issue of this paper is to obtain an analytic formula of the error bound, where the strong duality theorem for the primal and dual pair of continuous-time linear programming problems with time-dependent matrices and piecewise continuous functions is a by-product. We shall propose two kinds of computational procedure to evaluate the error bounds. One needs to solve the dual problem of the discretized linear programming problem, and another one does not need to solve the dual problem. The detailed differences between these two computational procedures will be also presented. Finally we present a numerical example to demonstrate the usefulness of the numerical method.
- continuous-time linear programming problems,
- discretized problems,
- piecewise continuous functions,
- weak duality theorem,
- strong duality theorem
Citation: Hsien-Chung Wu. Numerical method for solving the continuous-time linear programming problems with time-dependent matrices and piecewise continuous functions[J]. AIMS Mathematics, 2020, 5(6): 5572-5627. doi: 10.3934/math.2020358

Related Papers:

Abstract

The numerical method is proposed in this paper to solve a general class of continuous-time linear programming problems in which the functions appeared in the coefficients and the time-dependent matrices are assumed to be piecewise continuous. In order to make sure that all the subintervals of time interval will not contain the discontinuities of the involved functions, a methodology for not equally partitioning the time interval is proposed. The main issue of this paper is to obtain an analytic formula of the error bound, where the strong duality theorem for the primal and dual pair of continuous-time linear programming problems with time-dependent matrices and piecewise continuous functions is a by-product. We shall propose two kinds of computational procedure to evaluate the error bounds. One needs to solve the dual problem of the discretized linear programming problem, and another one does not need to solve the dual problem. The detailed differences between these two computational procedures will be also presented. Finally we present a numerical example to demonstrate the usefulness of the numerical method.

References

[1]	E. J. Anderson, P. Nash and A. F. Perold, Some properties of a class of continuous linear programs, SIAM J. Control Optim., 21 (1983), 758-765. doi: 10.1137/0321046
[2]	E. J. Anderson and A. B. Philpott, On the solutions of a class of continuous linear programs, SIAM J. Control Optimi., 32 (1994), 1289-1296. doi: 10.1137/S0363012992227216
[3]	E. J. Anderson and M. C. Pullan, Purification for separated continuous linear programs, Math. Methods Oper. Res., 43 (1996), 9-33. doi: 10.1007/BF01303432
[4]	R. E. Bellman, Dynamic Programming, Princeton University Press, Princeton, 1957.
[5]	R. N. Buie and J. Abrham, Numerical solutions to continuous linear programming problems, Math. Methods Oper. Res., 17 (1973), 107-117. doi: 10.1007/BF01956855
[6]	W. H. Farr, M. A. Hanson, Continuous Time Programming with Nonlinear Constraints, J. Math. Anal. Appl., 45 (1974), 96-115. doi: 10.1016/0022-247X(74)90124-3
[7]	W. H. Farr, M. A. Hanson, Continuous Time Programming with Nonlinear Time-Delayed Constraints, J. Math. Anal. Appl., 46 (1974), 41-61. doi: 10.1016/0022-247X(74)90280-7
[8]	L. Fleischer and J. Sethuraman, Efficient algorithms for separated continuous linear programs: the multicommodity flow problem with holding costs and extensions, Math. Oper. Res., 30 (2005), 916-938. doi: 10.1287/moor.1050.0166
[9]	R. C. Grinold, Continuous Programming Part One: Linear Objectives, J. Math. Anal. Appl., 28 (1969), 32-51. doi: 10.1016/0022-247X(69)90106-1
[10]	R. C. Grinold, Continuous Programming Part Two: Nonlinear Objectives, J. Math. Anal. Appl., 27 (1969), 639-655. doi: 10.1016/0022-247X(69)90143-7
[11]	M. A. Hanson and B. Mond, A Class of Continuous Convex Programming Problems, J. Math. Anal. Appl., 22 (1968), 427-437. doi: 10.1016/0022-247X(68)90184-4
[12]	N. Levinson, A class of continuous linear programming problems, J. Math. Anal. Appl., 16 (1966), 73-83. doi: 10.1016/0022-247X(66)90187-9
[13]	R. Meidan and A. F. Perold, Optimality conditions and strong duality in abstract and continuoustime linear programming, J. Optimiz. Theory App., 40 (1983), 61-77. doi: 10.1007/BF00934631
[14]	S. Nobakhtian, M. R. Pouryayevali, Optimality Criteria for Nonsmooth Continuous-Time Problems of Multiobjective Optimization, J. Optimiz. Theory App., 136 (2008), 69-76. doi: 10.1007/s10957-007-9302-1
[15]	S. Nobakhtian, M. R. Pouryayevali, Duality for Nonsmooth Continuous-Time Problems of Vector Optimization, J. Optimiz. Theory App., 136 (2008), 77-85. doi: 10.1007/s10957-007-9301-2
[16]	N. S. Papageorgiou, A class of infinite dimensional linear programming problems, J. Math. Anal. Appl., 87 (1982), 228-245. doi: 10.1016/0022-247X(82)90163-9
[17]	M. C. Pullan, An algorithm for a class of continuous linear programs, SIAM J. Control Optim., 31 (1993), 1558-1577. doi: 10.1137/0331073
[18]	M. C. Pullan, Forms of optimal solutions for separated continuous linear programs, SIAM J. Control Optim., 33 (1995), 1952-1977. doi: 10.1137/S0363012993247858
[19]	M.C. Pullan, A duality theory for separated continuous linear programs, SIAM J. Control Optim., 34 (1996), 931-965. doi: 10.1137/S0363012993257507
[20]	M. C. Pullan, Convergence of a general class of algorithms for separated continuous linear programs, SIAM J. Optimiz., 10 (2000), 722-731. doi: 10.1137/S1052623494278827
[21]	M. C. Pullan, An extended algorithm for separated continuous linear programs, Math. Program., 93 (2002), 415-451. doi: 10.1007/s10107-002-0307-0
[22]	T. W. Reiland, Optimality Conditions and Duality in Continuous Programming I: Convex Programs and a Theorem of the Alternative, J. Math. Anal. Appl., 77 (1980), 297-325. doi: 10.1016/0022-247X(80)90278-4
[23]	T. W. Reiland, Optimality Conditions and Duality in Continuous Programming II: The Linear Problem Revisited, J. Math. Anal. Appl., 77 (1980), 329-343. doi: 10.1016/0022-247X(80)90230-9
[24]	T. W. Reiland, M. A. Hanson, Generalized Kuhn-Tucker Conditions and Duality for Continuous Nonlinear Programming Problems, J. Math. Anal. Appl., 74 (1980), 578-598. doi: 10.1016/0022-247X(80)90149-3
[25]	F. Riesz and B. Sz.-Nagy, Functional Analysis, Frederick Ungar Publishing Co., New York, 1955.
[26]	M. A. Rojas-Medar, J. V. Brandao, G. N. Silva, Nonsmooth Continuous-Time Optimization Problems: Sufficient Conditions, J. Math. Anal. Appl., 227 (1998), 305-318. doi: 10.1006/jmaa.1998.6024
[27]	M. Schechter, Duality in continuous linear programming, J. Math. Anal. Appl., 37 (1972), 130-141. doi: 10.1016/0022-247X(72)90262-4
[28]	E. Shindin, G. Weiss, Structure of Solutions for Continuous Linear Programs with Constant Coefficients, SIAM J. Optimiz., 25 (2015), 1276-1297. doi: 10.1137/140971725
[29]	C. Singh, A Sufficient Optimality Criterion in Continuous Time Programming for Generalized Convex Functions, J. Math. Anal. Appl., 62 (1978), 506-511. doi: 10.1016/0022-247X(78)90143-9
[30]	C. Singh, W. H. Farr, Saddle-Point Optimality Criteria of Continuous Time Programming without Differentiability, J. Math. Anal. Appl., 59 (1977), 442-453. doi: 10.1016/0022-247X(77)90072-5
[31]	W. F. Tyndall, A duality theorem for a class of continuous linear programming problems, SIAM J. Appl. Math., 15 (1965), 644-666.
[32]	W. F. Tyndall, An extended duality theorem for continuous linear programming problems, SIAM J. Appl. Math., 15 (1967), 1294-1298. doi: 10.1137/0115112
[33]	X. Q. Wang, S. Zhang, D. D. Yao, Separated Continuous Conic Programming: Strong Duality and an Approximation Algorithm, SIAM J. Control Optim., 48 (2009), 2118-2138. doi: 10.1137/060650532
[34]	G. Weiss, A simplex based algorithm to solve separated continuous linear programs, Math. Program., 115 (2008), 151-198. doi: 10.1007/s10107-008-0217-x
[35]	C.-F. Wen, H.-C. Wu, Using the Dinkelbach-Type Algorithm to Solve the Continuous-Time Linear Fractional Programming Problems, J. Global Optim., 49 (2011), 237-263. doi: 10.1007/s10898-010-9542-8
[36]	C.-F. Wen, H.-C. Wu, Using the Parametric Approach to Solve the Continuous-Time Linear Fractional Max-Min Problems, J. Global Optim., 54 (2012), 129-153. doi: 10.1007/s10898-011-9751-9
[37]	C.-F. Wen, H.-C. Wu, The Approximate Solutions and Duality Theorems for the Continuous-Time Linear Fractional Programming Problems, Numer. Func. Anal. Opt., 33 (2012), 80-129. doi: 10.1080/01630563.2011.629312
[38]	H.-C. Wu, Solving the Continuous-Time Linear Programming Problems Based on the Piecewise Continuous Functions, Numer. Func. Anal. Opt., 37 (2016), 1168-1201. doi: 10.1080/01630563.2016.1193517
[39]	G. J. Zalmai, Duality for a Class of Continuous-Time Homogeneous Fractional Programming Problems, Zeitschrift für Operations Research, 30 (1986), A43-A48.
[40]	G. J. Zalmai, Duality for a Class of Continuous-Time Fractional Programming Problems, Utilitas Mathematica, 31 (1987), 209-218.
[41]	G. J. Zalmai, Optimality Conditions and Duality for a Class of Continuous-Time Generalized Fractional Programming Problems, J. Math. Anal. Appl., 153 (1990), 365-371.
[42]	G. J. Zalmai, Optimality Conditions and Duality models for a Class of Nonsmooth Constrained Fractional Optimal Control Problems, J. Math. Anal. Appl., 210 (1997), 114-149. doi: 10.1006/jmaa.1997.5377

Reader Comments

Your name:*

Email:*
© 2020 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)