Global Optimization Theory

An Adaptive Proximal ADMM for Nonconvex Linearly-Constrained Composite Programs

  • Leandro Farias Maia
  • David H. Gutman
  • Renato D.C. Monteiro
  • Gilson Silva
    • Categories Convex and Nonsmooth Optimization, Global Optimization Theory, Nonlinear Optimization Tags , , , ,

    This paper develops an adaptive Proximal Alternating Direction Method of Multipliers (P-ADMM) for solving linearly-constrained, weakly convex, composite optimization problems. This method is adaptive to all problem parameters, including smoothness and weak convexity constants. It is assumed that the smooth component of the objective is weakly convex and possibly nonseparable, while the non-smooth component is … Read more

    Regularized Gradient Clipping Provably Trains Wide and Deep Neural Networks

  • Anirbit Mukherjee
    • Categories Data Science Algorithms, Global Optimization Theory, Nonlinear Optimization

    In this work, we instantiate a regularized form of the gradient clipping algorithm and prove that it can converge to the global minima of deep neural network loss functions provided that the net is of sufficient width. We present empirical evidence that our theoretically founded regularized gradient clipping algorithm is also competitive with the state-of-the-art … Read more

    Strengthening Lasserre’s Hierarchy in Real and Complex Polynomial Optimization

  • Jie Wang
    • Categories Constrained Nonlinear Optimization, Global Optimization Theory, Semi-definite Programming Tags , , , , ,

    We establish a connection between multiplication operators and shift operators. Moreover, we derive positive semidefinite conditions of finite rank moment sequences and use these conditions to strengthen Lasserre’s hierarchy for real and complex polynomial optimization. Integration of the strengthening technique with sparsity is considered. Extensive numerical experiments show that our strengthening technique can significantly improve … Read more

    Sparse Polynomial Optimization with Unbounded Sets

  • Jie Wang
    • Categories Constrained Nonlinear Optimization, Global Optimization Theory, Semi-definite Programming Tags , , , ,

    This paper considers sparse polynomial optimization with unbounded sets. When the problem possesses correlative sparsity, we propose a sparse homogenized Moment-SOS hierarchy with perturbations to solve it. The new hierarchy introduces one extra auxiliary variable for each variable clique according to the correlative sparsity pattern. Under the running intersection property, we prove that this hierarchy … Read more

    Exact Matrix Completion via High-Rank Matrices in Sum-of-Squares Relaxations

  • Sunyoung Kim
  • Godai Azuma
  • Makoto Yamashita
    • Categories Convex Optimization, Global Optimization Theory, Semi-definite Programming Tags , , , ,

    We study exact matrix completion from partially available data with hidden connectivity patterns. Exact matrix completion was shown to be possible recently by Cosse and Demanet in 2021 with Lasserre’s relaxation using the trace of the variable matrix as the objective function with given data structured in a chain format. In this study, we introduce … Read more

    Solving Nonconvex Optimization Problems using Outer Approximations of the Set-Copositive Cone

  • Kurt M. Anstreicher
  • MarkusGabl
    • Categories (Mixed) Integer Nonlinear Programming, Cone Programming, Global Optimization Theory Tags , ,

    We consider the solution of nonconvex quadratic optimization problems using an outer approximation of the set-copositive cone that is iteratively strengthened with conic constraints and cutting planes. Our methodology utilizes an MILP-based oracle for a generalization of the copositive cone that considers additional linear equality constraints. In numerical testing we evaluate our algorithm on a … Read more

    A real moment-HSOS hierarchy for complex polynomial optimization with real coefficients

  • Jie Wang
  • Victor Magron
    • Categories Global Optimization, Global Optimization Theory, Semi-definite Programming Tags , , , ,

    This paper proposes a real moment-HSOS hierarchy for complex polynomial optimization problems with real coefficients. We show that this hierarchy provides the same sequence of lower bounds as the complex analogue, yet is much cheaper to solve. In addition, we prove that global optimality is achieved when the ranks of the moment matrix and certain … Read more

    Convex envelopes of bounded monomials on two-variable cones

  • Pietro Belotti
    • Categories Global Optimization Theory Tags , ,

    \(\) We consider an \(n\)-variate monomial function that is restricted both in value by lower and upper bounds and in domain by two homogeneous linear inequalities. Such functions are building blocks of several problems found in practical applications, and that fall under the class of Mixed Integer Nonlinear Optimization. We show that the upper envelope … Read more

    A more efficient reformulation of complex SDP as real SDP

  • Jie Wang
    • Categories Global Optimization Theory, Semi-definite Programming Tags , , , ,

    This note proposes a new reformulation of complex semidefinite programs (SDPs) as real SDPs. As an application, we present an economical reformulation of complex SDP relaxations of complex polynomial optimization problems as real SDPs and derive some further reductions by exploiting inner structure of the complex SDP relaxations. Various numerical examples demonstrate that our new … Read more

    Optimal Low-Rank Matrix Completion: Semidefinite Relaxations and Eigenvector Disjunctions

  • Dimitris Bertsimas
  • Ryan Cory-Wright
  • Sean Lo
  • Jean Pauphilet
    • Categories Data-Mining, Global Optimization Theory, Semi-definite Programming

    Low-rank matrix completion consists of computing a matrix of minimal complexity that recovers a given set of observations as accurately as possible. Unfortunately, existing methods for matrix completion are heuristics that, while highly scalable and often identifying high-quality solutions, do not possess any optimality guarantees. We reexamine matrix completion with an optimality-oriented eye. We reformulate … Read more