convex optimization

FAST FIRST-ORDER METHODS FOR COMPOSITE CONVEX OPTIMIZATION WITH BACKTRACKING

Categories Nonsmooth Optimization Tags , , , , ,

We propose new versions of accelerated first order methods for convex composite optimization, where the prox parameter is allowed to increase from one iteration to the next. In particular we show that a full backtracking strategy can be used within the FISTA \cite{Beck-Teboulle-2009} and FALM algorithms \cite{Goldfarb-Ma-Scheinberg-2010} while preserving their worst-case iteration complexities of $O(\sqrt{L(f)/\epsilon})$. … Read more

Level methods uniformly optimal for composite and structured nonsmooth convex optimization

Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Stochastic Programming Tags , , , , ,

The main goal of this paper is to develop uniformly optimal first-order methods for large-scale convex programming (CP). By uniform optimality we mean that the first-order methods themselves do not require the input of any problem parameters, but can still achieve the best possible iteration complexity bounds. To this end, we provide a substantial generalization … Read more

Level methods uniformly optimal for composite and structured nonsmooth convex optimization

Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Stochastic Programming Tags , , , , ,

The main goal of this paper is to develop uniformly optimal first-order methods for large-scale convex programming (CP). By uniform optimality we mean that the first-order methods themselves do not require the input of any problem parameters, but can still achieve the best possible iteration complexity bounds. To this end, we provide a substantial generalization … Read more

A Double Smoothing Technique for Constrained Convex Optimization Problems and Applications to Optimal Control

Categories Convex Optimization, Infinite Dimensional Optimization, Nonsmooth Optimization Tags , , , ,

In this paper, we propose an efficient approach for solving a class of convex optimization problems in Hilbert spaces. Our feasible region is a (possibly infinite-dimensional) simple convex set, i.e. we assume that projections on this set are computationally easy to compute. The problem we consider is the minimization of a convex function over this … Read more

Alternating Direction Method with Gaussian Back Substitution for Separable Convex Programming

Categories Convex Optimization Tags , , ,

We consider the linearly constrained separable convex programming whose objective function is separable into m individual convex functions without crossed variables. The alternating direction method (ADM) has been well studied in the literature for the special case m=2. But the convergence of extending ADM to the general case m>=3 is still open. In this paper, … Read more

Inexact Dynamic Bundle Methods

Categories Convex Optimization, Nonsmooth Optimization Tags , , ,

We give a proximal bundle method for minimizing a convex function $f$ over $\mathbb{R}_+^n$. It requires evaluating $f$ and its subgradients with a possibly unknown accuracy $\epsilon\ge0$, and maintains a set of free variables $I$ to simplify its prox subproblems. The method asymptotically finds points that are $\epsilon$-optimal. In Lagrangian relaxation of convex programs, it … Read more

A Monotone+Skew Splitting Model for Composite Monotone Inclusions in Duality

Categories Convex Optimization, Nonsmooth Optimization Tags , , , , , , , ,

The principle underlying this paper is the basic observation that the problem of simultaneously solving a large class of composite monotone inclusions and their duals can be reduced to that of finding a zero of the sum of a maximally monotone operator and a linear skew-adjoint operator. An algorithmic framework is developed for solving this … Read more

A Parallel Inertial Proximal Optimization Method

Categories Complementarity and Variational Inequalities, Convex Optimization, Parallel Algorithms Tags , , , , ,

The Douglas-Rachford algorithm is a popular iterative method for finding a zero of a sum of two maximal monotone operators defined on a Hilbert space. In this paper, we propose an extension of this algorithm including inertia parameters and develop parallel versions to deal with the case of a sum of an arbitrary number of … Read more

A contraction method with implementable proximal regularization for linearly constrained convex programming

Categories Convex Optimization Tags , , , ,

The proximal point algorithm (PPA) is classical, and it is implicit in the sense that the resulting proximal subproblems may be as difficult as the original problem. In this paper, we show that with appropriate choices of proximal parameters, the application of PPA to the linearly constrained convex programming can result in easy proximal subproblems. … Read more

Evaluation complexity of adaptive cubic regularization methods for convex unconstrained optimization

Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags ,

The adaptive cubic regularization algorithms described in Cartis, Gould & Toint (2009, 2010) for unconstrained (nonconvex) optimization are shown to have improved worst-case efficiency in terms of the function- and gradient-evaluation count when applied to convex and strongly convex objectives. In particular, our complexity upper bounds match in order (as a function of the accuracy … Read more