Global Optimization

Multi-objective Optimization Based Algorithms for Solving Mixed Integer Linear Minimum Multiplicative Programs

  • Hadi Charkhgard
  • Vahid Mahmoodian
  • Yu Zhang
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Global Optimization

    We present two new algorithms for a class of single-objective non-linear optimization problems, the so-called Mixed Integer Linear minimum Multiplicative Programs (MIL-mMPs). This class of optimization problems has a desirable characteristic: a MIL-mMP can be viewed as a special case of the problem of optimization over the efficient set in multi-objective optimization. The proposed algorithms … Read more

    Optimization and Validation of Pumping System Design and Operation for Water Supply in High-Rise Buildings

  • Lena C. Altherr
  • Peter F. Pelz
  • Philipp Leise
  • Imke-Sophie Lorenz
  • Tim M. Müller
    • Categories Global Optimization Applications, Mechanical Engineering Tags , , , , ,

    The application of mathematical optimization methods provides the capacity to increase the energy efficiency and to lower the investment costs of technical systems, considerably. We present a system approach for the optimization of the design and operation of pumping systems and exemplify it by applying it to the water supply of high-rise buildings. The underlying … Read more

    Spurious Local Minima Exist for Almost All Over-parameterized Neural Networks

  • Tian Ding
  • Ruoyu Sun
  • Dawei Li
    • Categories Global Optimization Theory, Nonlinear Optimization

    A popular belief for explaining the efficiency in training deep neural networks is that over-paramenterized neural networks have nice landscape. However, it still remains unclear whether over-parameterized neural networks contain spurious local minima in general, since all current positive results cannot prove non-existence of bad local minima, and all current negative results have strong restrictions … Read more

    On Sum of Squares Representation of Convex Forms and Generalized Cauchy-Schwarz Inequalities

  • Bachir El Khadir
    • Categories Convex Optimization, Global Optimization Theory, Semi-definite Programming Tags , ,

    A convex form of degree larger than one is always nonnegative since it vanishes together with its gradient at the origin. In 2007, Parrilo asked if convex forms are always sums of squares. A few years later, Blekherman answered the question in the negative by showing through volume arguments that for high enough number of … Read more

    Distance geometry and data science

  • Leo Liberti
    • Categories Data-Mining, Global Optimization Applications, Graphs and Matroids Tags , , , , ,

    Data are often represented as graphs. Many common tasks in data science are based on distances between entities. While some data science methodologies natively take graphs as their input, there are many more that take their input in vectorial form. In this survey we discuss the fundamental problem of mapping graphs to vectors, and its … Read more

    Sparse PCA on fixed-rank matrices

  • Alberto Del Pia
    • Categories Global Optimization Theory, Quadratic Programming Tags , , , ,

    Sparse PCA is the optimization problem obtained from PCA by adding a sparsity constraint on the principal components. Sparse PCA is NP-hard and hard to approximate even in the single-component case. In this paper we settle the computational complexity of sparse PCA with respect to the rank of the covariance matrix. We show that, if … Read more

    Visible points, the separation problem, and applications to MINLP

  • Felipe Serrano
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Global Optimization Tags , , , ,

    In this paper we introduce a technique to produce tighter cutting planes for mixed-integer non-linear programs. Usually, a cutting plane is generated to cut off a specific infeasible point. The underlying idea is to use the infeasible point to restrict the feasible region in order to obtain a tighter domain. To ensure validity, we require … Read more

    Solving Multiobjective Mixed Integer Convex Optimization Problems

  • Marianna De Santis
  • Gabriele Eichfelder
  • Julia Niebling
  • Stefan Rocktäschel
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Multi-Criteria Optimization Tags , ,

    Multiobjective mixed integer convex optimization refers to mathematical programming problems where more than one convex objective function needs to be optimized simultaneously and some of the variables are constrained to take integer values. We present a branch-and-bound method based on the use of properly defined lower bounds. We do not simply rely on convex relaxations, … Read more

    Improved convergence analysis of Lasserre’s measure-based upper bounds for polynomial minimization on compact sets

  • Monique Laurent
  • Lucas Slot
    • Categories Global Optimization, Linear, Cone and Semidefinite Programming

    We consider the problem of computing the minimum value of a polynomial f over a compact set K⊆R^n, which can be reformulated as finding a probability measure ν on K minimizing the expected value of f over K. Lasserre showed that it suffices to consider such measures of the form ν=qμ, where q is a … Read more

    A Class of Stochastic Variance Reduced Methods with an Adaptive Stepsize

  • Tiande Guo
  • Congying Han
  • Yan Liu
    • Categories Convex Optimization, Stochastic Approaches, Unconstrained Optimization Tags

    Stochastic variance reduced methods have recently surged into prominence for solving large scale optimization problems in the context of machine learning. Tan, Ma and Dai et al. first proposed the new stochastic variance reduced gradient (SVRG) method with the Barzilai-Borwein (BB) method to compute step sizes automatically, which performs well in practice. On this basis, … Read more