集值混合变分不等式的一类自适应惯性投影次梯度算法

本文在实Hilbert空间上引入了一类求解集值混合变分不等式新的自适应惯性投影次梯度算法.在集值映射T为f-强伪单调或单调的条件下,我们证明了由该自适应惯性投影次梯度算法所产生的序列强收敛于集值混合变分不等式问题的的唯一解.     

Metric subregularity and the proximal point method

We examine the linear convergence rates of variants of the proximal point method for finding zeros of maximal monotone operators. We begin by showing how metric subregularity is sufficient for local linear convergence to a zero of a maximal monotone operator. This result is then generalized to obtain convergence rates for the problem of finding a common zero of multiple monotone operators by considering randomized and averaged proximal methods.     

Boundary value problems for differential equations with deviated arguments which depend on the unknown solution

We discuss boundary value problems for first-order functional differential equations with deviated arguments which depend on the unknown solution. We formulate sufficient conditions for existence of a quasisolution and a unique solution of such problems. To obtain the results we use the method of monotone iterations.     

Nearly monotone and nearly convex approximation by smooth splines in ,

Given a monotone or convex function on a finite interval we construct splines of arbitrarily high order having maximum smoothness which are “nearly monotone” or “nearly convex” and provide the rate of -approximation which can be estimated in terms of the third or fourth (classical or Ditzian–Totik) moduli of smoothness (for uniformly spaced or Chebyshev knots). It is known that these estimates are impossible in terms of higher moduli and are no longer true for “purely monotone” and “purely convex” spline approximation.     

Singular stochastic equations on Hilbert spaces: Harnack inequalities for their transition semigroups

We consider stochastic equations in Hilbert spaces with singular drift in the framework of [G. Da Prato, M. Röckner, Singular dissipative stochastic equations in Hilbert spaces, Probab. Theory Related Fields 124 (2) (2002) 261-303]. We prove a Harnack inequality (in the sense of [F.-Y. Wang, Logarithmic Sobolev inequalities on noncompact Riemannian manifolds, Probab. Theory Related Fields 109 (1997) 417-424]) for its transition semigroup and exploit its consequences. In particular, we prove regularizing and ultraboundedness properties of the transition semigroup as well as that the corresponding Kolmogorov operator has at most one infinitesimally invariant measure μ (satisfying some mild integrability conditions). Finally, we prove existence of such a measure μ for noncontinuous drifts.     

Enlargements of positive sets

In this paper we introduce the notion of enlargement of a positive set in SSD spaces. To a maximally positive set A we associate a family of enlargements E(A) and characterize the smallest and biggest element in this family with respect to the inclusion relation. We also emphasize the existence of a bijection between the subfamily of closed enlargements of E(A) and the family of so-called representative functions of A. We show that the extremal elements of the latter family are two functions recently introduced and studied by Stephen Simons. In this way we extend to SSD spaces some former results given for monotone and maximally monotone sets in Banach spaces.     

Proximal-Point Algorithm Using a Linear Proximal Term

Proximal-point algorithms (PPAs) are classical solvers for convex optimization problems and monotone variational inequalities (VIs). The proximal term in existing PPAs usually is the gradient of a certain function. This paper presents a class of PPA-based methods for monotone VIs. For a given current point, a proximal point is obtained via solving a PPA-like subproblem whose proximal term is linear but may not be the gradient of any functions. The new iterate is updated via an additional slight calculation. Global convergence of the method is proved under the same mild assumptions as the original PPA. Finally, profiting from the less restrictions on the linear proximal terms, we propose some parallel splitting augmented Lagrangian methods for structured variational inequalities with separable operators. B.S. He was supported by NSFC Grant 10571083 and Jiangsu NSF Grant BK2008255.     

φ凹混合单调算子(-φ凸反向混合单调算子)不动点定理

对两变元的算子引进φ凹(-φ凸)条件,证明了在这种凹凸性条件下,混合单调算子和反向混合单调的不动点的存在唯一性,并给出了不动点的迭代收敛序列.     

Tighter approximation bounds for LPT scheduling in two special cases

$Q||C_{\max }$ denotes the problem of scheduling n jobs on m machines of different speeds such that the makespan is minimized. In the paper two special cases of $Q||C_{\max }$ are considered: case I, when $m?1$ machine speeds are equal, and there is only one faster machine; and case II, when machine speeds are all powers of 2 (2-divisible machines). Case I has been widely studied in the literature, while case II is significant in an approach to design so called monotone algorithms for the scheduling problem.We deal with the worst case approximation ratio of the classic list scheduling algorithm ‘Largest Processing Time (LPT)’. We provide an analysis of this ratio $\mathit{Lpt}/\mathit{Opt}$ for both special cases: For ‘one fast machine’, a tight bound of $(\sqrt{3}+1)/2\approx 1.3660$ is given. For 2-divisible machines, we show that in the worst case $1.3673<\mathit{Lpt}/\mathit{Opt}<1.4$. Besides, we prove another lower bound of $955/699>(\sqrt{3}+1)/2$ when LPT breaks ties arbitrarily.To our knowledge, the best previous lower and upper bounds were $(4/3,3/2?1/2m]$ in case I [T. Gonzalez, O.H. Ibarra, S. Sahni, Bounds for LPT schedules on uniform processors, SIAM Journal on Computing 6 (1) (1977) 155–166], respectively $[4/3?1/3m,3/2]$ in case II [R.L. Graham, Bounds on multiprocessing timing anomalies, SIAM Journal on Applied Mathematics 17 (1969) 416–429; A. Kovács, Fast monotone 3-approximation algorithm for scheduling related machines, in: Proc. 13th Europ. Symp. on Algs. (ESA), in: LNCS, vol. 3669, Springer, 2005, pp. 616–627]. Moreover, Gonzalez et al. conjectured the lower bound 4/3 to be tight in the ‘one fast machine’ case [T. Gonzalez, O.H. Ibarra, S. Sahni, Bounds for LPT schedules on uniform processors, SIAM Journal on Computing 6 (1) (1977) 155–166].     

一个新的单调类定理

定义了一个新的集类M-类,并给出了M-类的单调类定理.