-
作者：Pataki, G
作者单位：Columbia University
摘要：We derive some basic results on the geometry of semidefinite programming (SDP) and eigenvalue-optimization, i.e., the minimization of the sum of the k largest eigenvalues of a smooth matrix-valued function. We provide upper bounds on the rank of extreme matrices in SDPs, and the first theoretically solid explanation of a phenomenon of intrinsic interest in eigenvalue-optimization. In the spectrum of an optimal matrix, the kth and (k + 1)st largest eigenvalues tend to be equal and frequently ha...
-
作者：Heath, D; Resnick, S; Samorodnitsky, G
作者单位：Cornell University
摘要：On/off models are common inputs for a variety of communication network models as well as storage and inventory models. A stationary renewal process alternating periods of activity (active transmission, fluid buildup, etc) with periods of inactivity (silence, no transmission, inputs off, etc) induces a stationary indicator process which indicates if the system is active or not. Heavy tails for the on periods induces a covariance function for the indicator process which decreases slowly at a rat...
-
作者：Burkard, RE; Deineko, VG; Woeginger, GJ
作者单位：Graz University of Technology; University of Warwick
摘要：Let D = (d(ij)) be the n x n distance matrix of a set of n cities {1, 2,..., n}, and let T be a PQ-tree with node degree bounded by d that represents a set n(T) of permutations over {1, 2,..., n }. We show how to compute for D in O(2(d)n(3)) time the shortest travelling salesman tour contained in n(T). Our algorithm may be interpreted as a common generalization of the well-known Held and Karp dynamic programming algorithm for the TSP and of the dynamic programming algorithm for finding the sho...
-
作者：Teo, CP; Sethuraman, J
作者单位：National University of Singapore; Massachusetts Institute of Technology (MIT)
摘要：We study the classical stable marriage and stable roommates problems using a polyhedral approach. We propose a new LP formulation for the stable roommates problem, which has a feasible solution if and only if the underlying roommates problem has a stable matching. Furthermore, for certain special weight functions on the edges, we construct a a-approximation algorithm for the optimal stable roommates problem. Our technique exploits features of the geometry of fractional solutions of this formul...
-
作者：Monteiro, RDC; Pang, JS
作者单位：University System of Georgia; Georgia Institute of Technology; Johns Hopkins University
摘要：Extending our previous work (Monteiro and Pang 1996), this paper studies properties of two fundamental mappings associated with the family of interior-point methods for solving monotone nonlinear complementarity problems over the cone of symmetric positive semidefinite matrices. The first of these maps lead to a family of new continuous trajectories which include the central trajectory as a special case. These trajectories completely fill up the set of interior feasible points of the problem i...
-
作者：Sznajder, R; Gowda, MS
作者单位：University System of Maryland; Bowie State University; University System of Maryland; University of Maryland Baltimore County
摘要：A zero of a piecewise smooth function Sis said to be nondegenerate if the function is Frechet differentiable at that point. Using this concept, we describe the usual nondegeneracy notions in the settings of nonlinear (vertical, horizontal, mixed) complementarity problems and the variational inequality problem corresponding to a polyhedral convex set. Some properties of nondegenerate zeros of piecewise affine functions are described. We generalize a recent result of Ferris and Pang on the exist...
-
作者：Naiman, DQ; Stone, RE
作者单位：Johns Hopkins University
摘要：A real square matrix M is said to be a e-matrix if the linear complementarity problem (q, M) has a solution for every vector q. There is, as yet, no characterization of e-matrices which makes it easy to determine whether or not a given matrix is Q. Ideas from topology, in particular degree theory, have previously been used to obtain sufficient conditions fdr when a matrix is Q. In this paper we will apply some other ideas from topology to give a homological characterization of Q-matrices. Cont...
-
作者：Li, W; Singer, I
作者单位：Old Dominion University; Institute of Mathematics of the Romanian Academy; Romanian Academy
摘要：We give some results on the existence of global error bounds for convex multifunctions between normed linear spaces (until the present, only some results on local error bounds have been known in this general setting). As applications we obtain, among others, improvements of a theorem of Robinson on global error bounds for convex inequalities, of a result of Luo and Tseng on uniform boundedness of the Hoffman constants for linear inequalities and equalities, and of Lotov's result on pointwise L...
-
作者：Facchinei, F
作者单位：Sapienza University Rome
摘要：We consider P-0 nonlinear complementarity problems and study the connectedness and stability of the solutions by applying degree theory and the Mountain Pass Theorem to a smooth reformulation of the complementarity problem. We show that the solution set is connected and bounded if a bounded isolated component of the solution set exists and that a solution is locally unique if and only if it is globally unique. Furthermore, we prove that a solution is stable in Ha's sense if and only if it is g...
-
作者：Asmussen, S; Perry, D
作者单位：Lund University; University of Haifa
摘要：A distribution G on (0, infinity) is called matrix-exponential if the density has the form alpha e(Tz)s where tu is a row vector, T a square matrix and s a column vector. Equivalently, the Laplace transform is rational. For such distributions, we develop an operator calculus, where the key step is manipulation of analytic functions f(z) extended to matrix arguments. The technique is illustrated via an inventory model moving according to a reflected Brownian motion with negative drift, such tha...
