-
作者：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...
-
作者：He, Qie; Ahmed, Shabbir; Nemhauser, George L.
作者单位：University of Minnesota System; University of Minnesota Twin Cities; University System of Georgia; Georgia Institute of Technology
摘要：The minimum concave cost network flow problem (MCCNFP) is NP-hard, but efficient polynomial-time algorithms exist for some special cases such as the uncapacitated lot-sizing problem and many of its variants. We study the MCCNFP over a grid network with a general nonnegative separable concave cost function. We show that this problem is polynomially solvable when all sources are in the first echelon and all sinks are in two echelons, and when there is a single source but many sinks in multiple e...
-
作者：Huang, Chien-Chung; Kavitha, Telikepalli
作者单位：Chalmers University of Technology; Tata Institute of Fundamental Research (TIFR)
摘要：We consider the problem of computing a large stable matching in a bipartite graph where each vertex ranks its neighbors in an order of preference, perhaps involving ties. Let the matched partner of u in a matching M be M(u). A matching M is said to be stable if there is no edge (a, b) such that a is unmatched or prefers b to M(a) and similarly, b is unmatched or prefers a to M(b). While a stable matching in G can be easily computed in linear time by the Gale-Shapley algorithm, it is known that...
-
作者：Chubanov, Sergei
作者单位：Universitat Siegen
摘要：We propose a polynomial algorithm for linear feasibility problems. The algorithm represents a linear problem in the form of a system of linear equations and non-negativity constraints. Then it uses a procedure which either finds a solution for the respective homogeneous system or provides the information based on which the algorithm rescales the homogeneous system so that its feasible solutions in the unit cube get closer to the vector of all ones. In a polynomial number of calls to the proced...
