An Efficient Decomposition Algorithm for Static, Stochastic, Linear and Mixed-Integer Linear Programs with Conditional-Value-at-Risk Constraints

  • Pu Huang
  • Dharmashankar Subramanian
    • Categories Applications - OR and Management Sciences, Robust Optimization

    We present an efficient decomposition algorithm for single-stage, stochastic linear programs, where conditional value at risk (CVaR) appears as a risk measure in multiple constraints. It starts with a well-known nonlinear, convex reformulation of conditional value at risk constraints, and establishes the connection to a combinatorially large polyhedral representation of the convex feasible set induced … Read more

    On Low Rank Matrix Approximations with Applications to Synthesis Problem in Compressed Sensing

  • Anatoli Juditsky
  • Fatma Kılınç-Karzan
  • Arkadi Nemirovski
    • Categories Basic Sciences Applications, Stochastic Programming Tags ,

    We consider the synthesis problem of Compressed Sensing: given $s$ and an $M\times n$ matrix $A$, extract from $A$ an $m\times n$ submatrix $A_m$, with $m$ as small as possible, which is $s$-good, that is, every signal $x$ with at most $s$ nonzero entries can be recovered from observation $A_m x$ by $\ell_1$ minimization: $x … Read more

    Superlinear Convergence of Infeasible Predictor-Corrector Path-Following Interior Point Algorithm for SDLCP using the HKM Direction

  • Chee-Khian Sim
    • Categories Semi-definite Programming

    Interior point method (IPM) defines a search direction at each interior point of a region. These search directions form a direction field which in turn gives rise to a system of ordinary differential equations (ODEs). The solutions of the system of ODEs can be viewed as underlying paths in the interior of the region. In … Read more

    Efficiency of coordinate descent methods on huge-scale optimization problems

  • Yurii Nesterov
    • Categories Convex Optimization Tags , , , ,

    In this paper we propose new methods for solving huge-scale optimization problems. For problems of this size, even the simplest full-dimensional vector operations are very expensive. Hence, we propose to apply an optimization technique based on random partial update of decision variables. For these methods, we prove the global estimates for the rate of convergence. … Read more

    The Maximum Flow Problem with Disjunctive Constraints

  • Ulrich Pferschy
  • Joachim Schauer
    • Categories Graphs and Matroids, Network Optimization Tags , ,

    We study the maximum flow problem subject to binary disjunctive constraints in a directed graph: A negative disjunctive constraint states that a certain pair of arcs in a digraph cannot be simultaneously used for sending flow in a feasible solution. In contrast to this, positive disjunctive constraints force that for certain pairs of arcs at … Read more

    Worst-Case Violation of Sampled Convex Programs for Optimization with Uncertainty

  • Takafumi Kanamori
  • Akiko Takeda
    • Categories Robust Optimization Tags , , , ,

    Uncertain programs have been developed to deal with optimization problems including inexact data, i.e., uncertainty. A deterministic approach called robust optimization is commonly applied to solve these problems. Recently, Calafiore and Campi have proposed a randomized approach based on sampling of constraints, where the number of samples is determined so that only small portion of … Read more

    On the complexity of maximizing the minimum Shannon capacity in wireless networks by joint channel assignment and power allocation

  • Mikael Fallgren
    • Categories Telecommunications Tags ,

    We consider wireless telecommunications systems with orthogonal frequency bands, where each band is referred to as a channel, e.g., orthogonal frequencydivision multiple access (OFDMA). For a snap-shot in time, a joint channel assignment and power allocation optimization problem is presented, both in downlink and in uplink, where the objective is to maximize the minimum total … Read more

    Copositivity detection by difference-of-convex decomposition and omega-subdivision

  • Immanuel M. Bomze
  • Gabriele Eichfelder
    • Categories Linear, Cone and Semidefinite Programming Tags

    We present three new copositivity tests based upon difference-of-convex (d.c.) decompositions, and combine them to a branch-and-bound algorithm of $\omega$-subdivision type. The tests employ LP or convex QP techniques, but also can be used heuristically using appropriate test points. We also discuss the selection of efficient d.c.~decompositions and propose some preprocessing ideas based on the … Read more

    ^phBcnorms, log-barriers and Cramer transform in optimization

  • Jean-Bernard Lasserre
  • Eduardo Santillan Zeron
    • Categories Constrained Nonlinear Optimization, Convex Optimization

    We show that the Laplace approximation of a supremum by $L^p$-norms has interesting consequences in optimization. For instance, the logarithmic barrier functions (LBF) of a primal convex problem $P$ and its dual $P^*$ appear naturally when using this simple approximation technique for the value function $g$ of $P$ or its Legendre-Fenchel conjugate $g^*$. In addition, … Read more

    A joint+marginal approach to parametric polynomial optimization

  • Jean-Bernard Lasserre
    • Categories Global Optimization, Global Optimization Theory, Semi-definite Programming

    Given a compact parameter set $Y\subset R^p$, we consider polynomial optimization problems $(P_\y$) on $R^n$ whose description depends on the parameter $y\in Y$. We assume that one can compute all moments of some probability measure $\varphi$ on $Y$, absolutely continuous with respect to the Lebesgue measure (e.g. $Y$ is a box or a simplex and … Read more