Restricted Normal Cones and the Method of Alternating Projections: Applications

The method of alternating projections (MAP) is a common method for solving feasibility problems. While employed traditionally to subspaces or to convex sets, little was known about the behavior of the MAP in the nonconvex case until 2009, when Lewis, Luke, and Malick derived local linear convergence results provided that a condition involving normal cones holds and at least one of the sets is superregular (a property less restrictive than convexity). However, their results failed to capture very simple classical convex instances such as two lines in a three-dimensional space. In this paper, we extend and develop the Lewis-Luke-Malick framework so that not only any two linear subspaces but also any two closed convex sets whose relative interiors meet are covered. We also allow for sets that are more structured such as unions of convex sets. The key tool required is the restricted normal cone, which is a generalization of the classical Mordukhovich normal cone. Numerous examples are provided to illustrate the theory.     

SMOOTHING NEWTON ALGORITHM FOR THE CIRCULAR CONE PROGRAMMING WITH A NONMONOTONE LINE SEARCH

In this paper, we present a nonmonotone smoothing Newton algorithm for solving the circular cone programming(CCP) problem in which a linear function is minimized or maximized over the intersection of an affine space with the circular cone. Based on the relationship between the circular cone and the second-order cone(SOC), we reformulate the CCP problem as the second-order cone problem(SOCP). By extending the nonmonotone line search for unconstrained optimization to the CCP, a nonmonotone smoothing Newton method is proposed for solving the CCP. Under suitable assumptions, the proposed algorithm is shown to be globally and locally quadratically convergent. Some preliminary numerical results indicate the effectiveness of the proposed algorithm for solving the CCP.     

Optimality Conditions for Extended Ky Fan Inequality with Cone and Affine Constraints and Their Applications

The purpose of this paper is to establish necessary and sufficient conditions for a point to be solution of an extended Ky Fan inequality. Using a separation theorem for convex sets, involving the quasi-interior of a convex set, we obtain optimality conditions for solutions of the generalized problem with cone and affine constraints. Then the main result is applied to vector optimization problems with cone and affine constraints and to duality theory.     

A nonmonotone smoothing Newton method for circular cone programming

The circular cone programming (CCP) problem is to minimize or maximize a linear function over the intersection of an affine space with the Cartesian product of circular cones. In this paper, we study nondegeneracy and strict complementarity for the CCP, and present a nonmonotone smoothing Newton method for solving the CCP. We reformulate the CCP as a second-order cone programming (SOCP) problem using the algebraic relation between the circular cone and the second-order cone. Then based on a one parametric class of smoothing functions for the SOCP, a smoothing Newton method is developed for the CCP by adopting a new nonmonotone line search scheme. Without restrictions regarding its starting point, our algorithm solves one linear system of equations approximately and performs one line search at each iteration. Under mild assumptions, our algorithm is shown to possess global and local quadratic convergence properties. Some preliminary numerical results illustrate that our nonmonotone smoothing Newton method is promising for solving the CCP.     

Elliptic cone optimization and primal–dual path-following algorithms

In elliptic cone optimization problems, we minimize a linear objective function over the intersection of an affine linear manifold with the Cartesian product of the so-called elliptic cones. We present some general classes of optimization problems that can be cast as elliptic cone programmes such as second-order cone programmes and circular cone programmes. We also describe some real-world applications of this class of optimization problems. We study and analyse the Jordan algebraic structure of the elliptic cones. Then, we present a glimpse of the duality theory associated with elliptic cone optimization. A primal–dual path-following interior-point algorithm is derived for elliptic cone optimization problems. We prove the polynomial convergence of the proposed algorithms by showing that the logarithmic barrier is a strongly self-concordant barrier. The numerical examples show the path-following algorithms are efficient.     

Global convergence of the affine scaling algorithm for primal degenerate strictly convex quadratic programming problems

In this paper we deal with global convergence of the affine scaling algorithm for strictly convex QP problems satisfying a dual nondegeneracy condition. By means of the local Karmarkar potential function which was successfully applied to demonstrate global convergence of the affine scaling algorithm for LP, we show global convergence of the algorithm when the step-size 1/8 is adopted without requiring any primal nondegeneracy condition.This paper was presented at the 14th International Symposium on Mathematical Programming, held August 5–9, 1991, in Amsterdam, The Netherlands.     

An SQP-type algorithm for nonlinear second-order cone programs

We propose an SQP-type algorithm for solving nonlinear second-order cone programming (NSOCP) problems. At every iteration, the algorithm solves a convex SOCP subproblem in which the constraints involve linear approximations of the constraint functions in the original problem and the objective function is a convex quadratic function. Those subproblems can be transformed into linear SOCP problems, for which efficient interior point solvers are available. We establish global convergence and local quadratic convergence of the algorithm under appropriate assumptions. We report numerical results to examine the effectiveness of the algorithm. This work was supported in part by the Scientific Research Grant-in-Aid from Japan Society for the Promotion of Science.     

Stochastic second-order cone programming: Applications models

Second-order cone programs are a class of convex optimization problems. We refer to them as deterministic second-order cone programs (DSCOPs) since data defining them are deterministic. In DSOCPs we minimize a linear objective function over the intersection of an affine set and a product of second-order (Lorentz) cones. Stochastic programs have been studied since 1950s as a tool for handling uncertainty in data defining classes of optimization problems such as linear and quadratic programs. Stochastic second-order cone programs (SSOCPs) with recourse is a class of optimization problems that defined to handle uncertainty in data defining DSOCPs. In this paper we describe four application models leading to SSOCPs.     

Quadratic factorization heuristics for copositive programming

Copositive optimization problems are particular conic programs: optimize linear forms over the copositive cone subject to linear constraints. Every quadratic program with linear constraints can be formulated as a copositive program, even if some of the variables are binary. So this is an NP-hard problem class. While most methods try to approximate the copositive cone from within, we propose a method which approximates this cone from outside. This is achieved by passing to the dual problem, where the feasible set is an affine subspace intersected with the cone of completely positive matrices, and this cone is approximated from within. We consider feasible descent directions in the completely positive cone, and regularized strictly convex subproblems. In essence, we replace the intractable completely positive cone with a nonnegative cone, at the cost of a series of nonconvex quadratic subproblems. Proper adjustment of the regularization parameter results in short steps for the nonconvex quadratic programs. This suggests to approximate their solution by standard linearization techniques. Preliminary numerical results on three different classes of test problems are quite promising.     

A parallel projection method for solving generalized linear least-squares problems

Summary A parallel projection algorithm is proposed to solve the generalized linear least-squares problem: find a vector to minimize the 2-norm distance from its image under an affine mapping to a closed convex cone. In each iteration of the algorithm the problem is decomposed into several independent small problems of finding projections onto subspaces, which are simple and can be tackled parallelly. The algorithm can be viewed as a dual version of the algorithm proposed by Han and Lou [8]. For the special problem under consideration, stronger convergence results are established. The algorithm is also related to the block iterative methods of Elfving [6], Dennis and Steihaug [5], and the primal-dual method of Springarn [14].This material is based on work supported in part by the National Science foundation under Grant DMS-8602416 and by the Center for Supercomputing Research and Development, University of Illinois at Urbana-Champaign     

On the convergence of asynchronous parallel algorithm for large-scale linearly constrained minimization problem

As a synchronization parallel framework, the parallel variable transformation (PVT) algorithm is effective to solve unconstrained optimization problems. In this paper, based on the idea that a constrained optimization problem is equivalent to a differentiable unconstrained optimization problem by introducing the Fischer Function, we propose an asynchronous PVT algorithm for solving large-scale linearly constrained convex minimization problems. This new algorithm can terminate when some processor satisfies terminal condition without waiting for other processors. Meanwhile, it can enhances practical efficiency for large-scale optimization problem. Global convergence of the new algorithm is established under suitable assumptions. And in particular, the linear rate of convergence does not depend on the number of processors.     

On the convergence of the coordinate descent method for convex differentiable minimization

The coordinate descent method enjoys a long history in convex differentiable minimization. Surprisingly, very little is known about the convergence of the iterates generated by this method. Convergence typically requires restrictive assumptions such as that the cost function has bounded level sets and is in some sense strictly convex. In a recent work, Luo and Tseng showed that the iterates are convergent for the symmetric monotone linear complementarity problem, for which the cost function is convex quadratic, but not necessarily strictly convex, and does not necessarily have bounded level sets. In this paper, we extend these results to problems for which the cost function is the composition of an affine mapping with a strictly convex function which is twice differentiable in its effective domain. In addition, we show that the convergence is at least linear. As a consequence of this result, we obtain, for the first time, that the dual iterates generated by a number of existing methods for matrix balancing and entropy optimization are linearly convergent.This work was partially supported by the U.S. Army Research Office, Contract No. DAAL03-86-K-0171, by the National Science Foundation, Grant No. ECS-8519058, and by the Science and Engineering Research Board of McMaster University.     

复合凸优化的快速邻近点算法

在大数据时代,随着数据采集手段的不断提升,大规模复合凸优化问题大量的出现在包括统计数据分析,机器与统计学习以及信号与图像处理等应用中.本文针对大规模复合凸优化问题介绍了一类快速邻近点算法.在易计算的近似准则和较弱的平稳性条件下,本文给出了该算法的全局收敛与局部渐近超线性收敛结果.同时,我们设计了基于对偶原理的半光滑牛顿法来高效稳定求解邻近点算法所涉及的重要子问题.最后,本文还讨论了如何通过深入挖掘并利用复合凸优化问题中由非光滑正则函数所诱导的非光滑二阶信息来极大减少半光滑牛顿算法中求解牛顿线性系统所需的工作量,从而进一步加速邻近点算法.     

Global optimization of a quadratic function subject to a bounded mixed integer consraint set

In this paper we consider the optimization of a quadratic function subject to a linearly bounded mixed integer constraint set. We develop two types of piecewise affine convex underestimating functions for the objective function. These are used in a branch and bound algorithm for solving the original problem. We show finite convergence to a near optimal solution for this algorithm. We illustrate the algorithm with a small numerical example. Finally we discuss some modifications of the algorithm and address the question of extending the problem to include quadratic constraints.Supported by grants from the Danish Natural Science Research Council and the Danish Research Academy.     

复合凸优化问题的Gauss-Newton法的收敛性

本文研究解决复合凸优化问题:min F(x):=h(f(x)) （P）x∈X的Gauss-Newton法的收敛性.这里f是从Banach空间X到Banach空间Y的具有Frechet导数的非线性映照,h是定义在Y上的凸泛函. 复合凸优化问题近年来一直受到广泛的关注,目前它已成为非线性光滑理论中的一个主流方向.它在非线性包含,最大最小问题,罚函数技巧 [1-5]等许多重要的问题和技巧中得到了广泛的应用.同时它也提供了一个新的统一框架,使优化问题数值解的理论分析得到别开生面的发展.并且它也是研究有限区域内一阶或二阶最优性条件的一个便利工具[3,5,6,7].     

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.     

Power iteration and inverse power iteration for eigenvalue complementarity problem

In this paper, an inverse complementarity power iteration method (ICPIM) for solving eigenvalue complementarity problems (EiCPs) is proposed. Previously, the complementarity power iteration method (CPIM) for solving EiCPs was designed based on the projection onto the convex cone K. In the new algorithm, a strongly monotone linear complementarity problem over the convex cone K is needed to be solved at each iteration. It is shown that, for the symmetric EiCPs, the CPIM can be interpreted as the well‐known conditional gradient method, which requires only linear optimization steps over a well‐suited domain. Moreover, the ICPIM is closely related to the successive quadratic programming (SQP) via renormalization of iterates. The global convergence of these two algorithms is established by defining two nonnegative merit functions with zero global minimum on the solution set of the symmetric EiCP. Finally, some numerical simulations are included to evaluate the efficiency of the proposed algorithms.     

Local and global convergence of a general inertial proximal splitting scheme for minimizing composite functions

This paper is concerned with convex composite minimization problems in a Hilbert space. In these problems, the objective is the sum of two closed, proper, and convex functions where one is smooth and the other admits a computationally inexpensive proximal operator. We analyze a family of generalized inertial proximal splitting algorithms (GIPSA) for solving such problems. We establish weak convergence of the generated sequence when the minimum is attained. Our analysis unifies and extends several previous results. We then focus on \(\ell _1\)-regularized optimization, which is the ubiquitous special case where the nonsmooth term is the \(\ell _1\)-norm. For certain parameter choices, GIPSA is amenable to a local analysis for this problem. For these choices we show that GIPSA achieves finite “active manifold identification”, i.e. convergence in a finite number of iterations to the optimal support and sign, after which GIPSA reduces to minimizing a local smooth function. We prove local linear convergence under either restricted strong convexity or a strict complementarity condition. We determine the rate in terms of the inertia, stepsize, and local curvature. Our local analysis is applicable to certain recent variants of the Fast Iterative Shrinkage–Thresholding Algorithm (FISTA), for which we establish active manifold identification and local linear convergence. Based on our analysis we propose a momentum restart scheme in these FISTA variants to obtain the optimal local linear convergence rate while maintaining desirable global properties.     

Decomposable norm minimization with proximal-gradient homotopy algorithm

We study the convergence rate of the proximal-gradient homotopy algorithm applied to norm-regularized linear least squares problems, for a general class of norms. The homotopy algorithm reduces the regularization parameter in a series of steps, and uses a proximal-gradient algorithm to solve the problem at each step. Proximal-gradient algorithm has a linear rate of convergence given that the objective function is strongly convex, and the gradient of the smooth component of the objective function is Lipschitz continuous. In many applications, the objective function in this type of problem is not strongly convex, especially when the problem is high-dimensional and regularizers are chosen that induce sparsity or low-dimensionality. We show that if the linear sampling matrix satisfies certain assumptions and the regularizing norm is decomposable, proximal-gradient homotopy algorithm converges with a linear rate even though the objective function is not strongly convex. Our result generalizes results on the linear convergence of homotopy algorithm for \(\ell _1\)-regularized least squares problems. Numerical experiments are presented that support the theoretical convergence rate analysis.     

Superlinearly convergent affine scaling interior trust-region method for linear constrained LC<Superscript>1</Superscript> minimization

We extend the classical affine scaling interior trust region algorithm for the linear constrained smooth minimization problem to the nonsmooth case where the gradient of objective function is only locally Lipschitzian. We propose and analyze a new affine scaling trust-region method in association with nonmonotonic interior backtracking line search technique for solving the linear constrained LC1 optimization where the second-order derivative of the objective function is explicitly required to be locally Lipschitzian. The general trust region subproblem in the proposed algorithm is defined by minimizing an augmented affine scaling quadratic model which requires both first and second order information of the objective function subject only to an affine scaling ellipsoidal constraint in a null subspace of the augmented equality constraints. The global convergence and fast local convergence rate of the proposed algorithm are established under some reasonable conditions where twice smoothness of the objective function is not required. Applications of the algorithm to some nonsmooth optimization problems are discussed.