Month: April 2008

A Hybrid Relax-and-Cut/Branch-and-Cut Algorithm for the Degree-Constrained Minimum Spanning Tree Problem

  • Alexandre Cunha
  • Abílio Lucena
    • Categories Branch and Cut Algorithms, Telecommunications Tags , , ,

    A new exact solution algorithm is proposed for the Degree-Constrained Minimum Spanning Tree Problem. The algorithm involves two combined phases. The first one contains a Lagrangian Relax-and-Cut procedure while the second implements a Branch-and-Cut algorithm. Both phases rely on a standard formulation for the problem, reinforced with Blossom Inequalities. An important feature of the proposed … Read more

    Smoothing techniques for computing Nash equilibria of sequential games

  • Andrew Gilpin
  • Javier F. Peña
  • Samid Hoda
    • Categories Convex Optimization, Game Theory Tags , ,

    We develop first-order smoothing techniques for saddle-point problems that arise in the Nash equilibria computation of sequential games. The crux of our work is a construction of suitable prox-functions for a certain class of polytopes that encode the sequential nature of the games. An implementation based on our smoothing techniques computes approximate Nash equilibria for … Read more

    Accelerated line-search and trust-region methods

  • Pierre-Antoine Absil
  • Kyle A. Gallivan
    • Categories Applications - Science and Engineering, Unconstrained Optimization Tags , , ,

    In numerical optimization, line-search and trust-region methods are two important classes of descent schemes, with well-understood global convergence properties. Here we consider “accelerated” versions of these methods, where the conventional iterate is allowed to be replaced by any point that produces at least as much decrease in the cost function as a fixed fraction of … Read more

    Cutting-Set Methods for Robust Convex Optimization with Pessimizing Oracles

  • Stephen Boyd
  • Almir Mutapcic
    • Categories Robust Optimization Tags , , ,

    We consider a general worst-case robust convex optimization problem, with arbitrary dependence on the uncertain parameters, which are assumed to lie in some given set of possible values. We describe a general method for solving such a problem, which alternates between optimization and worst-case analysis. With exact worst-case analysis, the method is shown to converge … Read more