共查询到20条相似文献,搜索用时 718 毫秒
1.
The authors of this paper recently introduced a transformation [4] that converts a class of semidefinite programs (SDPs)
into nonlinear optimization problems free of matrix-valued constraints and variables. This transformation enables the application
of nonlinear optimization techniques to the solution of certain SDPs that are too large for conventional interior-point methods
to handle efficiently. Based on the transformation, we proposed a globally convergent, first-order (i.e., gradient-based)
log-barrier algorithm for solving a class of linear SDPs. In this paper, we discuss an efficient implementation of the proposed
algorithm and report computational results on semidefinite relaxations of three types of combinatorial optimization problems.
Our results demonstrate that the proposed algorithm is indeed capable of solving large-scale SDPs and is particularly effective
for problems with a large number of constraints.
Received: June 22, 2001 / Accepted: January 20, 2002 Published online: December 9, 2002
RID="†"
ID="†"Computational results reported in this paper were obtained on an SGI Origin2000 computer at Rice University acquired
in part with support from NSF Grant DMS-9872009.
RID="⋆"
ID="⋆"This author was supported in part by NSF Grants CCR-9902010, INT-9910084 and CCR-0203426
RID="⋆⋆"
ID="⋆⋆"This author was supported in part by NSF Grants CCR-9902010, INT-9910084 and CCR-0203113
RID="⋆⋆⋆"
ID="⋆⋆⋆"This author was supported in part by DOE Grant DE-FG03-97ER25331, DOE/LANL Contract 03891-99-23 and NSF Grant DMS-9973339.
Key Words. semidefinite program – semidefinite relaxation – nonlinear programming – interior-point methods – limited memory quasi-Newton
methods.
Mathematics Subject Classification (1991): 90C06, 90C27, 90C30. 相似文献
2.
In this paper we consider the problem
where B is a ball in R
n
. For a small d>0, we show the uniqueness (up to rotation) of the one-bubbling solution which concentrates at a point of the boundary.
Received: 12 December 2001 / Published online: 10 February 2003
RID="⋆"
ID="⋆" Supported by M.U.R.S.T., project: ``Variational methods and nonlinear differential equations'
RID="⋆⋆"
ID="⋆⋆" Partial supported by National Center for Theoretical Sciences of NSC, Taiwan
Mathematics Subject Classification (2000): 35J60 相似文献
3.
The maximal Seshadri number μ(L) of an ample line bundle L on a smooth projective variety X measures the local positivity of the line bundle L at a general point of X. By refining the method of Ein-Küchle-Lazarsfeld, lower bounds on μ(L) are obtained in terms of L
n
, n=dim(X), for a class of varieties. The main idea is to show that if a certain lower bound is violated, there exists a non-trivial
foliation on the variety whose leaves are covered by special curves. In a number of examples, one can show that such foliations
must be trivial and obtain lower bounds for μ(L). The examples include the hyperplane line bundle on a smooth surface in ℙ3 and ample line bundles on smooth threefolds of Picard number 1.
Received: 29 June 2001 / Published online: 16 October 2002
RID="⋆"
ID="⋆" Supported by Grant No. 98-0701-01-5-L from the KOSEF.
RID="⋆⋆"
ID="⋆⋆" Supported by Grant No. KRF-2001-041-D00025 from the KRF. 相似文献
4.
Dedicated to the memory of Paul Erdős
In [9] Thomassen proved that a -connected graph either contains k vertex disjoint odd cycles or an odd cycle cover containing at most 2k-2 vertices, i.e. he showed that the Erdős–Pósa property holds for odd cycles in highly connected graphs. In this paper, we
will show that the above statement is still valid for 576k-connected graphs which is essentially best possible.
Received November 17, 1999
RID="*"
ID="*" This work was supported by a post-doctoral DONET grant.
RID="†"
ID="†" This work was supported by an NSF-CNRS collaborative research grant.
RID="‡"
ID="‡" This work was performed while both authors were visiting the LIRMM, Université de Montpellier II, France. 相似文献
5.
It is proved that, for any ɛ>0 and n>n
0(ɛ), every set of n points in the plane has at most triples that induce isosceles triangles. (Here e denotes the base of the natural logarithm, so the exponent is roughly 2.136.) This easily implies the best currently known
lower bound, , for the smallest number of distinct distances determined by n points in the plane, due to Solymosi–Cs. Tóth and Tardos.
Received: February, 2002 Final version received: September 15, 2002
RID="*"
ID="*" Supported by NSF grant CCR-00-86013, PSC-CUNY Research Award 63382-00-32, and OTKA-T-032452
RID="†"
ID="†" Supported by OTKA-T-030059 and AKP 2000-78-21 相似文献
6.
Dedicated to the memory of Paul Erdős
A graph is called H-free if it contains no induced copy of H. We discuss the following question raised by Erdős and Hajnal. Is it true that for every graph H, there exists an such that any H-free graph with n vertices contains either a complete or an empty subgraph of size at least ? We answer this question in the affirmative for a special class of graphs, and give an equivalent reformulation for tournaments.
In order to prove the equivalence, we establish several Ramsey type results for tournaments.
Received August 22, 1999
RID="*"
ID="*" Supported by a USA Israeli BSF grant, by a grant from the Israel Science Foundation and by the Hermann Minkowski Minerva
Center for Geometry at Tel Aviv University.
RID="†"
ID="†" Supported by NSF grant CR-9732101, PSC-CUNY Research Award 663472, and OTKA-T-020914.
RID="‡"
ID="‡" Supported by TKI grant Stochastics@TUB, and OTKA-T-026203. 相似文献
7.
In this paper we show that the so-called commutative class of primal-dual interior point algorithms which were designed by
Monteiro and Zhang for semidefinite programming extends word-for-word to optimization problems over all symmetric cones. The
machinery of Euclidean Jordan algebras is used to carry out this extension. Unlike some non-commutative algorithms such as
the XS+SX method, this class of extensions does not use concepts outside of the Euclidean Jordan algebras. In particular no assumption
is made about representability of the underlying Jordan algebra. As a special case, we prove polynomial iteration complexities
for variants of the short-, semi-long-, and long-step path-following algorithms using the Nesterov-Todd, XS, or SX directions.
Received: April 2000 / Accepted: May 2002
Published online: March 28, 2003
RID="⋆"
ID="⋆" Part of this research was conducted when the first author was a postdoctoral associate at Center for Computational
Optimization at Columbia University.
RID="⋆⋆"
ID="⋆⋆" Research supported in part by the U.S. National Science Foundation grant CCR-9901991 and Office of Naval Research
contract number N00014-96-1-0704. 相似文献
8.
Let Γ be the fundamental group of the complement of a K(Γ, 1) hyperplane arrangement (such as Artin's pure braid group) or more generally a homologically toroidal group as defined below.
The triviality of bundles arising from orthogonal representations of Γ is characterized completely as follows. An orthogonal
representation gives rise to a trivial bundle if and only if the representation factors through the spinor groups. Furthermore,
the subgroup of elements in the complex K-theory of BΓ which arises from complex unitary representations of Γ is shown to be trivial. In the case of real K-theory, the subgroup of elements which arises from real orthogonal representations of Γ is an elementary abelian 2-group,
which is characterized completely in terms of the first two Stiefel-Whitney classes of the representation.
In addition, quadratic relations in the cohomology algebra of the pure braid groups which correspond precisely to the Jacobi
identity for certain choices of Poisson algebras are shown to give the existence of certain homomorphisms from the pure braid
group to generalized Heisenberg groups. These cohomology relations correspond to non-trivial Spin representations of the pure
braid groups which give rise to trivial bundles.
Received: 6 February 2002 / Revised version: 19 September 2002 /
Published online: 8 April 2003
RID="⋆"
ID="⋆" Partially supported by the NSF
RID="⋆⋆"
ID="⋆⋆" Partially supported by grant LEQSF(1999-02)-RD-A-01 from the Louisiana Board of Regents, and by grant MDA904-00-1-0038
from the National Security Agency
RID="⋆"
ID="⋆" Partially supported by the NSF
Mathematics Subject Classification (2000): 20F36, 32S22, 55N15, 55R50 相似文献
9.
Dedicated to the memory of Paul Erdős
Let H be a simple graph having no isolated vertices. An (H,k)-vertex-cover of a simple graph G = (V,E) is a collection of subgraphs of G satisfying
1. , for all i = 1, ..., r,
2. ,
3. , for all , and
4. each is in at most k of the . We consider the existence of such vertex covers when H is a complete graph, , in the context of extremal and random graphs.
Received October 31, 1999
RID="*"
ID="*" Supported in part by NSF grant DMS-9627408.
RID="†"
ID="†" Supported in part by NSF grant CCR-9530974.
RID="‡"
ID="‡" Supported in part by OTKA Grants T 030059 and T 29074, FKFP 0607/1999 and by the Bolyai Foundation.
RID="§"
ID="§" Supported in part by NSF grant DMS-9970622. 相似文献
10.
We consider Finsler spaces with a Randers metric F=α+β, on the three dimensional real vector space, where α is the Euclidean metric and β=bdx
3
is a 1-form with norm b,0≤b<1. By using the notion of mean curvature for immersions in Finsler spaces introduced by Z. Shen, we get the ordinary differential
equation that characterizes the minimal surfaces of rotation around the x
3
axis. We prove that for every b,0≤b<1, there exists, up to homothety, a unique forward complete minimal surface of rotation. The surface is embedded, symmetric
with respect to a plane perpendicular to the rotation axis and it is generated by a concave plane curve. Moreover, for every
there are non complete minimal surfaces of rotation, which include explicit minimal cones.
Received: 30 November 2001 / Published online: 10 February 2003
RID="⋆"
ID="⋆" Partially supported by CAPES
RID="⋆⋆"
ID="⋆⋆" Partially supported by CNPq and PROCAD. 相似文献
11.
For a fixed q ℕ and a given Σ1 definition φ(d,x), where d is a parameter, we construct a model M of 1 Δ0 + ? exp and a non standard d M such that in M either φ has no witness smaller than d or phgr; is equivalent to a formula ϕ(d,x) having no more than q alternations of blocks of quantifiers.
Received: 29 September 1998 / Revised version: 7 November 2001 Published online: 10 October 2002
RID="⋆"
ID="⋆" Research supported in part by The State Committee for Scientific Research (Poland), KBN, grant number 2 PO3A 018 13.
RID="⋆"
ID="⋆" Research supported in part by The State Committee for Scientific Research (Poland), KBN, grant number 2 PO3A 018 13. 相似文献
12.
Summary. Impedance tomography seeks to recover the electrical conductivity distribution inside a body from measurements of current
flows and voltages on its surface. In its most general form impedance tomography is quite ill-posed, but when additional a-priori
information is admitted the situation changes dramatically. In this paper we consider the case where the goal is to find a
number of small objects (inhomogeneities) inside an otherwise known conductor. Taking advantage of the smallness of the inhomogeneities,
we can use asymptotic analysis to design a direct (i.e., non-iterative) reconstruction algorithm for the determination of
their locations. The viability of this direct approach is documented by numerical examples.
Received May 28, 2001 / Revised version received March 15, 2002 / Published online July 18, 2002
RID="⋆"
ID="⋆" Supported by the Deutsche Forschungsgemeinschaft (DFG) under grant HA 2121/2-3
RID="⋆⋆"
ID="⋆⋆" Supported by the National Science Foundation under grant DMS-0072556
Mathematics Subject Classification (2000): 65N21, 35R30, 35C20 相似文献
13.
In this article we present characterizations of locally well-dominated graphs and locally independent well-dominated graphs,
and a sufficient condition for a graph to be k-locally independent well-dominated. Using these results we show that the irredundance number, the domination number and the
independent domination number can be computed in polynomial time within several classes of graphs, e.g., the class of locally
well-dominated graphs.
Received: September 13, 2001 Final version received: May 17, 2002
RID="*"
ID="*" Supported by the INTAS and the Belarus Government (Project INTAS-BELARUS 97-0093)
RID="†"
ID="†" Supported by RUTCOR
RID="*"
ID="*" Supported by the INTAS and the Belarus Government (Project INTAS-BELARUS 97-0093)
05C75, 05C69
Acknowledgments. The authors thank the referees for valuable suggestions. 相似文献
14.
In this paper, we analyze a unique continuation problem for the linearized Benjamin-Bona-Mahony equation with space-dependent
potential in a bounded interval with Dirichlet boundary conditions. The underlying Cauchy problem is a characteristic one.
We prove two unique continuation results by means of spectral analysis and the (generalized) eigenvector expansion of the
solution, instead of the usual Holmgren-type method or Carleman-type estimates. It is found that the unique continuation property
depends very strongly on the nature of the potential and, in particular, on its zero set, and not only on its boundedness
or integrability properties.
Received: 6 December 2001 / Revised version: 13 June 2002 / Published online: 10 February 2003
RID="⋆"
ID="⋆" Supported by a Postdoctoral Fellowship of the Spanish Education and Culture Ministry, the Foundation for the Author
of National Excellent Doctoral Dissertation of P.R. China (Project No: 200119), and the NSF of China under Grant 19901024
RID="⋆⋆"
ID="⋆⋆" Supported by grant PB96-0663 of the DGES (Spain) and the EU TMR Project "Homogenization and Multiple Scales".
Mathematics Subject Classification (2000): 35B60, 47A70, 47B07 相似文献
15.
Norbert Sauer 《Combinatorica》2001,21(2):293-308
Dedicated to the memory of Paul Erdős
Erdős, Hajnal and Pósa exhibited in [1] a partition (U,D) of the edges of the Rado graph which is a counterexample to . They also obtained that if every vertex of a graph has either in or in the complement of finite degree then .
We will characterize all graphs so that .
Received October 29, 1999
RID="†"
ID="†" Supported by NSERC of Canada Grant #691325. 相似文献
16.
We show that every 6-edge connected graph admits a circulation whose range lies in the interval [1,3).
Received March 29, 2000
RID="*"
ID="*" Supported by NATO-CNR Fellowship; this work was done while the author was visiting the Dept. of Mathematics and Statistics
at Simon Fraser University, Canada.
RID="†"
ID="†" Supported by a National Sciences and Engineering Research Council Research Grant 相似文献
17.
We show that knowing the displacement-to-traction map associated to the equations of isotropic elastodynamics with residual
stress we can determine the lens maps of compressional and shear waves. We derive several consequences of this for the inverse
problem of determining the residual stress and the Lamé parameters from the displacement-to-traction map.
Received: 6 December 2001 / Revised version: 29 October 2002 /
Published online: 8 April 2003
RID="⋆"
ID="⋆" The author thanks the Department of Mathematics at the University of Washington for its hospitality during his visit
in fall 2000.
RID="⋆⋆"
ID="⋆⋆" Partly supported by NSF grant DMS-0070488 and a John Simon Guggenheim fellowship. The author also thanks MSRI for
partial support and for providing a very stimulating environment during the inverse problems program in fall 2001. 相似文献
18.
Dedicated to the memory of Paul Erdős
We extend a result of J. Alexander and D. Zagier on the Garsia entropy of the Erdős measure. Our investigation heavily relies
on methods from combinatorics on words. Furthermore, we introduce a new singular measure related to the Farey tree.
Received October 7, 1999
RID="†"
ID="†" This author is supported by the START-project Y96-MAT of the Austrian Science Fund
RID="‡"
ID="‡" This author is supported by the Austrian Science Fund (FWF) grant P14200-MAT
RID="*"
ID="*" This author is supported by the Austrian Science Fund (FWF) grant S8307-MAT 相似文献
19.
Improved Bounds for Acyclic Job Shop Scheduling 总被引:2,自引:0,他引:2
In acyclic job shop scheduling problems there are n jobs and m machines. Each job is composed of a sequence of operations to be performed on different machines. A legal schedule is one
in which within each job, operations are carried out in order, and each machine performs at most one operation in any unit
of time. If D denotes the length of the longest job, and C denotes the number of time units requested by all jobs on the most loaded machine, then clearly lb = max[C,D] is a lower bound on the length of the shortest legal schedule. A celebrated result of Leighton, Maggs, and Rao shows that
if all operations are of unit length, then there always is a legal schedule of length O(lb), independent of n and m. For the case that operations may have different lengths, Shmoys, Stein and Wein showed that there always is a legal schedule
of length , where the notation is used to suppress terms. We improve the upper bound to . We also show that our new upper bound is essentially best possible, by proving the existence of instances of acyclic job
shop scheduling for which the shortest legal schedule is of length . This resolves (negatively) a known open problem of whether the linear upper bound of Leighton, Maggs, and Rao applies to
arbitrary job shop scheduling instances (without the restriction to acyclicity and unit length operations).
Received June 30, 1998
RID="*"
ID="*" Incumbent of the Joseph and Celia Reskin Career Development Chair
RID="†"
ID="†" Research was done while staying at the Weizmann Institute, supported by a scholarship from the Minerva foundation. 相似文献
20.
Summary. Let A be an n×m real matrix and consider the linear conic system
In [Cheung and Cucker 2001] a condition number 𝒞(A) for this system is defined. In this paper we let the coefficients of A be independent identically distributed random variables with standard Gaussian distribution and we estimate the moments of
the random variable ln𝒞(A). In particular, when n is sufficiently larger than m we obtain for its expected value E(ln𝒞(A))=max{ln m, ln ln n}+𝒪(1). Bounds for the expected value of the condition number introduced by Renegar [1994b, 1995a, 1995b] follow.
Received June 12, 2001 / Revised version received October 29, 2001 /
Published online November 27, 2002
RID="⋆"
ID="⋆" Partially supported by CERG grant City U 1085/02p.
Mathematics Subject Classification (1991): 65F35, 65K05 相似文献