Month: January 2020

Best Principal Submatrix Selection for the Maximum Entropy Sampling Problem: Scalable Algorithms and Performance Guarantees

  • Yongchun Li
  • Weijun Xie
    • Categories Data-Mining

    This paper studies a classic maximum entropy sampling problem (MESP), which aims to select the most informative principal submatrix with a given size out of a covariance matrix from a system. MESP has been widely applied to many areas, including healthcare, power system, manufacturing, data science, etc. Investigating its Lagrangian dual and primal characterization, we … Read more

    Primal Space Necessary Characterizations of Transversality Properties

  • Nguyen Duy Cuong
  • Alexander Y. Kruger
    • Categories Nonsmooth Optimization Tags , , , , ,

    This paper continues the study of general nonlinear transversality properties of collections of sets and focuses on primal space necessary (in some cases also sufficient) characterizations of the properties. We formulate geometric, metric and slope characterizations, particularly in the convex setting. The Holder case is given a special attention. Quantitative relations between the nonlinear transversality … Read more

    Equal Risk Pricing and Hedging of Financial Derivatives with Convex Risk Measures

  • Erick Delage
  • Jonathan Yu-Meng Li
  • Saeed Marzban
    • Categories Dynamic Programming, Finance and Economics, Robust Optimization Tags , , , , ,

    In this paper, we consider the problem of equal risk pricing and hedging in which the fair price of an option is the price that exposes both sides of the contract to the same level of risk. Focusing for the first time on the context where risk is measured according to convex risk measures, we … Read more

    Computing Technical Capacities in the European Entry-Exit Gas Market is NP-Hard

  • Lars Schewe
  • Martin Schmidt
  • Johannes Thürauf
    • Categories Applications - Science and Engineering, Network Optimization Tags , , , ,

    As a result of its liberalization, the European gas market is organized as an entry-exit system in order to decouple the trading and transport of natural gas. Roughly summarized, the gas market organization consists of four subsequent stages. First, the transmission system operator (TSO) is obliged to allocate so-called maximal technical capacities for the nodes … Read more

    Nonconvex Constrained Optimization by a Filtering Branch and Bound

  • Gabriele Eichfelder
  • Kathrin Klamroth
  • Julia Niebling
    • Categories Constrained Nonlinear Optimization, Global Optimization Theory, Multi-Criteria Optimization

    A major difficulty in optimization with nonconvex constraints is to find feasible solutions. As simple examples show, the alphaBB-algorithm for single-objective optimization may fail to compute feasible solutions even though this algorithm is a popular method in global optimization. In this work, we introduce a filtering approach motivated by a multiobjective reformulation of the constrained … Read more

    A dimensionality reduction technique for unconstrained global optimization of functions with low effective dimensionality

  • Coralia Cartis
  • Adilet Otemissov
    • Categories Global Optimization, Stochastic Approaches Tags , , ,

    We investigate the unconstrained global optimization of functions with low effective dimensionality, that are constant along certain (unknown) linear subspaces. Extending the technique of random subspace embeddings in [Wang et al., Bayesian optimization in a billion dimensions via random embeddings. JAIR, 55(1): 361–387, 2016], we study a generic Random Embeddings for Global Optimization (REGO) framework … Read more

    Estimation of Marginal Cost to Serve Individual Customers

  • Jeffrey E. Arbogast
  • Chrysanthos E. Gounaris
  • Gildas Bonnier
  • Akang Wang
  • Zachary Wilson
    • Categories Supply Chain Management, Transportation Tags , , , ,

    This paper proposes a scenario sampling-based framework to estimate the expected incremental routing cost required so as to incorporate a target customer into an inherently stochastic supply chain network. Inspired from a real-life setting arising in the distribution of industrial gases, we demonstrate our framework and elucidate the quality of the marginal cost estimates it … Read more

    Games with distributionally robust joint chance constraints

  • Eshan Balachandar
  • Abdel Lisser
  • Shen Peng
  • Nalin Gupta
  • Vikas Vikram Singh
    • Categories Game Theory, Stochastic Programming Tags , , ,

    This paper studies an n-player non-cooperative game with strategy sets defined by stochastic linear constraints. The stochastic constraints of each player are jointly satisfied with a probability exceeding a given threshold. We consider the case where the row vectors defining the constraints are independent random vectors whose probability distributions are not completely known and belong … Read more

    Centering ADMM for the Semidefinite Relaxation of the QAP

  • Shin-ichi Kanoh
  • Akiko Yoshise
    • Categories Linear, Cone and Semidefinite Programming

    We propose a new method for solving the semidefinite (SD) relaxation of the quadratic assignment problem (QAP), called the Centering ADMM. The Centering ADMM is an alternating direction method of multipliers (ADMM) combining the centering steps used in the interior-point method. The first stage of the Centering ADMM updates the iterate so that it approaches … Read more

    Exploiting problem structure in derivative free optimization

  • Margherita Porcelli
  • Philippe L. Toint
    • Categories Nonlinear Optimization, Optimization Software and Modeling Systems Tags , , ,

    A structured version of derivative-free random pattern search optimization algorithms is introduced which is able to exploit coordinate partially separable structure (typically associated with sparsity) often present in unconstrained and bound-constrained optimization problems. This technique improves performance by orders of magnitude and makes it possible to solve large problems that otherwise are totally intractable by … Read more