共查询到20条相似文献,搜索用时 406 毫秒
1.
Krzysztof C. Kiwiel 《Mathematical Programming》2001,90(1):1-25
We study a general subgradient projection method for minimizing a quasiconvex objective subject to a convex set constraint
in a Hilbert space. Our setting is very general: the objective is only upper semicontinuous on its domain, which need not
be open, and various subdifferentials may be used. We extend previous results by proving convergence in objective values and
to the generalized solution set for classical stepsizes t
k
→0, ∑t
k
=∞, and weak or strong convergence of the iterates to a solution for {t
k
}∈ℓ2∖ℓ1 under mild regularity conditions. For bounded constraint sets and suitable stepsizes, the method finds ε-solutions with an
efficiency estimate of O(ε-2), thus being optimal in the sense of Nemirovskii.
Received: October 4, 1998 / Accepted: July 24, 2000?Published online January 17, 2001 相似文献
2.
Albert Visser 《Archive for Mathematical Logic》2001,40(4):277-295
A Kripke model ? is a submodel of another Kripke model ℳ if ? is obtained by restricting the set of nodes of ℳ. In this paper we show that the class of
formulas of Intuitionistic Predicate Logic that is preserved under taking submodels of Kripke models is precisely the class
of semipositive formulas. This result is an analogue of the Łoś-Tarski theorem for the Classical Predicate Calculus.
In Appendix A we prove that for theories with decidable identity we can take as the embeddings between domains in Kripke models
of the theory, the identical embeddings. This is a well known fact, but we know of no correct proof in the literature. In
Appendix B we answer, negatively, a question posed by Sam Buss: whether there is a classical theory T, such that ℋT is HA. Here ℋT is the theory of all Kripke models ℳ such that the structures assigned to the nodes of ℳ all satisfy T in the sense of classical model theory.
Received: 4 February 1999 / Published online: 25 January 2001 相似文献
3.
For a certain class of domains Ω⊂ℂ with smooth boundary and Δtilde;Ω=w
2Δ the Laplace–Beltrami operator with respect to the Poincaré metric ds
2=w(z)-2
dz dz on Ω, we (1) show that the Green function for the biharmonic operator Δtilde;Ω
2, with Dirichlet boundary data, is positive on Ω×Ω; and (2) obtain an eigenfunction expansion for the operator Δtilde;Ω, which reduces to the ordinary non-Euclidean Fourier transform of Helgason for Ω=𝔻 (the unit disc). In both cases the proofs
go via uniformization, and in (1) we obtain a Myrberg-like formula for the corresponding Green function. Finally, the latter
formula as well as the eigenfunction expansion are worked out more explicitly in the simplest case of Ω an annulus, and a
result is established concerning the convergence of the series ∑
ω∈G
(1-|ω0|2)
s
for G the covering group of the uniformization map of Ω and 0<s<1.
Received: August 21, 2000?Published online: October 30, 2002
RID="*"
ID="*"The first author was supported by GA AV CR grants no. A1019701 and A1019005. 相似文献
4.
We show a descent method for submodular function minimization based on an oracle for membership in base polyhedra. We assume
that for any submodular function f: ?→R on a distributive lattice ?⊆2
V
with ?,V∈? and f(?)=0 and for any vector x∈R
V
where V is a finite nonempty set, the membership oracle answers whether x belongs to the base polyhedron associated with f and that if the answer is NO, it also gives us a set Z∈? such that x(Z)>f(Z). Given a submodular function f, by invoking the membership oracle O(|V|2) times, the descent method finds a sequence of subsets Z
1,Z
2,···,Z
k
of V such that f(Z
1)>f(Z
2)>···>f(Z
k
)=min{f(Y) | Y∈?}, where k is O(|V|2). The method furnishes an alternative framework for submodular function minimization if combined with possible efficient
membership algorithms.
Received: September 9, 2001 / Accepted: October 15, 2001?Published online December 6, 2001 相似文献
5.
Xia Chen 《Probability Theory and Related Fields》2000,116(1):89-123
Let {X
n
}
n
≥0 be a Harris recurrent Markov chain with state space E and invariant measure π. The law of the iterated logarithm and the law of weak convergence are given for the additive functionals
of the form
where ƒ is a real π-centered function defined on E. Some similar results are also obtained for additive functionals which are martingales associated with {X
n
}
n
≥0.
Received: 15 September 1998 / Revised version: 1 April 1999 相似文献
6.
Leonardo Colzani Alice Cominardi Krzysztof Stempak 《Annali di Matematica Pura ed Applicata》2002,181(1):25-54
We study some boundedness properties of radial solutions to the Cauchy problem associated to the wave equation (∂
t
2-▵
x
)u(t,x)=0 and meanwhile we give a new proof of the solution formula.
Received: July 7, 1998?Published online: March 19, 2002 相似文献
7.
Ulrich Kohlenbach 《Archive for Mathematical Logic》2001,40(2):89-92
In this note we show that the so-called weakly extensional arithmetic in all finite types, which is based on a quantifier-free
rule of extensionality due to C. Spector and which is of significance in the context of G?del"s functional interpretation,
does not satisfy the deduction theorem for additional axioms. This holds already for Π0
1-axioms. Previously, only the failure of the stronger deduction theorem for deductions from (possibly open) assumptions (with
parameters kept fixed) was known.
Received: 11 March 1999 / Published online: 21 December 2000 相似文献
8.
J. Donald Monk 《Archive for Mathematical Logic》2001,40(4):243-254
The main notion dealt with in this article is
where A is a Boolean algebra. A partition of 1 is a family ofnonzero pairwise disjoint elements with sum 1. One of the main reasons for interest in this notion is from
investigations about maximal almost disjoint families of subsets of sets X, especially X=ω. We begin the paper with a few results about this set-theoretical notion.
Some of the main results of the paper are:
• (1) If there is a maximal family of size λ≥κ of pairwise almost disjoint subsets of κ each of size κ, then there is a maximal
family of size λ of pairwise almost disjoint subsets of κ+ each of size κ.
• (2) A characterization of the class of all cardinalities of partitions of 1 in a product in terms of such classes for the
factors; and a similar characterization for weak products.
• (3) A cardinal number characterization of sets of cardinals with a largest element which are for some BA the set of all
cardinalities of partitions of 1 of that BA.
• (4) A computation of the set of cardinalities of partitions of 1 in a free product of finite-cofinite algebras.
Received: 9 October 1997 / Published online: 21 March 2001 相似文献
9.
Masashi Misawa 《Annali di Matematica Pura ed Applicata》2002,181(4):389-405
We study a H?lder regularity of gradients for evolutional p-Laplacian systems with H?lder continuous coefficients and exterior force. We use the perturbation argument with the p-Laplacian systems with constant coefficients and only principal terms. The main task is to make the H?lder estimate of gradients
for the systems above well-worked in the perturbation estimate. We also need to make a localization of the H?lder estimate
in [2].
Received: June 25, 2001?Published online: July 9, 2002
Dedicated to Professor Norio Kikuchi on his sixtieth birthday
This research was partially supported by the Grant-in-Aid for Encouragement of Young Scientists No. 12740102 at the Ministry
of Educations, Science, Sports and Culture. 相似文献
10.
Polynomial convergence of primal-dual algorithms for the second-order cone program based on the MZ-family of directions 总被引:5,自引:0,他引:5
In this paper we study primal-dual path-following algorithms for the second-order cone programming (SOCP) based on a family
of directions that is a natural extension of the Monteiro-Zhang (MZ) family for semidefinite programming. We show that the
polynomial iteration-complexity bounds of two well-known algorithms for linear programming, namely the short-step path-following
algorithm of Kojima et al. and Monteiro and Adler, and the predictor-corrector algorithm of Mizuno et al., carry over to the
context of SOCP, that is they have an O( logε-1) iteration-complexity to reduce the duality gap by a factor of ε, where n is the number of second-order cones. Since the MZ-type family studied in this paper includes an analogue of the Alizadeh,
Haeberly and Overton pure Newton direction, we establish for the first time the polynomial convergence of primal-dual algorithms
for SOCP based on this search direction.
Received: June 5, 1998 / Accepted: September 8, 1999?Published online April 20, 2000 相似文献
11.
Philippe Souplet 《Annali di Matematica Pura ed Applicata》2002,181(4):427-436
We prove an a priori estimate and a universal bound for any global solution of the nonlinear degenerate reaction-diffusion
equation u
t
=Δu
m
+u
p
in a bounded domain with zero Dirichlet boundary conditions.
Received: October 1, 2001?Published online: July 9, 2002 相似文献
12.
Alexandra Shlapentokh 《Archive for Mathematical Logic》2001,40(4):297-328
We investigate the issues of Diophantine definability over the non-finitely generated version of non-degenerate modules contained
in the infinite algebraic extensions of the rational numbers. In particular, we show the following. Let k be a number field and let K
inf
be a normal algebraic, possibly infinite, extension of k such that k has a normal extension L linearly disjoint from K
inf
over k. Assume L is totally real and K
inf
is totally complex. Let M
inf
be a non-degenerate O
k
-module, possibly non-finitely generated and contained in O
Kinf
. Then M
inf
contains a submodule Mˉ
inf
such that M
inf
/Mˉ
inf
is torsion and O
k
has a Diophantine definition over Mˉ
inf
.
Received: 4 May 1999 / Published online: 21 March 2001 相似文献
13.
In this paper we introduce the ℬ-prenucleolus for a transferable utility game (N,v), where ℬ⊆2
N
. The ℬ-prenucleolus is a straightforward generalization of the ordinary prenucleolus, where only the coalitions in ℬ determine
the outcome. We impose a combinatorial structure on the collection ℬ which enables us to compute the ℬ-prenucleolus in ?(n
3|ℬ|) time. The algorithm can be used for computing the nucleolus of several classes of games, among which is the class of
minimum cost spanning tree games.
Received: September 4, 1995 / Accepted: May 5, 1997?Published online June 8, 2000 相似文献
14.
We consider the diagonal inexact proximal point iteration where f(x,r)=c
T
x+r∑exp[(A
i
x-b
i
)/r] is the exponential penalty approximation of the linear program min{c
T
x:Ax≤b}. We prove that under an appropriate choice of the sequences λ
k
, ε
k
and with some control on the residual ν
k
, for every r
k
→0+ the sequence u
k
converges towards an optimal point u
∞ of the linear program. We also study the convergence of the associated dual sequence μ
i
k
=exp[(A
i
u
k
-b
i
)/r
k
] towards a dual optimal solution.
Received: May 2000 / Accepted: November 2001?Published online June 25, 2002 相似文献
15.
András A. Benczúr 《Mathematical Programming》1999,84(3):595-640
1 ,E2,..., such that ⋃i≤τEi optmially increases the connectivity by τ, for any integer τ. The main result of the paper is that this sequence of edge
sets can be divided into O(n) groups such that within one group, all Ei are basically the same. Using this result, we improve on the running time of edge connectivity augmentation, as well as we
give the first parallel (RNC) augmentation algorithm. We also present new efficient subroutines for finding the so-called
extreme sets and the cactus representation of min-cuts required in our algorithms. Augmenting the connectivity of hypergraphs
with ordinary edges is known to be structurally harder than that of ordinary graphs. In a weaker version when one exceptional
hyperedge is allowed in the augmenting edge set, we derive similar results as for ordinary graphs.
Received November 1995 / Revised version received July 1998
Published online March 16, 1999 相似文献
16.
Giuseppina Vannella 《Annali di Matematica Pura ed Applicata》2002,180(4):429-440
We consider a Neumann problem of the type -εΔu+F
′(u(x))=0 in an open bounded subset Ω of R
n
, where F is a real function which has exactly k maximum points.
Using Morse theory we find that, for ε suitably small, there are at least 2k nontrivial solutions of the problem and we give some qualitative information about them.
Received: October 30, 1999 Published online: December 19, 2001 相似文献
17.
For a polytope in the [0,1]
n
cube, Eisenbrand and Schulz showed recently that the maximum Chvátal rank is bounded above by O(n
2logn) and bounded below by (1+ε)n for some ε>0. Chvátal cuts are equivalent to Gomory fractional cuts, which are themselves dominated by Gomory mixed integer
cuts. What do these upper and lower bounds become when the rank is defined relative to Gomory mixed integer cuts? An upper
bound of n follows from existing results in the literature. In this note, we show that the lower bound is also equal to n. This result still holds for mixed 0,1 polyhedra with n binary variables.
Received: March 15, 2001 / Accepted: July 18, 2001?Published online September 17, 2001 相似文献
18.
We propose a class of non-interior point algorithms for solving the complementarity problems(CP): Find a nonnegative pair
(x,y)∈ℝ
2n
satisfying y=f(x) and x
i
y
i
=0 for every i∈{1,2,...,n}, where f is a continuous mapping from ℝ
n
to ℝ
n
. The algorithms are based on the Chen-Harker-Kanzow-Smale smoothing functions for the CP, and have the following features;
(a) it traces a trajectory in ℝ
3n
which consists of solutions of a family of systems of equations with a parameter, (b) it can be started from an arbitrary
(not necessarily positive) point in ℝ
2n
in contrast to most of interior-point methods, and (c) its global convergence is ensured for a class of problems including
(not strongly) monotone complementarity problems having a feasible interior point. To construct the algorithms, we give a
homotopy and show the existence of a trajectory leading to a solution under a relatively mild condition, and propose a class
of algorithms involving suitable neighborhoods of the trajectory. We also give a sufficient condition on the neighborhoods
for global convergence and two examples satisfying it.
Received April 9, 1997 / Revised version received September 2, 1998? Published online May 28, 1999 相似文献
19.
We consider the parametric programming problem (Q
p
) of minimizing the quadratic function f(x,p):=x
T
Ax+b
T
x subject to the constraint Cx≤d, where x∈ℝ
n
, A∈ℝ
n×n
, b∈ℝ
n
, C∈ℝ
m×n
, d∈ℝ
m
, and p:=(A,b,C,d) is the parameter. Here, the matrix A is not assumed to be positive semidefinite. The set of the global minimizers and the set of the local minimizers to (Q
p
) are denoted by M(p) and M
loc
(p), respectively. It is proved that if the point-to-set mapping M
loc
(·) is lower semicontinuous at p then M
loc
(p) is a nonempty set which consists of at most ?
m,n
points, where ?
m,n
= is the maximal cardinality of the antichains of distinct subsets of {1,2,...,m} which have at most n elements. It is proved also that the lower semicontinuity of M(·) at p implies that M(p) is a singleton. Under some regularity assumption, these necessary conditions become the sufficient ones.
Received: November 5, 1997 / Accepted: September 12, 2000?Published online November 17, 2000 相似文献
20.
It is shown that: (1) any action of a Moscow group G on a first countable, Dieudonné complete (in particular, on a metrizable) space X can uniquely be extended to an action of the Dieudonné completion γG on X, (2) any action of a locally pseudocompact topological group G on a b
f
-space (in particular, on a first countable space) X can uniquely be extended to an action of the Weil completion on the Dieudonné completion γX of X. As a consequence, we obtain that, for each locally pseudocompact topological group G, every G-space with the b
f
-property admits an equivariant embedding into a compact Hausdorff G-space. Furthermore, for each pseudocompact group G, every metrizable G-space has a G-invariant metric compatible with its topology. We also give a direct construction of such an invariant metric.
Received: June 22, 2000; in final form: May 22, 2001?Published online: June 11, 2002 相似文献