Adaptive robust optimization problems are usually solved
approximately
by restricting the adaptive decisions to simple parametric decision rules. However, the corresponding approximation error can be ...substantial. In this paper we show that two-stage robust and distributionally robust linear programs can often be reformulated
exactly
as conic programs that scale polynomially with the problem dimensions. Specifically, when the ambiguity set constitutes a 2-Wasserstein ball centered at a discrete distribution, the distributionally robust linear program is equivalent to a copositive program (if the problem has complete recourse) or can be approximated arbitrarily closely by a sequence of copositive programs (if the problem has sufficiently expensive recourse). These results directly extend to the classical robust setting and motivate strong tractable approximations of two-stage problems based on semidefinite approximations of the copositive cone. We also demonstrate that the two-stage distributionally robust optimization problem is equivalent to a tractable linear program when the ambiguity set constitutes a 1-Wasserstein ball centered at a discrete distribution and there are no support constraints.
The online appendix is available at
https://doi.org/10.1287/opre.2017.1698
.
In this paper, we focus on the “positive” l2 induced norm of discrete-time linear time-invariant systems where the input signals are restricted to be nonnegative. To cope with the nonnegativity of ...the input signals, we employ copositive programming as the mathematical tool for the analysis. Then, by applying an inner approximation to the copositive cone, we derive numerically tractable semidefinite programming problems for the upper and lower bound computation of the “positive” l2 induced norm. This norm is typically useful for the stability analysis of feedback systems constructed from an LTI system and nonlinearities where the nonlinear elements provide only nonnegative signals. As a concrete example, we illustrate the usefulness of the “positive” l2 induced norm for the stability analysis of recurrent neural networks with activation functions being rectified linear units.
Recently and simultaneously, two MILP-based approaches to copositivity testing were proposed. This note tries a performance comparison, using a group of test sets containing a large number of ...designed instances. According to the numerical results, we find that one copositivity detection approach performs better when the function value of the defined function h of a matrix is large while the other one performs better when the dimension of problems is increasing moderately. A problem set that is hard for both approaches is also presented, which may be used as a test bed for future competing approaches. An improved variant of one of the approaches is also proposed to handle those hard instances more efficiently.
•A matrix parameter is proposed for predicting the difficulty of copositivity checks.•A guide for choosing among two up-to-date copositivity checks instance by instance is provided according to the parameter.•A hard problem set for copositivity test is presented, which may be used as a test bed for future competing approaches.•An improved variant of one of the approaches is proposed to handle those hard instances properly.
In this article, we address Bayesian persuasion between a sender and a receiver with state-dependent quadratic cost measures for general classes of distributions. The receiver seeks to make ...mean-square-error estimate of a state based on a signal sent by the sender while the sender signals strategically in order to control the receiver's estimate in a certain way. Such a scheme could model, e.g., deception and privacy, problems in multiagent systems. Existing solution concepts are not viable since here the receiver has continuous action space. We show that for finite state spaces, optimal signaling strategies can be computed through an equivalent linear optimization problem over the cone of completely positive matrices. We then establish its strong duality to a copositive program. To exemplify the effectiveness of this equivalence result, we adopt sequential polyhedral approximation of completely positive cones and analyze its performance numerically. We also quantify the approximation error for a quantized version of a continuous distribution and show that a semi-definite program relaxation of the equivalent problem could be a benchmark lower bound for the sender's cost for large state spaces.
The paper is devoted to the regularization of linear Copositive Programming problems which consists of transforming a problem to an equivalent form, where the Slater condition is satisfied and ...therefore the strong duality holds. We describe regularization algorithms based on a concept of immobile indices and on the understanding of the important role that these indices play in the feasible sets' characterization. These algorithms are compared to some regularization procedures developed for a more general case of convex problems and based on a facial reduction approach. We show that the immobile-index-based approach combined with the specifics of copositive problems allows us to construct more explicit and detailed regularization algorithms for linear Copositive Programming problems than those already available.
Let G be a directed acyclic graph with n arcs, a source s and a sink t. We introduce the cone K of flow matrices, which is a polyhedral cone generated by the matrices 1P1TP∈Rn×n, where 1P∈Rn is the ...incidence vector of the (s,t)–path P. Several combinatorial problems reduce to a linear optimization problem over K. This cone is intractable, but we provide two convergent approximation hierarchies, one of them based on a completely positive representation of K. We illustrate this approach by computing bounds for a maximum flow problem with pairwise arc-capacities.
We first provide an inner-approximation hierarchy described by a sum-of-squares (SOS) constraint for the copositive (COP) cone over a general symmetric cone. The hierarchy is a generalization of that ...proposed by Parrilo (Structured semidefinite programs and semialgebraic geometry methods in Robustness and optimization, Ph.D. Thesis, California Institute of Technology, Pasadena, CA, 2000) for the usual COP cone (over a nonnegative orthant). We also discuss its dual. Second, we characterize the COP cone over a symmetric cone using the usual COP cone. By replacing the usual COP cone appearing in this characterization with the inner- or outer-approximation hierarchy provided by de Klerk and Pasechnik (SIAM J Optim 12(4):875–892,
https://doi.org/10.1137/S1052623401383248
, 2002) or Yıldırım (Optim Methods Softw 27(1):155–173,
https://doi.org/10.1080/10556788.2010.540014
, 2012), we obtain an inner- or outer-approximation hierarchy described by semidefinite but not by SOS constraints for the COP matrix cone over the direct product of a nonnegative orthant and a second-order cone. We then compare them with the existing hierarchies provided by Zuluaga et al. (SIAM J Optim 16(4):1076–1091,
https://doi.org/10.1137/03060151X
, 2006) and Lasserre (Math Program 144:265–276,
https://doi.org/10.1007/s10107-013-0632-5
, 2014). Theoretical and numerical examinations imply that we can numerically increase a depth parameter, which determines an approximation accuracy, in the approximation hierarchies derived from de Klerk and Pasechnik (SIAM J Optim 12(4):875–892,
https://doi.org/10.1137/S1052623401383248
, 2002) and Yıldırım (Optim Methods Softw 27(1):155–173,
https://doi.org/10.1080/10556788.2010.540014
, 2012), particularly when the nonnegative orthant is small. In such a case, the approximation hierarchy derived from Yıldırım (Optim Methods Softw 27(1):155–173,
https://doi.org/10.1080/10556788.2010.540014
, 2012) can yield nearly optimal values numerically. Combining the proposed approximation hierarchies with existing ones, we can evaluate the optimal value of COP programming problems more accurately and efficiently.
PDF
