Convex and Nonsmooth Optimization

Fast Alternating Linearization Methods for Minimizing the Sum of Two Convex Functions

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

We present in this paper first-order alternating linearization algorithms based on an alternating direction augmented Lagrangian approach for minimizing the sum of two convex functions. Our basic methods require at most $O(1/\epsilon)$ iterations to obtain an $\epsilon$-optimal solution, while our accelerated (i.e., fast) versions of them require at most $O(1/\sqrt{\epsilon})$ iterations, with little change in … Read more

A Sequential Quadratic Programming Algorithm for Nonconvex, Nonsmooth Constrained Optimization

Categories Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , , , ,

We consider optimization problems with objective and constraint functions that may be nonconvex and nonsmooth. Problems of this type arise in important applications, many having solutions at points of nondifferentiability of the problem functions. We present a line search algorithm for situations when the objective and constraint functions are locally Lipschitz and continuously differentiable on … Read more

Hedge Algorithm and Subgradient Methods

Categories Convex Optimization Tags , , , ,

We show that the Hedge Algorithm, a method that is widely used in Machine Learning, can be interpreted as a particular subgradient algorithm for minimizing a well-chosen convex function, namely as a Mirror Descent Scheme. Using this reformulation, we establish three modificitations and extensions of the Hedge Algorithm that are better or at least as … Read more

Alternating Direction Algorithms for $\ell_1hBcProblems in Compressive Sensing

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

In this paper, we propose and study the use of alternating direction algorithms for several $\ell_1$-norm minimization problems arising from sparse solution recovery in compressive sensing, including the basis pursuit problem, the basis-pursuit denoising problems of both unconstrained and constrained forms, as well as others. We present and investigate two classes of algorithms derived from … Read more

Extension of the semidefinite characterization of sum of squares functional systems to algebraic structures

Categories Convex Optimization, Semi-definite Programming Tags , , , , ,

We extend Nesterov’s semidefinite programming (SDP) characterization of the cone of functions that can be expressed as sums of squares (SOS) of functions in finite dimensional linear functional spaces. Our extension is to algebraic systems that are endowed with a binary operation which map two elements of a finite dimensional vector space to another vector … Read more

A Proximal Algorithm with Quasi Distance. Application to Habit’s Formation

Categories Nonsmooth Optimization, Unconstrained Optimization

We consider a proximal algorithm with quasi distance applied to nonconvex and nonsmooth functions involving analytic properties for an unconstrained minimization problem. We show the behavioral importance of this proximal point model for habit’s formation in Decision and Making Sciences. ArticleDownload View PDF

Identifying Active Manifolds in Regularization Problems

Categories Generalized Convexity/Monoticity, Nonsmooth Optimization Tags , , , ,

In this work we consider the problem $\min_x \{ f(x) + P(x) \}$, where $f$ is $\mathcal{C}^2$ and $P$ is nonsmooth, but contains an underlying smooth substructure. Specifically, we assume the function $P$ is prox-regular partly smooth with respect to a active manifold $\M$. Recent work by Tseng and Yun \cite{tseng-yun-2009}, showed that such a … Read more

Alternating directions based contraction method for generally separable linearly constrained convex programming problems

Categories Convex Optimization Tags , , , ,

The classical alternating direction method (ADM) has been well studied in the context of linearly constrained convex programming problems and variational inequalities where both the involved operators and constraints are separable into two parts. In particular, recentness has witnessed a number of novel applications arising in diversified areas (e.g. Image Processing and Statistics), for which … Read more

Alternating direction algorithms for total variation deconvolution in image reconstruction

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

Image restoration and reconstruction from blurry and noisy observation is known to be ill-posed. To stabilize the recovery, total variation (TV) regularization was introduced by Rudin, Osher and Fatemi in \cite{LIR92}, which has demonstrated superiority in preserving image edges. However, the nondifferentiability of TV makes the underlying optimization problems difficult to solve. In this paper, … Read more

Local superlinear convergence of polynomial-time interior-point methods for hyperbolic cone optimization problems

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

In this paper, we establish the local superlinear convergence property of some polynomial-time interior-point methods for an important family of conic optimization problems. The main structural property used in our analysis is the logarithmic homogeneity of self-concordant barrier function, which must have {\em negative curvature}. We propose a new path-following predictor-corrector scheme, which work only … Read more