Linear, Cone and Semidefinite Programming

Ambiguous Chance-Constrained Binary Programs under Mean-Covariance Information

  • Ruiwei Jiang
  • Siqian Shen
  • Yiling Zhang
    • Categories 0-1 Programming, Second-Order Cone Programming, Stochastic Programming

    We consider chance-constrained binary programs, where each row of the inequalities that involve uncertainty needs to be satis ed probabilistically. Only the information of the mean and covariance matrix is available, and we solve distributionally robust chance-constrained binary programs (DCBP). Using two different ambiguity sets, we equivalently reformulate the DCBPs as 0-1 second-order cone (SOC) programs. … Read more

    Positive and Z-operators on closed convex cones

  • Michael Orlitzky
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , , ,

    Let K be a closed convex cone with dual K-star in a finite-dimensional real Hilbert space V. A positive operator on K is a linear operator L on V such that L(K) is a subset of K. Positive operators generalize the nonnegative matrices and are essential to the Perron-Frobenius theory. We say that L is … Read more

    Max-Norm Optimization for Robust Matrix Recovery

  • Ethan Fang
  • Kim-Chuan Toh
  • Han Liu
  • Wen-Xin Zhou
    • Categories Convex Optimization, Semi-definite Programming, Statistics Tags , , ,

    This paper studies the matrix completion problem under arbitrary sampling schemes. We propose a new estimator incorporating both max-norm and nuclear-norm regularization, based on which we can conduct efficient low-rank matrix recovery using a random subset of entries observed with additive noise under general non-uniform and unknown sampling distributions. This method significantly relaxes the uniform … Read more

    A Copositive Approach for Two-Stage Adjustable Robust Optimization with Uncertain Right-Hand Sides

  • Samuel Burer
  • Guanglin Xu
    • Categories Dynamic Programming, Linear, Cone and Semidefinite Programming, Robust Optimization Tags , , , , ,

    We study two-stage adjustable robust linear programming in which the right-hand sides are uncertain and belong to a convex, compact uncertainty set. This problem is NP-hard, and the affine policy is a popular, tractable approximation. We prove that under standard and simple conditions, the two-stage problem can be reformulated as a copositive optimization problem, which … Read more

    Quadratic Two-Stage Stochastic Optimization with Coherent Measures of Risk

  • Rodrigues Brian
  • Lizhi Liao
  • Jie Sun
    • Categories Linear, Cone and Semidefinite Programming, Robust Optimization, Stochastic Programming

    A new scheme to cope with two-stage stochastic optimization problems uses a risk measure as the objective function of the recourse action, where the risk measure is defined as the worst-case expected values over a set of constrained distributions. This paper develops an approach to deal with the case where both the first and second … Read more

    On the identification of optimal partition for semidefinite optimization

  • Ali Mohammad-Nezhad
  • Tamás Terlaky
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming

    The concept of the optimal partition was originally introduced for linear optimization and linear complementarity problems and subsequently extended to semidefinite optimization. For linear optimization and sufficient linear complementarity problems, from a central solution sufficiently close to the optimal set, the optimal partition and a maximally complementary optimal solution can be identified in strongly polynomial … Read more

    Convergence rates of moment-sum-of-squares hierarchies for optimal control problems

  • Didier Henrion
  • Colin N. Jones
  • Milan Korda
    • Categories Control Applications, Semi-definite Programming, Systems governed by Differential Equations Optimization Tags , , , ,

    We study the convergence rate of moment-sum-of-squares hierarchies of semidefinite programs for optimal control problems with polynomial data. It is known that these hierarchies generate polynomial under-approximations to the value function of the optimal control problem and that these under-approximations converge in the $L^1$ norm to the value function as their degree $d$ tends to … Read more

    A generalized simplex method for integer problems given by verification oracles

  • Sergei Chubanov
    • Categories Integer Programming, Linear Programming Tags , , ,

    We consider a linear problem over a finite set of integer vectors and assume that there is a verification oracle, which is an algorithm being able to verify whether a given vector optimizes a given linear function over the feasible set. Given an initial solution, the algorithm proposed in this paper finds an optimal solution … Read more

    A Riemannian conjugate gradient method for optimization on the Stiefel manifold

  • Xiaojing Zhu
    • Categories Applications - Science and Engineering, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , , , ,

    In this paper we propose a new Riemannian conjugate gradient method for optimization on the Stiefel manifold. We introduce two novel vector transports associated with the retraction constructed by the Cayley transform. Both of them satisfy the Ring-Wirth nonexpansive condition, which is fundamental for convergence analysis of Riemannian conjugate gradient methods, and one of them … Read more

    On max-k-sums

  • Michael J. Todd
    • Categories Basic Sciences Applications, Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    The max-$k$-sum of a set of real scalars is the maximum sum of a subset of size $k$, or alternatively the sum of the $k$ largest elements. We study two extensions: First, we show how to obtain smooth approximations to functions that are pointwise max-$k$-sums of smooth functions. Second, we discuss how the max-$k$-sum can … Read more