Two-Phase Image Segmentation by Nonconvex Nonsmooth Models with Convergent Alternating Minimization Algorithms

Two-phase image segmentation is a fundamental task to partition an image into foreground and background. In this paper, two types of nonconvex and nonsmooth regularization models are proposed for basic two-phase segmentation. They extend the convex regularization on the characteristic function on the image domain to the nonconvex case, which are able to better obtain piecewise constant regions with neat boundaries. By analyzing the proposed non-Lipschitz model, we combine the proximal alternating minimization framework with support shrinkage and linearization strategies to design our algorithm. This leads to two alternating strongly convex subproblems which can be easily solved. Similarly, we present an algorithm without support shrinkage operation for the nonconvex Lipschitz case. Using the Kurdyka-Łojasiewicz property of the objective function, we prove that the limit point of the generated sequence is a critical point of the original nonconvex nonsmooth problem. Numerical experiments and comparisons illustrate the effectiveness of our method in two-phase image segmentation.     

A partially isochronous splitting algorithm for three-block separable convex minimization problems

During the last decade, the state-of-the-art alternating direction method of multipliers (ADMM) has successfully been used to solve many two-block separable convex minimization problems arising from several applied areas such as signal/image processing and statistical and machine learning. It however remains an interesting problem of how to implement ADMM to three-block separable convex minimization problems as required by the situation where many objective functions in the above-mentioned areas are actually more conveniently decomposed to the sum of three convex functions, due also to the observation that the straightforward extension of ADMM from the two-block case to the three-block case is apparently not convergent. In this paper, we shall introduce a new algorithm that is called a partially isochronous splitting algorithm (PISA) in order to implement ADMM for the three-block separable model. The main idea of our algorithm is to incorporate only one proximal term into the last subproblem of the extended ADMM so that the resulting algorithm maximally inherits the promising properties of ADMM. A remarkable superiority over the extended ADMM is that we can simultaneously solve two of the subproblems, thereby taking advantages of the separable structure and parallel architectures. Theoretically, we will establish the global convergence of our algorithm under standard conditions, and also the O(1/t) rate of convergence in both ergodic and nonergodic senses, where t is the iteration counter. The computational competitiveness of our algorithm is shown by numerical experiments on an application to the well-tested robust principal component analysis model.     

Computational Experience with a New Class of Convex Underestimators: Box-constrained NLP Problems

In Akrotirianakis and Floudas (2004) we presented the theoretical foundations of a new class of convex underestimators for C ² nonconvex functions. In this paper, we present computational experience with those underestimators incorporated within a Branch-and-Bound algorithm for box-conatrained problems. The algorithm can be used to solve global optimization problems that involve C ² functions. We discuss several ways of incorporating the convex underestimators within a Branch-and-Bound framework. The resulting Branch-and-Bound algorithm is then used to solve a number of difficult box-constrained global optimization problems. A hybrid algorithm is also introduced, which incorporates a stochastic algorithm, the Random-Linkage method, for the solution of the nonconvex underestimating subproblems, arising within a Branch-and-Bound framework. The resulting algorithm also solves efficiently the same set of test problems.     

A distributed Douglas-Rachford splitting method for multi-block convex minimization problems

A customized Douglas-Rachford splitting method (DRSM) was recently proposed to solve two-block separable convex optimization problems with linear constraints and simple abstract constraints. The algorithm has advantage over the well-known alternating direction method of multipliers (ADMM), the dual application of DRSM to the two-block convex minimization problem, in the sense that the subproblems can have larger opportunity of possessing closed-form solutions since they are unconstrained. In this paper, we further study along this way by considering the primal application of DRSM for the general case m≥3, i.e., we consider the multi-block separable convex minimization problem with linear constraints where the objective function is separable into m individual convex functions without coupled variables. The resulting method fully exploits the separable structure and enjoys decoupled subproblems which can be solved simultaneously. Both the exact and inexact versions of the new method are presented in a unified framework. Under mild conditions, we manage to prove the global convergence of the algorithm. Preliminary numerical experiments for extracting the background from corrupted surveillance video verify the encouraging efficiency of the new algorithm.     

A customized Douglas–Rachford splitting algorithm for separable convex minimization with linear constraints

We consider applying the Douglas–Rachford splitting method (DRSM) to the convex minimization problem with linear constraints and a separable objective function. The dual application of DRSM has been well studied in the literature, resulting in the well known alternating direction method of multipliers (ADMM). In this paper, we show that the primal application of DRSM in combination with an appropriate decomposition can yield an efficient structure-exploiting algorithm for the model under consideration, whose subproblems could be easier than those of ADMM. Both the exact and inexact versions of this customized DRSM are studied; and their numerical efficiency is demonstrated by some preliminary numerical results.     

A parametric solution algorithm for a class of rank-two nonconvex programs

The aim of this paper is to propose a solution algorithm for a particular class of rank-two nonconvex programs having a polyhedral feasible region. The algorithm lies within the class of the so called “optimal level solutions” parametric methods. The subproblems obtained by means of this parametrical approach are quadratic convex ones, but not necessarily neither strictly convex nor linear. For this very reason, in order to solve in an unifying framework all of the considered rank-two nonconvex programs a new approach needs to be proposed. The efficiency of the algorithm is improved by means of the use of underestimation functions. The results of a computational test are provided and discussed.     

Column enumeration based decomposition techniques for a class of non-convex MINLP problems

We propose a decomposition algorithm for a special class of nonconvex mixed integer nonlinear programming problems which have an assignment constraint. If the assignment decisions are decoupled from the remaining constraints of the optimization problem, we propose to use a column enumeration approach. The master problem is a partitioning problem whose objective function coefficients are computed via subproblems. These problems can be linear, mixed integer linear, (non-)convex nonlinear, or mixed integer nonlinear. However, the important property of the subproblems is that we can compute their exact global optimum quickly. The proposed technique will be illustrated solving a cutting problem with optimum nonlinear programming subproblems.     

Convergence analysis of a proximal point algorithm for minimizing differences of functions

Several optimization schemes have been known for convex optimization problems. However, numerical algorithms for solving nonconvex optimization problems are still underdeveloped. A significant progress to go beyond convexity was made by considering the class of functions representable as differences of convex functions. In this paper, we introduce a generalized proximal point algorithm to minimize the difference of a nonconvex function and a convex function. We also study convergence results of this algorithm under the main assumption that the objective function satisfies the Kurdyka–?ojasiewicz property.     

An inexact alternating direction method of multipliers with relative error criteria

In this paper, we study an inexact version of the alternating direction method of multipliers (ADMM) for solving two-block separable linearly constrained convex optimization problems. Specifically, the two subproblems in the classic ADMM are allowed to be solved inexactly by certain relative error criteria, in the sense that only two parameters are needed to control the inexactness. Related convergence analysis are established under the assumption that the solution set to the KKT system of the problem is not empty. Numerical results on solving a class of sparse signal recovery problems are also provided to demonstrate the efficiency of the proposed algorithm.     

A minimization method for the sum of a convex function and a continuously differentiable function

This paper presents a method for finding the minimum for a class of nonconvex and nondifferentiable functions consisting of the sum of a convex function and a continuously differentiable function. The algorithm is a descent method which generates successive search directions by solving successive convex subproblems. The algorithm is shown to converge to a critical point.The authors wish to express their appreciation to the referees for their careful review and helpful comments.     

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.     

Successive convex approximations to cardinality-constrained convex programs: a piecewise-linear DC approach

In this paper we consider cardinality-constrained convex programs that minimize a convex function subject to a cardinality constraint and other linear constraints. This class of problems has found many applications, including portfolio selection, subset selection and compressed sensing. We propose a successive convex approximation method for this class of problems in which the cardinality function is first approximated by a piecewise linear DC function (difference of two convex functions) and a sequence of convex subproblems is then constructed by successively linearizing the concave terms of the DC function. Under some mild assumptions, we establish that any accumulation point of the sequence generated by the method is a KKT point of the DC approximation problem. We show that the basic algorithm can be refined by adding strengthening cuts in the subproblems. Finally, we report some preliminary computational results on cardinality-constrained portfolio selection problems.     

A note on the convergence of ADMM for linearly constrained convex optimization problems

This note serves two purposes. Firstly, we construct a counterexample to show that the statement on the convergence of the alternating direction method of multipliers (ADMM) for solving linearly constrained convex optimization problems in a highly influential paper by Boyd et al. (Found Trends Mach Learn 3(1):1–122, 2011) can be false if no prior condition on the existence of solutions to all the subproblems involved is assumed to hold. Secondly, we present fairly mild conditions to guarantee the existence of solutions to all the subproblems of the ADMM and provide a rigorous convergence analysis on the ADMM with a computationally more attractive large step-length that can even exceed the practically much preferred golden ratio of \((1+\sqrt{5})/2\).     

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

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.     

An algorithm for nonconvex programming problems

Branch and bound approaches for nonconvex programming problems had been given in [1] and [4]. Crucial for both are the use of rectangular partitions, convex envelopes and separable nonconvex portions of the objective function and constraints. We want to propose a similar algorithm which solves a sequence of problems in each of which the objective function is convex or even linear. The main difference between this approach and previous approaches is the use of general compact partitions instead of rectangular ones and a different refining rule such that the algorithm does not rely on the concept of convex envelopes and handles non-separable functions.First we describe a general algorithm and prove a convergence theorem under suitable regularity assumptions. Then we give as example an algorithm for concave minimization problems.     

An efficient inexact symmetric Gauss–Seidel based majorized ADMM for high-dimensional convex composite conic programming

In this paper, we propose an inexact multi-block ADMM-type first-order method for solving a class of high-dimensional convex composite conic optimization problems to moderate accuracy. The design of this method combines an inexact 2-block majorized semi-proximal ADMM and the recent advances in the inexact symmetric Gauss–Seidel (sGS) technique for solving a multi-block convex composite quadratic programming whose objective contains a nonsmooth term involving only the first block-variable. One distinctive feature of our proposed method (the sGS-imsPADMM) is that it only needs one cycle of an inexact sGS method, instead of an unknown number of cycles, to solve each of the subproblems involved. With some simple and implementable error tolerance criteria, the cost for solving the subproblems can be greatly reduced, and many steps in the forward sweep of each sGS cycle can often be skipped, which further contributes to the efficiency of the proposed method. Global convergence as well as the iteration complexity in the non-ergodic sense is established. Preliminary numerical experiments on some high-dimensional linear and convex quadratic SDP problems with a large number of linear equality and inequality constraints are also provided. The results show that for the vast majority of the tested problems, the sGS-imsPADMM is 2–3 times faster than the directly extended multi-block ADMM with the aggressive step-length of 1.618, which is currently the benchmark among first-order methods for solving multi-block linear and quadratic SDP problems though its convergence is not guaranteed.     

边界约束非凸二次规划问题的分枝定界方法

本文是研究带有边界约束非凸二次规划问题,我们把球约束二次规划问题和线性约束凸二次规划问题作为子问题,分明引用了它们的一个求整体最优解的有效算法,我们提出几种定界的紧、松驰策略,给出了求解原问题整体最优解的分枝定界算法,并证明了该算法的收敛性,不同的定界组合就可以产生不同的分枝定界算法,最后我们简单讨论了一般有界凸域上非凸二次规划问题求整体最优解的分枝与定界思想。     

Quadratic Majorization for Nonconvex Loss with Applications to the Boosting Algorithm

Classical robust statistical methods dealing with noisy data are often based on modifications of convex loss functions. In recent years, nonconvex loss-based robust methods have been increasingly popular. A nonconvex loss can provide robust estimation for data contaminated with outliers. The significant challenge is that a nonconvex loss can be numerically difficult to optimize. This article proposes quadratic majorization algorithm for nonconvex (QManc) loss. The QManc can decompose a nonconvex loss into a sequence of simpler optimization problems. Subsequently, the QManc is applied to a powerful machine learning algorithm: quadratic majorization boosting algorithm (QMBA). We develop QMBA for robust classification (binary and multi-category) and regression. In high-dimensional cancer genetics data and simulations, the QMBA is comparable with convex loss-based boosting algorithms for clean data, and outperforms the latter for data contaminated with outliers. The QMBA is also superior to boosting when directly implemented to optimize nonconvex loss functions. Supplementary material for this article is available online.     

Using conical partition to globally maximizing the nonlinear sum of ratios

This article presents a global optimization algorithm for globally maximizing the sum of concave–convex ratios problem with a convex feasible region. The algorithm uses a branch and bound scheme where a concave envelope of the objective function is constructed to obtain an upper bound of the optimal value by using conical partition. As a result, the upper-bound subproblems during the algorithm search are all ordinary convex programs with less variables and constraints and do not grow in size from iterations to iterations in the computation procedure, and furthermore a new bounding tightening strategy is proposed such that the upper-bound convex relaxation subproblems are closer to the original nonconvex problem to enhance solution procedure. At last, some numerical examples are given to vindicate our conclusions.     

A practical relative error criterion for augmented Lagrangians

This paper develops a new error criterion for the approximate minimization of augmented Lagrangian subproblems. This criterion is practical since it is readily testable given only a gradient (or subgradient) of the augmented Lagrangian. It is also “relative” in the sense of relative error criteria for proximal point algorithms: in particular, it uses a single relative tolerance parameter, rather than a summable parameter sequence. Our analysis first describes an abstract version of the criterion within Rockafellar’s general parametric convex duality framework, and proves a global convergence result for the resulting algorithm. Specializing this algorithm to a standard formulation of convex programming produces a version of the classical augmented Lagrangian method with a novel inexact solution condition for the subproblems. Finally, we present computational results drawn from the CUTE test set—including many nonconvex problems—indicating that the approach works well in practice.