共查询到20条相似文献,搜索用时 31 毫秒
1.
2.
Laurent Lafforgue 《Inventiones Mathematicae》2002,147(1):1-241
One proves Langlands’ correspondence for GL
r
over function fields. This is a generalization of Drinfeld’s proof in the case of rank 2 : Langlands’ correspondence is realized
in ℓ-adic cohomology spaces of the modular varieties classifying rank r Drinfeld shtukas.
Oblatum 13-X-2000 & 7-VI-2001?Published online: 12 October 2001 相似文献
3.
Stephen J. Wright 《Mathematical Programming》2001,90(3):459-473
Techniques for transforming convex quadratic programs (QPs) into monotone linear complementarity problems (LCPs) and vice
versa are well known. We describe a class of LCPs for which a reduced QP formulation – one that has fewer constraints than
the “standard” QP formulation – is available. We mention several instances of this class, including the known case in which
the coefficient matrix in the LCP is symmetric.
Received: May 2000 / Accepted: February 22, 2001?Published online April 12, 2001 相似文献
4.
Lagrangian relaxation is often an efficient tool to solve (large-scale) optimization problems, even nonconvex. However it
introduces a duality gap, which should be small for the method to be really efficient. Here we make a geometric study of the
duality gap. Given a nonconvex problem, we formulate in a first part a convex problem having the same dual. This formulation
involves a convexification in the product of the three spaces containing respectively the variables, the objective and the
constraints. We apply our results to several relaxation schemes, especially one called “Lagrangean decomposition” in the combinatorial-optimization
community, or “operator splitting” elsewhere. We also study a specific application, highly nonlinear: the unit-commitment
problem.
Received: June 1997 / Accepted: December 2000?Published online April 12, 2001 相似文献
5.
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 相似文献
6.
J. Huisman 《Annali di Matematica Pura ed Applicata》2003,182(1):21-35
We show that there is a large class of non-special divisors of relatively small degree on a given real algebraic curve. If
the real algebraic curve has many real components, such a divisor gives rise to an embedding (birational embedding, resp.)
of the real algebraic curve into the real projective space ℙ
r
for r≥3 (r=2, resp.). We study these embeddings in quite some detail.
Received: October 17, 2001?Published online: February 20, 2003 相似文献
7.
Ali Enayat 《Archive for Mathematical Logic》2001,40(4):273-276
We give a new negative solution to Keisler's problem regarding Skolem functions and elementary extensions. In contrast to
existing ad hoc solutions due to Payne, Knight, and Lachlan, our solution uses well-known models.
Received: 20 September 1999 / Published online: 21 March 2001 相似文献
8.
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 相似文献
9.
We consider a class of non-linear mixed integer programs with n integer variables and k continuous variables. Solving instances from this class to optimality is an NP-hard problem. We show that for the cases with
k=1 and k=2, every optimal solution is integral. In contrast to this, for every k≥3 there exist instances where every optimal solution takes non-integral values.
Received: August 2001 / Accepted: January 2002?Published online March 27, 2002 相似文献
10.
Entropic proximal decomposition methods for convex programs and variational inequalities 总被引:2,自引:0,他引:2
We consider convex optimization and variational inequality problems with a given separable structure. We propose a new decomposition
method for these problems which combines the recent logarithmic-quadratic proximal theory introduced by the authors with a
decomposition method given by Chen-Teboulle for convex problems with particular structure. The resulting method allows to
produce for the first time provably convergent decomposition schemes based on C
∞ Lagrangians for solving convex structured problems. Under the only assumption that the primal-dual problems have nonempty
solution sets, global convergence of the primal-dual sequences produced by the algorithm is established.
Received: October 6, 1999 / Accepted: February 2001?Published online September 17, 2001 相似文献
11.
Many optimization problems have several equivalent mathematical models. It is often not apparent which of these models is
most suitable for practical computation, in particular, when a certain application with a specific range of instance sizes
is in focus. Our paper addresses the Asymmetric Travelling Salesman Problem with time windows (ATSP-TW) from such a point
of view. The real–world application we aim at is the control of a stacker crane in a warehouse.?We have implemented codes
based on three alternative integer programming formulations of the ATSP-TW and more than ten heuristics. Computational results
for real-world instances with up to 233 nodes are reported, showing that a new model presented in a companion paper outperforms
the other two models we considered – at least for our special application – and that the heuristics provide acceptable solutions.
Received: August 1999 / Accepted: September 2000?Published online April 12, 2001 相似文献
12.
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 相似文献
13.
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 相似文献
14.
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 相似文献
15.
Mixed-integer rounding (MIR) inequalities play a central role in the development of strong cutting planes for mixed-integer
programs. In this paper, we investigate how known MIR inequalities can be combined in order to generate new strong valid inequalities.?Given
a mixed-integer region S and a collection of valid “base” mixed-integer inequalities, we develop a procedure for generating new valid inequalities
for S. The starting point of our procedure is to consider the MIR inequalities related with the base inequalities. For any subset
of these MIR inequalities, we generate two new inequalities by combining or “mixing” them. We show that the new inequalities
are strong in the sense that they fully describe the convex hull of a special mixed-integer region associated with the base
inequalities.?We discuss how the mixing procedure can be used to obtain new classes of strong valid inequalities for various
mixed-integer programming problems. In particular, we present examples for production planning, capacitated facility location,
capacitated network design, and multiple knapsack problems. We also present preliminary computational results using the mixing
procedure to tighten the formulation of some difficult integer programs. Finally we study some extensions of this mixing procedure.
Received: April 1998 / Accepted: January 2001?Published online April 12, 2001 相似文献
16.
Logarithmic SUMT limits in convex programming 总被引:1,自引:1,他引:0
The limits of a class of primal and dual solution trajectories associated with the Sequential Unconstrained Minimization Technique
(SUMT) are investigated for convex programming problems with non-unique optima. Logarithmic barrier terms are assumed. For
linear programming problems, such limits – of both primal and dual trajectories – are strongly optimal, strictly complementary,
and can be characterized as analytic centers of, loosely speaking, optimality regions. Examples are given, which show that
those results do not hold in general for convex programming problems. If the latter are weakly analytic (Bank et al. [3]),
primal trajectory limits can be characterized in analogy to the linear programming case and without assuming differentiability.
That class of programming problems contains faithfully convex, linear, and convex quadratic programming problems as strict
subsets. In the differential case, dual trajectory limits can be characterized similarly, albeit under different conditions,
one of which suffices for strict complementarity.
Received: November 13, 1997 / Accepted: February 17, 1999?Published online February 22, 2001 相似文献
17.
Self-regular functions and new search directions for linear and semidefinite optimization 总被引:11,自引:0,他引:11
In this paper, we introduce the notion of a self-regular function. Such a function is strongly convex and smooth coercive on its domain, the positive real axis. We show that any
such function induces a so-called self-regular proximity function and a corresponding search direction for primal-dual path-following
interior-point methods (IPMs) for solving linear optimization (LO) problems. It is proved that the new large-update IPMs enjoy
a polynomial ?(n
log) iteration bound, where q≥1 is the so-called barrier degree of the kernel function underlying the algorithm. The constant hidden in the ?-symbol depends
on q and the growth degree p≥1 of the kernel function. When choosing the kernel function appropriately the new large-update IPMs have a polynomial ?(lognlog) iteration bound, thus improving the currently best known bound for large-update methods by almost a factor . Our unified analysis provides also the ?(log) best known iteration bound of small-update IPMs. At each iteration, we need to solve only one linear system. An extension
of the above results to semidefinite optimization (SDO) is also presented.
Received: March 2000 / Accepted: December 2001?Published online April 12, 2002 相似文献
18.
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 相似文献
19.
An improved rounding method and semidefinite programming relaxation for graph partition 总被引:8,自引:0,他引:8
Given an undirected graph G=(V,E) with |V|=n and an integer k between 0 and n, the maximization graph partition (MAX-GP) problem is to determine a subset S⊂V of k nodes such that an objective function w(S) is maximized. The MAX-GP problem can be formulated as a binary quadratic program and it is NP-hard. Semidefinite programming
(SDP) relaxations of such quadratic programs have been used to design approximation algorithms with guaranteed performance
ratios for various MAX-GP problems. Based on several earlier results, we present an improved rounding method using an SDP
relaxation, and establish improved approximation ratios for several MAX-GP problems, including Dense-Subgraph, Max-Cut, Max-Not-Cut,
and Max-Vertex-Cover.
Received: March 10, 2000 / Accepted: July 13, 2001?Published online February 14, 2002 相似文献
20.
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. 相似文献