Convergence Properties of a Self-adaptive Levenberg-Marquardt Algorithm Under Local Error Bound Condition

We propose a new self-adaptive Levenberg-Marquardt algorithm for the system of nonlinear equations F(x) = 0. The Levenberg-Marquardt parameter is chosen as the product of ‖F_k‖^δ with δ being a positive constant, and some function of the ratio between the actual reduction and predicted reduction of the merit function. Under the local error bound condition which is weaker than the nonsingularity, we show that the Levenberg-Marquardt method converges superlinearly to the solution for δ∈ (0, 1), while quadratically for δ∈ [1, 2]. Numerical results show that the new algorithm performs very well for the nonlinear equations with high rank deficiency. This work is supported by Chinese NSFC grants 10401023 and 10501013, Research Grants for Young Teachers of Shanghai Jiao Tong University, and E-Institute of Shanghai Municipal Education Commission, N. E03004.     

A perturbed version of an inexact generalized Newton method for solving nonsmooth equations

In this paper, we present the combination of the inexact Newton method and the generalized Newton method for solving nonsmooth equations F(x)?=?0, characterizing the local convergence in terms of the perturbations and residuals. We assume that both iteration matrices taken from the B-differential and vectors F(x ^(k)) are perturbed at each step. Some results are motivated by the approach of C?tina? regarding to smooth equations. We study the conditions, which determine admissible magnitude of perturbations to preserve the convergence of method. Finally, the utility of these results is considered based on some variant of the perturbed inexact generalized Newton method for solving some general optimization problems.     

On a function associated with the Bessel functions

Summary Defining the function Δn, 1,k;x(J) asΔn, 1,k;x(J)=J _n+1(x)−J _n(x)J _n+k+1(x) associated with the Bessel functionJ _n(x), we derive a series of products of Bessel functions for Δ_{n, f, k, x} (J). Whenk=1,k;x (J) becomes Turàn expression for Bessel functions. Some consequences have been pointed out.

---

Riassunto Definita la Δ_{n, f, k, x} (J) come Δ_{n, f, k, x}, (J)=J _n+1(x)J _n+k(x)-J _n(_n+k+1)(x) associata alla funzioneJ _n(x) di Bessel, si ricava una serie di prodotti di funzioni di Bessel per Δ_{n, f, k, x}, (J). 3 Quandok=1, Δ_{n, f, k, x}, (J) diventa una espressione di Turàn per le funzioni di 2 Bessel, vengono inoltre indicate alcune altre conseguenze.

     

The Johnson–Lindenstrauss Lemma Almost Characterizes Hilbert Space, But Not Quite

Let X be a normed space that satisfies the Johnson–Lindenstrauss lemma (J–L lemma, in short) in the sense that for any integer n and any x ₁,…,x _n ∈X, there exists a linear mapping L:X→F, where F⊆X is a linear subspace of dimension O(log n), such that ‖x _i −x _j ‖≤‖L(x _i )−L(x _j )‖≤O(1)⋅‖x _i −x _j ‖ for all i,j∈{1,…,n}. We show that this implies that X is almost Euclidean in the following sense: Every n-dimensional subspace of X embeds into Hilbert space with distortion 2^2O(log*n)2^{2^{O(\log^{*}n)}} . On the other hand, we show that there exists a normed space Y which satisfies the J–L lemma, but for every n, there exists an n-dimensional subspace E _n ⊆Y whose Euclidean distortion is at least 2^Ω(α(n)), where α is the inverse Ackermann function.     

Greedy Drawings of Triangulations

Greedy Routing is a class of routing algorithms in which the packets are forwarded in a manner that reduces the distance to the destination at every step. In an attempt to provide theoretical guarantees for a class of greedy routing algorithms, Papadimitriou and Ratajczak (Theor. Comput. Sci. 344(1):3–14, 2005) came up with the following conjecture:

Any 3-connected planar graph can be drawn in the plane such that for every pair of vertices s and t a distance decreasing path can be found. A path s=v ₁,v ₂,…,v _k =t in a drawing is said to be distance decreasing if ‖v _i −t‖<‖v _i−1−t‖,2≤i≤k where ‖…‖ denotes the Euclidean distance.

We settle this conjecture in the affirmative for the case of triangulations.     

Continuation of Time Bounds for a Regularized Boussinesq System

We study the periodic solution of a perturbed regularized Boussinesq system (Bona et al., J. Nonlinear Sci. 12:283–318, 2002, Bona et al., Nonlinearity 17:925–952, 2004), namely the system η _t +u _x +β(−η _xxt +u _xxx )+α((ηu) _x +ηη _x +uu _x )=0,u _t +η _x +β(η _xxx −u _xxt )+α((ηu) _x +ηη _x +uu _x )=0, with 0<α,β≤1. We prove that the solution, starting from an initial datum of size ε, remains smaller than ε for a time scale of order (ε ⁻¹ α ⁻¹ β)², whereas the natural time is of order ε ⁻¹ α ⁻¹ β.     

Iterative methods based on the signum function approach for solving nonlinear equations

For finding a root of an equation f(x) = 0 on an interval (a, b), we develop an iterative method using the signum function and the trapezoidal rule for numerical integrations based on the recent work (Yun, Appl Math Comput 198:691–699, 2008). This method, so-called signum iteration method, depends only on the signum function sgn(f(x)){\rm{sgn}}\left(f(x)\right) independently of the behavior of f(x), and the error bound of the kth approximation is (b − a)/(2N ^k ), where N is the number of integration points for the trapezoidal rule in each iteration. In addition we suggest hybrid methods which combine the signum iteration method with usual methods such as Newton, Ostrowski and secant methods. In particular the hybrid method combined with the signum iteration and the secant method is a predictor-corrector type method (Noor and Ahmad, Appl Math Comput 180:167–172, 2006). The proposed methods result in the rapidly convergent approximations, without worry about choosing a proper initial guess. By some numerical examples we show the superiority of the presented methods over the existing iterative methods.     

The bicompletion of an asymmetric normed linear space

A biBanach space is an asymmetric normed linear space (X,‖·‖) such that the normed linear space (X,‖·‖^s) is a Banach space, where ‖x‖^s= max {‖x‖,‖-x‖} for all x∈X. We prove that each asymmetric normed linear space (X,‖·‖) is isometrically isomorphic to a dense subspace of a biBanach space (Y,‖·‖_Y). Furthermore the space (Y,‖·‖_Y) is unique (up to isometric isomorphism). This revised version was published online in August 2006 with corrections to the Cover Date.     

Swan-like results for binomials and trinomials over finite fields of odd characteristic

Swan (Pac. J. Math. 12:1099–1106, 1962) gives conditions under which the trinomial x ⁿ + x ^k + 1 over \mathbbF₂{\mathbb{F}_{2}} is reducible. Vishne (Finite Fields Appl. 3:370–377, 1997) extends this result to trinomials over extensions of \mathbbF₂{\mathbb{F}_{2}}. In this work we determine the parity of the number of irreducible factors of all binomials and some trinomials over the finite field \mathbbF_q{\mathbb{F}_{q}}, where q is a power of an odd prime.     

Optimal properties of contraction semigroups in banach spaces

Suppose that(T _t )_t>0 is aC ₀ semi-group of contractions on a Banach spaceX, such that there exists a vectorx∈X, ‖x‖=1 verifyingJ ⁻¹(Jx)={x}, whereJ is the duality mapping fromX toP(X ^*). If |<T _t x,f>|→1, whent→+∞ for somef∈X ^*, ‖f‖≤1 thenx is an eigenvector of the generatorA, associated with a purcly imaginary eigenvalue. Because of Lin's example [L], the hypothesis onx∈X is the best possible. If the hypothesisJ ⁻¹(Jx)={x} is not verified, we can prove that ifJx is a singleton and ifJ ⁻¹(Jx) is weakly compact, then if |<T _t x, f>|→1, whent→+∞ for somef∈X ^*, ‖f‖≤1, there existsy∈J ⁻¹(Jx) such thaty is an eigenvector of the generatorA, associated with a purely imaginary eigenvalue. We give also a counter-example in the case whereX is one of the spaces ℓ₁ orL ₁.     

Accelerated hybrid conjugate gradient algorithm with modified secant condition for unconstrained optimization

An accelerated hybrid conjugate gradient algorithm represents the subject of this paper. The parameter β _k is computed as a convex combination of b_k^HS\beta_k^{HS} (Hestenes and Stiefel, J Res Nat Bur Stand 49:409–436, 1952) and b_k^DY\beta_k^{DY} (Dai and Yuan, SIAM J Optim 10:177–182, 1999), i.e. b_k^C = (1-q_k)b_k^HS + q_k b_k^DY\beta_k^C =\left({1-\theta_k}\right)\beta_k^{HS} + \theta_k \beta_k^{DY}. The parameter θ _k in the convex combinaztion is computed in such a way the direction corresponding to the conjugate gradient algorithm is the best direction we know, i.e. the Newton direction, while the pair (s _k , y _k ) satisfies the modified secant condition given by Li et al. (J Comput Appl Math 202:523–539, 2007) B _k + 1 s _k  = z _k , where z_k = y_k +(h_k / || s_k ||² )s_kz_k =y_k +\left({{\eta_k} / {\left\| {s_k} \right\|^2}} \right)s_k, h_k = 2( f_k -f_k+1 )+( g_k +g_k+1 )^Ts_k\eta_k =2\left( {f_k -f_{k+1}} \right)+\left( {g_k +g_{k+1}} \right)^Ts_k, s _k  = x _k + 1 − x _k and y _k  = g _k + 1 − g _k . It is shown that both for uniformly convex functions and for general nonlinear functions the algorithm with strong Wolfe line search is globally convergent. The algorithm uses an acceleration scheme modifying the steplength α _k for improving the reduction of the function values along the iterations. Numerical comparisons with conjugate gradient algorithms show that this hybrid computational scheme outperforms a variant of the hybrid conjugate gradient algorithm given by Andrei (Numer Algorithms 47:143–156, 2008), in which the pair (s _k , y _k ) satisfies the classical secant condition B _k + 1 s _k  = y _k , as well as some other conjugate gradient algorithms including Hestenes-Stiefel, Dai-Yuan, Polack-Ribière-Polyak, Liu-Storey, hybrid Dai-Yuan, Gilbert-Nocedal etc. A set of 75 unconstrained optimization problems with 10 different dimensions is being used (Andrei, Adv Model Optim 10:147–161, 2008).     

Embeddings ofl p m intol ∞ n , 1≦p≦2

Isomorphic embeddings ofl _l ^m intol _∞ ⁿ are studied, and ford(n, k)=inf{‖T ‖ ‖T ⁻¹ ‖;T varies over all isomorphic embeddings ofl ₁ ^[klog2n] intol _∞ ⁿ we have that lim _n→∞ d(n, k)=γ(k)⁻¹,k>1, whereγ(k) is the solution of (1+γ)ln(1+γ)+(1 −γ)ln(1 −γ)=k ⁻¹ln4. Here [x] denotes the integer part of the real numberx.     

Solution of monotone complementarity problems with locally Lipschitzian functions

The paper deals with complementarity problems CP(F), where the underlying functionF is assumed to be locally Lipschitzian. Based on a special equivalent reformulation of CP(F) as a system of equationsφ(x)=0 or as the problem of minimizing the merit functionΘ=1/2∥Φ∥ ₂ ² , we extend results which hold for sufficiently smooth functionsF to the nonsmooth case. In particular, ifF is monotone in a neighbourhood ofx, it is proved that 0 εδθ(x) is necessary and sufficient forx to be a solution of CP(F). Moreover, for monotone functionsF, a simple derivative-free algorithm that reducesΘ is shown to possess global convergence properties. Finally, the local behaviour of a generalized Newton method is analyzed. To this end, the result by Mifflin that the composition of semismooth functions is again semismooth is extended top-order semismooth functions. Under a suitable regularity condition and ifF isp-order semismooth the generalized Newton method is shown to be locally well defined and superlinearly convergent with the order of 1+p.     

A global Newton method for the zeros of cylinder functions

The zeros of cylinder functions C _u (x)=cos α, J _u (x) - sin α, Y _u(x) coincide with those of the ratios H _u (x)=C _u (x)/C _u-1 (x) except, perhaps, at x = 0. We show monotonicity properties of H u(x) and f _u (x) = x ^2v-1 H u(x) and their derivatives for x > 0. We then build a Newton-Raphson iterative method based on the monotonic function f u(x) which is shown to be convergent, for any real values of u and α and any starting value x ₀ > 0, to an sth positive root c ,s of C _u (x) = 0, s being such that c _,s and x0 belong to the same interval (c _u-1 ,s', c _{u -1} ,s'+1]. We also show applications of the method. In particular, taking advantage of the fact that the ratio H _u (x) for first kind Bessel functions J u(x) can be evaluated by using a continued fraction, a very simple algorithm is built; it becomes especially efficient for low values of u and s and it allows the evaluation of the real zeros for arbitrary orders u, positive or negative. This revised version was published online in August 2006 with corrections to the Cover Date.     

A sieve result for Farey fractions

This paper is concerned with the sieve problem for Farey fractions (i.e., rational numbers with denominators less thanx) lying in an interval (λ₁, λ₂). An asymptotic formula for the sifting function is derived under the assumption that (λ₁, λ₂)x→∞ asx→∞. Two applications of this result are made. In the first one, the value distribution of the vector η(m/n)=(ξ(m), ξ(n)) is considered; here, fork=p ₁ p ₂...p _s ,p ₁≥p ₂>-..., ξk)_is defined by ξ(k)=(logp ₁/logk, logp ₂/logk,..., logp _s /logk, 0, ...); allp _i are prime numbers. It is shown that the limit distribution is π×π, where π is the Poisson-Dirichlet distribution. The asymptotical behavior of finite-dimensional distributions of ξ(k) for natural numbers was studied by Billingsley, Knuth, Trabb Pardo, Vershik, and others; the result of weak convergence to the Poisson-Dirichlet distribution appears in Donnelly and Grimmett. The second application is concerned with the density of sets {m/n: f(m/n)=a}, wheref is a function with the almost squareful kernel. Supported by the Lithuanian State Science and Studies Foundation. Vilnius University, Naugarduko 24, 2600, Vilnius, Lithuania. Translated from Lietuvos Matematikos Rinkinys, Vol. 39, No. 1, pp. 108–127, January–March, 1999. Translated by V. Stakénas     

General Study of Iterative Processes of <Emphasis Type="Italic">R</Emphasis>-Order at Least Three under Weak Convergence Conditions

We consider a family of Newton-type iterative processes solving nonlinear equations in Banach spaces, that generalizes the usually iterative methods of R-order at least three. The convergence of this family in Banach spaces is usually studied when the second derivative of the operator involved is Lipschitz continuous and bounded. In this paper, we relax the first condition, assuming that ‖F″(x)−F″(y)‖≤ω(‖x−y‖), where ω is a nondecreasing continuous real function. We prove that the different R-orders of convergence that we can obtain depend on the quasihomogeneity of the function ω. We end the paper by applying the study to some nonlinear integral equations. This work was supported by the Ministry of Science and Technology (BFM 2002-00222), the University of La Rioja (API-04/13) and the Government of La Rioja (ACPI 2003/2004).     

The range of a projection of small norm inl 1 n

It is proved that there exists a positive function Φ(∈) defined for sufficiently small ∈ 〉 0 and satisfying lim_t→0 Φ(∈) =0 such that for any integersn 〉>0, ifQ is a projection ofl ₁ ⁿ onto ak-dimensional subspaceE with ‖|Q‖|≦1+∈ then there is an integerh〉=k(1−Φ(∈)) and anh-dimensional subspaceF ofE withd(F,l ₁ ^h ) 〈= 1+Φ (∈) whered(X, Y) denotes the Banach-Mazur distance between the Banach spacesX andY. Moreover, there is a projectionP ofl ₁ ⁿ ontoF with ‖|P‖| ≦1+Φ(∈). Author was partially supported by the N.S.F. Grant MCS 79-03042.     

Integral kašin splittings

Forx ∈ ℝ ⁿ andp≥1 put ‖x‖ _p :=(n ⁻¹Σ|x _i| ^p )^1/p . An orthogonal direct sum decomposition ℝ^2k =E⊕E ^⊥ where dimE=k and ‖x‖₂/‖x‖₁≤C is called here a (k, C)-splitting. By a theorem of Kašin there existsC>0 such that (k, C)-splittings exist for allk, and by the volume ratio method of Szarek one can takeC=32eπ. All proofs of existence of (k, C)-splittings heretofore given are nonconstructive. Here we investigate the representation of (k, C)-splittings by matrices with integral entries. For everyC>8e _1/2 π _−1/2 and positive integerk we specify a positive integerN(k, C) such that in the set ofk by 2k matrices with integral entries of absolute value not exceedingN(k, C) there exists a matrix with row span a summand in a (k, C)-splitting. We haveN(k, C)≤2^18k fork large enough depending onC. We explain in detail how to test a matrix for the property of representing a (k, C)-splitting. Taken together our results yield an explicit (if impractical) construction of (k, C)-splittings.     

Existence of subgraph with orthogonal (g,f)-factorization

Simple graphs are considered. Let G be a graph andg(x) andf(x) integer-valued functions defined on V(G) withg(x)⩽f(x) for everyxɛV(G). For a subgraphH ofG and a factorizationF=|F ₁,F ₂,⃛,F ₁| ofG, if |E(H)∩E(F ₁)|=1,1⩽i⩽j, then we say thatF orthogonal toH. It is proved that for an (mg(x)+k,mf(x) -k)-graphG, there exists a subgraphR ofG such that for any subgraphH ofG with |E(H)|=k,R has a (g,f)-factorization orthogonal toH, where 1⩽k<m andg(x)⩾1 orf(x)⩾5 for everyxɛV(G). Project supported by the Chitia Postdoctoral Science Foundation and Chuang Xin Foundation of the Chinese Academy of Sciences.     

Variable target value relaxed alternating projection method

In this paper we propose a modification of the von Neumann method of alternating projection x _k+1=P _A P _B x _k where A,B are closed and convex subsets of a real Hilbert space ℋ. If Fix P _A P _B ≠∅ then any sequence generated by the classical method converges weakly to a fixed point of the operator T=P _A P _B . If the distance δ=inf  _x∈A,y∈B ‖ x−y ‖ is known then one can efficiently apply a modification of the von Neumann method, which has the form x _k+1=P _A (x _k +λ _k (P _A P _B x _k −x _k )) for λ _k >0 depending on x _k (for details see: Cegielski and Suchocka, SIAM J. Optim. 19:1093–1106, 2008). Our paper contains a generalization of this modification, where we do not suppose that we know the value δ. Instead of δ we apply its approximation which is updated in each iteration.