joint work with Jourdain Lamperski, Michael Todd
Consider the ellipsoid method applied to compute a point in P where P is represented as the feasible solutions of a system of linear inequalities. When P is empty, there exists a certificate of infeasibility (via a theorem of the alternative), yet the standard ellipsoid method does not automatically furnish such a certificate. In this talk we present a modified version of the ellipsoid method that computes a point in P when P is nonempty, and computes a certificate of infeasibility when P is empty, and whose complexity depends on max(m,n) and on a natural condition number of the problem.
The aim of structured optimization is to assemble a solution, using a given set of atoms, to fit a model to data. Polarity, which generalizes the notion of orthogonality from linear sets to general convex sets, plays a special role in a simple and geometric form of convex duality. The atoms and their implicit "duals" share a special relationship, and their participation in the solution assembly depends on a notion of alignment. This geometric perspective leads to practical algorithms for large-scale problems.
joint work with Qihang Lin, Selva Nadarajah, Tianbao Yang
Stochastic optimization problems with expectation constraints (SOEC) arise in several applications. Only recently has an efficient stochastic subgradient method been developed for solving a SOEC defined by an objective and a single inequality constraint, where both are defined by expectations of stochastic convex functions. We develop a level-set method to compute near-optimal solutions to a generalization of this SOEC containing multiple inequality constraints, each involving an expectation of a stochastic convex function. We establish convergence guarantees for this method.