Algorithms for Fitting the Constrained Lasso

We compare alternative computing strategies for solving the constrained lasso problem. As its name suggests, the constrained lasso extends the widely used lasso to handle linear constraints, which allow the user to incorporate prior information into the model. In addition to quadratic programming, we employ the alternating direction method of multipliers (ADMM) and also derive an efficient solution path algorithm. Through both simulations and benchmark data examples, we compare the different algorithms and provide practical recommendations in terms of efficiency and accuracy for various sizes of data. We also show that, for an arbitrary penalty matrix, the generalized lasso can be transformed to a constrained lasso, while the converse is not true. Thus, our methods can also be used for estimating a generalized lasso, which has wide-ranging applications. Code for implementing the algorithms is freely available in both the Matlab toolbox SparseReg and the Julia package ConstrainedLasso. Supplementary materials for this article are available online.     

A Strongly Convergent Method for Nonsmooth Convex Minimization in Hilbert Spaces

In this article, we propose a strongly convergent variant on the projected subgradient method for constrained convex minimization problems in Hilbert spaces. The advantage of the proposed method is that it converges strongly when the problem has solutions, without additional assumptions. The method also has the following desirable property: the sequence converges to the solution of the problem which lies closest to the initial iterate.     

求解两块可分离凸极小化问题的惯性交替方向乘子法

The alternating direction method of multipliers(ADMM)is a widely used method for solving many convex minimization models arising in signal and image processing.In this paper,we propose an inertial ADMM for solving a two-block separable convex minimization problem with linear equality constraints.This algorithm is obtained by making use of the inertial Douglas-Rachford splitting algorithm to the corresponding dual of the primal problem.We study the convergence analysis of the proposed algorithm in infinite-dimensional Hilbert spaces.Furthermore,we apply the proposed algorithm on the robust principal component analysis problem and also compare it with other state-of-the-art algorithms.Numerical results demonstrate the advantage of the proposed algorithm.     

Study on the Splitting Methods for Separable Convex Optimization in a Unified Algorithmic Framework

It is well recognized the convenience of converting the linearly constrained convex optimization problems to a monotone variational inequality. Recently, we have proposed a unified algorithmic framework which can guide us to construct the solution methods for solving these monotone variational inequalities. In this work, we revisit two full Jacobian decomposition of the augmented Lagrangian methods for separable convex programming which we have studied a few years ago. In particular, exploiting this framework, we are able to give a very clear and elementary proof of the convergence of these solution methods.     

An Augmented ADMM Algorithm With Application to the Generalized Lasso Problem

In this article, we present a fast and stable algorithm for solving a class of optimization problems that arise in many statistical estimation procedures, such as sparse fused lasso over a graph, convex clustering, and trend filtering, among others. We propose a so-called augmented alternating direction methods of multipliers (ADMM) algorithm to solve this class of problems. Compared to a standard ADMM algorithm, our proposal significantly reduces the computational cost at each iteration while maintaining roughly the same overall convergence speed. We also consider a new varying penalty scheme for the ADMM algorithm, which could further accelerate the convergence, especially when solving a sequence of problems with tuning parameters of different scales. Extensive numerical experiments on the sparse fused lasso problem show that the proposed algorithm is more efficient than the standard ADMM and two other existing state-of-the-art specialized algorithms. Finally, we discuss a possible extension and some interesting connections to two well-known algorithms. Supplementary materials for the article are available online.     

Application of the alternating direction method of multipliers to separable convex programming problems

This paper presents a decomposition algorithm for solving convex programming problems with separable structure. The algorithm is obtained through application of the alternating direction method of multipliers to the dual of the convex programming problem to be solved. In particular, the algorithm reduces to the ordinary method of multipliers when the problem is regarded as nonseparable. Under the assumption that both primal and dual problems have at least one solution and the solution set of the primal problem is bounded, global convergence of the algorithm is established.     

一类自适应广义交替方向乘子法

广义交替方向乘子法是求解凸优化问题的有效算法.当实际问题中子问题难以求解时,可以采用在子问题中添加邻近项的方法处理,邻近矩阵正定时,算法收敛,然而这也会使迭代步长较小.最新研究表明,邻近矩阵可以有一定的不正定性.本文在基于不定邻近项的广义交替方向乘子法框架下,提出一种自适应的广义交替方向乘子法,动态地选择邻近矩阵,增大迭代步长.在一些较弱的假设下,证明了算法的全局收敛性.我们进行一些初等数值实验,验证了算法的有效性.     

Convergence Analysis of Some Methods for Minimizing a Nonsmooth Convex Function

In this paper, we analyze a class of methods for minimizing a proper lower semicontinuous extended-valued convex function . Instead of the original objective function f, we employ a convex approximation f _{k + 1} at the kth iteration. Some global convergence rate estimates are obtained. We illustrate our approach by proposing (i) a new family of proximal point algorithms which possesses the global convergence rate estimate even it the iteration points are calculated approximately, where are the proximal parameters, and (ii) a variant proximal bundle method. Applications to stochastic programs are discussed.     

A note on the sufficient initial condition ensuring the convergence of directly extended 3-block ADMM for special semidefinite programming

ABSTRACT

In this note, we consider three types of problems, H-weighted nearest correlation matrix problem and two types of important doubly non-negative semidefinite programming, derived from the binary integer quadratic programming and maximum cut problem. The dual of these three types of problems is a 3-block separable convex optimization problem with a coupling linear equation constraint. It is known that, the directly extended 3-block alternating direction method of multipliers (ADMM3d) is more efficient than many of its variants for solving these convex optimization, but its convergence is not guaranteed. By choosing initial points properly, we obtain the convergence of ADMM3d for solving the dual of these three types of problems. Furthermore, we simplify the iterative scheme of ADMM3d and show the equivalence of ADMM3d to the 2-block semi-proximal ADMM for solving the dual's reformulation, under these initial conditions.     

模糊聚类分析的新算法

提出了一种模糊聚类分析的新算法——追踪法 ,解决了以往模糊聚类分析计算量过大以及难于编程实现的问题 .该方法尤其适用于大规模数据的模糊聚类分析 ,对于模糊聚类分析的推广使用有重要意义 .     

A Subgradient Method Based on Gradient Sampling for Solving Convex Optimization Problems

Based on the gradient sampling technique, we present a subgradient algorithm to solve the nondifferentiable convex optimization problem with an extended real-valued objective function. A feature of our algorithm is the approximation of subgradient at a point via random sampling of (relative) gradients at nearby points, and then taking convex combinations of these (relative) gradients. We prove that our algorithm converges to an optimal solution with probability 1. Numerical results demonstrate that our algorithm performs favorably compared with existing subgradient algorithms on applications considered.     

The Extragradient Method for Convex Optimization in the Presence of Computational Errors

In this article, we study convergence of the extragradient method for constrained convex minimization problems in a Hilbert space. Our goal is to obtain an ε-approximate solution of the problem in the presence of computational errors, where ε is a given positive number. Most results known in the literature establish convergence of optimization algorithms, when computational errors are summable. In this article, the convergence of the extragradient method for solving convex minimization problems is established for nonsummable computational errors. We show that the the extragradient method generates a good approximate solution, if the sequence of computational errors is bounded from above by a constant.     

A modified alternating direction method for convex quadratically constrained quadratic semidefinite programs

We propose a modified alternating direction method for solving convex quadratically constrained quadratic semidefinite optimization problems. The method is a first-order method, therefore requires much less computational effort per iteration than the second-order approaches such as the interior point methods or the smoothing Newton methods. In fact, only a single inexact metric projection onto the positive semidefinite cone is required at each iteration. We prove global convergence and provide numerical evidence to show the effectiveness of this method.     

Linearized Alternating Direction Method of Multipliers for Separable Convex Optimization of Real Functions in Complex Domain

The alternating direction method of multipliers (ADMM) for separable convex optimization of real functions in complex variables has been proposed recently[21]. Furthermore, the convergence and $O(1/K)$ convergence rate of ADMM in complex domain have also been derived[22]. In this paper, a fast linearized ADMM in complex domain has been presented as the subproblems do not have closed solutions. First, some useful results in complex domain are developed by using the Wirtinger Calculus technique. Second, the convergence of the linearized ADMM in complex domain based on the VI is established. Third, an extended model of least absolute shrinkage and selectionator operator (LASSO) is solved by using linearized ADMM in complex domain. Finally, some numerical simulations are provided to show that linearized ADMM in complex domain has the rapid speed.     

线性约束两分块非凸优化的ADMM-SQP算法

基于乘子交替方向法(ADMM)和序列二次规划(SQP)方法思想, 致力于研究线 性约束两分块非凸优化的新型高效算法. 首先, 以SQP思想为主线, 在其二次规划(QP)子问题的求解中引入ADMM思想, 将QP分解为两个相互独立的小规模QP求解. 其次, 借助增广拉格朗日函数和Armijo线搜索产生原始变量新迭代点. 最后, 以显式解析式更新对偶变量. 因此, 构建了一个新型ADMM-SQP算法. 在较弱条件下, 分析了算法通常意义下的全局收敛性, 并对算法进行了初步的数值试验.     

The Projected Subgradient Method for Nonsmooth Convex Optimization in the Presence of Computational Errors

We study the convergence of the projected subgradient method for constrained convex optimization in a Hilbert space. Our goal is to obtain an ε-approximate solution of the problem in the presence of computational errors, where ε is a given positive number. The results that we obtain are important in practice because computations always introduce numerical errors.     

Hierarchical Model-Based Clustering for Large Datasets

In recent years, hierarchical model-based clustering has provided promising results in a variety of applications. However, its use with large datasets has been hindered by a time and memory complexity that are at least quadratic in the number of observations. To overcome this difficulty, this article proposes to start the hierarchical agglomeration from an efficient classification of the data in many classes rather than from the usual set of singleton clusters. This initial partition is derived from a subgraph of the minimum spanning tree associated with the data. To this end, we develop graphical tools that assess the presence of clusters in the data and uncover observations difficult to classify. We use this approach to analyze two large, real datasets: a multiband MRI image of the human brain and data on global precipitation climatology. We use the real datasets to discuss ways of integrating the spatial information in the clustering analysis. We focus on two-stage methods, in which a second stage of processing using established methods is applied to the output from the algorithm presented in this article, viewed as a first stage.     

A decomposition heuristic for mixed-integer supply chain problems

Mixed-integer supply chain models typically are very large but are also very sparse and can be decomposed into loosely coupled blocks. In this paper, we use general-purpose techniques to obtain a block decomposition of supply chain instances and apply a tailored penalty alternating direction method, which exploits the structural properties of the decomposed instances. We further describe problem-specific enhancements of the algorithm and present numerical results on real-world instances that illustrate the applicability of the approach.     

Convex Variational Formulation with Smooth Coupling for Multicomponent Signal Decomposition and Recovery

A convex variational formulation is proposed to solve multicomponent signal processing problems in Hilbert spaces. The cost function consists of a separable term, in which each component is modeled through its own potential, and of a coupling term, in which constraints on linear transformations of the components are penalized with smooth functionals. An algorithm with guaranteed weak convergence to a solution to the problem is provided. Various multicomponent signal decomposition and recovery applications are discussed.