Spline prewavelets for non-uniform knots

Summary In this paper, we develop a framework suitable for performing a multiresolution analysis using univariate spline spaces of arbitrary degree and with non-uniform knot-sequences. To this end, we show, among other things, the existence of compactly supported prewavelets and of prewavelets that are globally supported, but decay exponentially. In each case we obtain a decomposition of a fine spline space as a sum of a coarse spline space plus a spline space spanned by prewavelets.     

Piecewise linear prewavelets on arbitrary triangulations

This paper studies locally supported piecewise linear prewavelets on bounded triangulations of arbitrary topology. It is shown that a concrete choice of prewavelets form a basis of the wavelet space when the degree of the vertices in the triangulation is not too high. Received December 29, 1997 / Revised version received April 14, 1998     

Bell-shaped nonstationary refinable ripplets

We study the approximation properties of the class of nonstationary refinable ripplets introduced in Gori and Pitolli (2008). These functions are the solution of an infinite set of nonstationary refinable equations and are defined through sequences of scaling masks that have an explicit expression. Moreover, they are variation-diminishing and highly localized in the scale-time plane, properties that make them particularly attractive in applications. Here, we prove that they enjoy Strang-Fix conditions, convolution and differentiation rules and that they are bell-shaped. Then, we construct the corresponding minimally supported nonstationary prewavelets and give an iterative algorithm to evaluate the prewavelet masks. Finally, we give a procedure to construct the associated nonstationary biorthogonal bases and filters to be used in efficient decomposition and reconstruction algorithms. As an example, we calculate the prewavelet masks and the nonstationary biorthogonal filter pairs corresponding to the C ² nonstationary scaling functions in the class and construct the corresponding prewavelets and biorthogonal bases. A simple test showing their good performances in the analysis of a spike-like signal is also presented.     

Wavelet-based preconditioners for boundary integral equations

We study simple preconditioners for the conjugate gradient method when used to solve matrix systems arising from some hypersingular and weakly singular integral equations. The preconditioners, which are of the type of hierarchical basis preconditioners, are based on the decomposition of the piecewise-linear (respectively piecewise-constant) functions as the sum of prewavelets (respectively derivatives of prewavelets). We prove that with these preconditioners the preconditioned systems have condition numbers uniformly bounded with respect to the degrees of freedom. Numerical experiments support our analysis. This revised version was published online in June 2006 with corrections to the Cover Date.     

Prewavelet analysis of the heat equation

Summary. We consider the heat equation in a smooth domain of R with Dirichlet and Neumann boundary conditions. It is solved by using its integral formulation with double-layer potentials, where the unknown , the jump of the solution through the boundary, belongs to an anisotropic Sobolev space. We approximate by the Galerkin method and use a prewavelet basis on , which characterizes the anisotropic space. The use of prewavelets allows to compress the stiffness matrix from to when N is the size of the matrix, and the condition number of the compressed matrix is uniformly bounded as the initial one in the prewavelet basis. Finally we show that the compressed scheme converges as fast as the Galerkin one, even for the Dirichlet problem which does not admit a coercive variational formulation. Received April 16, 1999 / Published online August 2, 2000     

关于非线性不等式组Levenberg-Marquardt算法的收敛性(英文)

本文研究了一类非线性不等式组的求解问题.利用一列目标函数两次可微的参数优化问题来逼近非线性不等式组的解,光滑Levenberg-Marquardt方法来求解参数优化问题,在一些较弱的条件下证明了文中算法的全局收敛性,数值实例显示文中算法效果较好.     

Approximate Wavelets and the Approximation of Pseudodifferential Operators

This paper studiesapproximate multiresolution analysisfor spaces generated by smooth functions providing high-order semi-analytic cubature formulas for multidimensional integral operators of mathematical physics. Since these functions satisfy refinement equations with any prescribed accuracy, methods from wavelet theory can be applied. We obtain an approximate decomposition of the finest scale space into almost orthogonal wavelet spaces. For the example of the Gaussian function we study some properties of the analytic prewavelets and describe the projection operators onto the wavelet spaces. The multivariate wavelets retain the property of the scaling function to provide efficient analytic expressions for the action of important integral operators, which leads to sparse and semi-analytic representations of these operators.     

Optimality Conditions for Multiobjective Optimization Problem Constrained by Parameterized Variational Inequalities

We study a multiobjective optimality problem constrained by parameterized variational inequalities. By separation theorem for convex sets, we translate the multiobjective optimality problem into single objective optimality problem, and obtain the first-order optimality conditions of this problem. Under the calmness conditions, an efficient upper estimate of coderivative for a composite set-valued mapping is derived. At last, we apply that result to the multiobjective bilevel programming problem and MPEC with Nash equilibrium constraints.     

Almost sure equidistribution in expansive families

In this paper we study generic equidistribution in families of sequences of points on tori. We assume that the sequences are parameterized by some subset of a Euclidean space, and we formulate geometric conditions on the dependence so that equidistribution holds almost everywhere with respect to the Lebesgue measure on the parameter space. As a consequence, we can give a new proof of an old result by Koksma.     

Computation Models for Parameterized Complexity

A parameterized computational problem is a set of pairs (x, k), where k is a distinguished item called “parameter”. FPT is the class of fixed-parameter tractable problems: for any fixed value of k, they are solvable in time bounded by a polynomial of degree α, where α is a constant not dependent on the parameter. In order to deal with parameterized intractability, Downey and Fellows have introduced a hierarchy of classes W[l] ? W[2] ? ? containing likely intractable parameterized problems, and they have shown that such classes have many natural, complete languages. In this paper we analyze several variations of the halting problem for nondeterministic Turing machines with parameterized time, and we show that its parameterized complexity strongly depends on some resources like the number of tapes, head and internal states, and on the size of the alphabet. Notice that classical polynomial-time complexity fails in distinguishing such features. As byproducts, we show that parameterized complexity is a useful tool for the study of the intrinsic power of some computational models, and we underline the different “computational powers” of some levels of the parameterized hierarchy.     

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 prefix array for parameterized strings

A parameterized string (p-string) is a generalization of the traditional string over two alphabets: a constant alphabet and a parameter alphabet. A parameterized match (p-match) exists between two p-strings if the constants match exactly and if there exists a bijection between the parameter symbols. Historically, p-strings have been leveraged for source code cloning, plagiarism detection, and biological sequence structural similarity. In this work, we identify the connection between the p-match and music, one of several applications to motivate our study of holes in p-strings, and prefix array-based data structures for p-strings. First, we introduce the parameterized prefix array (pPA) for p-strings and its succinct representation, the compact parameterized prefix array (cpPA). We show an interesting construction of the cpPA via the parameterized longest previous factor (pLPF), a more recently proposed array with connections to various pattern matching data structures and LZ factorization. Next, we introduce the parameterized string with holes (hp-string), needed to address a special form of indeterminate pattern matching with p-strings. Then, we show how to construct the compact prefix array for hp-strings. Finally, we discuss applications for our data structures.     

Comments on: Farkas’ Lemma: three decades of generalizations for mathematical optimization

In these comments on the excellent survey by Dinh and Jeyakumar, we briefly discuss some recently developed topics and results on applications of extended Farkas’ lemma(s) and related qualification conditions to problems of variational analysis and optimization, which are not fully reflected in the survey. They mainly concern: Lipschitzian stability of feasible solution maps for parameterized semi-infinite and infinite programs with linear and convex inequality constraints indexed by arbitrary sets; optimality conditions for nonsmooth problems involving such constraints; evaluating various subdifferentials of optimal value functions in DC and bilevel infinite programs with applications to Lipschitz continuity of value functions and optimality conditions; calculating and estimating normal cones to feasible solution sets for nonlinear smooth as well as nonsmooth semi-infinite, infinite, and conic programs with deriving necessary optimality conditions for them; calculating coderivatives of normal cone mappings for convex polyhedra in finite and infinite dimensions with applications to robust stability of parameterized variational inequalities. We also give some historical comments on the original Farkas’ papers.     

Cubic Spline Prewavelets on the Four-Directional Mesh

Dedicated to Professor M. J. D. Powell on the occasion of his sixty-fifth birthday and his retirement. In this paper, we design differentiable, two-dimensional, piecewise polynomial cubic prewavelets of particularly small compact support. They are given in closed form, and provide stable, orthogonal decompositions of L ² (R ² ) . In particular, the splines we use in our prewavelet constructions give rise to stable bases of spline spaces that contain all cubic polynomials, whereas the more familiar box spline constructions cannot reproduce all cubic polynomials, unless resorting to a box spline of higher polynomial degree.     

Statistical characteristics of attainability set of controllable systems with random coefficients

For controllable systems with random coefficients we study a property of statistical invariance, satisfied with given probability. We obtain sufficient conditions for invariance of a set with respect to controllable system expressed in terms of Lyapunov functions and shift dynamic system. We study the statistical characteristics of attainability set of a controllable system which is parameterized by metric dynamic system.     

On Higher-Order Sensitivity Analysis in Nonsmooth Vector Optimization

We propose the notion of higher-order radial-contingent derivative of a set-valued map, develop some calculus rules and use them directly to obtain optimality conditions for several particular optimization problems. Then we employ this derivative together with contingent-type derivatives to analyze sensitivity for nonsmooth vector optimization. Properties of higher-order contingent-type derivatives of the perturbation and weak perturbation maps of a parameterized optimization problem are obtained.     

On higher-order proto-differentiability of perturbation maps

This paper is concerned with higher-order sensitivity analysis in parametric vector optimization problems. Firstly, higher-order proto-differentiability of a set-valued mapping from one Euclidean space to another is defined. Then, we prove that the perturbation map/the proper perturbation map/the weak perturbation map of a parameterized vector optimization problem are higher-order proto-differentiable under some suitable qualification conditions.

     

非线性不等式系统带折线步的信赖域方法及其收敛性

针对一类非线性不等式系统求解的问题,利用一系列目标函数二次可微的带参数优化问题来逐次逼近非线性不等式系统的解,从而提出了针对参数最优化问题带折线步的信赖域算法．在较弱的条件下,算法的全局收敛性得到了保证．数值试验显示算法有效．     

On proto-differentiability of generalized perturbation maps

This paper is devoted to the sensitivity analysis in optimization problems and variational inequalities. The concept of proto-differentiability of set-valued maps (see [R.T. Rockafellar, Proto-differentiability of set-valued mappings and its applications in optimization, Ann. Inst. H. Poincaré Anal. Non Linéaire 6 (1989) 449-482]) plays the key role in our investigation. It is proved that, under some suitable qualification conditions, the generalized perturbation maps (that is, the solution set map to a parameterized constraint system, to a parameterized variational inequality, or to a parameterized optimization problem) are proto-differentiable.     

The Convergence of a Levenberg–Marquardt Method for Nonlinear Inequalities

In this paper, we consider the least l ₂-norm solution for a possibly inconsistent system of nonlinear inequalities. The objective function of the problem is only first-order continuously differentiable. By introducing a new smoothing function, the problem is approximated by a family of parameterized optimization problems with twice continuously differentiable objective functions. Then a Levenberg–Marquardt algorithm is proposed to solve the parameterized smooth optimization problems. It is proved that the algorithm either terminates finitely at a solution of the original inequality problem or generates an infinite sequence. In the latter case, the infinite sequence converges to a least l ₂-norm solution of the inequality problem. The local quadratic convergence of the algorithm was produced under some conditions.