second-order cone programming

A New Second-Order Cone Programming Relaxation for MAX-CUT problems

  • Masakazu Muramatsu
  • Tsunehiro Suzuki
    • Categories Combinatorial Optimization, Global Optimization Applications, Linear, Cone and Semidefinite Programming Tags , , , ,

    We propose a new relaxation scheme for the MAX-CUT problem using second-order cone programming. We construct relaxation problems to reflect the structure of the original graph. Numerical experiments show that our relaxation approaches give better bounds than those based on the spectral decomposition proposed by Kim and Kojima, and that the efficiency of the branch-and-bound … Read more

    Minimum Risk Arbitrage with Risky Financial Contracts

  • Mustafa C. Pinar
    • Categories Finance and Economics, Robust Optimization, Second-Order Cone Programming Tags , , , ,

    For a set of financial securities specified by their expected returns and variance/covariances we propose the concept of minimum risk arbitrage, characterize conditions under which such opportunities may exist. We use conic duality and convex analysis to derive these characterizations. For practical computation a decidability result on the existence of an arbitrage opportunity is derived. … Read more