共查询到20条相似文献,搜索用时 31 毫秒
1.
Convergence rate analysis of iteractive algorithms for solving variational inequality problems 总被引:3,自引:0,他引:3
M.V. Solodov 《Mathematical Programming》2003,96(3):513-528
We present a unified convergence rate analysis of iterative methods for solving the variational inequality problem. Our results
are based on certain error bounds; they subsume and extend the linear and sublinear rates of convergence established in several
previous studies. We also derive a new error bound for $\gamma$-strictly monotone variational inequalities. The class of algorithms
covered by our analysis in fairly broad. It includes some classical methods for variational inequalities, e.g., the extragradient,
matrix splitting, and proximal point methods. For these methods, our analysis gives estimates not only for linear convergence
(which had been studied extensively), but also sublinear, depending on the properties of the solution. In addition, our framework
includes a number of algorithms to which previous studies are not applicable, such as the infeasible projection methods, a
separation-projection method, (inexact) hybrid proximal point methods, and some splitting techniques. Finally, our analysis
covers certain feasible descent methods of optimization, for which similar convergence rate estimates have been recently obtained
by Luo [14].
Received: April 17, 2001 / Accepted: December 10, 2002
Published online: April 10, 2003
RID="⋆"
ID="⋆" Research of the author is partially supported by CNPq Grant 200734/95–6, by PRONEX-Optimization, and by FAPERJ.
Key Words. Variational inequality – error bound – rate of convergence
Mathematics Subject Classification (2000): 90C30, 90C33, 65K05 相似文献
2.
, for the monotone depth of functions in monotone-P. As a result we achieve the separation of the following classes.
1. monotone-NC ≠ monotone-P.
2. For every i≥1, monotone-≠ monotone-.
3. More generally: For any integer function D(n), up to (for some ε>0), we give an explicit example of a monotone Boolean function, that can be computed by polynomial size monotone
Boolean circuits of depth D(n), but that cannot be computed by any (fan-in 2) monotone Boolean circuits of depth less than Const·D(n) (for some constant Const).
Only a separation of monotone- from monotone- was previously known.
Our argument is more general: we define a new class of communication complexity search problems, referred to below as DART
games, and we prove a tight lower bound for the communication complexity of every member of this class. As a result we get
lower bounds for the monotone depth of many functions. In particular, we get the following bounds:
1. For st-connectivity, we get a tight lower bound of . That is, we get a new proof for Karchmer–Wigderson's theorem, as an immediate corollary of our general result.
2. For the k-clique function, with , we get a tight lower bound of Ω(k log n). This lower bound was previously known for k≤ log n [1]. For larger k, however, only a bound of Ω(k) was previously known.
Received: December 19, 1997 相似文献
3.
This paper is devoted to the study of the proximal point algorithm for solving monotone second-order cone complementarity
problems. The proximal point algorithm is to generate a sequence by solving subproblems that are regularizations of the original
problem. After given an appropriate criterion for approximate solutions of subproblems by adopting a merit function, the proximal
point algorithm is verified to have global and superlinear convergence properties. For the purpose of solving the subproblems
efficiently, we introduce a generalized Newton method and show that only one Newton step is eventually needed to obtain a
desired approximate solution that approximately satisfies the appropriate criterion under mild conditions. Numerical comparisons
are also made with the derivative-free descent method used by Pan and Chen (Optimization 59:1173–1197, 2010), which confirm the theoretical results and the effectiveness of the algorithm. 相似文献
4.
Error bounds for proximal point subproblems and associated inexact proximal point algorithms 总被引:1,自引:0,他引:1
We study various error measures for approximate solution of proximal point regularizations of the variational inequality problem,
and of the closely related problem of finding a zero of a maximal monotone operator. A new merit function is proposed for
proximal point subproblems associated with the latter. This merit function is based on Burachik-Iusem-Svaiter’s concept of
ε-enlargement of a maximal monotone operator. For variational inequalities, we establish a precise relationship between the
regularized gap function, which is a natural error measure in this context, and our new merit function. Some error bounds
are derived using both merit functions for the corresponding formulations of the proximal subproblem. We further use the regularized
gap function to devise a new inexact proximal point algorithm for solving monotone variational inequalities. This inexact
proximal point method preserves all the desirable global and local convergence properties of the classical exact/inexact method,
while providing a constructive error tolerance criterion, suitable for further practical applications. The use of other tolerance
rules is also discussed.
Received: April 28, 1999 / Accepted: March 24, 2000?Published online July 20, 2000 相似文献
5.
Francisco J. Aragón Artacho Michel H. Geoffroy 《Journal of Mathematical Analysis and Applications》2007,335(1):168-183
We study stability properties of a proximal point algorithm for solving the inclusion 0∈T(x) when T is a set-valued mapping that is not necessarily monotone. More precisely we show that the convergence of our algorithm is uniform, in the sense that it is stable under small perturbations whenever the set-valued mapping T is metrically regular at a given solution. We present also an inexact proximal point method for strongly metrically subregular mappings and show that it is super-linearly convergent to a solution to the inclusion 0∈T(x). 相似文献
6.
We study a class of stochastic flows connected to the coalescent processes that have been studied recently by M?hle, Pitman,
Sagitov and Schweinsberg in connection with asymptotic models for the genealogy of populations with a large fixed size. We
define a bridge to be a right-continuous process (B(r),r[0,1]) with nondecreasing paths and exchangeable increments, such that B(0)=0 and B(1)=1. We show that flows of bridges are in one-to-one correspondence with the so-called exchangeable coalescents. This yields
an infinite-dimensional version of the classical Kingman representation for exchangeable partitions of ℕ. We then propose
a Poissonian construction of a general class of flows of bridges and identify the associated coalescents. We also discuss
an important auxiliary measure-valued process, which is closely related to the genealogical structure coded by the coalescent
and can be viewed as a generalized Fleming-Viot process.
Received: 26 November 2002 / Revised version: 10 February 2003 /
Published online: 15 April 2003
Mathematics Subject Classification (2000): 60G09, 60J25, 92D30
Key words or phrases: Flow – Coalescence – Exchangeability – Bridge 相似文献
7.
1 IntroductionThe multivalued operator equations occur in various applications, e.g., mecha11ical systeimwith dry and viscous damping, electrical networks with switches, oscil1ations in viscoelastic-ity, optimization probIems with uonsmooth data, dynanilcal systems with nondifferentiablepotential, and optimal colltroI problellls. There have been a number of results, for instance,[1l-[6l, oll the solutions of multivallled operator equations. Amoug theln, R.T.Rockafellar[1]gave a prorimal poin… 相似文献
8.
In this paper we construct a proximal point algorithm for maximal monotone operators with appropriate regularization parameters.
We obtain the strong convergence of the proposed algorithm, which affirmatively answer the open question put forth by Boikanyo
and Morosanu (Optim Lett 4:635–641, 2010). 相似文献
9.
We introduce an iterative sequence for finding the solution to 0∈T(v), where T
:
E⇉E
* is a maximal monotone operator in a smooth and uniformly convex Banach space E. This iterative procedure is a combination of iterative algorithms proposed by Kohsaka and Takahashi (Abstr. Appl. Anal.
3:239–249, 2004) and Kamamura, Kohsaka and Takahashi (Set-Valued Anal. 12:417–429, 2004). We prove a strong convergence theorem and a weak convergence theorem under different conditions respectively and give an
estimate of the convergence rate of the algorithm. An application to minimization problems is given.
This work was partially supported by the National Natural Sciences Grant 10671050 and the Heilongjiang Province Natural Sciences
Grant A200607. The authors thank the referees for useful comments improving the presentation and Professor K. Kohsaka for
pointing out Ref. 7. 相似文献
10.
The Existence of Positive Almost Periodic Type Solutions for Some Nonlinear Delay Integral Equations
Bin XU Rong YUAN 《数学学报(英文版)》2005,21(6):1351-1360
This paper presents the conditions of existence of positive almost periodic type solutions for some nonlinear delay integral equations, by using a fixed point theorem in the mixed monotone operators (Ma, Y.: On a class of mixed monotone operators and a kind of two-point bounded value problem. Indian J. Math., 41(2), 211-220 (1999]]. Some known results are operators. 相似文献
11.
A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization 总被引:7,自引:0,他引:7
In this paper, we present a nonlinear programming algorithm for solving semidefinite programs (SDPs) in standard form. The
algorithm's distinguishing feature is a change of variables that replaces the symmetric, positive semidefinite variable X of the SDP with a rectangular variable R according to the factorization X=RR
T
. The rank of the factorization, i.e., the number of columns of R, is chosen minimally so as to enhance computational speed while maintaining equivalence with the SDP. Fundamental results
concerning the convergence of the algorithm are derived, and encouraging computational results on some large-scale test problems
are also presented.
Received: March 22, 2001 / Accepted: August 30, 2002 Published online: December 9, 2002
Key Words. semidefinite programming – low-rank factorization – nonlinear programming – augmented Lagrangian – limited memory BFGS
This research was supported in part by the National Science Foundation under grants CCR-9902010, INT-9910084, CCR-0203426
and CCR-0203113 相似文献
12.
In this paper, we describe how to reformulate a problem that has second-order cone and/or semidefiniteness constraints in
order to solve it using a general-purpose interior-point algorithm for nonlinear programming. The resulting problems are smooth
and convex, and numerical results from the DIMACS Implementation Challenge problems and SDPLib are provided.
Received: March 10, 2001 / Accepted: January 18, 2002 Published online: September 27, 2002
Key Words. semidefinite programming – second-order cone programming – interior-point methods – nonlinear programming
Mathematics Subject Classification (2000): 20E28, 20G40, 20C20 相似文献
13.
Let H be a real Hilbert space and let T: H→2H be a maximal monotone operator. In this paper, we first introduce two algorithms of approximating solutions of maximal monotone operators. One of them is to generate a strongly convergent sequence with limit vT−10. The other is to discuss the weak convergence of the proximal point algorithm. Next, using these results, we consider the problem of finding a minimizer of a convex function. Our methods are motivated by Halpern's iteration and Mann's iteration. 相似文献
14.
We introduce a new upper bound for the maximum-entropy sampling problem. Our bound is described as the solution of a linear
integer program. The bound depends on a partition of the underlying set of random variables. For the case in which each block
of the partition has bounded cardinality, we describe an efficient dynamic-programming algorithm to calculate the bound. For
the very special case in which the blocks have no more than two elements, we describe an efficient algorithm for calculating
the bound based on maximum-weight matching. This latter formulation has particular value for local-search procedures that
seek to find a good partition. We relate our bound to recent bounds of Hoffman, Lee and Williams. Finally, we report on the
results of some computational experiments.
Received: September 27, 2000 / Accepted: July 26, 2001 Published online: September 5, 2002
Key words. experimental design – design of experiments – entropy – maximum-entropy sampling – matching – integer program – spectral
bound – Fischer's inequality – branch-and-bound – dynamic programming
Mathematics Subject Classification (2000): 52B12, 90C10
Send offprint requests to: Jon Lee
Correspondence to: Jon Lee 相似文献
15.
It is known, by Rockafellar (SIAM J Control Optim 14:877–898, 1976), that the proximal point algorithm (PPA) converges weakly to a zero of a maximal monotone operator in a Hilbert space, but
it fails to converge strongly. Lehdili and Moudafi (Optimization 37:239–252, 1996) introduced the new prox-Tikhonov regularization method for PPA to generate a strongly convergent sequence and established
a convergence property for it by using the technique of variational distance in the same space setting. In this paper, the
prox-Tikhonov regularization method for the proximal point algorithm of finding a zero for an accretive operator in the framework
of Banach space is proposed. Conditions which guarantee the strong convergence of this algorithm to a particular element of
the solution set is provided. An inexact variant of this method with error sequence is also discussed. 相似文献
16.
Roberto Maieli 《Archive for Mathematical Logic》2003,42(3):205-220
We introduce a new correctness criterion for multiplicative non commutative proof nets which can be considered as the non-commutative
counterpart to the Danos-Regnier criterion for proof nets of linear logic. The main intuition relies on the fact that any
switching for a proof net (obtained by mutilating one premise of each disjunction link) can be naturally viewed as a series-parallel order variety (a cyclic relation) on the conclusions of the proof net.
Received: 8 November 2000 / Revised version: 21 June 2001 / Published online: 2 September 2002
Research supported by the EU TMR Research Programme ``Linear Logic and Theoretical Computer Science'.
Mathematics Subject Classification (2000): 03F03, 03F07, 03F52, 03B70
Key words or phrases: Linear and non-commutative logic – Proof nets – Series-parallel orders and order varieties 相似文献
17.
We investigate the NP–hard label number maximization problem (LNM): Given a set of rectangular labels Λ, each of which belongs to a point feature
in the plane, the task is to find a labeling for a largest subset Λ
P
of Λ. A labeling is a placement such that none of the labels overlap and each λΛ
P
is placed according to a labeling model: In the discrete models, the label must be placed so that the labeled point coincides with an element of a predefined subset of corners of the rectangular
label, in the continuous or slider models, the point must lie on a subset of boundaries of the label. Obviously, the slider models allow a continuous movement of a
label around its point feature, leading to a significantly higher number of labels that can be placed.
We present exact algorithms for this problem that are based on a pair of so-called constraint graphs that code horizontal
and vertical positioning relations. The key idea is to link the two graphs by a set of additional constraints, thus characterizing
all feasible solutions of LNM. This enables us to formulate a zero-one integer linear program whose solution leads to an optimal
labeling.
We can express LNM in both the discrete and the slider labeling models. To our knowledge, we present the first algorithm that
computes provably optimal solutions in the slider models. We find it remarkable that our approach is independent of the labeling
model and results in a discrete algorithm even if the problem is of continuous nature as in the slider models. Extensive experimental
results on both real-world instances and point sets created by a widely used benchmark generator show that the new approach
- although being an exponential time algorithm - is applicable in practice.
Received: November 20, 2000 / Accepted: April 9, 2002 Published online: September 5, 2002
RID="★"
ID="★" This work is partially supported by the German Bundesministerium für Bildung, Wissenschaft, Forschung und Technologie
(No. 03-MU7MP1-4).
Key words. map labeling – point feature map labeling – constraint graphs – combinatorial optimization – integer programming 相似文献
18.
On the capacitated vehicle routing problem 总被引:1,自引:0,他引:1
We consider the Vehicle Routing Problem, in which a fixed fleet of delivery vehicles of uniform capacity must service known
customer demands for a single commodity from a common depot at minimum transit cost. This difficult combinatorial problem
contains both the Bin Packing Problem and the Traveling Salesman Problem (TSP) as special cases and conceptually lies at the
intersection of these two well-studied problems. The capacity constraints of the integer programming formulation of this routing
model provide the link between the underlying routing and packing structures. We describe a decomposition-based separation
methodology for the capacity constraints that takes advantage of our ability to solve small instances of the TSP efficiently.
Specifically, when standard procedures fail to separate a candidate point, we attempt to decompose it into a convex combination
of TSP tours; if successful, the tours present in this decomposition are examined for violated capacity constraints; if not,
the Farkas Theorem provides a hyperplane separating the point from the TSP polytope. We present some extensions of this basic
concept and a general framework within which it can be applied to other combinatorial models. Computational results are given
for an implementation within the parallel branch, cut, and price framework SYMPHONY.
Received: October 30, 2000 / Accepted: December 19, 2001 Published online: September 5, 2002
Key words. vehicle routing problem – integer programming – decomposition algorithm – separation algorithm – branch and cut
Mathematics Subject Classification (2000): 20E28, 20G40, 20C20 相似文献
19.
This work is concerned with existence for a stochastic free boundary problem arising in phase transition (the Stefan two
phase problem). The existence of an invariant ergodic measure associated with the corresponding transition semigroup P(t) is also proved, together with an integration by parts formula for the generator of P(t).
Received: 20 June 2001 / Revised version: 17 June 2002 / Published online: 24 October 2002
Mathematics Subject Classification (2000): 35K35, 35R15, 60H15
Key words or phrases: Stochastic Stefan problem – Invariant measures – Wiener process – Transition semigroup – Kolmogorov operator 相似文献
20.
A Relaxed Approximate Proximal Point Algorithm 总被引:1,自引:0,他引:1
For a maximal monotone operator T, a well-known overrelaxed point algorithm is often used to find the zeros of T. In this paper, we enhance the algorithm to find a point in
, where
is a given closed convex set. In the inexact case of our modified relaxed proximal point algorithm, we give a new criterion.
The convergence analysis is quite easy to follow. 相似文献