nonconvex optimization

Global Complexity Bound of a Proximal ADMM for Linearly-Constrained Nonseperable Nonconvex Composite Programming

  • Weiwei Kong
  • Renato D.C. Monteiro
    • Categories Nonlinear Optimization, Nonsmooth Optimization Tags , , , , ,

    This paper proposes and analyzes a dampened proximal alternating direction method of multipliers (DP.ADMM) for solving linearly-constrained nonconvex optimization problems where the smooth part of the objective function is nonseparable. Each iteration of DP.ADMM consists of: (ii) a sequence of partial proximal augmented Lagrangian (AL) updates, (ii) an under-relaxed Lagrange multiplier update, and (iii) a … Read more

    Nonlinear matrix recovery using optimization on the Grassmann manifold

  • Coralia Cartis
  • Armin Eftekhari
  • Florentin Goyens
    • Categories Applications - Science and Engineering, Constrained Nonlinear Optimization Tags , , ,

    We investigate the problem of recovering a partially observed high-rank matrix whose columns obey a nonlinear structure such as a union of subspaces, an algebraic variety or grouped in clusters. The recovery problem is formulated as the rank minimization of a nonlinear feature map applied to the original matrix, which is then further approximated by … Read more

    An abstract convergence framework with application to inertial inexact forward-backward methods

  • Silvia Bonettini
  • Peter Ochs
  • Marco Prato
  • Simone Rebegoldi
    • Categories Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

    In this paper we introduce a novel abstract descent scheme suited for the minimization of proper and lower semicontinuous functions. The proposed abstract scheme generalizes a set of properties that are crucial for the convergence of several first-order methods designed for nonsmooth nonconvex optimization problems. Such properties guarantee the convergence of the full sequence of … Read more

    On obtaining the convex hull of quadratic inequalities via aggregations

  • Santanu S. Dey
  • Felipe Serrano
  • Gonzalo Muñoz
    • Categories Global Optimization Theory Tags , ,

    A classical approach for obtaining valid inequalities for a set involves weighted aggregations of the inequalities that describe such set. When the set is described by linear inequalities, thanks to the Farkas lemma, we know that every valid inequality can be obtained using aggregations. When the inequalities describing the set are two quadratics, Yildiran showed … Read more

    Local Minimizers of the Crouzeix Ratio: A Nonsmooth Optimization Case Study

  • Michael L. Overton
    • Categories Global Optimization, Nonsmooth Optimization Tags , , ,

    Given a square matrix $A$ and a polynomial $p$, the Crouzeix ratio is the norm of the polynomial on the field of values of $A$ divided by the 2-norm of the matrix $p(A)$. Crouzeix’s conjecture states that the globally minimal value of the Crouzeix ratio is 0.5, regardless of the matrix order and polynomial degree, … Read more

    New Bregman proximal type algorithms for solving DC optimization problems

  • Shota Takahashi
  • Mituhiro Fukuda
  • Mirai Tanaka
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , , , ,

    Difference of Convex (DC) optimization problems have objective functions that are differences between two convex functions. Representative ways of solving these problems are the proximal DC algorithms, which require that the convex part of the objective function have L-smoothness. In this article, we propose the Bregman Proximal DC Algorithm (BPDCA) for solving large-scale DC optimization … Read more

    Factorization of completely positive matrices using iterative projected gradient steps

  • Radu Ioan Bot
  • Dang-Khoa Nguyen
    • Categories Nonsmooth Optimization Tags , , , ,

    We aim to factorize a completely positive matrix by using an optimization approach which consists in the minimization of a nonconvex smooth function over a convex and compact set. To solve this problem we propose a projected gradient algorithm with parameters that take into account the effects of relaxation and inertia. Both projection and gradient … Read more

    A Proximal Quasi-Newton Trust-Region Method for Nonsmooth Regularized Optimization

  • Aleksandr Y. Aravkin
  • Robert Baraldi
  • Dominique Orban
    • Categories Nonlinear Optimization, Nonsmooth Optimization Tags , , , , , , ,

    We develop a trust-region method for minimizing the sum of a smooth term f and a nonsmooth term h, both of which can be nonconvex. Each iteration of our method minimizes apossibly nonconvex model of f+h in a trust region. The model coincides with f+h in value and subdifferential at the center. We establish global … Read more

    Further developments of methods for traversing regions of non-convexity in optimization problems

  • Michael Bartholomew-Biggs
  • Salah Beddiaf
  • Bruce Christianson
    • Categories Unconstrained Optimization Tags , ,

    This paper continues to address one of its author’s obsession with the well- known problem of dealing with non-convexity during the minimization of a nonlinear function f(x) by Newton-like methods. It builds on some proposals made by the present authors in “A Comparison of methods for traversing regions of non-convexity in optimization problems”. (Numerical Algorithms … Read more

    A Computational Study of Perspective Cuts

  • Ksenia Bestuzheva
  • Ambros Gleixner
  • Stefan Vigerske
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Optimization Software and Modeling Systems Tags , , ,

    The benefits of cutting planes based on the perspective function are well known for many specific classes of mixed-integer nonlinear programs with on/off structures. However, we are not aware of any empirical studies that evaluate their applicability and computational impact over large, heterogeneous test sets in general-purpose solvers. This paper provides a detailed computational study … Read more