Month: May 2015

Quadratically Perturbed Chance Constrained Programming with Fitted Distribution: t-Distribution vs. Gaussian

  • Xin He
    • Categories Stochastic Programming Tags , , ,

    For chance-constrained programming (CCP) with non-Gaussian uncertainty, the optimization is generally intractable owing to the complicated probability density function (PDF). Using a simple fitted distribution with Kullback-Leibler (KL) divergence to represent the PDF mismatch is a systematic way to tackle CCP with non-Gaussian uncertainty. However, the essential difficulty of this methodology is to choose the … Read more

    A Bundle Method for Exploiting Additive Structure in Difficult Optimization Problems

  • Welington de Oliveira
  • Jonathan Eckstein
    • Categories Convex Optimization, Nonsmooth Optimization

    This paper describes a bundle method for (approximately) minimizing complicated nonsmooth convex functions with additive structure, with the primary goal of computing bounds on the solution values of difficult optimization problems such as stochastic integer programs. The method combines features that have appeared in previously proposed bundle methods, but not in the particular configuration we … Read more

    New computer-based search strategies for extreme functions of the Gomory–Johnson infinite group problem

  • Matthias Köppe
  • Yuan Zhou
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , ,

    We describe new computer-based search strategies for extreme functions for the Gomory–Johnson infinite group problem. They lead to the discovery of new extreme functions, whose existence settles several open questions. Article Download View New computer-based search strategies for extreme functions of the Gomory–Johnson infinite group problem

    Regularization vs. Relaxation: A convexification perspective of statistical variable selection

  • Kun Chen
  • Hongbo Dong
  • Jeff Linderoth
    • Categories (Mixed) Integer Nonlinear Programming, Linear, Cone and Semidefinite Programming, Statistics Tags , , ,

    Variable selection is a fundamental task in statistical data analysis. Sparsity-inducing regularization methods are a popular class of methods that simultaneously perform variable selection and model estimation. The central problem is a quadratic optimization problem with an $\ell_0$-norm penalty. Exactly enforcing the $\ell_0$-norm penalty is computationally intractable for larger scale problems, so different sparsity-inducing penalty … Read more

    A Taxonomy of Constraints in Black-Box Simulation-Based Optimization

  • Sébastien Le Digabel
  • Stefan M. Wild
    • Categories Nonlinear Optimization, Optimization Software and Modeling Systems Tags , ,

    The types of constraints encountered in black-box simulation-based optimization problems differ significantly from those addressed in nonlinear programming. We introduce a characterization of constraints to address this situation. We provide formal definitions for several constraint classes and present illustrative examples in the context of the resulting taxonomy. This taxonomy, denoted KARQ, is useful for modeling … Read more

    A Theoretical and Algorithmic Characterization of Bulge Knees

  • Marlon Braun
  • Hartmut Schmeck
  • Pradyumn Kumar Shukla
    • Categories Constrained Nonlinear Optimization, Multi-Criteria Optimization

    This paper deals with the problem of finding convex bulges on the Pareto-front of a multi-objective optimization problem. The point of maximum bulge is of particular interest as this point shows good trade-off properties and it is also close to the non-attainable utopia point. Our approach is to use a population based algorithm to simultaneously … Read more

    A SQP type method for constrained multiobjective optimization

  • Jörg Fliege
  • A. Ismael F. Vaz
    • Categories Multi-Criteria Optimization, Optimization Software and Modeling Systems Tags ,

    We propose an SQP type method for constrained nonlinear multiobjective optimization. The proposed algorithm maintains a list of nondominated points that is improved both for spread along the Pareto front and optimality by solving singleobjective constrained optimization problems. Under appropriate differentiability assumptions we discuss convergence to local optimal Pareto points. We provide numerical results for … Read more

    An Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimization

  • Arda Aytekin
  • Hamid Reza Feyzmahdavian
  • Mikael Johansson
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , ,

    Mini-batch optimization has proven to be a powerful paradigm for large-scale learning. However, the state of the art parallel mini-batch algorithms assume synchronous operation or cyclic update orders. When worker nodes are heterogeneous (due to different computational capabilities or different communication delays), synchronous and cyclic operations are inefficient since they will leave workers idle waiting … Read more

    Probabilistic optimization via approximate p-efficient points and bundle methods

  • V. Berge
  • Welington de Oliveira
  • Claudia Sagastizábal
  • Wim van Ackooij
    • Categories Convex and Nonsmooth Optimization, Stochastic Programming

    For problems when decisions are taken prior to observing the realization of underlying random events, probabilistic constraints are an important modelling tool if reliability is a concern. A key concept to numerically dealing with probabilistic constraints is that of p-efficient points. By adopting a dual point of view, we develop a solution framework that includes … Read more

    Stronger Multi-Commodity Flow Formulations of the (Capacitated) Sequential Ordering Problem

  • Adam N. Letchford
  • Juan-José Salazar-González
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Network Optimization Tags , , , ,

    The “sequential ordering problem” (SOP) is the generalisation of the asymmetric travelling salesman problem in which there are precedence relations between pairs of nodes. Hernández & Salazar introduced a “multi-commodity flow” (MCF) formulation for a generalisation of the SOP in which the vehicle has a limited capacity. We strengthen this MCF formulation by fixing variables … Read more