Search

This paper is devoted to two problems in the theory of optimal control for linear processes. The first one is characterized by a cost of the form ess sup {p(u(t)):t∈[a, b]}, whereby p denotes the distance function of a compact convex set C ∘ ℝm containing the origin as an interior point and u:[a, b] → ℝm represents the control. In the second problem the cost depends linear on the controls, which are limited by a bound for ess sup {p(u(t)):t∈[a, b]}.

In this paper we consider the stochastic integral y t = ∫ 0 t e ( s , b ) d b s {y_t} = \int _0^t {e(s,b)d{b_s}} of a nonanticipating Brownian functional e e that is essentially bounded with respect to both time and the Brownian paths. Let f f be a convex function satisfying a certain mild growth condition. Then E f ( y t ) ≦ E f ( | | e | | b t ) Ef({y_t}) \leqq Ef(||e||{b_t}) , where b t {b_t} is the position at time t t of the Brownian path b b . As a corollary, sharp bounds are obtained on the moments of y t {y_t} . The key point in the proof is the use of a transformation, derived from Itô’s lemma, that converts a hyperbolic partial differential equation into a parabolic one.

Even in a finite-dimensional setting for two dual linear programming problems where the positive orthant is replaced by a closed convex cone, it is possible to have a duality gap, i.e., the infimum of one problem greater than the supremum of its dual. The absence of duality gaps is characterized in this paper by using a class of parameterized subsidiary problems of the original pair of dual problems. Characterizations are thereby obtained of “normality”—where the infimum of one problem equate the supremum of its dual. Heretofore only sufficient conditions for normality have been given. In this setting the linear programming characterizations obtained distinguish the four cases of normality where the supremum may or may not be a maximum, and the infimum may or may not be a minimum. An example is given in six dimensions of a dual pair of problems, neither of which is stable, neither of which has an optimal solution, but both of which are normal.

Let E be a normed linear space, S a closed bounded subset of E and J an u.s.c. (for the norm topology) and bounded above mapping of S into ℝ.

Let $y_1, y_2, \cdots$ be a sequence of random variables with known joint distribution. We are allowed to observe the $y$'s sequentially. We must terminate the observation process at some point, and if we stop at time $n$, we receive a reward which is a known function of $y_1, \cdots, y_n$. Our decision to stop at time $n$ is allowed to depend on the observations we have previously made but may not depend on the future, which is still unknown. We are interested in finding stopping rules which maximize our expected terminal reward. More formally, let $(x_n, F_n)_{1 \leqq n}$ be a stochastic sequence on a probability space $(W, F, P)$, i.e., let $(F_n)$ be an increasing sequence of sub-sigma-algebras of $F$ and for each $n \leqq 1$ let $x_n$ be a random variable (rv) measurable $F_n$. In terms of the intuitive background of the preceding paragraph, $F_n = B(y_1, \cdots, y_n)$; and although it is convenient to keep this interpretation in mind, our general results do not depend on it. A stopping rule or stopping variable (sv) is a rv $t$ with values $1, 2, \cdots, +\infty$, such that $P(t < \infty) = 1$ and for each $n \geqq 1 (t = n) \varepsilon F_n. x_t$ is (up to an equivalence) a rv, and if $v = \sup Ex_t$, where the supremum is taken over all sv's such that $Ex_t$ exists, we are interested in answering the following questions: (a) What is $v$? (b) Is there an optimal sv, i.e., one for which $Ex_t$ exists and equals $v$? (c) If there exists an optimal sv, what is it? The problem stated above is not sufficiently well formulated, as the class of sv's $t$ such that $Ex_t$ exists may be vacuous. To avoid this and other uninteresting complications we shall add the assumption that $E|x_n| < \infty, n \geqq 1$. We recall that the essential supremum (e. sup) of a family of rv's $\{q_t, t \varepsilon T\}$ is a rv $Q$ such that (1) $Q \geqq q_t$ a.s. $t \varepsilon T$, and (2) if $Q'$ is any rv such that $Q' \geqq q_t$ a.s., $t \varepsilon T$, then $Q' \geqq Q$ a.s. It is known that the essential supremum of a family of rv's always exists and can be assumed to be the supremum of some countable subfamily (e.g., [12], p. 44). Let $C_n$ be the class of all sv's $t$ such that $P(t \geqq n) = 1$ and $EX^-_t < \infty$. Let $f_n = e. \sup_{t \varepsilon C_n} E(x_t \mid F_n), v_n = \sup_{C_n} Ex_t$. It is known (Theorem 2 of [3]) that if $v < \infty$ and an optimal rule exists, then $s = \text{first} n \geqq 1$ such that $x_n = f_n$ is an optimal rule. For this and various other reasons which will become apparent, e.g., Theorem 1 below, it is desirable to have a constructive method for computing the $f_n$. The technique of backward induction and taking limits, originating with [1] and described in Theorem 2 below, achieves the desired result under certain conditions (see Theorem 2 of [4] for a general statement of these conditions). The central theorem of Section 2 provides completely general methods for computing the $f_n$. Although it seems unlikely that one would ever find it desirable to carry out these computations, there are, nevertheless, several interesting applications of the results to the theory of optimal stopping rules, and it is these applications which concern us throughout the remainder of this paper. In the course of these investigations we find it convenient to introduce the notion of an extended sv, i.e., we drop the requirement that $t$ be finite with probability one while defining $x_\infty$ to be $\lim \sup x_n$. We show that $\bar f_n = f_n$, where, relative to the class of extended sv's, $\bar f_n$ is defined analogously to $f_n$. We utilize extended sv's as a technical device within the framework of the usual theory and give examples which illustrate the inherent value of these sv's. In Section 3 we define the Markov case. We show that by paying proper attention to the Markovian structure of many stopping rule problems we are able to simplify somewhat the general theory and to give relatively simple descriptions of optimal rules when they exist. We also define randomized sv's and show that randomization does not increase $v$. We then apply this result to prove the monotonocity and continuity of $v = v(p)$ in the case where $x_n$ is the proportion of heads in $n$ independent tosses of a coin having probability $p$ of heads on each toss.

HI denotes the space of all bounded functions g on the unit circle whose Fourier coefficients g(n) are zero for all negative n. It is known that, if {nfk},O is a sequence of nonnegative integers with nk+l > (1 +5)nk for all k, and if Z0-0 IVk 12 < OO, then there is a functiong in HI with A(nk)=vk for all k. Previous proofs of this fact have not indicated how to construct such HI functions. This paper contains a simple, direct construction of such functions. The construction depends on properties of some polynomials similar to those introduced by Shapiro and Rudin. There is also a connection with a type of Riesz product studied by Salem and Zygmund. We shall present the construction in ?1 and discuss its relation to other results in ?2. First we recall some notation. For p < xo, LI denotes the space of all measurable functions on the unit circle whose p'th power is integrable; as usual, functions are identified if they agree almost everywhere. L' denotes the space of all essentially bounded measurable functions on the unit circle; for g in L', 1ig Ioo denotes the essential supremum of Igl. The Fourier coefficients of an LI function g are defined by g(n) = f g(eiO)e-no dO (n = 0, 41, 42** Finally, H' is taken to be the space of all g in L' which have g(n) =0 for all n