共查询到20条相似文献,搜索用时 31 毫秒
1.
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 相似文献
2.
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. 相似文献
3.
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 相似文献
4.
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 相似文献
5.
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. 相似文献
6.
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 相似文献
7.
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. 相似文献
8.
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. 相似文献
9.
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. 相似文献
10.
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. 相似文献
11.
We shall give, in an optimal form, a sufficient numerical condition for the finiteness of the fundamental group of the smooth
locus of a normal K3 surface. We shall moreover prove that, if the normal K3 surface is elliptic and the above fundamental
group is not finite, then there is a finite covering which is a complex torus.
Received: 13 April 2001 / Published online: 16 October 2002
RID="⋆"
ID="⋆" Supported by Korea Research Foundation Grant(KRF-2001-041-D00025)
Mathematics Subject Classification (2000): 14J28 相似文献
12.
On polynomial collocation for second kind integral equations with fixed singularities of Mellin type
Summary. We consider a polynomial collocation for the numerical solution of a second kind integral equation with an integral kernel
of Mellin convolution type. Using a stability result by Junghanns and one of the authors, we prove that the error of the approximate
solution is less than a logarithmic factor times the best approximation and, using the asymptotics of the solution, we derive
the rates of convergence. Finally, we describe an algorithm to compute the stiffness matrix based on simple Gau? quadratures
and an alternative algorithm based on a recursion in the spirit of Monegato and Palamara Orsi. All together an almost best
approximation to the solution of the integral equation can be computed with 𝒪(n
2[log n]2) resp. 𝒪(n
2) operations, where n is the dimension of the polynomial trial space.
Received February 18, 2002 / Revised version received May 15, 2002 / Published online October 29, 2002
RID="⋆"
ID="⋆" Correspondence to: A. Rathsfeld
Mathematics Subject Classification (1991): 65R20 相似文献
13.
We consider a modification of the pigeonhole principle, M P H P, introduced by Goerdt in [7]. M P H P is defined over n pigeons and log n holes, and more than one pigeon can go into a hole (according to some rules). Using a technique of Razborov [9] and simplified
by Impagliazzo, Pudlák and Sgall [8], we prove that any Polynomial Calculus refutation of a set of polynomials encoding the
M P H P, requires degree Ω(log n). We also prove a simple Lemma giving a simulation of Resolution by Polynomial Calculus. Using this lemma, and a Resolution
upper bound by Goerdt [7], we obtain that the degree lower bound is tight.
Our lower bound establishes the optimality of the tree-like Resolution simulation by the Polynomial Calculus given in [6].
Received: 29 March 2001 /
Published online: 2 September 2002
RID="⋆"
ID="⋆" A prelimianry version appeared as part of the paper A Study of Proof Search Algorithms for Resolution and Polynomial Calculus published in the Proceedings of the 40-th IEEE Conference on Foundations of Computer Science, 1999
RID="†"
ID="†" Partly supported by Project CICYT, TIC 98-0410-C02-01 and Promoción General del Conocimiento PB98-0937-C04-03.
RID="††"
ID="††" Part of this work was done while the author was a member of the School of Mathematics at Institute for Advanced Study
supported by a NSF grant n. 9987845 相似文献
14.
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. 相似文献
15.
Maximal Energy Bipartite Graphs 总被引:1,自引:0,他引:1
Given a graph G, its energy E(G) is defined to be the sum of the absolute values of the eigenvalues of G. This quantity is used in chemistry to approximate the total π-electron energy of molecules and in particular, in case G is bipartite, alternant hydrocarbons. Here we show that if G is a bipartite graph with n vertices, then
must hold, characterize those bipartite graphs for which this bound is sharp, and provide an infinite family of maximal energy
bipartite graphs.
Received: December 1, 2000 Final version received: August 28, 2001
RID="*"
ID="*" The author thanks the Swedish Natural Science Research Council (NFR) – grant M12342-300 – for its support.
Acknowledgments. The authors would like to thank Ivan Gutman for encouraging them to write this paper, and for helpful discussions on this
topic. They also would like to thank Edwin van Dam for his reference concerning connected bipartite regular graphs with four
eigenvalues. 相似文献
16.
Non-Interior continuation methods for solving semidefinite complementarity problems 总被引:13,自引:0,他引:13
There recently has been much interest in non-interior continuation/smoothing methods for solving linear/nonlinear complementarity
problems. We describe extensions of such methods to complementarity problems defined over the cone of block-diagonal symmetric
positive semidefinite real matrices. These extensions involve the Chen-Mangasarian class of smoothing functions and the smoothed
Fischer-Burmeister function. Issues such as existence of Newton directions, boundedness of iterates, global convergence, and
local superlinear convergence will be studied. Preliminary numerical experience on semidefinite linear programs is also reported.
Received: October 1999 / Accepted: April 2002 Published online: December 19, 2002
RID="⋆"
ID="⋆" This research is supported by National Science Foundation Grant CCR-9731273.
Key words. semidefinite complementarity problem – smoothing function – non-interior continuation – global convergence – local superlinear
convergence 相似文献
17.
Let K be a field of characteristic 0 and let p, q, G
0
, G
1
, P ∈K[x], deg P ⩾ 1. Further, let the sequence of polynomials (G
n
(x))
n=0
∞ be defined by the second order linear recurring sequence
In this paper we give conditions under which the diophantine equation G
n
(x) = G
m
(P(x)) has at most exp(1018) many solutions (n, m) ε ℤ2, n, m ⩾ 0. The proof uses a very recent result on S-unit equations over fields of characteristic 0 due to Evertse, Schlickewei and Schmidt [14]. Under the same conditions we
present also bounds for the cardinality of the set
In the last part we specialize our results to certain families of orthogonal polynomials.
This work was supported by the Austrian Science Foundation FWF, grant S8307-MAT.
The second author was supported by the Hungarian National Foundation for Scientific Research Grants No 16741 and 38225.
Received June 5, 2001; in revised form February 26, 2002
RID="a"
ID="a" Dedicated to Edmund Hlawka on the occasion of his 85th birthday 相似文献
18.
Kazuhide Nakata Katsuki Fujisawa Mituhiro Fukuda Masakazu Kojima Kazuo Murota 《Mathematical Programming》2003,95(2):303-327
In Part I of this series of articles, we introduced a general framework of exploiting the aggregate sparsity pattern over
all data matrices of large scale and sparse semidefinite programs (SDPs) when solving them by primal-dual interior-point methods.
This framework is based on some results about positive semidefinite matrix completion, and it can be embodied in two different
ways. One is by a conversion of a given sparse SDP having a large scale positive semidefinite matrix variable into an SDP
having multiple but smaller positive semidefinite matrix variables. The other is by incorporating a positive definite matrix
completion itself in a primal-dual interior-point method. The current article presents the details of their implementations.
We introduce new techniques to deal with the sparsity through a clique tree in the former method and through new computational
formulae in the latter one. Numerical results over different classes of SDPs show that these methods can be very efficient
for some problems.
Received: March 18, 2001 / Accepted: May 31, 2001 Published online: October 9, 2002
RID="⋆"
ID="⋆"The author was supported by The Ministry of Education, Culture, Sports, Science and Technology of Japan.
Key Words. semidefinite programming – primal-dual interior-point method – matrix completion problem – clique tree – numerical results
Mathematics Subject Classification (2000): 90C22, 90C51, 05C50, 05C05 相似文献
19.
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. 相似文献
20.
Narong Punnim 《Graphs and Combinatorics》2002,18(4):781-785
Let ω(G) be the clique number of a graph G. We prove that if G runs over the set of graphs with a fixed degree sequence d, then the values ω(G) completely cover a line segment [a,b] of positive integers. For an arbitrary graphic degree sequence d, we define min(ω,d) and max(ω,d) as follows:
where is the graph of realizations of d.
Thus the two invariants a:=min(ω,d) and b:=max(ω,d) naturally arise. For a graphic degree sequence d=r
n
:=(r,r,…,r) where r is the vertex degree and n is the number of vertices, the exact values of a and b are found in all situations. Since the independence number, α(G)=ω(Gˉ), we obtain parallel results for the independence number of graphs.
Received: October, 2001 Final version received: July 25, 2002
RID="*"
ID="*" Work supported by The Thailand Research Fund, under the grant number BRG/09/2545 相似文献