A recursive method for computing interpolants

In this paper, we describe a recursive method for computing interpolants defined in a space spanned by a finite number of continuous functions in R^d${\mathbb{R}}^d$. We apply this method to construct several interpolants such as spline interpolants, tensor product interpolants and multivariate polynomial interpolants. We also give a simple algorithm for solving a multivariate polynomial interpolation problem and constructing the minimal interpolation space for a given finite set of interpolation points.     

A simple method for smoothing functions and compressing Hermite data

Let =(a=x₀<x₁<<x_n=b) be a partition of an interval [a,b] of R, and let f be a piecewise function of class C^k on [a,b] except at knots x_i where it is only of class , k_ik. We study in this paper a novel method which smooth the function f at x_i, 0in. We first define a new basis of the space of polynomials of degree 2k+1, and we describe algorithms for smoothing the function f. Then, as an application, we give a recursive computation of classical Hermite spline interpolants, and we present a method which allows us to compress Hermite data. The most part of these results are illustrated by some numerical examples. AMS subject classification 41A05, 41A15, 65D05, 65D07, 65D10     

A non-interior-point smoothing method for variational inequality problem

In this paper, we focus on the variational inequality problem. Based on the Fischer-Burmeister function with smoothing parameters, the variational inequality problem can be reformulated as a system of parameterized smooth equations, a non-interior-point smoothing method is presented for solving the problem. The proposed algorithm not only has no restriction on the initial point, but also has global convergence and local quadratic convergence, moreover, the local quadratic convergence is established without a strict complementarity condition. Preliminary numerical results show that the algorithm is promising.     

A new modified one-step smoothing Newton method for solving the general mixed complementarity problem

In last decades, there has been much effort on the solution and the analysis of the mixed complementarity problem (MCP) by reformulating MCP as an unconstrained minimization involving an MCP function. In this paper, we propose a new modified one-step smoothing Newton method for solving general (not necessarily P₀) mixed complementarity problems based on well-known Chen-Harker-Kanzow-Smale smooth function. Under suitable assumptions, global convergence and locally superlinear convergence of the algorithm are established.     

A nonmonotone smoothing Newton method for circular cone programming

The circular cone programming (CCP) problem is to minimize or maximize a linear function over the intersection of an affine space with the Cartesian product of circular cones. In this paper, we study nondegeneracy and strict complementarity for the CCP, and present a nonmonotone smoothing Newton method for solving the CCP. We reformulate the CCP as a second-order cone programming (SOCP) problem using the algebraic relation between the circular cone and the second-order cone. Then based on a one parametric class of smoothing functions for the SOCP, a smoothing Newton method is developed for the CCP by adopting a new nonmonotone line search scheme. Without restrictions regarding its starting point, our algorithm solves one linear system of equations approximately and performs one line search at each iteration. Under mild assumptions, our algorithm is shown to possess global and local quadratic convergence properties. Some preliminary numerical results illustrate that our nonmonotone smoothing Newton method is promising for solving the CCP.     

A smoothing Newton method for mathematical programs constrained by parameterized quasi-variational inequalities

We consider a class of mathematical programs governed by parameterized quasi-variational inequalities(QVI).The necessary optimality conditions for the optimization problem with QVI constraints are reformulated as a system of nonsmooth equations under the linear independence constraint qualification and the strict slackness condition.A set of second order sufficient conditions for the mathematical program with parameterized QVI constraints are proposed,which are demonstrated to be sufficient for the second o...     

A class of smoothing functions for nonlinear and mixed complementarity problems

We propose a class of parametric smooth functions that approximate the fundamental plus function, (x)₊=max{0, x}, by twice integrating a probability density function. This leads to classes of smooth parametric nonlinear equation approximations of nonlinear and mixed complementarity problems (NCPs and MCPs). For any solvable NCP or MCP, existence of an arbitrarily accurate solution to the smooth nonlinear equations as well as the NCP or MCP, is established for sufficiently large value of a smoothing parameter . Newton-based algorithms are proposed for the smooth problem. For strongly monotone NCPs, global convergence and local quadratic convergence are established. For solvable monotone NCPs, each accumulation point of the proposed algorithms solves the smooth problem. Exact solutions of our smooth nonlinear equation for various values of the parameter , generate an interior path, which is different from the central path for interior point method. Computational results for 52 test problems compare favorably with these for another Newton-based method. The smooth technique is capable of solving efficiently the test problems solved by Dirkse and Ferris [6], Harker and Xiao [11] and Pang & Gabriel [28].This material is based on research supported by Air Force Office of Scientific Research Grant F49620-94-1-0036 and National Science Foundation Grant CCR-9322479.     

A new class of smoothing functions and a smoothing Newton method for complementarity problems

In this paper, we introduce a new class of smoothing functions, which include some popular smoothing complementarity functions. We show that the new smoothing functions possess a system of favorite properties. The existence and continuity of a smooth path for solving the nonlinear complementarity problem (NCP) with a P ₀ function are discussed. The Jacobian consistency of this class of smoothing functions is analyzed. Based on the new smoothing functions, we investigate a smoothing Newton algorithm for the NCP and discuss its global and local superlinear convergence. Some preliminary numerical results are reported.     

A new smoothing quasi-Newton method for nonlinear complementarity problems

A new smoothing quasi-Newton method for nonlinear complementarity problems is presented. The method is a generalization of Thomas’ method for smooth nonlinear systems and has similar properties as Broyden's method. Local convergence is analyzed for a strictly complementary solution as well as for a degenerate solution. Presented numerical results demonstrate quite similar behavior of Thomas’ and Broyden's methods.     

A smoothing Newton method for second-order cone optimization based on a new smoothing function

A new smoothing function is given in this paper by smoothing the symmetric perturbed Fischer-Burmeister function. Based on this new smoothing function, we present a smoothing Newton method for solving the second-order cone optimization (SOCO). The method solves only one linear system of equations and performs only one line search at each iteration. Without requiring strict complementarity assumption at the SOCO solution, the proposed algorithm is shown to be globally and locally quadratically convergent. Numerical results demonstrate that our algorithm is promising and comparable to interior-point methods.     

A new smoothing Newton method for solving constrained nonlinear equations

In this paper, a new smoothing Newton method is proposed for solving constrained nonlinear equations. We first transform the constrained nonlinear equations to a system of semismooth equations by using the so-called absolute value function of the slack variables, and then present a new smoothing Newton method for solving the semismooth equations by constructing a new smoothing approximation function. This new method is globally and quadratically convergent. It needs to solve only one system of unconstrained equations and to perform one line search at each iteration. Numerical results show that the new algorithm works quite well.     

A new smoothing Newton-type method for second-order cone programming problems

A new smoothing function of the well-known Fischer–Burmeister function is given. Based on this new function, a smoothing Newton-type method is proposed for solving second-order cone programming. At each iteration, the proposed algorithm solves only one system of linear equations and performs only one line search. This algorithm can start from an arbitrary point and it is Q-quadratically convergent under a mild assumption. Numerical results demonstrate the effectiveness of the algorithm.     

A finite volume method on general surfaces and its error estimates

In this paper, we study a finite volume method and its error estimates for the numerical solution of some model second order elliptic partial differential equations defined on a smooth surface. The discretization is defined via a surface mesh consisting of piecewise planar triangles and piecewise polygons. The optimal error estimates of the approximate solution are proved in both the H¹ and L² norms which are of first order and second order respectively under mesh regularity assumptions. Some numerical tests are also carried out to experimentally verify our theoretical analysis.     

One-step smoothing Newton method for solving the mixed complementarity problem with a function

The mixed complementarity problem (denote by MCP(F)) can be reformulated as the solution of a smooth system of equations. In the paper, based on a perturbed mid function, we propose a new smoothing function, which has an important property, not satisfied by many other smoothing function. The existence and continuity of a smooth path for solving the mixed complementarity problem with a P₀ function are discussed. Then we presented a one-step smoothing Newton algorithm to solve the MCP with a P₀ function. The global convergence of the proposed algorithm is verified under mild conditions. And by using the smooth and semismooth technique, the rate of convergence of the method is proved under some suitable assumptions.     

A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities

In this paper we take a new look at smoothing Newton methods for solving the nonlinear complementarity problem (NCP) and the box constrained variational inequalities (BVI). Instead of using an infinite sequence of smoothing approximation functions, we use a single smoothing approximation function and Robinson’s normal equation to reformulate NCP and BVI as an equivalent nonsmooth equation H(u,x)=0, where H:ℜ ²ⁿ →ℜ ²ⁿ , u∈ℜ ⁿ is a parameter variable and x∈ℜ ⁿ is the original variable. The central idea of our smoothing Newton methods is that we construct a sequence {z ^k =(u ^k ,x ^k )} such that the mapping H(·) is continuously differentiable at each z ^k and may be non-differentiable at the limiting point of {z ^k }. We prove that three most often used Gabriel-Moré smoothing functions can generate strongly semismooth functions, which play a fundamental role in establishing superlinear and quadratic convergence of our new smoothing Newton methods. We do not require any function value of F or its derivative value outside the feasible region while at each step we only solve a linear system of equations and if we choose a certain smoothing function only a reduced form needs to be solved. Preliminary numerical results show that the proposed methods for particularly chosen smoothing functions are very promising. Received June 23, 1997 / Revised version received July 29, 1999?Published online December 15, 1999     

A new smoothing and regularization Newton method for the symmetric cone complementarity problem

Based on a regularized Chen–Harker–Kanzow–Smale (CHKS) smoothing function, we propose a new smoothing and regularization Newton method for solving the symmetric cone complementarity problem. By using the theory of Euclidean Jordan algebras, we establish the global and local quadratic convergence of the method on certain assumptions. The proposed method uses a nonmonotone line search technique which includes the usual monotone line search as a special case. In addition, our method treats both the smoothing parameter \(\mu \) and the regularization parameter \(\varepsilon \) as independent variables. Preliminary numerical results are reported which indicate that the proposed method is effective.     

A local smoothing estimate for the Schrödinger equation

We show that the Schrödinger operator eitΔ is bounded from Wα,q(Rn) to Lq(Rn×[0,1]) for all α>2n(1/2−1/q)−2/q and q?2+4/(n+1). This is almost sharp with respect to the Sobolev index. We also show that the Schrödinger maximal operator sup0<t<1|eitΔf| is bounded from Hs(Rn) to when s>s₀ if and only if it is bounded from Hs(Rn) to L²(Rn) when s>2s₀. A corollary is that sup0<t<1|eitΔf| is bounded from Hs(R²) to L²(R²) when s>3/4.