Infinite-horizon deterministic dynamic programming in discrete time: a monotone convergence principle and a penalty method

We consider infinite-horizon deterministic dynamic programming problems in discrete time. We show that the value function of such a problem is always a fixed point of a modified version of the Bellman operator. We also show that value iteration converges increasingly to the value function if the initial function is dominated by the value function, is mapped upward by the modified Bellman operator and satisfies a transversality-like condition. These results require no assumption except for the general framework of infinite-horizon deterministic dynamic programming. As an application, we show that the value function can be approximated by computing the value function of an unconstrained version of the problem with the constraint replaced by a penalty function.     

A class of nonseparable dynamic programming problems

A solution procedure is proposed for a class of deterministic sequential decision problems whose objective functions are of the form f _n(x _n)+(g _n(x _n)) where is differentiable and either concave or convex. The procedure calls for the collaboration between dynamic programming and c-programming, and is demonstrated in our treatment of a minimum variance type problem.     

Optimality conditions and duality for a class of nondifferentiable multi-objective fractional programming problems

A class of multi-objective fractional programming problems (MFP) are considered where the involved functions are locally Lipschitz. In order to deduce our main results, we give the definition of the generalized (F,θ,ρ,d)-convex class about the Clarke’s generalized gradient. Under the above generalized convexity assumption, necessary and sufficient conditions for optimality are given. Finally, a dual problem corresponding to (MFP) is formulated, appropriate dual theorems are proved.      

Application of duality theory to a class of composite cost control problems

Let a control system be described by a continuous linear map * from the input spaceU* (some dual Banach space) into the output spaceX* (some finite-dimensional normed space). Within the class of control problems where the constraints and cost are expressed in terms of the norms on the input and output spaces, the following two have had extensive coverage: (i)minimum effort problem: find, from amongst all inputs which have corresponding outputs lying in some closed sphere inX* centered on some desired outputx _d *, an output of minimum norm; and (ii)minimum deviation problem: find, from amongst all inputs lying in some closed sphere inU*, an input having corresponding output at a minimum distance fromx _d *. However, thecomposite cost problem, where we seek to minimizeF(u*, x _d * –x*) over elements satisfyingx* = *u* (F a certain kind of convex functional), has not received the same attention. This paper presents results for the composite cost problem paralleling known results for the minimum effort and deviation problems. It is hoped that a gap in the literature is thereby filled. We show that (a) a solution exists, (b) the solution can be characterized in terms of some closed hyperplaneH inX, and (c)H can be computed as being an element on which some concave functional over closed hyperplanes inX achieves its maximum. The treatment allows of infinite-dimensional output spaces. We make extensive use of recently developed duality theory.This research was supported by the Science Research Council of Great Britain and the Commonwealth Fund (Harkness Fellowship).     

On a class of dynamic programming problems whose optimal controls and states are independent of the future

When applying dynamic programming for optimal decision making one usually needs considerable knowledge about the future. This knowledge, e.g. about future functions and parameters, necessary to determine optimal control policies, however, is often not available and thus precludes the application of dynamic programming.In the present paper it is shown that for a certain class of dynamic programming problems the optimal control policy is independent of the future. To illustrate the results an application in inventory control is given and further applications in the theories of economic growth and corporate finance are listed in the references.     

Optimal control problems on manifolds: a dynamic programming approach

Dynamic programming identifies the value function of continuous time optimal control with a solution to the Hamilton-Jacobi equation, appropriately defined. This relationship in turn leads to sufficient conditions of global optimality, which have been widely used to confirm the optimality of putative minimisers. In continuous time optimal control, the dynamic programming methodology has been used for problems with state space a vector space. However there are many problems of interest in which it is necessary to regard the state space as a manifold. This paper extends dynamic programming to cover problems in which the state space is a general finite-dimensional C^∞ manifold. It shows that, also in a manifold setting, we can characterise the value function of a free time optimal control problem as a unique lower semicontinuous, lower bounded, generalised solution of the Hamilton-Jacobi equation. The application of these results is illustrated by the investigation of minimum time controllers for a rigid pendulum.     

On sufficiency and duality for a class of interval-valued programming problems

In this paper, we are concerned with an interval-valued programming problem. Sufficient optimality conditions are established under generalized convex functions for a feasible solution to be an efficient solution. Appropriate duality theorems for Mond-Weir and Wolfe type duals are discussed in order to relate the efficient solutions of primal and dual programs.     

一类多目标广义分式规划问题的最优性条件和对偶

研究了一类不可微多目标广义分式规划问题．首先,在广义Abadie约束品性条件下,给出了其真有效解的Kuhn—Tucker型必要条件．随后,在（C,a,P,d）一凸性假设下给出其真有效解的充分条件．最后,在此基础上建立了一种对偶模型,证明了对偶定理．得到的结果改进了相关文献中的相应结论．     

Implementation of dynamic programming for chaos control in discrete systems

In this paper the control of discrete chaotic systems by designing linear feedback controllers is presented. The linear feedback control problem for nonlinear systems has been formulated under the viewpoint of dynamic programming. For suppressing chaos with minimum control effort, the system is stabilized on its first order unstable fixed point (UFP). The presented method also could be employed to make any desired nth order fixed point of the system, stable. Two different methods for higher order UFPs stabilization are suggested. Afterwards, these methods are applied to two well-known chaotic discrete systems: the Logistic and the Henon Maps. For each of them, the first and second UFPs in their chaotic regions are stabilized and simulation results are provided for the demonstration of performance.     

Successive approximation technique for a class of large-scale NLP problems and its application to dynamic programming

In this paper, two successive approximation techniques are presented for a class of large-scale nonlinear programming problems with decomposable constraints and a class of high-dimensional discrete optimal control problems, respectively. It is shown that: (a) the accumulation point of the sequence produced by the first method is a Kuhn-Tucker point if the constraint functions are decomposable and if the uniqueness condition holds; (b) the sequence converges to an optimum solution if the objective function is strictly pseudoconvex and if the constraint functions are decomposable and quasiconcave; and (c) similar conclusions for the second method hold also for a class of discrete optimal control problems under some assumptions.     

Generalized geometric programming applied to problems of optimal control: I. Theory

The interest in convexity in optimal control and the calculus of variations has gone through a revival in the past decade. In this paper, we extend the theory of generalized geometric programming to infinite dimensions in order to derive a dual problem for the convex optimal control problem. This approach transfers explicit constraints in the primal problem to the dual objective functional.The authors are indebted to the referees for suggestions leading to improvement of the paper.     

Optimality conditions and duality for a class of nondifferentiable multiobjective generalized fractional programming problems

This paper studies a class of multiobjective generalized fractional programming problems, where the numerators of objective functions are the sum of differentiable function and convex function, while the denominators are the difference of differentiable function and convex function. Under the assumption of Calmness Constraint Qualification the Kuhn-Tucker type necessary conditions for efficient solution are given, and the Kuhn-Tucker type sufficient conditions for efficient solution are presented under the assumptions of （F, α, ρ, d）-V-convexity. Subsequently, the optimality conditions for two kinds of duality models are formulated and duality theorems are proved.     

Generalized geometric programming applied to problems of optimal control: Part I,theory

A modification to the formulation in Ref. 1 is given.     

State aggregation in dynamic programming — An application to scheduling of independent jobs on parallel processors

Exact dynamic programming formulations of capacity loading problems will, in general, involve a prohibitively large state space. This paper offers a methodology for aggregation of the state space when dealing with such problems. Instead of future costs with respect to a known state, we are considering the costs in the worst (or best) case with respect to the given aggregate information. We apply the technique to scheduling of independent jobs on parallel processors.     

Selecting preferred solutions in the minimax approach to dynamic programming problems under flexible constraints

Dynamic Programming is a powerful approach to the optimization of sequential or multistage decision processes, e.g., in planning or in system control. In this paper, we consider both theoretical and algorithmic issues in sequential decision processes under flexible constraints. Such processes must attain a given goal within some tolerance. Tolerances or preferences also apply to the values the decision variables may take or on the action chosen at each step. Such problems boil down to maximin optimization. Unfortunately, this approach suffers from the so-called “drowning effect” (lack of discrimination) and the optimality principle of dynamic programming is not always verified. In this context, we introduce a general framework for refined minimax optimization procedures in order to compare and select preferred alternatives. This framework encompasses already introduced methods such as LexiMin and DiscriMin, but it allows their extension to the comparison of vectors of unequal lengths. We show that these refined comparisons restore compatibility with the optimality principle, and that classical algorithms can be adapted to compute such preferred solutions, by exploiting existing results on idempotent semirings.     

Geometry of optimal value functions with applications to redundancy in linear programming

In 1967, Wets and Witzgall (Ref. 1) made, in passing, a connection between frames of polyhedral cones and redundancy in linear programming. The present work elaborates and formalizes the theoretical details needed to establish this relation. We study the properties of optimal value functions in order to derive the correspondence between problems in redundancy and the frame of a polyhedral cone. The insights obtained lead to schemes to improve the efficiency of procedures to detect redundancy in the areas of linear programming, stochastic programming, and computational geometry.The author is indebted to G. Dewan for his review and discussions.     

A class of polynomially solvable 0-1 programming problems and an application

It is well known that general 0-1 programming problems are NP-Complete and their optimal solutions cannot be found with polynomial-time algorithms unless P=NP. In this paper, we identify a specific class of 0-1 programming problems that is polynomially solvable, and propose two polynomial-time algorithms to find its optimal solutions. This class of 0-1 programming problems commits to a wide range of real-world industrial applications. We provide an instance of representative in the field of supply chain man...     

Subgradients of value functions in parametric dynamic programming

We study in this paper the first-order behavior of value functions in parametric dynamic programming with linear constraints and nonconvex cost functions. By establishing an abstract result on the Fréchet subdifferential of value functions of parametric mathematical programming problems, some new formulas on the Fréchet subdifferential of value functions in parametric dynamic programming are obtained.     

An analytical bound on the fleet size in vehicle routing problems: A dynamic programming approach

We present an analytical upper bound on the number of required vehicles for vehicle routing problems with split deliveries and any number of capacitated depots. We show that a fleet size greater than the proposed bound is not achievable based on a set of common assumptions. This property of the upper bound is proved through a dynamic programming approach. We also discuss the validity of the bound for a wide variety of routing problems with or without split deliveries.