A globally convergent method for solving nonlinear equations without the differentiability condition

We give a general iterative method which computes the maximal real rootx _max of a one variable Lipschitzian function in a given interval. The method generates a monotonically decreasing sequence which converges towardsx _max or demonstrates the non-existence of a real root in the considered interval. We show that the method is globally convergent and locally linearly convergent. We also compute the number of iterations needed to reach the given accuracy.     

解变分不等式问题的混合方法

By using Fukushima‘s differentiable merit function,Taji,Fukushima and Ibaraki have given a globally convergent modified Newton method for the strongly monotone variational inequality problem and proved their method to be quadratically convergent under certain assumptions in 1993. In this paper a hybrid method for the variational inequality problem under the assumptions that the mapping F is continuously differentiable and its Jacobian matrix F(x) is positive definite for all x∈S rather than strongly monotone and that the set S is nonempty, polyhedral,closed and convex is proposed. Armijo-type line search and trust region strategies as well as Fukushima‘s differentiable merit function are incorporated into the method. It is then shown that the method is well defined and globally convergent and that,under the same assumptions as those of Taji et al. ,the method reduces to the basic Newton method and hence the rate of convergence is quadratic. Computational experiences show the efficiency of the proposed method.     

Automatic Smoothing Spline Projection Pursuit

Abstract

A highly flexible nonparametric regression model for predicting a response y given covariates {x_k}^d _k=1 is the projection pursuit regression (PPR) model ? = h(x) = β₀ + Σ_jβ_jf_j(α^T _jx) where the f_j , are general smooth functions with mean 0 and norm 1, and Σ^d _k=1α² _kj=1. The standard PPR algorithm of Friedman and Stuetzle (1981) estimates the smooth functions f_j using the supersmoother nonparametric scatterplot smoother. Friedman's algorithm constructs a model with M _max linear combinations, then prunes back to a simpler model of size M ≤ M _max, where M and M _max are specified by the user. This article discusses an alternative algorithm in which the smooth functions are estimated using smoothing splines. The direction coefficients α_j, the amount of smoothing in each direction, and the number of terms M and M _max are determined to optimize a single generalized cross-validation measure.     

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.     

New multiplier method for solving linear complementarity problems

A new multiplier method for solving the linear complementarity problem LCP(q, M) is proposed. By introducing a Lagrangian of LCP(q, M), a new smooth merit function ϑ(x, λ) for LCP(q, M) is constructed. Based on it, a simple damped Newton-type algorithm with multiplier self-adjusting step is presented. When M is a P-matrix, the sequence {ϑ(x ^k, λ ^k)} (where {(x ^k, λ ^k)} is generated by the algorithm) is globally linearly convergent to zero and convergent in a finite number of iterations if the solution is degenerate. Numerical results suggest that the method is highly efficient and promising. Selected from Numerical Mathematics (A Journal of Chinese Universities), 2004, 26(2): 162–171     

Finding independent sets in a graph using continuous multivariable polynomial formulations

Two continuous formulations of the maximum independent set problem on a graph G=(V,E) are considered. Both cases involve the maximization of an n-variable polynomial over the n-dimensional hypercube, where n is the number of nodes in G. Two (polynomial) objective functions F(x) and H(x) are considered. Given any solution to x ₀ in the hypercube, we propose two polynomial-time algorithms based on these formulations, for finding maximal independent sets with cardinality greater than or equal to F(x₀) and H(x₀), respectively. A relation between the two approaches is studied and a more general statement for dominating sets is proved. Results of preliminary computational experiments for some of the DIMACS clique benchmark graphs are presented.     

The Alternative Dunford–Pettis Property for Subspaces of the Compact Operators

A Banach space X has the alternative Dunford–Pettis property if for every weakly convergent sequences (x_n) → x in X and (x_n*) → 0 in X* with ||x_n|| = ||x||= 1 we have (x_n*(x_n)) → 0. We get a characterization of certain operator spaces having the alternative Dunford–Pettis property. As a consequence of this result, if H is a Hilbert space we show that a closed subspace M of the compact operators on H has the alternative Dunford–Pettis property if, and only if, for any h ∈ H, the evaluation operators from M to H given by S ↦ Sh, S ↦ S^th are DP1 operators, that is, they apply weakly convergent sequences in the unit sphere whose limits are also in the unit sphere into norm convergent sequences. We also prove a characterization of certain closed subalgebras of K(H) having the alternative Dunford-Pettis property by assuming that the multiplication operators are DP1.     

Rosen's Gradient Projection with discrete steps

In 1960, J. B. Rosen gave a famous Gradient Projection Method in [1]. But the convergence of the algorithm has not been proved for a long time. Many authors paid much attention to this problem, such as X.S. Zhang proved in [2] (1984) that the limit point of {x _k} which is generated by Rosen's algorithm is a K-T piont for a 3-dimensional caes, if {x _k} is convergent. D. Z. Du proved in [3] (1986) that Rosen's algorithm is convergent for 4-dimensional. In [4] (1986), the author of this paper gave a general proof of the convergence of Rosen's Gradient Projection Method for ann-dimensional case. As Rosen's method requires exact line search, we know that exact line search is very difficult on computer. In this paper a line search method of discrete steps are presented and the convergence of the algorithm is proved.     

Approximations and Well-Posedness in Multicriteria Games

First, sufficient conditions of minimal character are given which guarantee the sequential closedness of the set-valued function defined by the parametric weak-multicriteria Nash equilibria of a parametric multicriteria game, that is to say: a convergent sequence of parametric weak-multicriteria Nash equilibria, corresponding to an approximate value of the parameter x_n, converges to a weak-multicriteria Nash equilibrium corresponding to the limit value x of the sequence (x_n)_n. Then, approximating sequences and parametrically well-posedness for a multicriteria game are introduced and investigated.     

An everywhere convergent series representation of the distribution of Hotelling's generalized T0

A new series representation of the exact distribution of Hotelling's generalized T₀² statistic is obtained. Unlike earlier work, the series representation given here is everywhere convergent. Explicit formulae are given for both the null and the non-central distributions. Earlier results by [1], 215–225), which are convergent on the interval [0, 1), are also derived quite simply from our formulae. The paper therefore provides a solution to the long standing problem of the exact distribution of the T₀² statistic in the general case.     

A Smoothing Newton Method for General Nonlinear Complementarity Problems

Smoothing Newton methods for nonlinear complementarity problems NCP(F) often require F to be at least a P ₀-function in order to guarantee that the underlying Newton equation is solvable. Based on a special equation reformulation of NCP(F), we propose a new smoothing Newton method for general nonlinear complementarity problems. The introduction of Kanzow and Pieper's gradient step makes our algorithm to be globally convergent. Under certain conditions, our method achieves fast local convergence rate. Extensive numerical results are also reported for all complementarity problems in MCPLIB and GAMSLIB libraries with all available starting points.     

Acceleration methods based on convergence tests

Summary In this paper we propose an acceleration method based on a general convergence test and depending on an auxiliary sequence (x _n). For different choices of (x _n) we obtain some known and some new transformations and for each one sufficient conditions for acceleration are given.     

Higher-Order Method for the Solution of a Nonlinear Scalar Equation

A new iterative method to find the root of a nonlinear scalar function f is proposed. The method is based on a suitable Taylor polynomial model of order n around the current point x _k and involves at each iteration the solution of a linear system of dimension n. It is shown that the coefficient matrix of the linear system is nonsingular if and only if the first derivative of f at x _k is not null. Moreover, it is proved that the method is locally convergent with order of convergence at least n + 1. Finally, an easily implementable scheme is provided and some numerical results are reported.     

On uniform convergence of approximation methods for operator equations of the second kind

Schock (1985) has considered the convergence properties of various Galerkin-like methods for the approximate solution of the operator equation of the second kind x - Tx = y, where T is a bounded linear operator on a Banach space X, and x and y belong to X, and proved that the classical Galerkin method and in certain cases, the iterated Galerkin method are arbitrarily slowly convergent whereas the Kantororich method studied by him is uniformly convergent. It is the purpose of this paper to introduce a general class of approximations methods for x - Tx = y which includes the well-known methods of projection and the quadrature methods, and to characterize its uniform convergence, so that an arbitrarily slowly convergent method can be modified to obtain a uniformly convergent method.     

Global existence and decay of solutions of a singular nonlocal viscoelastic system with a nonlinear source term,nonlocal boundary condition,and localized damping term

The paper deals with the existence of a global solution of a singular one-dimensional viscoelastic system with a nonlinear source term, nonlocal boundary condition, and localized frictional damping a(x)u_t using the potential well theory. Furthermore, the general decay result is proved. We construct a suitable Lyapunov functional and make use of the perturbed energy method.     

A generalized Dantzig—Wolfe decomposition principle for a class of nonconvex programming problems

Since Dantzig—Wolfe's pioneering contribution, the decomposition approach using a pricing mechanism has been developed for a wide class of mathematical programs. For convex programs a linear space of Lagrangean multipliers is enough to define price functions. For general mathematical programs the price functions could be defined by using a subclass of nondecreasing functions. However the space of nondecreasing functions is no longer finite dimensional. In this paper we consider a specific nonconvex optimization problem min {f(x):h _j (x)g(x),j=1, ,m, xX}, wheref(·),h _j (·) andg(·) are finite convex functions andX is a closed convex set. We generalize optimal price functions for this problem in such a way that the parameters of generalized price functions are defined in a finite dimensional space. Combining convex duality and a nonconvex duality we can develop a decomposition method to find a globally optimal solution.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.     

A layer adaptive B‐spline collocation method for singularly perturbed one‐dimensional parabolic problem with a boundary turning point

In this article, we develop a parameter uniform numerical method for a class of singularly perturbed parabolic equations with a multiple boundary turning point on a rectangular domain. The coefficient of the first derivative with respect to x is given by the formula a₀(x, t)x^p, where a₀(x, t) ≥ α > 0 and the parameter p ∈ [1,∞) takes the arbitrary value. For small values of the parameter ε, the solution of this particular class of problem exhibits the parabolic boundary layer in a neighborhood of the boundary x = 0 of the domain. We use the implicit Euler method to discretize the temporal variable on uniform mesh and a B‐spline collocation method defined on piecewise uniform Shishkin mesh to discretize the spatial variable. Asymptotic bounds for the derivatives of the solution are established by decomposing the solution into smooth and singular component. These bounds are applied in the convergence analysis of the proposed scheme on Shishkin mesh. The resulting method is boundary layer resolving and has been shown almost second‐order accurate in space and first‐order accurate in time. It is also shown that the proposed method is uniformly convergent with respect to the singular perturbation parameter ε. Some numerical results are given to confirm the predicted theory and comparison of numerical results made with a scheme consisting of a standard upwind finite difference operator on a piecewise uniform Shishkin mesh. © 2010 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 27: 1143–1164, 2011     

A Combined Algorithm for Fractional Programming

In this paper, we present an outer approximation algorithm for solving the following problem: max _xS {f(x)/g(x)}, where f(x)0 and g(x)>0 are d.c. (difference of convex) functions over a convex compact subset S of R ⁿ . Let ()=max _xS (f(x)–g(x)), then the problem is equivalent to finding out a solution of the equation ()=0. Though the monotonicity of () is well known, it is very time-consuming to solve the previous equation, because that maximizing (f(x)–g(x)) is very hard due to that maximizing a convex function over a convex set is NP-hard. To avoid such tactics, we give a transformation under which both the objective and the feasible region turn to be d.c. After discussing some properties, we propose a global optimization approach to find an optimal solution for the encountered problem.     

An implicit one-step method of high-order accuracy for the numerical integration of ordinary differential equations

For a differential equationdx/dt=f(t, x) withf _t (t, x),f _x (t, x) computable, the author presents a new one-step method of high-order accuracy. A rule of controlling the mesh size is given and the method is compared with the Runge-Kutta method in two numerical examples.Dedicated to Professor Dr. Dr. h. c. L. Collatz for his 60^th birthday     

A Parallel Algorithm for the Estimation of the Global Error in Runge–Kutta Methods

The object of this work is the estimate of the global error in the numerical solution of the IVP for a system of ODE's. Given a Runge–Kutta formula of order q, which yields an approximation y _n to the true value y(x _n ), a general, parallel method is presented, that provides a second value y _n ^* of order q+2; the global error e _n =y _n –y(x _n ) is then estimated by the difference y _n –y _n ^*. The numerical tests reported, show the very good performance of the procedure proposed. A comparison with the code GEM90 is also appended.