Reference no: EM132135622

Problem -

Consider a closed convex set X ⊂ R^d, a function H : X x Ξ ι→ R^d, and a deterministic nonnegative sequence {αⁿ} such that _n=0∑^∞αⁿ = ∞ and _n=0∑^∞(αⁿ)² = ∞. Consider an inner product (·, ·) on R^d, and the associated norm ||x|| := √(x, x). Let Π_X(x) := argmin {||x - y|| : y ∈ X} denote the corresponding projection of x onto X. Consider a discrete time stochastic process {xⁿ, ξⁿ} such that for all n = 1, 2, ...,

xⁿ⁺¹ = Π_X(xⁿ + αⁿH(xⁿ, ξⁿ⁺¹))

Let Fⁿ denote the σ-algebra generated by x₀, ξ¹, . . . , ξⁿ. Suppose that for each x ∈ X there is a probability distribution, μ_x on Ξ such that for any function g : X x Ξ ι→ R,

E[g(xⁿ, ξⁿ⁺¹)|Fⁿ] = ∫_Ξ g(xⁿ, ξ)μ_x^n(dξ)

that is, given the history of the stochastic process up to time n, the distribution of ξⁿ⁺¹ depends only on xⁿ. Let

h(x) := ∫_Ξ H (x, ξ) μ_x(dξ)

that is, h(xⁿ) = E[H(xⁿ, ξⁿ⁺¹)|Fⁿ]. Suppose that there is a constant K such that

∫_Ξ||H(x, ξ)||²μ_x(dξ) < K (1 + ||x||²)

for all x ∈ X. Suppose that there is a x* ∈ X such that, for all ε > 0,

inf{(h(x), x* - x ) : ε ≤ ||x* - x|| ≤ 1/ε} > 0

You can use the supermartingale convergence theorem established in class without having to prove it. You can also use the following result without having to prove it: For any x, y ∈ R^d, it holds that

||Π_X(x) - Π_X(y)|| ≤ ||x - y||

1. Prove or disprove: w.p.1, xⁿ → x* as n → ∞.

2. Prove or disprove: w.p.1, h(xⁿ) → 0 as n → ∞.

Note - Do your own work. Show all calculations.