An Adaptive Partial Linearization Method for Optimization Problems on Product Sets

We consider a general class of composite optimization problems where the goal function is the sum of a smooth function and a non-necessary smooth convex separable function associated with some space partition, whereas the feasible set is a Cartesian product concordant to this partition. We suggest an adaptive version of the partial linearization method, which makes selective component-wise steps satisfying some descent condition and utilizes a sequence of control parameters. This technique is destined to reduce the computational expenses per iteration and maintain the basic convergence properties. We also establish its convergence rates and describe some examples of applications. Preliminary results of computations illustrate usefulness of the new method.     

Ergodic,primal convergence in dual subgradient schemes for convex programming,II: the case of inconsistent primal problems

Consider the utilization of a Lagrangian dual method which is convergent for consistent convex optimization problems. When it is used to solve an infeasible optimization problem, its inconsistency will then manifest itself through the divergence of the sequence of dual iterates. Will then the sequence of primal subproblem solutions still yield relevant information regarding the primal program? We answer this question in the affirmative for a convex program and an associated subgradient algorithm for its Lagrange dual. We show that the primal–dual pair of programs corresponding to an associated homogeneous dual function is in turn associated with a saddle-point problem, in which—in the inconsistent case—the primal part amounts to finding a solution in the primal space such that the Euclidean norm of the infeasibility in the relaxed constraints is minimized; the dual part amounts to identifying a feasible steepest ascent direction for the Lagrangian dual function. We present convergence results for a conditional \(\varepsilon \)-subgradient optimization algorithm applied to the Lagrangian dual problem, and the construction of an ergodic sequence of primal subproblem solutions; this composite algorithm yields convergence of the primal–dual sequence to the set of saddle-points of the associated homogeneous Lagrangian function; for linear programs, convergence to the subset in which the primal objective is at minimum is also achieved.     

A very simple SQCQP method for a class of smooth convex constrained minimization problems with nice convergence results

We introduce a new and very simple algorithm for a class of smooth convex constrained minimization problems which is an iterative scheme related to sequential quadratically constrained quadratic programming methods, called sequential simple quadratic method (SSQM). The computational simplicity of SSQM, which uses first-order information, makes it suitable for large scale problems. Theoretical results under standard assumptions are given proving that the whole sequence built by the algorithm converges to a solution and becomes feasible after a finite number of iterations. When in addition the objective function is strongly convex then asymptotic linear rate of convergence is established.     

On proximal gradient method for the convex problems regularized with the group reproducing kernel norm

We consider a class of nonsmooth convex optimization problems where the objective function is the composition of a strongly convex differentiable function with a linear mapping, regularized by the group reproducing kernel norm. This class of problems arise naturally from applications in group Lasso, which is a popular technique for variable selection. An effective approach to solve such problems is by the proximal gradient method. In this paper we derive and study theoretically the efficient algorithms for the class of the convex problems, analyze the convergence of the algorithm and its subalgorithm.     

A unified approach to error bounds for structured convex optimization problems

Error bounds, which refer to inequalities that bound the distance of vectors in a test set to a given set by a residual function, have proven to be extremely useful in analyzing the convergence rates of a host of iterative methods for solving optimization problems. In this paper, we present a new framework for establishing error bounds for a class of structured convex optimization problems, in which the objective function is the sum of a smooth convex function and a general closed proper convex function. Such a class encapsulates not only fairly general constrained minimization problems but also various regularized loss minimization formulations in machine learning, signal processing, and statistics. Using our framework, we show that a number of existing error bound results can be recovered in a unified and transparent manner. To further demonstrate the power of our framework, we apply it to a class of nuclear-norm regularized loss minimization problems and establish a new error bound for this class under a strict complementarity-type regularity condition. We then complement this result by constructing an example to show that the said error bound could fail to hold without the regularity condition. We believe that our approach will find further applications in the study of error bounds for structured convex optimization problems.     

On Weak and Strong Convergence of the Projected Gradient Method for Convex Optimization in Real Hilbert Spaces

This work focuses on convergence analysis of the projected gradient method for solving constrained convex minimization problems in Hilbert spaces. We show that the sequence of points generated by the method employing the Armijo line search converges weakly to a solution of the considered convex optimization problem. Weak convergence is established by assuming convexity and Gateaux differentiability of the objective function, whose Gateaux derivative is supposed to be uniformly continuous on bounded sets. Furthermore, we propose some modifications in the classical projected gradient method in order to obtain strong convergence. The new variant has the following desirable properties: the sequence of generated points is entirely contained in a ball with diameter equal to the distance between the initial point and the solution set, and the whole sequence converges strongly to the solution of the problem that lies closest to the initial iterate. Convergence analysis of both methods is presented without Lipschitz continuity assumption.     

Penalty schemes with inertial effects for monotone inclusion problems

We introduce a penalty term-based splitting algorithm with inertial effects designed for solving monotone inclusion problems involving the sum of maximally monotone operators and the convex normal cone to the (nonempty) set of zeros of a monotone and Lipschitz continuous operator. We show weak ergodic convergence of the generated sequence of iterates to a solution of the monotone inclusion problem, provided a condition expressed via the Fitzpatrick function of the operator describing the underlying set of the normal cone is verified. Under strong monotonicity assumptions we can even show strong nonergodic convergence of the iterates. This approach constitutes the starting point for investigating from a similar perspective monotone inclusion problems involving linear compositions of parallel-sum operators and, further, for the minimization of a complexly structured convex objective function subject to the set of minima of another convex and differentiable function.     

A block coordinate gradient descent method for regularized convex separable optimization and covariance selection

We consider a class of unconstrained nonsmooth convex optimization problems, in which the objective function is the sum of a convex smooth function on an open subset of matrices and a separable convex function on a set of matrices. This problem includes the covariance selection problem that can be expressed as an ℓ ₁-penalized maximum likelihood estimation problem. In this paper, we propose a block coordinate gradient descent method (abbreviated as BCGD) for solving this class of nonsmooth separable problems with the coordinate block chosen by a Gauss-Seidel rule. The method is simple, highly parallelizable, and suited for large-scale problems. We establish global convergence and, under a local Lipschizian error bound assumption, linear rate of convergence for this method. For the covariance selection problem, the method can terminate in O(n³/e){O(n^3/\epsilon)} iterations with an e{\epsilon}-optimal solution. We compare the performance of the BCGD method with the first-order methods proposed by Lu (SIAM J Optim 19:1807–1827, 2009; SIAM J Matrix Anal Appl 31:2000–2016, 2010) for solving the covariance selection problem on randomly generated instances. Our numerical experience suggests that the BCGD method can be efficient for large-scale covariance selection problems with constraints.     

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.     

On certain optimization methods with finite-step inner algorithms for convex finite-dimensional problems with inequality constraints

Numerical methods are proposed for solving finite-dimensional convex problems with inequality constraints satisfying the Slater condition. A method based on solving the dual to the original regularized problem is proposed and justified for problems having a strictly uniformly convex sum of the objective function and the constraint functions. Conditions for the convergence of this method are derived, and convergence rate estimates are obtained for convergence with respect to the functional, convergence with respect to the argument to the set of optimizers, and convergence to the g-normal solution. For more general convex finite-dimensional minimization problems with inequality constraints, two methods with finite-step inner algorithms are proposed. The methods are based on the projected gradient and conditional gradient algorithms. The paper is focused on finite-dimensional problems obtained by approximating infinite-dimensional problems, in particular, optimal control problems for systems with lumped or distributed parameters.     

Gradient-type penalty method with inertial effects for solving constrained convex optimization problems with smooth data

We consider the problem of minimizing a smooth convex objective function subject to the set of minima of another differentiable convex function. In order to solve this problem, we propose an algorithm which combines the gradient method with a penalization technique. Moreover, we insert in our algorithm an inertial term, which is able to take advantage of the history of the iterates. We show weak convergence of the generated sequence of iterates to an optimal solution of the optimization problem, provided a condition expressed via the Fenchel conjugate of the constraint function is fulfilled. We also prove convergence for the objective function values to the optimal objective value. The convergence analysis carried out in this paper relies on the celebrated Opial Lemma and generalized Fejér monotonicity techniques. We illustrate the functionality of the method via a numerical experiment addressing image classification via support vector machines.     

A coordinate gradient descent method for nonsmooth separable minimization

We consider the problem of minimizing the sum of a smooth function and a separable convex function. This problem includes as special cases bound-constrained optimization and smooth optimization with ?₁-regularization. We propose a (block) coordinate gradient descent method for solving this class of nonsmooth separable problems. We establish global convergence and, under a local Lipschitzian error bound assumption, linear convergence for this method. The local Lipschitzian error bound holds under assumptions analogous to those for constrained smooth optimization, e.g., the convex function is polyhedral and the smooth function is (nonconvex) quadratic or is the composition of a strongly convex function with a linear mapping. We report numerical experience with solving the ?₁-regularization of unconstrained optimization problems from Moré et al. in ACM Trans. Math. Softw. 7, 17–41, 1981 and from the CUTEr set (Gould and Orban in ACM Trans. Math. Softw. 29, 373–394, 2003). Comparison with L-BFGS-B and MINOS, applied to a reformulation of the ?₁-regularized problem as a bound-constrained optimization problem, is also reported.     

A parallel descent algorithm for convex programming

In this paper, we propose a parallel decomposition algorithm for solving a class of convex optimization problems, which is broad enough to contain ordinary convex programming problems with a strongly convex objective function. The algorithm is a variant of the trust region method applied to the Fenchel dual of the given problem. We prove global convergence of the algorithm and report some computational experience with the proposed algorithm on the Connection Machine Model CM-5.     

On a proximal point method for convex optimization in banach spaces

We analyze the behavior of a parallel proximal point method for solving convex optimization problems in reflexive Banach spaces. Similar algorithms were known to converge under the implicit assumption that the norm of the space is Hilbertian. We extend the area of applicability of the proximal point method to solving convex optimization problems in Banach spaces on which totally convex functions can be found. This includes the class of all smooth uniformly convex Banach spaces. Also, our convergence results leave more flexibility for the choice of the penalty function involved in the algorithm and, in this way, allow simplification of the computational procedure.     

Exterior Minimum-Penalty Path-Following Methods in Semidefinite Programming

A semidefinite programming problem is a mathematical program in which the objective function is linear in the unknowns and the constraint set is defined by a linear matrix inequality. This problem is nonlinear, nondifferentiable but convex. It covers several standard problems, such as linear and quadratic programming, and has many applications in engineering. In this paper, we introduce the notion of minimal-penalty path, which is defined as the collection of minimizers for a family of convex optimization problems, and propose two methods for solving the problem by following the minimal-penalty path from the exterior of the feasible set. Our first method, which is also a constraint-aggregation method, achieves the solution by solving a sequence of linear programs, but exhibits a zigzagging behavior around the minimal-penalty path. Our second method eliminates the above drawback by following efficiently the minimum-penalty path through the centering and ascending steps. The global convergence of the methods is proved and their performance is illustrated by means of an example.     

Iterative algorithm for minimizing a convex function at the intersection of a spherical surface and a convex compact set

A numerical algorithm for minimizing a convex function on the set-theoretic intersection of a spherical surface and a convex compact set is proposed. The idea behind the algorithm is to reduce the original minimization problem to a sequence of convex programming problems. Necessary extremum conditions are examined, and the convergence of the algorithm is analyzed.     

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.     

Fine tuning Nesterov’s steepest descent algorithm for differentiable convex programming

We modify the first order algorithm for convex programming described by Nesterov in his book (in Introductory lectures on convex optimization. A basic course. Kluwer, Boston, 2004). In his algorithms, Nesterov makes explicit use of a Lipschitz constant L for the function gradient, which is either assumed known (Nesterov in Introductory lectures on convex optimization. A basic course. Kluwer, Boston, 2004), or is estimated by an adaptive procedure (Nesterov 2007). We eliminate the use of L at the cost of an extra imprecise line search, and obtain an algorithm which keeps the optimal complexity properties and also inherit the global convergence properties of the steepest descent method for general continuously differentiable optimization. Besides this, we develop an adaptive procedure for estimating a strong convexity constant for the function. Numerical tests for a limited set of toy problems show an improvement in performance when compared with the original Nesterov’s algorithms.     

求解带线性约束的凸优化的一类自适应不定线性化增广拉格朗日方法

增广拉格朗日方法是求解带线性约束的凸优化问题的有效算法.线性化增广拉格朗日方法通过线性化增广拉格朗日函数的二次罚项并加上一个临近正则项,使得子问题容易求解,其中正则项系数的恰当选取对算法的收敛性和收敛速度至关重要.较大的系数可保证算法收敛性,但容易导致小步长.较小的系数允许迭代步长增大,但容易导致算法不收敛.本文考虑求解带线性等式或不等式约束的凸优化问题.我们利用自适应技术设计了一类不定线性化增广拉格朗日方法,即利用当前迭代点的信息自适应选取合适的正则项系数,在保证收敛性的前提下尽量使得子问题步长选择范围更大,从而提高算法收敛速度.我们从理论上证明了算法的全局收敛性,并利用数值实验说明了算法的有效性.     

Convex Modeling of Interactions With Strong Heredity

We consider the task of fitting a regression model involving interactions among a potentially large set of covariates, in which we wish to enforce strong heredity. We propose FAMILY, a very general framework for this task. Our proposal is a generalization of several existing methods, such as VANISH, hierNet, the all-pairs lasso, and the lasso using only main effects. It can be formulated as the solution to a convex optimization problem, which we solve using an efficient alternating directions method of multipliers (ADMM) algorithm. This algorithm has guaranteed convergence to the global optimum, can be easily specialized to any convex penalty function of interest, and allows for a straightforward extension to the setting of generalized linear models. We derive an unbiased estimator of the degrees of freedom of FAMILY, and explore its performance in a simulation study and on an HIV sequence dataset. Supplementary materials for this article are available online.