Global Optimization Theory

On exact copositive representation of simplicial quadratic optimization problems, their strong conic duality and a new proof of the Frank-Wolfe theorem

  • Immanuel M. Bomze
  • E. Alper Yildirim
    • Categories Cone Programming, Global Optimization, Global Optimization Theory

    We are interested in exactness, strong conic duality and dual attainability in copositive relaxations of quadratic optimization problems (QPs) of a special form, in which any (feasible) QP can be recast. By using our results, the celebrated Frank-Wolfe theorem on the attainability of any bounded QP even over unbounded polyhedra, regardless of whether the objective … Read more

    Separable QCQPs and Their Exact SDP Relaxations

  • Masakazu Kojima
  • Sunyoung Kim
  • Naohiko Arima
    • Categories Global Optimization Theory, Quadratic Programming, Semi-definite Programming Tags , , , , ,

    This paper studies exact semidefinite programming relaxations (SDPRs) for separable quadratically constrained quadratic programs (QCQPs). We consider the construction of a larger separable QCQP from multiple QCQPs with exact SDPRs. We show that exactness is preserved when such QCQPs are combined through a separable horizontal connection, where the coupling is induced through the right-hand-side parameters … Read more

    Hardness of some optimization problems over correlation polyhedra

  • Alberto Caprara
  • Fabio Furini
  • Claudio Gentile
  • Leo Liberti
  • Andrea Lodi
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Polyhedra Tags , , ,

    We prove the NP-hardness, using Karp reductions, of some problems related to the correlation polytope and its corresponding cone, spanned by all of the n×n rank-one matrices over {0, 1}. The problems are: membership, rank of the decomposition, and a “relaxed rank” obtained from relaxing the zero-norm expression for the rank to an ℓ1 norm. … Read more

    Modeling Binary Relations in Piecewise-Linear Approximations

  • Kristin Braun
  • Robert Burlacu
  • Tobias Kuen
  • Kristina Rolsing
    • Categories Combinatorial Optimization, Global Optimization Theory, Nonlinear Optimization Tags , , , , ,

    Over the last decades, using piecewise-linear mixed-integer relaxations of nonlinear expressions has become a strong alternative to spatial branching for solving mixed-integer nonlinear programs. Since these relaxations give rise to large numbers of binary variables that encode interval selections, strengthening them is crucial. We investigate how to exploit the resulting combinatorial structure by integrating cutting-plane … Read more

    On the Convergence and Properties of a Proximal-Gradient Method on Hadamard Manifolds

  • Glaydston Bento
  • Claudemir Rodrigues Santiago
    • Categories Constrained Nonlinear Optimization, Global Optimization Theory, Nonsmooth Optimization Tags , , ,

    In this paper, we address composite optimization problems on Hadamard manifolds, where the objective function is given by the sum of a smooth term (not necessarily convex) and a convex term (not necessarily differentiable). To solve this problem, we develop a proximal gradient method defined directly on the manifold, employing a strategy that enforces monotonicity … Read more

    A second-order cone representable class of nonconvex quadratic programs

  • Aida Khajavirad
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Integer Programming Tags , , , ,

    We consider the problem of minimizing a sparse nonconvex quadratic function over the unit hypercube. By developing an extension of the Reformulation Linearization Technique (RLT) to continuous quadratic sets, we propose a novel second-order cone (SOC) representable relaxation for this problem. By exploiting the sparsity of the quadratic function, we establish a sufficient condition under … 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

    The improvement function reformulation for graphs of minimal point mappings

  • Stefan Schwarze
  • Oliver Stein
    • Categories Constrained Nonlinear Optimization, Game Theory, Global Optimization Theory Tags , , , , ,

    Graphs of minimal point mappings of parametric optimization problems appear in the definition of feasible sets of bilevel optimization problems and of semi-infinite optimization problems, and the intersection of multiple such graphs defines (generalized) Nash equilibria. This paper shows how minimal point graphs of nonconvex parametric optimization problems can be written with the help of … Read more

    The Least Singular Value Function in Variational Analysis

  • Mario Jelitte
  • Boris S. Mordukhovich
    • Categories Constrained Nonlinear Optimization, Global Optimization Theory, Nonsmooth Optimization Tags , , , ,

    Metric regularity is among the central concepts of nonlinear and variational analysis, constrained optimization, and their numerous applications. However, met- ric regularity can be elusive for some important ill-posed classes of problems includ- ing polynomial equations, parametric variational systems, smooth reformulations of complementarity systems with degenerate solutions, etc. The study of stability issues for such … Read more

    New Sufficient and Necessary Conditions for Constrained and Unconstrained Lipschitzian Error Bounds

  • Andreas Fischer
  • Alexey F. Izmailov
  • Mario Jelitte
    • Categories Complementarity and Variational Inequalities, Global Optimization Theory, Nonsmooth Optimization Tags , , , , , , ,

    Local error bounds play a fundamental role in mathematical programming and variational analysis. They are used e.g. as constraint qualifications in optimization, in developing calculus rules for generalized derivatives in nonsmooth and set-valued analysis, and they serve as a key ingredient in the design and convergence analysis of Newton-type methods for solving systems of possibly … Read more