-
作者：Cucker, Felipe; Pena, Javier; Roshchina, Vera
作者单位：City University of Hong Kong; Carnegie Mellon University; Federation University Australia
摘要：We describe and analyze an interior-point method to decide feasibility problems of second-order conic systems. A main feature of our algorithm is that arithmetic operations are performed with finite precision. Bounds for both the number of arithmetic operations and the finest precision required are exhibited.
-
作者：Hanasusanto, Grani A.; Roitch, Vladimir; Kuhn, Daniel; Wiesemann, Wolfram
作者单位：Imperial College London; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Imperial College London
摘要：The objective of uncertainty quantification is to certify that a given physical, engineering or economic system satisfies multiple safety conditions with high probability. A more ambitious goal is to actively influence the system so as to guarantee and maintain its safety, a scenario which can be modeled through a chance constrained program. In this paper we assume that the parameters of the system are governed by an ambiguous distribution that is only known to belong to an ambiguity set chara...
-
作者：Bansal, Nikhil; Nagarajan, Viswanath
作者单位：Eindhoven University of Technology; University of Michigan System; University of Michigan
摘要：The input to the stochastic orienteering problem (Gupta et al. in SODA, pp 1522-1538, 2012) consists of a budget B and metric (V, d) where each vertex has a job with a deterministic reward and a random processing time (drawn from a known distribution). The processing times are independent across vertices. The goal is to obtain a non-anticipatory policy (originating from a given root vertex) to run jobs at different vertices, that maximizes expected reward, subject to the total distance travele...
-
作者：Nie, Jiawang
作者单位：University of California System; University of California San Diego
摘要：Let be a finite subset of and be the space spanned by monomials with . Let be a compact semialgebraic set of such that a polynomial in is positive on . Denote by the cone of polynomials in that are nonnegative on . The dual cone of is , the set of all truncated moment sequences in that admit representing measures supported in . First, we study geometric properties of the cones and (like interiors, closeness, duality, memberships), and construct a convergent hierarchy of semidefinite relaxation...
-
作者：Van Hentenryck, P.; Coffrin, C.
作者单位：NICTA; Australian National University
摘要：This paper studies the use of mathematical programming for the repair and restoration of a transmission system after a significant disruption (e.g., a natural disaster). Such blackouts may last several days and have significant impact on human and economic welfare. The transmission system repair and restoration problem (TSRRP) consists in dispatching crews to repair damaged electrical components in order to minimize the size of the blackout. The TSRRP can be modeled as a large-scale mixed nonl...
-
作者：Boland, N. L.; Eberhard, A. C.
作者单位：University of Newcastle; Royal Melbourne Institute of Technology (RMIT)
摘要：We consider the augmented Lagrangian dual for integer programming, and provide a primal characterization of the resulting bound. As a corollary, we obtain proof that the augmented Lagrangian is a strong dual for integer programming. We are able to show that the penalty parameter applied to the augmented Lagrangian term may be placed at a fixed, large value and still obtain strong duality for pure integer programs.
-
作者：Amelunxen, Dennis; Buergisser, Peter
作者单位：University of Manchester; Technical University of Berlin
摘要：We express the probability distribution of the solution of a random (standard Gaussian) instance of a convex cone program in terms of the intrinsic volumes and curvature measures of the reference cone. We then compute the intrinsic volumes of the cone of positive semidefinite matrices over the real numbers, over the complex numbers, and over the quaternions in terms of integrals related to Mehta's integral. In particular, we obtain a closed formula for the probability that the solution of a ra...
-
作者：Lee, James R.; Mendel, Manor; Moharrami, Mohammad
作者单位：University of Washington; University of Washington Seattle; Open University Israel
摘要：The classical Okamura-Seymour theorem states that for an edge-capacitated, multi-commodity flow instance in which all terminals lie on a single face of a planar graph, there exists a feasible concurrent flow if and only if the cut conditions are satisfied. Simple examples show that a similar theorem is impossible in the node-capacitated setting. Nevertheless, we prove that an approximate flow/cut theorem does hold: For some universal epsilon > 0, if the node cut conditions are satisfied, then ...
-
作者：Bomze, Immanuel M.; Overton, Michael L.
作者单位：University of Vienna; New York University
摘要：We study the Celis-Dennis-Tapia (CDT) problem: minimize a non-convex quadratic function over the intersection of two ellipsoids. In contrast to the well-studied trust region problem where the feasible set is just one ellipsoid, the CDT problem is not yet fully understood. Our main objective in this paper is to narrow the difficulty gap that occurs when the Hessian of the Lagrangian is indefinite at all Karush-Kuhn-Tucker points. We prove new sufficient and necessary conditions both for local a...
-
作者：Bot, Radu Ioan; Csetnek, Erno Robert; Heinrich, Andre; Hendrich, Christopher
作者单位：University of Vienna; Technische Universitat Chemnitz
摘要：We present two modified versions of the primal-dual splitting algorithm relying on forward-backward splitting proposed in V (Adv Comput Math 38(3):667-681, 2013) for solving monotone inclusion problems. Under strong monotonicity assumptions for some of the operators involved we obtain for the sequences of iterates that approach the solution orders of convergence of and , for , respectively. The investigated primal-dual algorithms are fully decomposable, in the sense that the operators are proc...
