Global Optimization

A new insight on the prediction-correction framework with applications to several first-order methods

  • Jianchao Bai
    • Categories Convex and Nonsmooth Optimization, Global Optimization

    We propose a generalized prediction-correction framework featuring a parameter-free relaxation iteration for solving linearly constrained convex programs. By leveraging variational characterization of the first-order optimality conditions for each resulting subproblem, we establish its global convergence and sublinear convergence rates in both ergodic and nonergodic senses. Furthermore, this new framework is applied to reformulate an indefinite … Read more

    Relaxations of KKT Conditions do not Strengthen Finite RLT and SDP-RLT Bounds for Nonconvex Quadratic Programs

  • E. Alper Yildirim
    • Categories Global Optimization, Linear, Cone and Semidefinite Programming, Quadratic Programming Tags , , , ,

    We consider linear and semidefinite programming relaxations of nonconvex quadratic programs given by the reformulation-linearization technique (RLT relaxation), and the Shor relaxation combined with the RLT relaxation (SDP-RLT relaxation). By incorporating the first-order optimality conditions, a quadratic program can be formulated as an optimization problem with complementarity constraints. We investigate the effect of incorporating optimality … Read more

    A relax-fix-and-exclude algorithm for an MINLP problem with multilinear interpolations

  • Bruno Machado Pacheco
  • Laio Seman
    • Categories (Mixed) Integer Nonlinear Programming, Chemical Engineering, Global Optimization Applications Tags , ,

    This paper introduces a novel algorithm for Mixed-Integer Nonlinear Programming (MINLP) problems with multilinear interpolations of look-up tables. These problems arise when objectives or constraints contain black-box functions only known at a finite set of evaluations on a predefined grid. We derive a piecewise-linear relaxation for the multilinear interpolants, which require an MINLP formulation. Supported … Read more

    Two-way Cutting-plane Algorithm for Best Subset Selection Considering Multicollinearity

  • Yuichi Takano
    • Categories Global Optimization, Integer Programming, Optimization in Data Science Tags , , , ,

    When linear dependence exists between some explanatory variables in a regression model, the estimates of regression coefficients become unstable, thereby making the interpretation of the estimation results unreliable. To eliminate such multicollinearity, we propose a high-performance method for selecting the best subset of explanatory variables for linear and logistic regression models. Specifically, we first derive … Read more

    A Framework for Explainable Knowledge Generation with Expensive Sample Evaluations

  • Alberto Costa
    • Categories Global Optimization, Multidisciplinary Design Optimization, Optimization of Simulated Systems Tags , , ,

    Real world problems often require complex modeling and computation efforts to be effectively addressed. Relying solely on data-driven approaches without integrating physics-based models can result in limited predictive capabilities. Even advanced techniques such as deep learning may be impractical for decision-makers due to the lack of data and challenges in justifying and explaining results. In … Read more

    A Graphical Global Optimization Framework for Parameter Estimation of Statistical Models with Nonconvex Regularization Functions

  • Danial Davarnia
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Global Optimization Theory Tags , , , ,

    Optimization problems with norm-bounding constraints appear in various applications, from portfolio optimization to machine learning, feature selection, and beyond. A widely used variant of these problems relaxes the norm-bounding constraint through Lagrangian relaxation and moves it to the objective function as a form of penalty or regularization term. A challenging class of these models uses … Read more

    An Adaptive Stochastic Dual Progressive Hedging Algorithm for Stochastic Programming

  • Di Zhang
  • Yihang Zhang
  • Suvrajeet Sen
    • Categories Stochastic Approaches, Stochastic Programming Tags , , ,

    The Progressive Hedging (PH) algorithm is one of the cornerstones in large-scale stochastic programming. However, its traditional development requires that all scenario subproblems are solved per iteration, and a probability distribution with finitely many outcomes. This paper introduces a stochastic dual PH algorithm (SDPH) to overcome these challenges. We introduce an adaptive sampling process and … Read more

    Global Optimization of Gas Transportation and Storage: Convex Hull Characterizations and Relaxations

  • Bahar Okumusoglu
  • Burak Kocuk
    • Categories (Mixed) Integer Linear Programming, Energy, Global Optimization Tags , , ,

    Gas transportation and storage has become one of the most relevant and important optimization problems in energy systems. This problem inherently includes highly nonlinear and nonconvex aspects due to gas physics, and discrete aspects due to the control decisions of active network elements. Obtaining even locally optimal solutions for this problem presents significant mathematical and … Read more

    Deterministic global optimization with trained neural networks: What is the benefit of the envelope of single neurons?

  • Clara Witte
  • Jannik Lüthje
  • Victor Schulte
  • Alexander Mitsos
  • Dominik Bongartz
    • Categories Global Optimization, Global Optimization Applications, Optimization in Data Science Tags , , ,

    Optimization problems containing trained neural networks remain challenging due to their nonconvexity. Deterministic global optimization relies on relaxations that should be tight, quickly convergent, and cheap to evaluate. While envelopes of common activation functions have been established for several years, the envelope of an entire neuron had not. Recently, Carrasco and Mu\~{n}oz (arXiv.2410.23362, 2024) proposed … Read more

    The improvement function in branch-and-bound methods for complete global optimization

  • Stefan Schwarze
  • Oliver Stein
  • Peter Kirst
    • Categories Constrained Nonlinear Optimization, Global Optimization Tags , , , ,

    We present a new spatial branch-and-bound approach for treating optimization problems with nonconvex inequality constraints. It is able to approximate the set of all global minimal points in case of solvability, and else to detect infeasibility. The new technique covers the nonconvex constraints by means of an improvement function which, although nonsmooth, can be treated … Read more