TY - GEN
T1 - Random projection algorithms for convex set intersection problems
AU - Nedić, Angelia
PY - 2010
Y1 - 2010
N2 - The focus of this paper is on the set intersection problem for closed convex sets admitting projection operation in a closed form. The objective is to investigate algorithms that would converge (in some sense) if and only if the problem has a solution. To do so, we view the set intersection problem as a stochastic optimization problem of minimizing the "average" residual error of the set collection. We consider a stochastic gradient method as a main tool for investigating the properties of the stochastic optimization problem. We show that the stochastic optimization problem has a solution if and only if the stochastic gradient method is convergent almost surely. We then consider a special case of the method, namely the random projection method, and we analyze its convergence. We show that a solution of the intersection problem exists if and only if the random projection method exhibits certain convergence behavior almost surely. In addition, we provide convergence rate results for the expected residual error.
AB - The focus of this paper is on the set intersection problem for closed convex sets admitting projection operation in a closed form. The objective is to investigate algorithms that would converge (in some sense) if and only if the problem has a solution. To do so, we view the set intersection problem as a stochastic optimization problem of minimizing the "average" residual error of the set collection. We consider a stochastic gradient method as a main tool for investigating the properties of the stochastic optimization problem. We show that the stochastic optimization problem has a solution if and only if the stochastic gradient method is convergent almost surely. We then consider a special case of the method, namely the random projection method, and we analyze its convergence. We show that a solution of the intersection problem exists if and only if the random projection method exhibits certain convergence behavior almost surely. In addition, we provide convergence rate results for the expected residual error.
KW - Convex sets
KW - Intersection problem
KW - Random projection
UR - http://www.scopus.com/inward/record.url?scp=79953141950&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79953141950&partnerID=8YFLogxK
U2 - 10.1109/CDC.2010.5717734
DO - 10.1109/CDC.2010.5717734
M3 - Conference contribution
AN - SCOPUS:79953141950
SN - 9781424477456
T3 - Proceedings of the IEEE Conference on Decision and Control
SP - 7655
EP - 7660
BT - 2010 49th IEEE Conference on Decision and Control, CDC 2010
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 49th IEEE Conference on Decision and Control, CDC 2010
Y2 - 15 December 2010 through 17 December 2010
ER -