Non-monotone trust region methods for nonlinear equality constrained optimization without a penalty function

 We propose and analyze a class of penalty-function-free nonmonotone trust-region methods for nonlinear equality constrained optimization problems. The algorithmic framework yields global convergence without using a merit function and allows nonmonotonicity independently for both, the constraint violation and the value of the Lagrangian function. Similar to the Byrd–Omojokun class of algorithms, each step is composed of a quasi-normal and a tangential step. Both steps are required to satisfy a decrease condition for their respective trust-region subproblems. The proposed mechanism for accepting steps combines nonmonotone decrease conditions on the constraint violation and/or the Lagrangian function, which leads to a flexibility and acceptance behavior comparable to filter-based methods. We establish the global convergence of the method. Furthermore, transition to quadratic local convergence is proved. Numerical tests are presented that confirm the robustness and efficiency of the approach. Received: December 14, 2000 / Accepted: August 30, 2001 Published online: September 27, 2002 Key words. nonmonotone trust-region methods – sequential quadratic programming – penalty function – global convergence – equality constraints – local convergence – large-scale optimization Mathematics Subject Classification (2000): 65K05, 90C30     

Convergence rate analysis of iteractive algorithms for solving variational inequality problems

 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     

Convergence theorems for semigroup-type families of non-self mappings

Motivated by a paper Chidume and Zegeye [Strong convergence theorems for common fixed points of uniformly L-Lipschitzian pseudocontractive semi-groups, Applicable Analysis, 86 (2007), 353–366], we prove several strong convergence theorems for a family (not necessarily a semigroup) ℱ = {T(t): t ∈ G} of nonexpansive or pseudocontractive non-self mappings in a reflexive strictly convex Banach space with a uniformly Gateaux differentiable norm, where G is an unbounded subset of ℝ⁺. Our results extend and improve the corresponding ones byMatsushita and Takahashi [Strong convergence theorems for nonexpansive nonself-mappings without boundary conditions,Nonlinear Analysis, 68 (2008), 412–419],Morales and Jung [Convergence of paths for pseudo-contractive mappings in Banach spaces, Proceedings of American Mathematical Society, 128 (2000), 3411–3419], Song [Iterative approximation to common fixed points of a countable family of nonexpansive mappings, Applicable Analysis, 86 (2007), 1329–1337], Song and Xu [Strong convergence theorems for nonexpansive semigroup in Banach spaces, Journal of Mathematical Analysis and Applications, 338 (2008), 152–161], Wong, Sahu, and Yao [Solving variational inequalities involving nonexpansive type mappings, Nonlinear Analysis, (2007) doi:10.1016/j.na. 2007.11.025] in the context of a non-semigroup family of non-self mappings.      

Viscosity approximation methods for resolvents of accretive operators in Banach spaces

In this paper, we first prove a strong convergence theorem for resolvents of accretive operators in a Banach space by the viscosity approximation method, which is a generalization of the results of Reich [J. Math. Anal. Appl. 75 (1980), 287–292], and Takahashi and Ueda [J. Math. Anal. Appl. 104 (1984), 546–553]. Further using this result, we consider the proximal point algorithm in a Banach space by the viscosity approximation method, and obtain a strong convergence theorem which is a generalization of the result of Kamimura and Takahashi [Set-Valued Anal. 8 (2000), 361–374]. Dedicated to the memory of Jean Leray     

Asymptotic of the heat kernel in general Benedicks domains

 Using a new inequality relating the heat kernel and the probability of survival, we prove asymptotic ratio limit theorems for the heat kernel (and survival probability) in general Benedicks domains. In particular, the dimension of the cone of positive harmonic measures with Dirichlet boundary conditions can be derived from the rate of convergence to zero of the heat kernel (or the survival probability). Received: 31 March 2002 / Revised version: 12 August 2002 / Published online: 19 December 2002 Mathematics Subject Classification (2000): 60J65, 31B05 Key words or phrases: Positive harmonic functions – Ratio limit theorems – Survival probability     

On convergence rates of inexact Newton regularizations

Summary. REGINN is an algorithm of inexact Newton type for the regularization of nonlinear ill-posed problems [Inverse Problems 15 (1999), pp. 309–327]. In the present article convergence is shown under weak smoothness assumptions (source conditions). Moreover, convergence rates are established. Some computational illustrations support the theoretical results. Received March 12, 1999 / Published online October 16, 2000     

A smoothed GPY sieve

Combining the arguments developed in the works of D. A. Goldston,S. W. Graham, J. Pintz, and C. Y. Yildirim [Preprint, 2005,arXiv: math.NT/506067] and Y. Motohashi [Number theory in progress– A. Schinzel Festschrift (de Gruyter, 1999) 1053–1064]we introduce a smoothing device to the sieve procedure of Goldston,Pintz, and Yildirim (see [Proc. Japan Acad. 82A (2006) 61–65]for its simplified version). Our assertions embodied in Lemmas3 and 4 of this article imply that a natural extension of aprime number theorem of E. Bombieri, J. B. Friedlander, andH. Iwaniec [Theorem 8 in Acta Math. 156 (1986) 203–251]should give rise infinitely often to bounded differences betweenprimes, that is, a weaker form of the twin prime conjecture.     

An augmented Lagrangian interior-point method using directions of negative curvature

 We describe an efficient implementation of an interior-point algorithm for non-convex problems that uses directions of negative curvature. These directions should ensure convergence to second-order KKT points and improve the computational efficiency of the procedure. Some relevant aspects of the implementation are the strategy to combine a direction of negative curvature and a modified Newton direction, and the conditions to ensure feasibility of the iterates with respect to the simple bounds. The use of multivariate barrier and penalty parameters is also discussed, as well as the update rules for these parameters. We analyze the convergence of the procedure; both the linesearch and the update rule for the barrier parameter behave appropriately. As the main goal of the paper is the practical usage of negative curvature, a set of numerical results on small test problems is presented. Based on these results, the relevance of using directions of negative curvature is discussed. Received: July 2000 / Accepted: October 2002 Published online: December 19, 2002 Key words. Primal-dual methods – Nonconvex optimization – Linesearches Research supported by Spanish MEC grant BEC2000-0167 Mathematics Subject Classification (1991): 49M37, 65K05, 90C30     

Universal bounds on the selfaveraging of random diffraction measures

 We consider diffraction at random point scatterers on general discrete point sets in ℝ^ν, restricted to a finite volume. We allow for random amplitudes and random dislocations of the scatterers. We investigate the speed of convergence of the random scattering measures applied to an observable towards its mean, when the finite volume tends to infinity. We give an explicit universal large deviation upper bound that is exponential in the number of scatterers. The rate is given in terms of a universal function that depends on the point set only through the minimal distance between points, and on the observable only through a suitable Sobolev-norm. Our proof uses a cluster expansion and also provides a central limit theorem. Received: 10 October 2001 / Revised version: 26 January 2003 / Published online: 15 April 2003 Work supported by the DFG Mathematics Subject Classification (2000): 78A45, 82B44, 60F10, 82B20 Key words or phrases: Diffraction theory – Random scatterers – Random point sets – Quasicrystals – Large deviations – Cluster expansions     

Hájek basic fuzzy logic and Łukasiewicz infinite-valued logic

 Using the theory of BL-algebras, it is shown that a propositional formula ϕ is derivable in Łukasiewicz infinite valued Logic if and only if its double negation ˜˜ϕ is derivable in Hájek Basic Fuzzy logic. If SBL is the extension of Basic Logic by the axiom (φ & (φ→˜φ)) → ψ, then ϕ is derivable in in classical logic if and only if ˜˜ ϕ is derivable in SBL. Axiomatic extensions of Basic Logic are in correspondence with subvarieties of the variety of BL-algebras. It is shown that the MV-algebra of regular elements of a free algebra in a subvariety of BL-algebras is free in the corresponding subvariety of MV-algebras, with the same number of free generators. Similar results are obtained for the generalized BL-algebras of dense elements of free BL-algebras. Received: 20 June 2001 / Published online: 2 September 2002 This paper was prepared while the first author was visiting the Universidad de Barcelona supported by INTERCAMPUS Program E.AL 2000. The second author was partially supported by Grants 2000SGR-0007 of D. G. R. of Generalitat de Catalunya and PB 97-0888 of D. G. I. C. Y. T. of Spain. Mathematics Subject classification (2000): 03B50, 03B52, 03G25, 06D35 Keywords or Phrases: Basic fuzzy logic – Łukasiewicz logic – BL-algebras – MV-algebras – Glivenko's theorem     

On the convergence of the Newton/log-barrier method

In the Newton/log-barrier method, Newton steps are taken for the log-barrier function for a fixed value of the barrier parameter until a certain convergence criterion is satisfied. The barrier parameter is then decreased and the Newton process is repeated. A naive analysis indicates that Newton’s method does not exhibit superlinear convergence to the minimizer of each instance of the log-barrier function until it reaches a very small neighborhood, namely within O(μ²) of the minimizer, where μ is the barrier parameter. By analyzing the structure of the barrier Hessian and gradient in terms of the subspace of active constraint gradients and the associated null space, we show that this neighborhood is in fact much larger –O(μ^σ) for any σ∈(1,2] – thus explaining why reasonably fast local convergence can be attained in practice. Moreover, we show that the overall convergence rate of the Newton/log-barrier algorithm is superlinear in the number of function/derivative evaluations, provided that the nonlinear program is formulated with a linear objective and that the schedule for decreasing the barrier parameter is related in a certain way to the step length and convergence criteria for each Newton process. Received: October 10, 1997 / Accepted: September 10, 2000?Published online February 22, 2001     

Aspects of strong compactness, measurability, and indestructibility

 We prove three theorems concerning Laver indestructibility, strong compactness, and measurability. We then state some related open questions. Received: 11 December 1999 / Revised version: 17 September 2000 / Published online: 2 September 2002 Mathematics Subject classification (2000): 03E35, 03E55 Keywords or phrases: Measurable cardinal – Strongly compact cardinal – Supercompact cardinal – Indestructibility     

Mappings of the sphere to a simply connected space

Fix an m ∈ ℕ, m ≥ 2. Let Y be a simply connected pointed CW-complex, and let B be a finite set of continuous mappings a: S^m → Y respecting the distinguished points. Let Γ(a) ⊂ S^m × Y be the graph of a, and we denote by [a] ∈ π_m(Y) the homotopy class of a. Then for some r ∈ ℕ depending on m only, there exist a finite set E ⊂ S^m × Y and a mapping k: E(r) = {F ⊂ E: |F| ≤ r} → π_m(Y) such that for each a ∈ B we have

Renormalization and homogenization of fractional diffusion equations with random data

 This paper presents a renormalization and homogenization theory for fractional-in-space or in-time diffusion equations with singular random initial conditions. The spectral representations for the solutions of these equations are provided. Gaussian and non-Gaussian limiting distributions of the renormalized solutions of these equations are then described in terms of multiple stochastic integral representations. Received: 30 May 2000 / Revised version: 9 November 2001 / Published online: 10 September 2002 Mathematics Subject Classification (2000): Primary 62M40, 62M15; Secondary 60H05, 60G60 Key words or phrases: Fractional diffusion equation – Scaling laws – Renormalised solution – Long-range dependence – Non-Gaussian scenario – Mittag-Leffler function – Stable distributions – Bessel potential – Riesz potential     

Functional operators and properties of set functions

Let X be the F-space of the functions x(t) defined on the measurable space (T, Σ, μ) with values in B-space Y. We consider the operators f mapping X to the B-space Z. X, Y, and Z are considered over the scalar field R. To each operator f is associated the family Φ_f of vector-valued functions . The characteristics of these families are given for various classes of operators. The relationship of convergence and continuation of the operators f with convergence and continuation of the corresponding families Φ_f is considered. Riesz' theorem on integral representation of linear functionals is generalized. Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 159, pp. 113–118, 1987.     

On Haar expansion of Riemann–Liouville process in a critical case

We show that Haar-based series representation of the critical Riemann–Liouville process R^α with α =3/2 is rearrangement non-optimal in the sense of convergence rate in C[0, 1]. Bibliography: 10 titles.     

Dynamic allocation indices for restless projects and queueing admission control: a polyhedral approach

 This paper develops a polyhedral approach to the design, analysis, and computation of dynamic allocation indices for scheduling binary-action (engage/rest) Markovian stochastic projects which can change state when rested (restless bandits (RBs)), based on partial conservation laws (PCLs). This extends previous work by the author [J. Ni?o-Mora (2001): Restless bandits, partial conservation laws and indexability. Adv. Appl. Probab. 33, 76–98], where PCLs were shown to imply the optimality of index policies with a postulated structure in stochastic scheduling problems, under admissible linear objectives, and they were deployed to obtain simple sufficient conditions for the existence of Whittle's (1988) RB index (indexability), along with an adaptive-greedy index algorithm. The new contributions include: (i) we develop the polyhedral foundation of the PCL framework, based on the structural and algorithmic properties of a new polytope associated with an accessible set system -extended polymatroid}); (ii) we present new dynamic allocation indices for RBs, motivated by an admission control model, which extend Whittle's and have a significantly increased scope; (iii) we deploy PCLs to obtain both sufficient conditions for the existence of the new indices (PCL-indexability), and a new adaptive-greedy index algorithm; (iv) we interpret PCL-indexability as a form of the classic economics law of diminishing marginal returns, and characterize the index as an optimal marginal cost rate; we further solve a related optimal constrained control problem; (v) we carry out a PCL-indexability analysis of the motivating admission control model, under time-discounted and long-run average criteria; this gives, under mild conditions, a new index characterization of optimal threshold policies; and (vi) we apply the latter to present new heuristic index policies for two hard queueing control problems: admission control and routing to parallel queues; and scheduling a multiclass make-to-stock queue with lost sales, both under state-dependent holding cost rates and birth-death dynamics. Received: April 2000 / Accepted: October 2002 Published online: December 9, 2002 RID="★" ID="★" Work partly supported by the Spanish Ministry of Science and Technology (grant BEC2000-1027), NATO (Collaborative Linkage Grant PST.CLG.976568), and the Joint Spanish-US (Fulbright) Commission for Scientific and Technical Exchange (project 2000-20132) Key words. Markov decision process – restless bandits – polyhedral combinatorics – extended polymatroid – adaptive-greedy algorithm – dynamic allocation index – stochastic scheduling – threshold policy – index policy – Gittins index – Klimov index – Whittle index – control of queues – admission control – routing – make-to-stock – multiclass queue – finite buffers – conservation laws – achievable performance Mathematics Subject Classification (1991): (AMS 2000 Subject Classification): 90B36, 90B22, 90C40, 90C57, 90C08     

Convergence analysis of Jacobi spectral collocation methods for Abel-Volterra integral equations of second kind

This work is to analyze a spectral Jacobi-collocation approximation for Volterra integral equations with singular kernel ϕ(t, s) = (t − s)^−μ. In an earlier work of Y. Chen and T. Tang [J. Comput. Appl. Math., 2009, 233: 938–950], the error analysis for this approach is carried out for 0 < μ < 1/2 under the assumption that the underlying solution is smooth. It is noted that there is a technical problem to extend the result to the case of Abel-type, i.e., μ = 1/2. In this work, we will not only extend the convergence analysis by Chen and Tang to the Abel-type but also establish the error estimates under a more general regularity assumption on the exact solution.     

Weak convergence to fractional Brownian motion in Brownian scenery

 Kesten and Spitzer have shown that certain random walks in random sceneries converge to stable processes in random sceneries. In this paper, we consider certain random walks in sceneries defined using stationary Gaussian sequence, and show their convergence towards a certain self-similar process that we call fractional Brownian motion in Brownian scenery. Received: 17 April 2002 / Revised version: 11 October 2002 / Published online: 15 April 2003 Research supported by NSFC (10131040). Mathematics Subject Classification (2002): 60J55, 60J15, 60J65 Key words or phrases: Weak convergence – Random walk in random scenery – Local time – Fractional Brownian motion in Brownian scenery     

Pseudomonotone operators and the Bregman Proximal Point Algorithm

To permit the stable solution of ill-posed problems, the Proximal Point Algorithm (PPA) was introduced by Martinet (RIRO 4:154–159, 1970) and further developed by Rockafellar (SIAM J Control Optim 14:877–898, 1976). Later on, the usual proximal distance function was replaced by the more general class of Bregman(-like) functions and related distances; see e.g. Chen and Teboulle (SIAM J Optim 3:538–543, 1993), Eckstein (Math Program 83:113–123, 1998), Kaplan and Tichatschke (Optimization 56(1–2):253–265, 2007), and Solodov and Svaiter (Math Oper Res 25:214–230, 2000). An adequate use of such generalized non-quadratic distance kernels admits to obtain an interior-point-effect, that is, the auxiliary problems may be treated as unconstrained ones. In the above mentioned works and nearly all other works related with this topic it was assumed that the operator of the considered variational inequality is a maximal monotone and paramonotone operator. The approaches of El-Farouq (JOTA 109:311–326, 2001), and Schaible et al. (Taiwan J Math 10(2):497–513, 2006) only need pseudomonotonicity (in the sense of Karamardian in JOTA 18:445–454, 1976); however, they make use of other restrictive assumptions which on the one hand contradict the desired interior-point-effect and on the other hand imply uniqueness of the solution of the problem. The present work points to the discussion of the Bregman algorithm under significantly weaker assumptions, namely pseudomonotonicity [and an additional assumption much less restrictive than the ones used by El-Farouq and Schaible et al. We will be able to show that convergence results known from the monotone case still hold true; some of them will be sharpened or are even new. An interior-point-effect is obtained, and for the generated subproblems we allow inexact solutions by means of a unified use of a summable-error-criterion and an error criterion of fixed-relative-error-type (this combination is also new in the literature).