-
作者：ROBINSON, SM
摘要：We study a certain piecewise linear manifold, which we call the normal manifold, associated with a polyhedral convex set, and a family of continuous functions, called normal maps, that are induced on this manifold by continuous functions from R(n) to R(n). These normal maps occur frequently in optimization and equilibrium problems, and the subclass of normal maps induced by linear transformations plays a key role. Our main result is that the normal map induced by a linear transformation is a L...
-
作者：NOWAK, AS; RAGHAVAN, TES
作者单位：University of Illinois System; University of Illinois Chicago; University of Illinois Chicago Hospital
摘要：The following theorem is proved: Every nonzero-sum discounted stochastic game in countably generated measurable state space with compact metric action spaces admits a stationary correlated equilibrium point with symmetric (public) information whenever the immediate rewards and transition densities are measurable with respect to the state variable and continuous with respect to joint actions.
-
作者：RITT, RK; SENNOTT, LI
摘要：The result of Sennott [9] on the existence of optimal stationary policies in countable state Markov decision chains with finite action sets is generalized to arbitrary state space Markov decision chains. The assumption of finite action sets occurring in a global countable action space allows a particularly simple theoretical structure for the general state space Markov decision chain. Two examples illustrate the results. Example 1 is a system of parallel queues with stochastic work requirement...
-
作者：THACH, PT
摘要：We consider the problem min{f(x, y): g(i)(x, y) less-than-or-equal-to 0, i = 1,..., m, x is-an-element-of X, y is-an-element-of Y} where f and the g(i) are lower semicontinuous and convex in y for fixed x but not convex jointly in (x, y), X is a compact subset of R(n), Y is a closed convex set in R(m). In order to decompose this problem into subproblems, each depending either on the x-variables alone or the y-variables alone, we propose a new partitioning method which does not require the Bend...
-
作者：GRANOT, D; GRANOT, F
摘要：We present a computational analysis of a game theoretic approach to a cost allocation problem arising from a graph optimization problem, referred to as the fixed cost spanning forest (FCSF) problem. The customers in the FCSF problem, represented by nodes in a graph G, are in need of service that can be produced at some facilities yet to be constructed. The cost allocation problem is concerned with the fair distribution of the cost of providing the service among customers. We formulate this cos...
-
作者：MAITRA, A; SUDDERTH, W
摘要：We consider the negative dynamic programming model of Strauch [12] and prove that the optimal reward function can be obtained by a transfinite iteration of the optimal reward operator. We show that a player loses nothing by restricting himself to measurable policies, if the returns from nonmeasurable policies are evaluated by lower integrals.
-
作者：HAN, SP; PANG, JS; RANGARAJ, N
作者单位：Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Bombay
摘要：This paper presents some globally convergent descent methods for solving systems of nonlinear equations defined by locally Lipschitzian functions. These methods resemble the well-known family of damped Newton and Gauss-Newton methods for solving systems of smooth equations; they generalize some recent Newton-like methods for solving B-differentiable equations which arise from various mathematical programs.
-
作者：SCHAL, M
摘要：For a semi-Markov decision model with average return, the validity of the second optimality equation is shown in the (nonmodified) form where the actions run through the set of all admissible actions rather than through the set of maximum points (conserving actions) for the first optimality equation. As a consequence the existence of a strongly optimal stationary policy is shown. The results seem to be known only for finite state finite action models whereas here countable state compact action...
-
作者：MONTICINO, MG
摘要：Suppose measurability structures are imposed upon a Dubins and Savage gambling problem. A long-standing question asks whether strategies which are measurable with respect to these structures enable the gambler to maximize his return. Measurable strategies have the advantage over arbitrary strategies in that they induce countably additive probability measures. In this work, we show that measurable strategies are adequate in order to maximize return if and only if the optimal return function is ...
-
作者：TARJAN, RE
作者单位：Nokia Corporation; Nokia Bell Labs; AT&T
摘要：We study the number of pivots required by the primal network simplex algorithm to solve the minimum-cost circulation problem. We propose a pivot selection rule with a bound of n(log n)/2 + O(1) on the number of pivots, for an n-vertex network. This is the first known subexponential bound. The network simplex algorithm with this rule can be implemented to run in n(log n)/2 + O(1) time. In the special case of planar graphs, we obtain a polynomial bound on the number of pivots and the running tim...
