Representation Theorems for Equivalent Optimization Problems
Representation Theorems for Equivalent Optimization Problems
复制标题
等效优化问题的表示定理
DOI：
10.1016/s0019-9958(72)90125-8
复制
发表时间：
1972
期刊：
影响因子：
--
通讯作者：
T. Ibaraki
中科院分区：
文献类型：
--
作者：
T. Ibaraki
Karp和Held（1967）结合将给定的优化问题转化为可得到动态规划泛函方程的形式的问题，从自动机理论的角度阐明了一类决策过程与动态规划的关系。本文还沿袭了Karp和Held的思路，提出了一些新的概念。首先，我们假设给定的优化问题是离散的和确定性的：它以离散决策过程（ddp）的形式给出。然后我们定义了六类决策过程：sdp（顺序决策过程）、msdp（单调决策过程）、smsdp（严格单调决策过程）、pmsdp（正单调决策过程）、ap（加性决策过程）和lmsdp（无循环决策过程）。sdp被认为是有限状态决策过程的一般模型。msdp是sdp的一个子类，从sdp中可以得到动态规划的泛函方程。smsdp、pmsdp、ap和lmsdp是msdp的子类，它们的结构比msdp更简单。事实上，对于这些子类，可以使用更简单的解函数方程的方法。两种类型的表示定理首次证明了每个类的决策过程:一个是体力(弱)表示定理是一个充分必要条件对于一个给定的ddp实现由一个特定类的决策过程,都有相同的一组最优的政策,另一个是药用(强)表示定理,假定巧合的成本价值为每一个可行的政策除了上述条件。基于低表示定理，研究了每一类最优策略集的各种性质。具体地说，尽管sdp和msdp的最优策略集在大多数操作下不闭合，但它们对于smsdp， pmsdp， ap和lmsdp是闭合的。事实上，一组策略可以是smsdp、pmsdp或ap的一组最优策略，当且仅当它是规则的（即，被有限自动机接受）。对于lmsdp，当且仅当一个集合是有限的，它可以是一组最优策略。
In conjunction with the problem of transforming a given optimization problem into a form from which the functional equations of dynamic programming are obtainable, Karp and Held (1967) made clear the relation between a certain class of decision processes and dynamic programming from the view point of automata theory.This paper also follows the line of Karp and Held, and presents a number of new concepts. First we assume that a given optimization problem is discrete and deterministic: it is given in the form of discrete decision process (ddp). Then we define six classes of decision processes: sdp (sequential decision process), msdp (monotone sdp), smsdp (strictly monotone sdp), pmsdp (positively monotone sdp), ap (additive process), and lmsdp (loop-free msdp). The sdp is considered as a general model of a decision process with finite states. The msdp is a subclass of sdp's from which the functional equations of dynamic programming are obtainable. The smsdp, pmsdp, ap, and lmsdp are subclasses of msdp's, which have simpler structures than that of msdp. In fact, simpler solution methods for solving the resulting functional equations are available for these subclasses. Two types of representation theorems are first proved for each class of decision processes: one is thew(weak)-representation theorem which is a necessary and sufficient condition for a given ddp to be realized by a decision process of the specific class in the sense that both have the same set of optimal policies, and the other is thes(strong)-representation theorem, which assumes the coincidence of cost value for each feasible policy in addition to the above condition.Based on thew-representation theorems, various properties of sets of optimal policies are investigated for each class. In particular, it is shown that although sets of optimal policies of sdp and msdp are not closed under most of operations, they are closed for smsdp, pmsdp, ap, and lmsdp. In fact, a set of policies can be a set of optimal policies of an smsdp, pmsdp, or ap if and only if it is regular (i.e., accepted by a finite automaton). For an lmsdp, a set can be a set of optimal policies if and only if it is finite.
DOI：
--
发表时间：
2008
期刊：
影响因子：
--
作者：
枝川明敬;丸山 幸宏;丸山幸宏;枝川 明敬;枝川 明敬;Y. Maruyama;枝川 明敬;福澤勝彦;枝川明敬;藤田渉;枝川明敬;Yukihiro Maruyama;枝川 明敬;永田吉朗・丸山幸宏;枝川明敬;枝川明敬;Y. Maruyama;枝川 明敬;Y. Maruyama
通讯作者：
Y. Maruyama