Linear, Cone and Semidefinite Programming

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

    A Robust Optimization Method with Successive Linear Programming for Intensity Modulated Radiation Therapy

  • Masaaki Tamai
  • Makoto Yamashita
    • Categories Applications - OR and Management Sciences, Linear Programming, Robust Optimization Tags , , , ,

    Intensity modulated radiation therapy (IMRT) is one of radiation therapies for cancers, and it is considered to be effective for complicated shapes of tumors, since dose distributions from each irradiation can be modulated arbitrary. Fluence map optimization (FMO), which optimizes beam intensities with given beam angles, is often formulated as an optimization problem with dose … Read more

    Strong duality of a conic optimization problem with a single hyperplane and two cone constraints

  • Sunyoung Kim
  • Masakazu Kojima
    • Categories Convex Optimization, Global Optimization Theory, Linear, Cone and Semidefinite Programming Tags , , , ,

    Strong (Lagrangian) duality of general conic optimization problems (COPs) has long been studied and its profound and complicated results appear in different forms in a wide range of literatures. As a result, characterizing the known and unknown results can sometimes be difficult. The aim of this article is to provide a unified and geometric view … Read more