Elementary Algorithms for Solving Convex Optimization Problems

Negar Soheili

Date and Time: 

Friday, November 15, 2013 - 2:30pm

Event Location: 

Mohler Lab #451

A convex feasibility problem is concerned with finding a point in the intersection of convex sets. These problems are fundamental in optimization because any convex optimization problem can be cast in this form. Elementary algorithms are iterative algorithms for solving convex feasibility problems that involve simple operations such as matrix-vector multiplications, vector updates and separation oracles. The simplicity and low computational cost of these algorithms are desirable features for large-scale problems. A major drawback of traditional elementary algorithms is their slow convergence rate. This talk presents new versions of elementary algorithms that are enhanced via smoothing and dilation techniques. These enhancements yield algorithms that retain the attractive simplicity of elementary algorithms while achieving substantially improved convergence rates.

Bio Sketch: 

Negar Soheili is a PhD candidate in Operations Research at the Tepper School of Business, Carnegie Mellon University. She has a Bachelor of Science in Applied Mathematics from University of Tehran. Her research lies at the intersection of machine learning and operations research. In particular, she is currently developing efficient algorithms for large scale convex optimization problems arising in
data analysis.