共查询到20条相似文献,搜索用时 15 毫秒
1.
Monique Laurent 《Mathematical Programming》2007,109(2-3):239-261
We give a hierarchy of semidefinite upper bounds for the maximum size A(n,d) of a binary code of word length n and minimum distance at least d. At any fixed stage in the hierarchy, the bound can be computed (to an arbitrary precision) in time polynomial in n; this is based on a result of de Klerk et al. (Math Program, 2006) about the regular ∗-representation for matrix ∗-algebras.
The Delsarte bound for A(n,d) is the first bound in the hierarchy, and the new bound of Schrijver (IEEE Trans. Inform. Theory 51:2859–2866, 2005) is located
between the first and second bounds in the hierarchy. While computing the second bound involves a semidefinite program with
O(n
7) variables and thus seems out of reach for interesting values of n, Schrijver’s bound can be computed via a semidefinite program of size O(n
3), a result which uses the explicit block-diagonalization of the Terwilliger algebra. We propose two strengthenings of Schrijver’s
bound with the same computational complexity.
Supported by the Netherlands Organisation for Scientific Research grant NWO 639.032.203. 相似文献
2.
Recently A. Schrijver derived new upper bounds for binary codes using semidefinite programming. In this paper we adapt this approach to codes on the unit sphere and we compute new upper bounds for the kissing number in several dimensions. In particular our computations give the (known) values for the cases .
3.
Semidefinite programming (SDP) bounds for the quadratic assignment problem (QAP) were introduced in Zhao et?al. (J Comb Optim 2:71–109, 1998). Empirically, these bounds are often quite good in practice, but computationally demanding, even for relatively small instances. For QAP instances where the data matrices have large automorphism groups, these bounds can be computed more efficiently, as was shown in Klerk and Sotirov (Math Program A, 122(2), 225–246, 2010). Continuing in the same vein, we show how one may obtain stronger bounds for QAP instances where one of the data matrices has a transitive automorphism group. To illustrate our approach, we compute improved lower bounds for several instances from the QAP library QAPLIB. 相似文献
4.
Chek Beng Chua 《Mathematical Programming》2008,115(2):239-271
The purpose of this paper is two-fold. Firstly, we show that every Cholesky-based weighted central path for semidefinite programming
is analytic under strict complementarity. This result is applied to homogeneous cone programming to show that the central
paths defined by the known class of optimal self-concordant barriers are analytic in the presence of strictly complementary
solutions. Secondly, we consider a sequence of primal–dual solutions that lies within a prescribed neighborhood of the central
path of a pair of primal–dual semidefinite programming problems, and converges to the respective optimal faces. Under the
additional assumption of strict complementarity, we derive two necessary and sufficient conditions for the sequence of primal–dual
solutions to converge linearly with their duality gaps.
This research was supported by a grant from the Faculty of Mathematics, University of Waterloo and by a Discovery Grant from
NSERC. 相似文献
5.
In this paper,we consider a class of quadratic maximization problems.For a subclass of the problems,we show that the SDP relaxation approach yields an approximation solution with the ratio is dependent on the data of the problem with α being a uniform lower bound.In light of this new bound,we show that the actual worst-case performance ratio of the SDP relaxation approach (with the triangle inequalities added) is at least α δd if every weight is strictly positive,where δd > 0 is a constant depending on the problem dimension and data. 相似文献
6.
We give a new upper bound on the maximum size Aq(n,d) of a code of word length n and minimum Hamming distance at least d over the alphabet of q?3 letters. By block-diagonalizing the Terwilliger algebra of the nonbinary Hamming scheme, the bound can be calculated in time polynomial in n using semidefinite programming. For q=3,4,5 this gives several improved upper bounds for concrete values of n and d. This work builds upon previous results of Schrijver [A. Schrijver, New code upper bounds from the Terwilliger algebra and semidefinite programming, IEEE Trans. Inform. Theory 51 (2005) 2859-2866] on the Terwilliger algebra of the binary Hamming scheme. 相似文献
7.
8.
Optimality conditions for nonconvex semidefinite programming 总被引:9,自引:0,他引:9
Anders Forsgren 《Mathematical Programming》2000,88(1):105-128
This paper concerns nonlinear semidefinite programming problems for which no convexity assumptions can be made. We derive
first- and second-order optimality conditions analogous to those for nonlinear programming. Using techniques similar to those
used in nonlinear programming, we extend existing theory to cover situations where the constraint matrix is structurally sparse.
The discussion covers the case when strict complementarity does not hold. The regularity conditions used are consistent with
those of nonlinear programming in the sense that the conventional optimality conditions for nonlinear programming are obtained
when the constraint matrix is diagonal.
Received: May 15, 1998 / Accepted: April 12, 2000?Published online May 12, 2000 相似文献
9.
O. R. Musin 《Proceedings of the Steklov Institute of Mathematics》2008,263(1):134-149
Delsarte’s method and its extensions allow one to consider the upper bound problem for codes in two-point homogeneous spaces
as a linear programming problem with perhaps infinitely many variables, which are the distance distribution. We show that
using as variables power sums of distances, this problem can be considered as a finite semidefinite programming problem. This
method allows one to improve some linear programming upper bounds. In particular, we obtain new bounds of one-sided kissing
numbers. 相似文献
10.
Lovász and Schrijver, and later Lasserre, proposed hierarchies of semidefinite programming relaxations for 0/1 linear programming problems. We revisit these two constructions and propose two new, block-diagonal hierarchies, which are at least as strong as the Lovász-Schrijver hierarchy, but less costly to compute. We report experimental results for the stable set problem of Paley graphs. 相似文献
11.
On Weyl-Heisenberg orbits of equiangular lines 总被引:1,自引:0,他引:1
Mahdad Khatirinejad 《Journal of Algebraic Combinatorics》2008,28(3):333-349
An element
is called fiducial if {gz:g∈G} is a set of lines with only one angle between each pair, where G
≅ℤ
d
×ℤ
d
is the one-dimensional finite Weyl-Heisenberg group modulo its centre. We give a new characterization of fiducial vectors.
Using this characterization, we show that the existence of almost flat fiducial vectors implies the existence of certain cyclic
difference sets. We also prove that the construction of fiducial vectors in prime dimensions 7 and 19 due to Appleby (J. Math.
Phys. 46(5):052107, 2005) does not generalize to other prime dimensions (except for possibly a set with density zero). Finally, we use our new characterization
to construct fiducial vectors in dimension 7 and 19 whose coordinates are real.
Research supported by the Natural Sciences and Engineering Research Council of Canada (NSERC). 相似文献
12.
In this paper, for solving the nonlinear semidefinite programming problem, a homotopy is constructed by using the parameterized matrix inequality constraint. Existence of a smooth path determined by the homotopy equation, which starts from almost everywhere and converges to a Karush–Kuhn–Tucker point, is proven under mild conditions. A predictor-corrector algorithm is given for numerically tracing the smooth path. Numerical tests with nonlinear semidefinite programming formulations of several control design problems with the data contained in COMPl e ib are done. Numerical results show that the proposed algorithm is feasible and applicable. 相似文献
13.
14.
《European Journal of Operational Research》2005,164(2):417-422
We extend the concept of ϵ-sensitivity analysis developed for linear programming to that for semidefinite programming. First, the notion of ϵ-optimality for a given semidefinite programming problem is defined, and then a generic ϵ-sensitivity analysis for semidefinite programming is introduced. Based on the definitions, we develop an implementation of the generic ϵ-sensitivity analysis under perturbations of either the cost parameters or the right-hand side. 相似文献
15.
Renato. D. C. Monteiro 《Mathematical Programming》2003,97(1-2):209-244
In this paper, we survey the most recent methods that have been developed for the solution of semidefinite programs. We first
concentrate on the methods that have been primarily motivated by the interior point (IP) algorithms for linear programming,
putting special emphasis in the class of primal-dual path-following algorithms. We also survey methods that have been developed
for solving large-scale SDP problems. These include first-order nonlinear programming (NLP) methods and more specialized path-following
IP methods which use the (preconditioned) conjugate gradient or residual scheme to compute the Newton direction and the notion
of matrix completion to exploit data sparsity.
Received: December 16, 2002 / Accepted: May 5, 2003
Published online: May 28, 2003
Key words. semidefinite programming – interior-point methods – polynomial complexity – path-following methods – primal-dual methods
– nonlinear programming – Newton method – first-order methods – bundle method – matrix completion
The author's research presented in this survey article has been supported in part by NSF through grants INT-9600343, INT-9910084,
CCR-9700448, CCR-9902010, CCR-0203113 and ONR through grants N00014-93-1-0234, N00014-94-1-0340 and N00014-03-1-0401.
Mathematics Subject Classification (2000): 65K05, 90C06, 90C22, 90C25, 90C30, 90C51 相似文献
16.
Rodrigo Garcés Walter Gómez Florian Jarre 《Mathematical Methods of Operations Research》2011,74(1):77-92
The paper considers nonconvex quadratic semidefinite problems. This class arises, for instance, as subproblems in the sequential
semidefinite programming algorithm for solving general smooth nonlinear semidefinite problems. We extend locally the concept
of self-concordance to problems that satisfy a weak version of the second order sufficient optimality conditions. 相似文献
17.
《Operations Research Letters》2021,49(2):164-170
Stochastic semidefinite programming (SSDP) is a new class of optimization problems with a wide variety of applications. In this article, asymptotic analysis results of sample average approximation estimator for SSDP are established. Asymptotic analysis result already existing for stochastic nonlinear programming is extended to SSDP, that is, the conditions ensuring the convergence in distribution of sample average approximation estimator for SSDP to a multivariate normal are obtained and the corresponding covariance matrix is described in a closed form. 相似文献
18.
Masakazu Muramatsu 《Mathematical Programming》1998,83(1-3):393-406
In this paper, we introduce an affine scaling algorithm for semidefinite programming (SDP), and give an example of a semidefinite
program such that the affine scaling algorithm converges to a non-optimal point. Both our program and its dual have interior
feasible solutions and unique optimal solutions which satisfy strict complementarity, and they are non-degenerate everywhere. 相似文献
19.
In this paper, with the help of convex-like function, we discuss the duality theory for nonconvex semidefinite programming.
Our contributions are: duality theory for the general nonconvex semidefinite programming when Slater’s condition holds; perfect
duality for a special case of the nonconvex semidefinite programming for which Slater’s condition fails. We point out that
the results of Fan (Appl. Math. Lett. 18:1068–1073, 2005) can be regarded as a special case of our result. 相似文献
20.
《Operations Research Letters》2023,51(2):197-203
We propose a classification approach exploiting relationships between ellipsoidal separation and Support-vector Machine (SVM) with quadratic kernel. By adding a (Semidefinite Programming) SDP constraint to SVM model we ensure that the chosen hyperplane in feature space represents a non-degenerate ellipsoid in input space. This allows us to exploit SDP techniques within Support-vector Regression (SVR) approaches, yielding better results in case ellipsoid-shaped separators are appropriate for classification tasks. We compare our approach with spherical separation and SVM on some classification problems. 相似文献