Convex and Nonsmooth Optimization

A Block Coordinate Descent Method for Regularized Multi-Convex Optimization with Applications to Nonnegative Tensor Factorization and Completion

  • Yangyang Xu
  • Wotao Yin
    • Categories Constrained Nonlinear Optimization, Data-Mining, Nonsmooth Optimization Tags , , , , , , ,

    This paper considers regularized block multi-convex optimization, where the feasible set and objective function are generally non-convex but convex in each block of variables. We review some of its interesting examples and propose a generalized block coordinate descent method. (Using proximal updates, we further allow non-convexity over some blocks.) Under certain conditions, we show that … Read more

    CHARACTERIZATIONS OF FULL STABILITY IN CONSTRAINED OPTIMIZATION

  • Boris S. Mordukhovich
  • Tyrrell Rockafellar
  • Ebrahim Sarabi
    • Categories Nonsmooth Optimization, Robust Optimization Tags , , , , , ,

    This paper is mainly devoted to the study of the so-called full Lipschitzian stability of local solutions to finite-dimensional parameterized problems of constrained optimization, which has been well recognized as a very important property from both viewpoints of optimization theory and its applications. Based on second- order generalized differential tools of variational analysis, we obtain … Read more

    A Newton-Fixed Point Homotopy Algorithm for Nonlinear Complementarity Problems with Generalized Monotonicity

  • Yun-Chol Jong
    • Categories Complementarity and Variational Inequalities, Generalized Convexity/Monoticity Tags , , ,

    In this paper has been considered probability-one global convergence of NFPH (Newton-Fixed Point Homotopy) algorithm for system of nonlinear equations and has been proposed a probability-one homotopy algorithm to solve a regularized smoothing equation for NCP with generalized monotonicity. Our results provide a theoretical basis to develop a new computational method for nonlinear equation systems … Read more

    Convex computation of the region of attraction of polynomial control systems

  • Didier Henrion
  • Milan Korda
    • Categories Control Applications, Convex Optimization, Semi-definite Programming Tags , , , , , ,

    We address the long-standing problem of computing the region of attraction (ROA) of a target set (typically a neighborhood of an equilibrium point) of a controlled nonlinear system with polynomial dynamics and semialgebraic state and input constraints. We show that the ROA can be computed by solving a convex linear programming (LP) problem over the … Read more

    Bounds on Eigenvalues of Matrices Arising from Interior-Point Methods

  • Chen Greif
  • Erin Moulding
  • Dominique Orban
    • Categories Convex Optimization, Quadratic Programming Tags , , , , , , ,

    Interior-point methods feature prominently among numerical methods for inequality-constrained optimization problems, and involve the need to solve a sequence of linear systems that typically become increasingly ill-conditioned with the iterations. To solve these systems, whose original form has a nonsymmetric 3×3 block structure, it is common practice to perform block Gaussian elimination and either solve … Read more

    An adaptive accelerated first-order method for convex optimization

  • Renato D.C. Monteiro
  • Camilo Ortiz
  • Benar Fux Svaiter
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , ,

    This paper presents a new accelerated variant of Nesterov’s method for solving composite convex optimization problems in which certain acceleration parameters are adaptively (and aggressively) chosen so as to substantially improve its practical performance compared to existing accelerated variants while at the same time preserve the optimal iteration-complexity shared by these methods. Computational results are … Read more

    Some criteria for error bounds in set optimization

  • Xuan Duc Ha Truong
    • Categories Multi-Criteria Optimization, Nonsmooth Optimization Tags , , , , , , , , ,

    We obtain sufficient and/or necessary conditions for global/local error bounds for the distances to some sets appeared in set optimization studied with both the set approach and vector approach (sublevel sets, constraint sets, sets of {\it all } Pareto efficient/ Henig proper efficient/super efficient solutions, sets of solutions {\it corresponding to one} Pareto efficient/Henig proper … Read more

    Complexity Analysis of Interior Point Algorithms for Non-Lipschitz and Nonconvex Minimization

  • Wei Bian
  • Xiaojun Chen
  • Yinyu Ye
    • Categories Applications - Science and Engineering, Constrained Nonlinear Optimization, Nonsmooth Optimization

    We propose a first order interior point algorithm for a class of non-Lipschitz and nonconvex minimization problems with box constraints, which arise from applications in variable selection and regularized optimization. The objective functions of these problems are continuously differentiable typically at interior points of the feasible set. Our algorithm is easy to implement and the … Read more

    A QCQP Approach to Triangulation

  • Sameer Agarwal
  • Chris Aholt
  • Rekha R. Thomas
    • Categories Convex Optimization, Quadratic Programming Tags , , ,

    Triangulation of a three-dimensional point from $n\ge 2$ two-dimensional images can be formulated as a quadratically constrained quadratic program. We propose an algorithm to extract candidate solutions to this problem from its semidefinite programming relaxations. We then describe a sufficient condition and a polynomial time test for certifying when such a solution is optimal. This … Read more

    A first-order block-decomposition method for solving two-easy-block structured semidefinite programs

  • Renato D.C. Monteiro
  • Camilo Ortiz
  • Benar Fux Svaiter
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Optimization Software Benchmark Tags , , , , , ,

    In this paper, we consider a first-order block-decomposition method for minimizing the sum of a convex differentiable function with Lipschitz continuous gradient, and two other proper closed convex (possibly, nonsmooth) functions with easily computable resolvents. The method presented contains two important ingredients from a computational point of view, namely: an adaptive choice of stepsize for … Read more