共查询到20条相似文献,搜索用时 31 毫秒
1.
A. Barvinok 《Discrete and Computational Geometry》1997,18(2):205-237
We construct a probabilistic polynomial time algorithm that computes the mixed discriminant of given n positive definite matrices within a 2
O(n)
factor. As a corollary, we show that the permanent of an nonnegative matrix and the mixed volume of n ellipsoids in R
n
can be computed within a 2
O(n)
factor by probabilistic polynomial time algorithms. Since every convex body can be approximated by an ellipsoid, the last
algorithm can be used for approximating in polynomial time the mixed volume of n convex bodies in R
n
within a factor n
O(n)
.
Received July 10, 1995, and in revised form May 20, 1996. 相似文献
2.
Alexander Barvinok 《Random Structures and Algorithms》1999,14(1):29-61
We present real, complex, and quaternionic versions of a simple randomized polynomial time algorithm to approximate the permanent of a nonnegative matrix and, more generally, the mixed discriminant of positive semidefinite matrices. The algorithm provides an unbiased estimator, which, with high probability, approximates the true value within a factor of O(cn), where n is the size of the matrix (matrices) and where c ≈ 0.28 for the real version, c ≈ 0.56 for the complex version, and c ≈ 0.76 for the quaternionic version. We discuss possible extensions of our method as well as applications of mixed discriminants to problems of combinatorial counting. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14, 29–61, 1999 相似文献
3.
Immanuel M. Bomze Werner Schachinger Gabriele Uchida 《Journal of Global Optimization》2012,52(3):423-445
Copositive optimization is a quickly expanding scientific research domain with wide-spread applications ranging from global
nonconvex problems in engineering to NP-hard combinatorial optimization. It falls into the category of conic programming (optimizing
a linear functional over a convex cone subject to linear constraints), namely the cone C{\mathcal{C}} of all completely positive symmetric n × n matrices (which can be factorized into FFT{FF^\top} , where F is a rectangular matrix with no negative entry), and its dual cone C*{\mathcal{C}^*} , which coincides with the cone of all copositive matrices (those which generate a quadratic form taking no negative value
over the positive orthant). We provide structural algebraic properties of these cones, and numerous (counter-)examples which
demonstrate that many relations familiar from semidefinite optimization may fail in the copositive context, illustrating the
transition from polynomial-time to NP-hard worst-case behaviour. In course of this development we also present a systematic
construction principle for non-attainability phenomena, which apparently has not been noted before in an explicit way. Last
but not least, also seemingly for the first time, a somehow systematic clustering of the vast and scattered literature is
attempted in this paper. 相似文献
4.
Immanuel M. Bomze Mirjam Dür Etienne de Klerk Cornelis Roos Arie J. Quist Tamás Terlaky 《Journal of Global Optimization》2000,18(4):301-320
A standard quadratic problem consists of finding global maximizers of a quadratic form over the standard simplex. In this paper, the usual semidefinite programming relaxation is strengthened by replacing the cone of positive semidefinite matrices by the cone of completely positive matrices (the positive semidefinite matrices which allow a factorization FF
T where F is some non-negative matrix). The dual of this cone is the cone of copositive matrices (i.e., those matrices which yield a non-negative quadratic form on the positive orthant). This conic formulation allows us to employ primal-dual affine-scaling directions. Furthermore, these approaches are combined with an evolutionary dynamics algorithm which generates primal-feasible paths along which the objective is monotonically improved until a local solution is reached. In particular, the primal-dual affine scaling directions are used to escape from local maxima encountered during the evolutionary dynamics phase. 相似文献
5.
Given a linear transformation L:?
n
→?
n
and a matrix Q∈?
n
, where ?
n
is the space of all symmetric real n×n matrices, we consider the semidefinite linear complementarity problem SDLCP(L,?
n
+,Q) over the cone ?
n
+ of symmetric n×n positive semidefinite matrices. For such problems, we introduce the P-property and its variants, Q- and GUS-properties. For a matrix A∈R
n×n
, we consider the linear transformation L
A
:?
n
→?
n
defined by L
A
(X):=AX+XA
T
and show that the P- and Q-properties for L
A
are equivalent to A being positive stable, i.e., real parts of eigenvalues of A are positive. As a special case of this equivalence, we deduce a theorem of Lyapunov.
Received: March 1999 / Accepted: November 1999?Published online April 20, 2000 相似文献
6.
Suliman Al-Homidan Mohammad M. Alshahrani Cosmin G. Petra Florian A. Potra 《Linear algebra and its applications》2010,433(6):1101-1109
We present a semidefinite programming approach for computing optimally conditioned positive definite Hankel matrices of order n. Unlike previous approaches, our method is guaranteed to find an optimally conditioned positive definite Hankel matrix within any desired tolerance. Since the condition number of such matrices grows exponentially with n, this is a very good test problem for checking the numerical accuracy of semidefinite programming solvers. Our tests show that semidefinite programming solvers using fixed double precision arithmetic are not able to solve problems with n>30. Moreover, the accuracy of the results for 24?n?30 is questionable. In order to accurately compute minimal condition number positive definite Hankel matrices of higher order, we use a Mathematica 6.0 implementation of the SDPHA solver that performs the numerical calculations in arbitrary precision arithmetic. By using this code, we have validated the results obtained by standard codes for n?24, and we have found optimally conditioned positive definite Hankel matrices up to n=100. 相似文献
7.
Paul Tseng 《Journal of Global Optimization》2004,30(2):285-300
We study convergence properties of Dikins affine scaling algorithm applied to nonconvex quadratic minimization. First, we show that the objective function value either diverges or converges Q-linearly to a limit. Using this result, we show that, in the case of box constraints, the iterates converge to a unique point satisfying first-order and weak second-order optimality conditions, assuming the objective function Hessian Q is rank dominant with respect to the principal submatrices that are maximally positive semidefinite. Such Q include matrices that are positive semidefinite or negative semidefinite or nondegenerate or have negative diagonals. Preliminary numerical experience is reported. 相似文献
8.
Fully copositive matrices 总被引:1,自引:0,他引:1
The class of fully copositive (C
0
f
) matrices introduced in [G.S.R. Murthy, T. Parthasarathy, SIAM Journal on Matrix Analysis and Applications 16 (4) (1995) 1268–1286] is a subclass of fully semimonotone matrices and contains the class of positive semidefinite matrices. It is shown that fully copositive matrices within the class ofQ
0-matrices areP
0-matrices. As a corollary of this main result, we establish that a bisymmetricQ
0-matrix is positive semidefinite if, and only if, it is fully copositive. Another important result of the paper is a constructive characterization ofQ
0-matrices within the class ofC
0
f
. While establishing this characterization, it will be shown that Graves's principal pivoting method of solving Linear Complementarity Problems (LCPs) with positive semidefinite matrices is also applicable toC
0
f
Q
0 class. As a byproduct of this characterization, we observe that aC
0
f
-matrix is inQ
0 if, and only if, it is completelyQ
0. Also, from Aganagic and Cottle's [M. Aganagic, R.W. Cottle, Mathematical Programming 37 (1987) 223–231] result, it is observed that LCPs arising fromC
0
f
Q
0 class can be processed by Lemke's algorithm. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Corresponding author. 相似文献
9.
This article studies some geometrical aspects of the semidefinite linear complementarity problem (SDLCP), which can be viewed as a generalization of the well-known linear complementarity problem (LCP). SDLCP is a special case of a complementarity problem over a closed convex cone, where the cone considered is the closed convex cone of positive semidefinite matrices. It arises naturally in the unified formulation of a pair of primal-dual semidefinite programming problems. In this article, we introduce the notion of complementary cones in the semidefinite setting using the faces of the cone of positive semidefinite matrices and show that unlike complementary cones induced by an LCP, semidefinite complementary cones need not be closed. However, under R 0-property of the linear transformation, closedness of all the semidefinite complementary cones induced by L is ensured. We also introduce the notion of a principal subtransformation with respect to a face of the cone of positive semidefinite matrices and show that for a self-adjoint linear transformation, strict copositivity is equivalent to strict semimonotonicity of each principal subtransformation. Besides the above, various other solution properties of SDLCP will be interpreted and studied geometrically. 相似文献
10.
Paul Tseng 《Journal of Global Optimization》2004,30(2-3):285-300
We study convergence properties of Dikin’s affine scaling algorithm applied to nonconvex quadratic minimization. First, we show that the objective function value either diverges or converges Q-linearly to a limit. Using this result, we show that, in the case of box constraints, the iterates converge to a unique point satisfying first-order and weak second-order optimality conditions, assuming the objective function Hessian Q is rank dominant with respect to the principal submatrices that are maximally positive semidefinite. Such Q include matrices that are positive semidefinite or negative semidefinite or nondegenerate or have negative diagonals. Preliminary numerical experience is reported. 相似文献
11.
For a number of computational search problems, the existence of a polynomial-time algorithm for the problem implies that a polynomial-time algorithm for the problem is constructively known. Some instances of such self-witnessing polynomial-time complexity are presented. Our main result demonstrates this property for the problem of computing the prime factorization of a positive integer, based on a lemma which shows that a certificate for primality or compositeness can be constructed for a positive integer p in deterministic polynomial time given a complete factorization of p - 1. 相似文献
12.
Proofs of classical Chernoff-Hoeffding bounds has been used to obtain polynomial-time implementations of Spencer's derandomization method of conditional probabilities on usual finite machine models: given m events whose complements are large deviations corresponding to weighted sums of n mutually independent Bernoulli trials. Raghavan's lattice approximation algorithm constructs for 0-1 weights, and integer deviation terms in O(mn)-time a point for which all events hold. For rational weighted sums of Bernoulli trials the lattice approximation algorithm or Spencer's hyperbolic cosine algorithm are deterministic precedures, but a polynomial-time implementation was not known. We resolve this problem with an O(mn2log $ {{mn}\over{\epsilon}} $)-time algorithm, whenever the probability that all events hold is at least ϵ > 0. Since such algorithms simulate the proof of the underlying large deviation inequality in a constructive way, we call it the algorithmic version of the inequality. Applications to general packing integer programs and resource constrained scheduling result in tight and polynomial-time approximations algorithms. © 1996 John Wiley & Sons, Inc. 相似文献
13.
The class of eigenvalue problems for upper Hessenberg matrices of banded-plus-spike form includes companion and comrade matrices as special cases. For this class of matrices a factored form is developed in which the matrix is represented as a product of essentially 2×2 matrices and a banded upper-triangular matrix. A non-unitary analogue of Francis’s implicitly-shifted QR algorithm that preserves the factored form and consequently computes the eigenvalues in O(n 2) time and O(n) space is developed. Inexpensive a posteriori tests for stability and accuracy are performed as part of the algorithm. The results of numerical experiments are mixed but promising in certain areas. The single-shift version of the code applied to companion matrices is much faster than the nearest competitor. 相似文献
14.
A heuristic for decomposing traffic matrices in TDMA satellite communication. With the time-division multiple access (TDMA) technique in satellite communication the problem arises to decompose a givenn×n traffic matrix into a weighted sum of a small number of permutation matrices such that the sum of the weights becomes minimal. There are polynomial algorithms when the number of permutation matrices in a decomposition is allowed to be as large asn
2. When the number of matrices is restricted ton, the problem is NP-hard. In this paper we propose a heuristic based on a scaling technique which for each number of allowed matrices in the range fromn ton
2 allows to give a performance guarantee with respect to the total weight of the solution. As a subroutine we use new heuristic methods for decomposing a matrix of small integers into as few matrices as possible without exceeding the lower bound on the total weight. Computational results indicate that the method might also be practical.This work was supported by the Fonds zur Förderung der wissenschaftlichen Forschung, Project S32/01. 相似文献
15.
In this paper we present a polynomial-time algorithm that finds paths of length Ω((logn/loglogn)2) in undirected Hamiltonian graphs, improving the previous best of Ω(logn). 相似文献
16.
Let Y be a convex set in \Re
k
defined by polynomial inequalities and equations of degree at most d ≥ 2 with integer coefficients of binary length at most l . We show that if the set of optimal solutions of the integer programming problem min is not empty, then the problem has an optimal solution of binary length ld
O(k4)
. For fixed k , our bound implies a polynomial-time algorithm for computing an optimal integral solution y
*
. In particular, we extend Lenstra's theorem on the polynomial-time solvability of linear integer programming in fixed dimension
to semidefinite integer programming.
Received August 3, 1998, and in revised form March 22, 1999. 相似文献
17.
This paper deals with the problem of projecting polytopes in finite-dimensional Euclidean spaces on subspaces of given dimension
so as to maximize or minimize the volume of the projection.
As to the computational complexity of the underlying decision problems we show that maximizing the volume of the orthogonal
projection on hyperplanes is already NP-hard for simplices. For minimization, the problem is easy for simplices but NP-hard for bipyramids over parallelotopes. Similar results are given for projections on lower-dimensional subspaces. Several
other related NP-hardness results are also proved including one for inradius computation of zonotopes and another for a location problem.
On the positive side, we present various polynomial-time approximation algorithms. In particular, we give a randomized algorithm
for maximizing orthogonal projections of CH-polytopes in R
n
on hyperplanes with an error bound of essentially .
Received February 17, 1999. 相似文献
18.
Janez Povh 《Journal of Global Optimization》2010,48(3):447-463
Finding global optimum of a non-convex quadratic function is in general a very difficult task even when the feasible set is
a polyhedron. We show that when the feasible set of a quadratic problem consists of orthogonal matrices from
\mathbbRn×k{\mathbb{R}^{n\times k}} , then we can transform it into a semidefinite program in matrices of order kn which has the same optimal value. This opens new possibilities to get good lower bounds for several problems from combinatorial
optimization, like the Graph partitioning problem (GPP), the Quadratic assignment problem (QAP) etc. In particular we show how to improve significantly the well-known Donath-Hoffman eigenvalue lower bound for GPP
by semidefinite programming. In the last part of the paper we show that the copositive strengthening of the semidefinite lower
bounds for GPP and QAP yields the exact values. 相似文献
19.
Cheriyan and Hagerup developed a randomized algorithm to compute the maximum flow in a graph with n nodes and m edges in O(mn + n2 log2n) expected time. The randomization is used to efficiently play a certain combinatorial game that arises during the computation. We give a version of their algorithm where a general version of their game arises. Then we give a strategy for the game that yields a deterministic algorithm for computing the maximum flow in a directed graph with n nodes and m edges that runs in time O(mn(logm/n log nn)). Our algorithm gives an O(mn) deterministic algorithm for all m/n = Ω(nε) for any positive constant ε, and is currently the fastest deterministic algorithm for computing maximum flow as long as m/n = ω(log n). 相似文献
20.
François Oustry 《Mathematical Programming》2000,89(1):1-33
In this paper we present a nonsmooth algorithm to minimize the maximum eigenvalue of matrices belonging to an affine subspace
of n×n symmetric matrices. We show how a simple bundle method, the approximate eigenvalue method can be used to globalize the second-order method developed by M.L. Overton in the eighties and recently revisited in the
framework of the ?-Lagrangian theory. With no additional assumption, the resulting algorithm generates a minimizing sequence.
A geometrical and constructive proof is given. To prove that quadratic convergence is achieved asymptotically, some strict complementarity and non-degeneracy assumptions are needed. We also introduce new variants of bundle methods for semidefinite programming.
Received: February 9, 1998 / Accepted: May 2, 2000?Published online September 20, 2000 相似文献