Immanuel M. Bomze

A First-Order Interior-Point Method for Linearly Constrained Smooth Optimization

  • Immanuel M. Bomze
  • Paul Tseng
  • Werner Schachinger
    • Categories Nonlinear Optimization, Quadratic Programming

    We propose a first-order interior-point method for linearly constrained smooth optimization that unifies and extends first-order affine-scaling method and replicator dynamics method for standard quadratic programming. Global convergence and, in the case of quadratic programs, (sub)linear convergence rate and iterate convergence results are derived. Numerical experience on simplex constrained problems with 1000 variables is reported. … Read more

    Gap, cosum, and product properties of the $\theta’$ bound on the clique number

  • Immanuel M. Bomze
  • Marco Locatelli
  • Florian Frommlet
    • Categories Graphs and Matroids, Semi-definite Programming Tags , , , ,

    In a paper published 1978, McEliece, Rodemich and Rumsey improved Lov\’asz’ bound for the Maximum Clique Problem. This strengthening has become well-known under the name Lov\’asz-Schrijver bound and is usually denoted by $\theta’$. This article now deals with situations where this bound is not exact. To provide instances for which the gap between this bound … Read more

    A conic duality Frank–Wolfe type theorem via exact penalization in quadratic optimization

  • Immanuel M. Bomze
  • Werner Schachinger
    • Categories Linear, Cone and Semidefinite Programming, Quadratic Programming Tags ,

    The famous Frank–Wolfe theorem ensures attainability of the optimal value for quadratic objective functions over a (possibly unbounded) polyhedron if the feasible values are bounded. This theorem does not hold in general for conic programs where linear constraints are replaced by more general convex constraints like positive-semidefiniteness or copositivity conditions, despite the fact that the … Read more

    Copositivity cuts for improving SDP bounds on the clique number

  • Immanuel M. Bomze
  • Marco Locatelli
  • Florian Frommlet
    • Categories Graphs and Matroids, Semi-definite Programming Tags , , ,

    Adding cuts based on copositive matrices, we propose to improve Lovász’ bound on the clique number and its tightening introduced by McEliece, Rodemich, Rumsey, and Schrijver. Candidates for cheap and efficient copositivity cuts of this type are obtained from graphs with known clique number. The cost of previously established semidefinite programming bound hierarchies rapidly increases … Read more

    Efficient and cheap bounds for (standard) quadratic optimization

  • Immanuel M. Bomze
  • Marco Locatelli
  • F. Tardella
    • Categories Global Optimization Applications, Quadratic Programming Tags , , , ,

    A standard quadratic optimization problem (StQP) consists in minimizing a quadratic form over a simplex. A number of problems can be transformed into a StQP, including the general quadratic problem over a polytope and the maximum clique problem in a graph. In this paper we present several polynomial-time bounds for StQP ranging from very simple … Read more

    New results for molecular formation under pairwise potential minimization

  • Bernardetta Addis
  • Immanuel M. Bomze
  • Werner Schachinger
  • Fabio Schoen
    • Categories Global Optimization, Global Optimization Applications, Global Optimization Theory Tags , , , , ,

    We establish new lower bounds on the distance between two points of a minimum energy configuration of $N$ points in $\mathbb{R}^3$ interacting according to a pairwise potential function. For the Lennard-Jones case, this bound is 0.67985 (and 0.7633 in the planar case). A similar argument yields an estimate for the minimal distance in Morse clusters, … Read more

    Solving standard quadratic optimization problems via linear, semidefinite and copositive programming

  • Immanuel M. Bomze
  • Etienne de Klerk
    • Categories Combinatorial Optimization, Global Optimization Theory, Semi-definite Programming Tags , , , ,

    The problem of minimizing a (non-convex) quadratic function over the simplex (the standard quadratic optimization problem) has an exact convex reformulation as a copositive programming problem. In this paper we show how to approximate the optimal solution by approximating the cone of copositive matrices via systems of linear inequalities, and, more refined, linear matrix inequalities … Read more