Linear, Cone and Semidefinite Programming

On solving large-scale multistage stochastic problems with a new specialized interior-point approach

  • Jordi Castro
  • Laureano F. Escudero
  • Juan F. Monge
    • Categories Linear, Cone and Semidefinite Programming, Stochastic Programming Tags , , , , ,

    A novel approach based on a specialized interior-point method (IPM) is presented for solving large-scale stochastic multistage continuous optimization problems, which represent the uncertainty in strategic multistage and operational two-stage scenario trees, the latter being rooted at the strategic nodes. This new solution approach considers a split-variable formulation of the strategic and operational structures, for … Read more

    Hub Network Design Problem with Capacity, Congestion and Stochastic Demand Considerations

  • Vedat Bayram
  • Barış Yıldız
  • M. Saleh Farham
    • Categories Second-Order Cone Programming, Stochastic Programming, Transportation Tags , , , , , , ,

    We introduce the hub network design problem with congestion, capacity, and stochastic demand considerations (HNDC), which generalizes the classical hub location problem in several directions. In particular, we extend state-of-the-art by integrating capacity acquisition decision and congestion cost effect into the problem and allowing dynamic routing for origin-destination pairs. Connecting strategic and operational level decisions, … Read more

    New interior-point approach for one- and two-class linear support vector machines using multiple variable splitting

  • Jordi Castro
    • Categories Data-Mining, Linear, Cone and Semidefinite Programming Tags , , , ,

    Multiple variable splitting is a general technique for decomposing problems by using copies of variables and additional linking constraints that equate their values. The resulting large optimization problem can be solved with a specialized interior-point method that exploits the problem structure and computes the Newton direction with a combination of direct and iterative solvers (i.e., … Read more

    An effective version of Schmüdgen’s Positivstellensatz for the hypercube

  • Monique Laurent
  • Lucas Slot
    • Categories Global Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    Let S be a compact semialgebraic set and let f be a polynomial nonnegative on S. Schmüdgen’s Positivstellensatz then states that for any \eta>0, the nonnegativity of f+\eta on S can be certified by expressing f+\eta as a conic combination of products of the polynomials that occur in the inequalities defining S, where the coefficients … Read more

    On approximate solutions for robust semi-infinite multi-objective convex symmetric cone optimization

  • Baha Alzalg
  • Amira Achouak Oulha
    • Categories Linear, Cone and Semidefinite Programming, Robust Optimization, Semi-infinite Programming Tags , , , ,

    We present approximate solutions for the robust semi-infinite multi-objective convex symmetric cone programming problem. By using the robust optimization approach, we establish an approximate optimality theorem and approximate duality theorems for approximate solutions in convex symmetric cone optimization problem involving infinitely many constraints to be satisfied and multiple objectives to be optimized simultaneously under the … Read more

    Algebraic-based primal interior-point algorithms for stochastic infinity norm optimization

  • Baha Alzalg
  • Karima Tamsaouete
    • Categories Linear, Cone and Semidefinite Programming, Nonlinear Optimization, Stochastic Programming Tags , , , ,

    We study the two-stage stochastic infinity norm optimization problem with recourse. First, we study and analyze the algebraic structure of the infinity norm cone, and use its algebra to compute the derivatives of the barrier recourse functions. Then, we show that the barrier recourse functions and the composite barrier functions for this optimization problem are … Read more

    Duality aspects in convex conic programming

  • Mária Trnovská
  • Jakub Hrdina
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    In this paper we study strong duality aspects in convex conic programming over general convex cones. It is known that the duality in convex optimization is linked with specific theorems of alternatives. We formulate and prove strong alternatives to the existence of the relative interior point in the primal (dual) feasible set. We analyze the … Read more

    Stochastic Dual Dynamic Programming for Optimal Power Flow Problems under Uncertainty

  • Adriana Kiszka
  • David Wozabal
    • Categories Energy, Semi-definite Programming, Stochastic Programming Tags , , ,

    We propose the first computationally tractable framework to solve multi-stage stochastic optimal power flow (OPF) problems in alternating current (AC) power systems. To this end, we use recent results on dual convex semi-definite programming (SDP) relaxations of OPF problems in order to adapt the stochastic dual dynamic programming (SDDP) algorithm for problems with a Markovian … Read more

    Revisiting semidefinite programming approaches to options pricing: complexity and computational perspectives

  • Didier Henrion
  • Felix Kirschner
  • Etienne de Klerk
  • Jean-Bernard Lasserre
  • Victor Magron
    • Categories Finance and Economics, Semi-definite Programming Tags , ,

    In this paper we consider the problem of finding bounds on the prices of options depending on multiple assets without assuming any underlying model on the price dynamics, but only the absence of arbitrage opportunities. We formulate this as a generalized moment problem and utilize the well-known Moment-Sum-of-Squares (SOS) hierarchy of Lasserre to obtain bounds … Read more

    A Column Generation Scheme for Distributionally Robust Multi-Item Newsvendor Problems

  • Shanshan Wang
  • Erick Delage
    • Categories Applications - OR and Management Sciences, Linear, Cone and Semidefinite Programming, Robust Optimization Tags , , ,

    In this paper, we study a distributionally robust multi-item newsvendor problem, where the demand distribution is unknown but specified with a general event-wise ambiguity set. Using the event-wise affine decision rules, we can obtain a conservative approximation formulation of the problem, which can typically be further reformulated as a linear program. In order to efficiently … Read more