排序方式: 共有30条查询结果,搜索用时 0 毫秒
1.
Anstreicher 《Discrete and Computational Geometry》2002,28(1):107-114
Abstract. Let S\subset[-1,1) . A finite set \Ccal=\set x
i
i=1
M
\subset\Re
n
is called a spherical S-code if \norm x
i
=1 for each i , and x
i
\tran x
j
∈ S , i\ne j . For S=[-1, 0.5] maximizing M=|C| is commonly referred to as the kissing number problem. A well-known technique based on harmonic analysis and linear programming can be used to bound M . We consider a modification of the bounding procedure that is applicable to antipodal codes; that is, codes where x∈\Ccal\implies -x∈\Ccal . Such codes correspond to packings of lines in the unit sphere, and include all codes obtained as the collection of minimal
vectors in a lattice. We obtain improvements in upper bounds for kissing numbers attainable by antipodal codes in dimensions
16≤ n≤ 23 . We also show that for n=4 , 6 and 7 the antipodal codes with maximal kissing numbers are essentially unique, and correspond to the minimal vectors
in the laminated lattices \Lam
n
. 相似文献
2.
3.
Kurt M. Anstreicher 《Mathematical Programming》1997,76(1):245-263
We consider the construction of small step path following algorithms using volumetric, and mixed volumetric-logarithmic, barriers.
We establish quadratic convergence of a volumetric centering measure using pure Newton steps, enabling us to use relatively
standard proof techniques for several subsequently needed results. Using a mixed volumetric-logarithmic barrier we obtain
an O(n
1/4
m
1/4
L) iteration algorithm for linear programs withn variables andm inequality constraints, providing an alternative derivation for results first obtained by Vaidya and Atkinson. In addition,
we show that the same iteration complexity can be attained while holding the work per iteration to O(n
2
m), as opposed to O(nm
2), operations, by avoiding use of the true Hessian of the volumetric barrier. Our analysis also provides a simplified proof
of self-concordancy of the volumetric and mixed volumetric-logarithmic barriers, originally due to Nesterov and Nemirovskii.
This paper was first presented at the 1994 Faculty Research Seminar “Optimization in Theory and Practice”, at the University
of Iowa Center for Advanced Studies. 相似文献
4.
The cone of Completely Positive (CP) matrices can be used to exactly formulate a variety of NP-Hard optimization problems. A tractable relaxation for CP matrices is provided by the cone of Doubly Nonnegative (DNN) matrices; that is, matrices that are both positive semidefinite and componentwise nonnegative. A natural problem in the optimization setting is then to separate a given DNN but non-CP matrix from the cone of CP matrices. We describe two different constructions for such a separation that apply to 5 × 5 matrices that are DNN but non-CP. We also describe a generalization that applies to larger DNN but non-CP matrices having block structure. Computational results illustrate the applicability of these separation procedures to generate improved bounds on difficult problems. 相似文献
5.
6.
We consider the problem of finding a maximum-weight complementary basis of anm × 2m matrix. The problem arises naturally, for example, when a complementary set of columns is proposed as an initial basis for a warm start of Lemke's algorithm, but the set of columns is rank-deficient. We show that the problem is a special case of the problem of finding a maximum-weight common base of two matroids. Furthermore, we show how to efficiently implement an algorithm for the general problem in the present context. Finally, we give computational results demonstrating the practicality of our algorithm in a typical application.Supported by the Canadian Natural Science and Engineering Research Council. 相似文献
7.
Solving large quadratic assignment problems on computational grids 总被引:10,自引:0,他引:10
Kurt Anstreicher Nathan Brixius Jean-Pierre Goux Jeff Linderoth 《Mathematical Programming》2002,91(3):563-588
The quadratic assignment problem (QAP) is among the hardest combinatorial optimization problems. Some instances of size n = 30 have remained unsolved for decades. The solution of these problems requires both improvements in mathematical programming
algorithms and the utilization of powerful computational platforms. In this article we describe a novel approach to solve
QAPs using a state-of-the-art branch-and-bound algorithm running on a federation of geographically distributed resources known
as a computational grid. Solution of QAPs of unprecedented complexity, including the nug30, kra30b, and tho30 instances, is
reported.
Received: September 29, 2000 / Accepted: June 5, 2001?Published online October 2, 2001 相似文献
8.
Let ${\mathcal{C}}$ be the convex hull of points ${{\{{1 \choose x}{1 \choose x}^T \,|\, x\in \mathcal{F}\subset \Re^n\}}}$ . Representing or approximating ${\mathcal{C}}$ is a fundamental problem for global optimization algorithms based on convex relaxations of products of variables. We show that if n ≤ 4 and ${\mathcal{F}}$ is a simplex, then ${\mathcal{C}}$ has a computable representation in terms of matrices X that are doubly nonnegative (positive semidefinite and componentwise nonnegative). We also prove that if n = 2 and ${\mathcal{F}}$ is a box, then ${\mathcal{C}}$ has a representation that combines semidefiniteness with constraints on product terms obtained from the reformulation-linearization technique (RLT). The simplex result generalizes known representations for the convex hull of ${{\{(x_1, x_2, x_1x_2)\,|\, x\in\mathcal{F}\}}}$ when ${\mathcal{F}\subset\Re^2}$ is a triangle, while the result for box constraints generalizes the well-known fact that in this case the RLT constraints generate the convex hull of ${{\{(x_1, x_2, x_1x_2)\,|\, x\in\mathcal{F}\}}}$ . When n = 3 and ${\mathcal{F}}$ is a box, we show that a representation for ${\mathcal{C}}$ can be obtained by utilizing the simplex result for n = 4 in conjunction with a triangulation of the 3-cube. 相似文献
9.
Kurt M. Anstreicher 《Journal of Global Optimization》2018,72(4):603-618
We consider a bound for the maximum-entropy sampling problem (MESP) that is based on solving a max-det problem over a relaxation of the Boolean quadric polytope (BQP). This approach to MESP was first suggested by Christoph Helmberg over 15 years ago, but has apparently never been further elaborated or computationally investigated. We find that the use of a relaxation of BQP that imposes semidefiniteness and a small number of equality constraints gives excellent bounds on many benchmark instances. These bounds can be further tightened by imposing additional inequality constraints that are valid for the BQP. Duality information associated with the BQP-based bounds can be used to fix variables to 0/1 values, and also as the basis for the implementation of a “strong branching” strategy. A branch-and-bound algorithm using the BQP-based bounds solves some benchmark instances of MESP to optimality for the first time. 相似文献
10.
The standard quadratic program (QPS) is
minxεΔxTQx, where
is the simplex Δ = {x ⩽ 0 ∣ ∑i=1n xi = 1}. QPS can be used to formulate combinatorial problems such as the maximum stable set problem, and also arises in global
optimization algorithms for general quadratic programming when the search space is partitioned using simplices. One class
of ‘d.c.’ (for ‘difference between convex’) bounds for QPS is based on writing Q=S−T, where S and T are both positive semidefinite, and bounding
xT Sx (convex on Δ) and −xTx
(concave on Δ) separately. We show that the maximum possible such bound can be obtained by solving a semidefinite programming
(SDP) problem. The dual of this SDP problem corresponds to adding a simple constraint to the well-known Shor relaxation of
QPS. We show that the max d.c. bound is dominated by another known bound based on a copositive relaxation of QPS, also obtainable
via SDP at comparable computational expense. We also discuss extensions of the d.c. bound to more general quadratic programming
problems. For the application of QPS to bounding the stability number of a graph, we use a novel formulation of the Lovasz
ϑ number to compare ϑ, Schrijver’s ϑ′, and the max d.c. bound. 相似文献