Variational Convergence of Bifunctions: Motivating Applications

  • Alejandro Jofré
  • Roger J.B. Wets
    • Categories Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization, Game Theory Tags , , , , , , , , ,

    It’s shown that a number of variational problems can be cast as finding the maxinf-points (or minsup-points) of bivariate functions, coveniently abbreviated to bifunctions. These variational problems include: linear and nonlinear complementarity problems, fixed points, variational inequalities, inclusions, non-cooperative games, Walras and Nash equilibrium problems. One can then appeal to the theory of lopsided convergence … Read more

    Branch-Cut-and-Propagate for the Maximum k-Colorable Subgraph Problem with Symmetry

  • Tim Januschowski
  • Marc E. Pfetsch
    • Categories 0-1 Programming, Branch and Cut Algorithms

    Given an undirected graph and a positive integer k, the maximum k-colorable subgraph problem consists of selecting a k-colorable induced subgraph of maximum cardinality. The natural integer programming formulation for this problem exhibits two kinds of symmetry: arbitrarily permuting the color classes and/or applying a non-trivial graph automorphism gives equivalent solutions. It is well known … Read more

    On the hyperplanes arrangements in mixed-integer techniques

  • Sorin Olaru
  • Florin Stoican
  • Ionela Prodan
    • Categories (Mixed) Integer Linear Programming

    This paper is concerned with the improved constraints handling in mixed-integer optimization problems. The novel element is the reduction of the number of binary variables used for expressing the complement of a convex (polytopic) region. As a generalization, the problem of representing the complement of a possibly non-connected union of such convex sets is detailed. … Read more

    Polynomial Approximations for Continuous Linear Programs

  • Dimitra Bampou
  • Daniel Kuhn
    • Categories Infinite Dimensional Optimization, Semi-definite Programming Tags , , , ,

    Continuous linear programs have attracted considerable interest due to their potential for modelling manufacturing, scheduling and routing problems. While efficient simplex-type algorithms have been developed for separated continuous linear programs, crude time discretization remains the method of choice for solving general (non-separated) problem instances. In this paper we propose a more generic approximation scheme for … Read more

    On the Dynamic Stability of Electricity Markets

  • Mihai Anitescu
  • Victor M. Zavala
    • Categories Complementarity and Variational Inequalities, Dynamic Programming, Game Theory Tags , , , ,

    In this work, we present new insights into the dynamic stability of electricity markets. In particular, we discuss how short forecast horizons, incomplete gaming, and physical ramping constraints can give rise to stability issues. Using basic concepts of market efficiency, Lyapunov stability, and predictive control, we construct a new stabilizing market design. A numerical case … Read more

    Approximation Theory of Matrix Rank Minimization and Its Application to Quadratic Equations

  • Yun-Bin Zhao
    • Categories Approximation Algorithms, Constrained Nonlinear Optimization, Semi-definite Programming Tags , , , , ,

    Matrix rank minimization problems are gaining a plenty of recent attention in both mathematical and engineering fields. This class of problems, arising in various and across-discipline applications, is known to be NP-hard in general. In this paper, we aim at providing an approximation theory for the rank minimization problem, and prove that a rank minimization … Read more

    CONVEX HULL RELAXATION (CHR) FOR CONVEX AND NONCONVEX MINLP PROBLEMS WITH LINEAR CONSTRAINTS

  • Aykut Ahlatçıoğlu
  • Monique Guignard
    • Categories (Mixed) Integer Nonlinear Programming, Approximation Algorithms, Constrained Nonlinear Optimization

    The behavior of enumeration-based programs for solving MINLPs depends at least in part on the quality of the bounds on the optimal value and of the feasible solutions found. We consider MINLP problems with linear constraints. The convex hull relaxation (CHR) is a special case of the primal relaxation (Guignard 1994, 2007) that is very … Read more

    A new, solvable, primal relaxation for convex nonlinear integer programming problems

  • Monique Guignard
    • Categories (Mixed) Integer Nonlinear Programming, Approximation Algorithms, Convex Optimization Tags , , ,

    The paper describes a new primal relaxation (PR) for computing bounds on nonlinear integer programming (NLIP) problems. It is a natural extension to NLIP problems of the geometric interpretation of Lagrangean relaxation presented by Geoffrion (1974) for linear problems, and it is based on the same assumption that some constraints are complicating and are treated … Read more

    Combining QCR and CHR for Convex Quadratic MINLP Problems with Linear Constraints

  • Aykut Ahlatçıoğlu
  • Monique Guignard
  • Michael Bussieck
  • Mustafa Esen
  • Jan Jagla
  • Alexander Meeraus
    • Categories (Mixed) Integer Nonlinear Programming, Approximation Algorithms, Semi-definite Programming Tags , , , , , , ,

    The convex hull relaxation (CHR) method (Albornoz 1998, Ahlatçıoğlu 2007, Ahlatçıoğlu and Guignard 2010) provides lower bounds and feasible solutions (thus upper bounds) on convex 0-1 nonlinear programming problems with linear constraints. In the quadratic case, these bounds may often be improved by a preprocessing step that adds to the quadratic objective function terms which … Read more

    Convexity Conditions of Kantorovich Function and Related Semi-infinite Linear Matrix Inequalities

  • Yun-Bin Zhao
    • Categories Convex Optimization, Robust Optimization, Semi-infinite Programming Tags , , , ,

    The Kantorovich function $(x^TAx)( x^T A^{-1} x)$, where $A$ is a positive definite matrix, is not convex in general. From a matrix or convex analysis point of view, it is interesting to address the question: When is this function convex? In this paper, we prove that the 2-dimensional Kantorovich function is convex if and only … Read more