In this paper, we present novel randomized algorithms for solving saddle point problems whose dual feasible region is a direct product of many convex sets. Our algorithms can achieve ${\cal O}(1/N)$ rate of convergence by solving only one dual subproblem at each iteration. Our algorithms can also achieve ${\cal O}(1/N^2)$ rate of convergence if a … Read more
This work is devoted to the study of a proximal decomposition algorithm for solving convex symmetric cone optimization with separable structures. The algorithm considered is based on the decomposition method proposed by Chen and Teboulle (1994), and the proximal generalized distance defined by Auslender and Teboulle (2006). Under suitable assumptions, first a class of proximal … Read more
Signomial programs (SPs) are optimization problems specified in terms of signomials, which are weighted sums of exponentials composed with linear functionals of a decision variable. SPs are non convex optimization problems in general, and families of NP-hard problems can be reduced to SPs. In this paper we describe a hierarchy of convex relaxations to obtain … Read more
This paper illustrates the fundamental connection between nonconvex quadratic optimization and copositive optimization—a connection that allows the reformulation of nonconvex quadratic problems as convex ones in a unified way. We intend the paper for readers new to the area, and hence the exposition is largely self-contained. We focus on examples having just a few variables … Read more
We consider the linearly constrained convex minimization model with a separable objective function which is the sum of m functions without coupled variables, and discuss how to design an efficient algorithm based on the fundamental technique of splitting the augmented Lagrangian method (ALM). Our focus is the specific big-data scenario where m is huge. A … Read more
We consider a generic convex optimization problem associated with regularized empirical risk minimization of linear predictors. The problem structure allows us to reformulate it as a convex-concave saddle point problem. We propose a stochastic primal-dual coordinate (SPDC) method, which alternates between maximizing over a randomly chosen dual variable and minimizing over the primal variable. An … Read more
We study the iterate convergence of strong descent algorithms applied to convex functions. We assume that the function satisfies a very simple growth condition around its minimizers, and then show that the trajectory described by the iterates generated by any such method has finite length, which proves that the sequence of iterates converge. Citation Federal … Read more
The primal-dual algorithm recently proposed by Chambolle \& Pock (abbreviated as CPA) for structured convex optimization is very efficient and popular. It was shown by Chambolle \& Pock in \cite{CP11} and also by Shefi \& Teboulle in \cite{ST14} that CPA and variants are closely related to preconditioned versions of the popular alternating direction method of … Read more
We revisit the proofs of convergence for a first order primal-dual algorithm for convex optimization which we have studied a few years ago. In particular, we prove rates of convergence for a more general version, with simpler proofs and more complete results. Article Download View On the ergodic convergence rates of a first-order primal-dual algorithm
This paper considers computation of Fr\’echet and limiting normal cones to a finite union of polyhedra. To this aim, we introduce a new concept of normally admissible stratification which is convenient for calculations of such cones and provide its basic properties. We further derive formulas for the above mentioned cones and compare our approach to … Read more