Optimization problems with equilibrium constraints and their numerical solution

  • Michal Kočvara
  • Jiri V. Outrata
    • Categories Complementarity and Variational Inequalities, Nonlinear Optimization, Other Topics Tags

    We consider a class of optimization problems with a generalized equation among the constraints. This class covers several problem types like MPEC (Mathematical Programs with Equilibrium Constraints) and MPCC (Mathematical Programs with Complementarity Constraints). We briefly review techniques used for numerical solution of these problems: penalty methods, nonlinear programming (NLP) techniques and Implicit Programming approach … Read more

    On Compact Formulations for Integer Programs Solved by Column Generation

  • Jacques Desrosiers
  • Marco E. Luebbecke
  • Francois Soumis
  • Daniel Villeneuve
    • Categories (Mixed) Integer Linear Programming

    Column generation has become a powerful tool in solving large scale integer programs. We argue that most of the often reported compatibility issues between pricing oracle and branching rules disappear when branching decisions are based on the reduction of the variables of the oracle’s domain. This can be generalized to branching on variables of a … Read more

    On the Representation and Characterization of Fullerene C60

  • Siemion Fajtlowicz
    • Categories Graphs and Matroids Tags , , , ,

    An operation on trivalent graphs leads from the truncated cube to buckminsterfullerene, and C60 is the only fullerene with disjoint pentagons which can be obtained by this method. The construction and the proof emphasize maximal independent sets that contain two fifths of the vertices of trivalent graphs. In the case of C60, these sets define … Read more

    An annotated bibliography of network interior point methods

  • Mauricio G.C. Resende
  • Geraldo Veiga
    • Categories Linear Programming, Network Optimization Tags , ,

    This paper presents an annotated bibliography on interior point methods for solving network flow problems. We consider single and multi-commodity network flow problems, as well as preconditioners used in implementations of conjugate gradient methods for solving the normal systems of equations that arise in interior network flow algorithms. Applications in electrical engineering and miscellaneous papers … Read more

    Detecting Infeasibility in Infeasible-Interior-Point Methods for Optimization

  • Michael J. Todd
    • Categories Linear Programming, Second-Order Cone Programming, Semi-definite Programming Tags , ,

    We study interior-point methods for optimization problems in the case of infeasibility or unboundedness. While many such methods are designed to search for optimal solutions even when they do not exist, we show that they can be viewed as implicitly searching for well-defined optimal solutions to related problems whose optimal solutions give certificates of infeasibility … Read more

    A Local Convergence Theory of a Filter Line Search Method for Nonlinear Programming

  • Choong Ming Chin
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , , ,

    In this paper the theory of local convergence for a class of line search filter type methods for nonlinear programming is presented. The algorithm presented here is globally convergent (see Chin [4]) and the rate of convergence is two-step superlinear. The proposed algorithm solves a sequence of quadratic progrmming subproblems to obtain search directions and … Read more

    Smoothed Analysis of Interior-Point Algorithms: Termination

  • Daniel Spielman
  • Shang-Hua Teng
    • Categories Linear Programming Tags , , ,

    We perform a smoothed analysis of the termination phase of an interior-point method. By combining this analysis with the smoothed analysis of Renegar’s interior-point algorithm by Dunagan, Spielman and Teng, we show that the smoothed complexity of an interior-point algorithm for linear programming is $O (m^{3} \log (m/\sigma ))$. In contrast, the best known bound … Read more

    Nonsmooth Matrix Valued Functions Defined by Singular Values

  • Jie Sun
  • Defeng Sun
    • Categories Complementarity and Variational Inequalities, Linear, Cone and Semidefinite Programming, Nonsmooth Optimization Tags , , ,

    A class of matrix valued functions defined by singular values of nonsymmetric matrices is shown to have many properties analogous to matrix valued functions defined by eigenvalues of symmetric matrices. In particular, the (smoothed) matrix valued Fischer-Burmeister function is proved to be strongly semismooth everywhere. This result is also used to show the strong semismoothness … Read more

    Solving large scale semidefinite programsvia an iterative solver onthe augmented systems

  • Kim-Chuan Toh
    • Categories Semi-definite Programming Tags , , , , , ,

    The search directions in an interior-point method for large scale semidefinite programming (SDP) can be computed by applying a Krylov iterative method to either the Schur complement equation (SCE) or the augmented equation. Both methods suffer from slow convergence as interior-point iterates approach optimality. Numerical experiments have shown that diagonally preconditioned conjugate residual method on … Read more

    Approximation Bounds for Quadratic Maximization with Semidefinite Programming Relaxation

  • Dachuan Xu
  • Shuzhong Zhang
    • Categories Approximation Algorithms Tags , , ,

    In this paper, we consider a class of quadratic maximization problems. One important instance in that class is the famous quadratic maximization formulation of the max-cut problem studied by Goemans and Williamson. Since the problem is NP-hard in general, following Goemans and Williamson, we apply the approximation method based on the semidefinite programming (SDP) relaxation. … Read more