Search

This paper proposes a path-based approach for the minimization of a continuously differentiable function over sparse symmetric sets, which is a hard problem that exhibits a restrictiveness-hierarchy of necessary optimality conditions. To achieve the more restrictive conditions in the hierarchy, state-of-the-art algorithms require a support optimization oracle that must exactly solve the problem in smaller dimensions. The path-based approach developed in this study produces a path-based optimality condition, which is placed well in the restrictiveness-hierarchy, and a method to achieve it that does not require a support optimization oracle and, moreover, is projection-free. In the development process, new results are derived for the regularized linear minimization problem over sparse symmetric sets, which give additional means to identify optimal solutions for convex and concave objective functions. We complement our results with numerical examples. [ABSTRACT FROM AUTHOR]

In this paper, we propose an interior-point method for linearly constrained|and possibly nonconvex|optimization problems. The method|which we call the Hessian barrier algorithm (HBA)|combines a forward Euler discretization of Hessian-Riemannian gradient flows with an Armijo backtracking step-size policy. In this way, HBA can be seen as an alternative to mirror descent, and contains as special cases the affine scaling algorithm, regularized Newton processes, and several other iterative solution methods. Our main result is that, modulo a nondegeneracy condition, the algorithm converges to the problem's critical set; hence, in the convex case, the algorithm converges globally to the problem's minimum set. In the case of linearly constrained quadratic programs (not necessarily convex), we also show that the method's convergence rate is O(1/k p) for some p ε (0,1] that depends only on the choice of kernel function (i.e., not on the problem's primitives). These theoretical results are validated by numerical experiments in standard nonconvex test functions and large-scale traffic assignment problems. [ABSTRACT FROM AUTHOR]

In this paper, we propose a perturbed proximal primal–dual algorithm (PProx-PDA) for an important class of linearly constrained optimization problems, whose objective is the sum of smooth (possibly nonconvex) and convex (possibly nonsmooth) functions. This family of problems can be used to model many statistical and engineering applications, such as high-dimensional subspace estimation and the distributed machine learning. The proposed method is of the Uzawa type, in which a primal gradient descent step is performed followed by an (approximate) dual gradient ascent step. One distinctive feature of the proposed algorithm is that the primal and dual steps are both perturbed appropriately using past iterates so that a number of asymptotic convergence and rate of convergence results (to first-order stationary solutions) can be obtained. Finally, we conduct extensive numerical experiments to validate the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

The main difficulty for solving semi-infinite programming (SIP) problem is precisely that it has infinitely many constraints. By using a maximum function, the SIP problem can be rewritten as a nonconvex nonsmooth constrained optimization (NNCO) problem. Global convergence in most of constrained optimization algorithms has traditionally been enforced by the use of a penalty function or filter strategy. In this paper, we propose an infeasible bundle method for NNCO problem based on the so-called improvement functions, without a penalty function and filter strategy. The method appears to be more direct and easier to implement, in the sense that it is closer in spirit and structure to the well-developed unconstrained bundle methods. Under a special constraint qualification, the sequence generated by this algorithm converges to the KKT point of the NNCO problem as well as the SIP problems. Preliminary numerical results show that this algorithm is robust and efficient for NNCO problems and SIP problems. [ABSTRACT FROM AUTHOR]

A method is proposed for solving equality constrained nonlinear optimization problems involving twice continuously differentiable functions. The method employs a trust funnel approach consisting of two phases: a first phase to locate an ε-feasible point and a second phase to seek optimality while maintaining at least ε-feasibility. Two-phase approaches of this kind based on a cubic regularization methodology have recently been proposed along with supporting worst-case iteration complexity analyses. Notably, in these approaches, the objective function is completely ignored in the first phase when ε-feasibility is sought. The main contribution of the method proposed in this paper is that the same worst-case iteration complexity is achieved, but with a first phase that also accounts for improvements in the objective function. As such, the method attempts to put significantly less burden on the second phase for seeking optimality. [ABSTRACT FROM AUTHOR]

The aim of this paper is to present the convergence analysis of a very general class of gradient projection methods for smooth, constrained, possibly nonconvex, optimization. The key features of these methods are the Armijo linesearch along a suitable descent direction and the non Euclidean metric employed to compute the gradient projection. We develop a very general framework from the point of view of block-coordinate descent methods, which are useful when the constraints are separable. In our numerical experiments we consider a large scale image restoration problem to illustrate the impact of the metric choice on the practical performances of the corresponding algorithm. [ABSTRACT FROM AUTHOR]

This paper considers a class of constrained stochastic composite optimization problems whose objective function is given by the summation of a differentiable (possibly nonconvex) component, together with a certain non-differentiable (but convex) component. In order to solve these problems, we propose a randomized stochastic projected gradient (RSPG) algorithm, in which proper mini-batch of samples are taken at each iteration depending on the total budget of stochastic samples allowed. The RSPG algorithm also employs a general distance function to allow taking advantage of the geometry of the feasible region. Complexity of this algorithm is established in a unified setting, which shows nearly optimal complexity of the algorithm for convex stochastic programming. A post-optimization phase is also proposed to significantly reduce the variance of the solutions returned by the algorithm. In addition, based on the RSPG algorithm, a stochastic gradient free algorithm, which only uses the stochastic zeroth-order information, has been also discussed. Some preliminary numerical results are also provided. [ABSTRACT FROM AUTHOR]

The alternating direction method of multipliers (ADMM) is widely used to solve large-scale linearly constrained optimization problems, convex or nonconvex, in many engineering fields. However there is a general lack of theoretical understanding of the algorithm when the objective function is nonconvex. In this paper we analyze the convergence of the ADMM for solving certain nonconvex consensus and sharing problems. We show that the classical ADMM converges to the set of stationary solutions, provided that the penalty parameter in the augmented Lagrangian is chosen to be sufficiently large. For the sharing problems, we show that the ADMM is convergent regardless of the number of variable blocks. Our analysis does not impose any assumptions on the iterates generated by the algorithm and is broadly applicable to many ADMM variants involving proximal update rules and various flexible block selection rules. [ABSTRACT FROM AUTHOR]