Month: April 2017

Interchangeability principle and dynamic equations in risk averse stochastic programming

  • Alexander Shapiro
    • Categories Stochastic Programming Tags , , , , ,

    In this paper we consider interchangeability of the minimization operator with monotone risk functionals. In particular we discuss the role of strict monotonicity of the risk functionals. We also discuss implications to solutions of dynamic programming equations of risk averse multistage stochastic programming problems. Article Download View Interchangeability principle and dynamic equations in risk averse … Read more

    Outer-Product-Free Sets for Polynomial Optimization and Oracle-Based Cuts

  • Daniel Bienstock
  • Chen Chen
  • Gonzalo Muñoz
    • Categories Constrained Nonlinear Optimization, Cutting Plane Approaches, Global Optimization Theory Tags , ,

    Cutting planes are derived from specific problem structures, such as a single linear constraint from an integer program. This paper introduces cuts that involve minimal structural assumptions, enabling the generation of strong polyhedral relaxations for a broad class of problems. We consider valid inequalities for the set $S\cap P$, where $S$ is a closed set, … Read more

    Combinatorial Optimization Problems in Engineering Applications

  • Hans D Mittelmann
    • Categories Applications - Science and Engineering, Combinatorial Optimization Tags , , , , , , ,

    This paper deals with several combinatorial optimization problems. The most challenging such problem is the quadratic assignment problem. It is considered in both two dimensions (QAP) and in three dimensions (Q3AP) and in the context of communication engineering. Semidefinite relaxations are used to derive lower bounds for the optimum while heuristics are applied to either … Read more

    On the use of the energy norm in trust-region and adaptive cubic regularization subproblems

  • Elhoucine Bergou
  • Youssef Diouane
  • Serge Gratton
    • Categories Unconstrained Optimization Tags , , , , , , ,

    We consider solving unconstrained optimization problems by means of two popular globalization techniques: trust-region (TR) algorithms and adaptive regularized framework using cubics (ARC). Both techniques require the solution of a so-called “subproblem” in which a trial step is computed by solving an optimization problem involving an approximation of the objective function, called “the model”. The … Read more

    A Branch-and-Cut Algorithm for Mixed Integer Bilevel Linear Optimization Problems and Its Implementation

  • S.T. DeNegre
  • Ted K. Ralphs
  • S. Tahernejad
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Optimization Software and Modeling Systems Tags , , ,

    In this paper, we describe an algorithmic framework for solving mixed integer bilevel linear optimization problems (MIBLPs) by a generalized branch-and-cut approach. The framework presented merges features from existing algorithms (for both traditional mixed integer linear optimization and MIBLPs) with new techniques to produce a flexible and robust framework capable of solving a wide range … Read more

    A Note on the Forward-Douglas–Rachford Splitting for Monotone Inclusion and Convex Optimization

  • Hugo Raguet
    • Categories Biomedical Applications, Convex Optimization, Generalized Convexity/Monoticity

    We shed light on the structure of the “three-operator” version of the forward-Douglas–Rachford splitting algorithm for finding a zero of a sum of maximally monotone operators $A + B + C$, where $B$ is cocoercive, involving only the computation of $B$ and of the resolvent of $A$ and of $C$, separately. We show that it … Read more

    A Hausdorff-type distance, a directional derivative of a set-valued map and applications in set optimization

  • Xuan Duc Ha Truong
    • Categories Generalized Convexity/Monoticity, Multi-Criteria Optimization Tags , , , ,

    In this paper, we follow Kuroiwa’s set approach in set optimization, which proposes to compare values of a set-valued objective map $F$ respect to various set order relations. We introduce a Hausdorff-type distance relative to an ordering cone between two sets in a Banach space and use it to define a directional derivative for $F$. … Read more

    Generation techniques for linear and integer programming instances with controllable properties

  • Davaatseren Baatar
  • Hans D Mittelmann
  • Simon Bowly
  • Kate Smith-Miles
    • Categories (Mixed) Integer Linear Programming, Optimization Software and Modeling Systems Tags , ,

    This paper addresses the problem of generating synthetic test cases for experimentation in linear programming. We propose a method which maps instance generation and instance space search to an alternative encoded space. This allows us to develop a generator for feasible bounded linear programming instances with controllable properties. We show that this method is capable … Read more

    A decoupled first/second-order steps technique for nonconvex nonlinear unconstrained optimization with improved complexity bounds

  • Serge Gratton
  • Clément W. Royer
  • Luis Nunes Vicente
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , , , ,

    In order to be provably convergent towards a second-order stationary point, optimization methods applied to nonconvex problems must necessarily exploit both first and second-order information. However, as revealed by recent complexity analyzes of some of these methods, the overall effort to reach second-order points is significantly larger when compared to the one of approaching first-order … Read more

    Partially separable convexly-constrained optimization with non-Lipschitz singularities and its complexity

  • Xiaojun Chen
  • Philippe L. Toint
  • Hong Wang
    • Categories Nonsmooth Optimization Tags , ,

    An adaptive regularization algorithm using high-order models is proposed for partially separable convexly constrained nonlinear optimization problems whose objective function contains non-Lipschitzian $\ell_q$-norm regularization terms for $q\in (0,1)$. It is shown that the algorithm using an $p$-th order Taylor model for $p$ odd needs in general at most $O(\epsilon^{-(p+1)/p})$ evaluations of the objective function and … Read more