A Preconditioned Iterative Interior Point Approach to the Conic Bundle Subproblem

The conic bundle implementation of the spectral bundle method for large scale semidefinite programming solves in each iteration a semidefinite quadratic subproblem by an interior point approach. For larger cutting model sizes the limiting operation is collecting and factorizing a Schur complement of the primal-dual KKT system. We explore possibilities to improve on this by … Read more

Dynamic Scaling and Submodel Selection in Bundle Methods for Convex Optimization

Bundle methods determine the next candidate point as the minimizer of a cutting model augmented with a proximal term. We propose a dynamic approach for choosing a quadratic proximal term based on subgradient information from past evaluations. For the special case of convex quadratic functions, conditions are studied under which this actually reproduces the Hessian. … Read more

A Parallel Bundle Framework for Asynchronous Subspace Optimisation of Nonsmooth Convex Functions

An algorithmic framework is presented for optimising general convex functions by non synchronised parallel processes. Each process greedily picks a suitable adaptive subset of coordinates and runs a bundle method on a corresponding restricted problem stopping whenever a descent step is encountered or predicted decrease is reduced sufficiently. No prior knowledge on the dependencies between … Read more

The Spectral Bundle Method with Second-Order Information

The spectral bundle method was introduced by Helmberg and Rendl to solve a class of eigenvalue optimization problems that is equivalent to the class of semidefinite programs with the constant trace property. We investigate the feasibility and effectiveness of including full or partial second-order information in the spectral bundle method, building on work of Overton … Read more

A Parallel Bundle Method for Asynchronous Subspace Optimization in Lagrangian Relaxation

An algorithmic approach is proposed for exploiting parallelization possibilities in large scale optimization models of the following generic type. Objects change their state over time subject to a limited availability of common resources. These are modeled by linear coupling constraints and result in few objects competing for the same resource at each point in time. … Read more

Dynamic Graph Generation for Large Scale Operational Train Timetabling

The aim of operational train timetabling is to find a conflict free timetable for a set of passenger and freight trains with predefined stopping time windows along given routes in an infrastructure network so that station capacities and train dependent running and headway times are observed. Typical models for this problem are based on time-discretized … Read more

The Symmetric Quadratic Traveling Salesman Problem

In the quadratic traveling salesman problem a cost is associated with any three nodes traversed in succession. This structure arises, e.g., if the succession of two edges represents energetic conformations, a change of direction or a possible change of transportation means. In the symmetric case, costs do not depend on the direction of traversal. We … Read more

LP and SDP Branch-and-Cut Algorithms for the Minimum Graph Bisection Problem: A Computational Comparison

While semidefinite relaxations are known to deliver good approximations for combinatorial optimization problems like graph bisection, their practical scope is mostly associated with small dense instances. For large sparse instances, cutting plane techniques are considered the method of choice. These are also applicable for semidefinite relaxations via the spectral bundle method, which allows to exploit … Read more

Graph Realizations Associated with Minimizing the Maximum Eigenvalue of the Laplacian

In analogy to the absolute algebraic connectivity of Fiedler, we study the problem of minimizing the maximum eigenvalue of the Laplacian of a graph by redistributing the edge weights. Via semidefinite duality this leads to a graph realization problem in which nodes should be placed as close as possible to the origin while adjacent nodes … Read more

The Rotational Dimension of a Graph

Given a connected graph $G=(N,E)$ with node weights $s\in\R^N_+$ and nonnegative edge lengths, we study the following embedding problem related to an eigenvalue optimization problem over the second smallest eigenvalue of the (scaled) Laplacian of $G$: Find $v_i\in\R^{|N|}$, $i\in N$ so that distances between adjacent nodes do not exceed prescribed edge lengths, the weighted barycenter … Read more