Random projection methods for stochastic convex minimization

Tursun, Umit Deniz

Permalink

https://hdl.handle.net/2142/45381 Copy

Description

Title

Random projection methods for stochastic convex minimization

Author(s)

Tursun, Umit Deniz

Issue Date

2013-08-22T16:38:27Z

Director of Research (if dissertation) or Advisor (if thesis)

Nedich, Angelia

Doctoral Committee Chair(s)

Nedich, Angelia

Committee Member(s)

• Beck, Carolyn L.
• Stipanović, Dušan M.
• Voulgaris, Petros G.

Department of Study

Industrial&Enterprise Sys Eng

Discipline

Industrial Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• stochastic convex minimization
• random projection
• stochastic convex feasibility problem

Abstract

The first focus of this thesis is to solve a stochastic convex minimization problem over an arbitrary family of nonempty, closed and convex sets. The problem has random features. Gradient or subgradient of objective function carries stochastic errors. Number of constraint sets can be extensive or infinitely many. Constraint sets might not be known apriori yet revealed through random realizations or randomly chosen from a collection of constraint sets throughout the horizon as in online learning concept. The traditional projection algorithms for solving minimization problems require projecting over complete collection of constraints at once or over a subset of them based on a predefined selection rule. But in practical applications either all of the constraints might not be known apriori or even if they are known projecting on the intersection set might be computationally prohibitive. We propose a two step gradient/subgradient iterative method with random projections. As the first step, a random gradient /subgradient projection is performed before observing the random constraint set realization. After taking random gradient /subgradient projection step we reach an intermittent point, which we obtained without considering the feasibility violation. Once the set realization is revealed or chosen within collection of constraint sets, the feasibility violation of intermittent point is corrected. We showed that projecting onto a random subcollection of them using our algorithm with diminishing stepsize is sufficient to converge to the solution set almost surely. Also the convergence of the algorithm for constant and nondiminishing nonsummable stepsizes are proved within an error bound. As the first set of experiments we tested the performance of the algorithm over a dynamic control system. We study three versions of the problem with correlated unknown-but-bounded additive noise, uncorrelated unknown-but-bounded additive noise and uncorrelated bounded output and peak input additive noise under fully known system description cases. It is essentially a robust least squares estimation problem where we recover state parameters from corrupted input and output data. We reformulated the linear least squares estimation problem as a stochastic convex minimization problem and then used the two step random projection algorithm to solve it. Although the problem has infinite number of constraints due to each realization of error term within bounded set, the algorithm goes through a finite subset of them and converges to the solution set. We also prove the existence of solution and provide equivalent minimization formulations or upper bound for these three types of robust least squares problems. We used standard subgradient algorithm to gauge the performance of our method. The implementation results are comparable to the ones found in literature. Our next focus is to solve a stochastic convex feasibility problem. We explored an algorithmic approach to solve both consistent and inconsistent convex feasibility problems for closed convex uncertain sets. We concentrated our attention on uncertain nature of sets and finding a feasible point using a random subcollection of them. The sets we consider might carry uncertainty due to inaccurate or imprecise spatial, spectral, stochastic information and confidence levels. For this objective we consider a stochastic optimization problem of minimizing an expected weighted proximity function over a collection of closed, convex sets. We show that the proposed algorithm converges to a point in the solution set when solution set is nonempty. In case of inconsistent feasibility problem i.e. the intersection of closed convex constraint sets being empty the algorithm minimizes the proximity function. The projection onto a subcollection of sets approach can be viewed as somewhere between random implementation of alternating projection method and parallel projection method. But our method is not deterministic. It uses random projections onto sets that carry additive bounded noise. Each realization within the bounded disturbances has equal chance of occurence. The conventional approach of set theoretic estimation problems provide solution that confirm with constraint sets known a priori or observed. But it fails to take into account that sets built on a priori or observed data may carry disturbances or have erroneously predicted statistical information, which may result in inconsistent sets. The attributes of original signal such as amplitude bound, region of support, band-limitedness that are used to built sets in estimation problems may not be accurate. Additionally sets that are built using moments, spectral properties, distribution and bounds information are based on predicted stochastic estimations. The overly conservative confidence bounds or statistical assumptions may cause inconsistencies. Also noise pertubations in measurements or random variations in the impulse response of a system can cause inconsistencies. Our algorithm projects onto a subcollection of sets some of which carry a random realization of noise on it. The implementation results show that the algorithm converges to the solution asymptotically even if the algorithm projects onto a random subcollection of sets at each iteration. All in all this thesis work presents iterative methods to solve stochastic convex minimization problems and stochastic convex set intersection problems. The almost sure convergence of algorithms are proven. And the performance of them are shown on numerical experiments.

Graduation Semester

2013-08

Permalink

http://hdl.handle.net/2142/45381

Copyright and License Information

Copyright 2013 Umit Tursun

Owning Collections