An interval branch and bound algorithm for bound constrained optimization problems

In this paper, we propose modifications to a prototypical branch and bound algorithm for nonlinear optimization so that the algorithm efficiently handles constrained problems with constant bound constraints. The modifications involve treating subregions of the boundary identically to interior regions during the branch and bound process, but using reduced gradients for the interval Newton method. The modifications also involve preconditioners for the interval Gauss-Seidel method which are optimal in the sense that their application selectively gives a coordinate bound of minimum width, a coordinate bound whose left endpoint is as large as possible, or a coordinate bound whose right endpoint is as small as possible. We give experimental results on a selection of problems with different properties.     

On constrained multivariate splines and their approximations

Summary The variational formulation of multivariate spline functions is generalized to include cases where the function has to satisfy inequality constraints such as positivity and convexity. Condition for existence and uniqueness of a solution is given. Approximation to the solution can be obtained by solving the variational problem in a finite dimensional subspace. Conditions for convergence and error estimates of the approximations are presented, both for interpolation problems and smoothing problems. The general theory is illustrated by specific examples including the volume-matching problem and the one-sided thin plate spline.This research is partially supported by the U.S. Army Contract No. DAAG 29-77-G-0207, and by NSF Grant No. MCS-8101836Part of this paper is based on Chapters 2 and 3 of the author's Ph. D. thesis. The author would like to express his sincere thanks to Professor Grance Wahba and to two referees for many helpful comments     

An algebraic structure for Faber polynomials

Let Σ be the set of functions, convergent for all |z|>1, with a Laurent series of the form f(z)=z+∑_n?0a_nz^-n. In this paper, we prove that the set of Faber polynomial sequences over Σ and the set of their normalized kth derivative sequences form groups which are isomorphic to the hitting time subgroup and the Bell^(k) subgroup of the Riordan group, respectively. Further, a relationship between such Faber polynomial sequences and Lucas and Sheffer polynomial sequences is derived.     

Strictly positive definite functions on the complex Hilbert sphere

We study strictly positive definite functions on the complex Hilbert sphere. A link between strict positive definiteness and (harmonic) polynomial interpolation on finite‐dimensional spheres is investigated. Sufficient conditions for strict positive definiteness are presented. This revised version was published online in June 2006 with corrections to the Cover Date.     

Composition based staircase algorithm and constrained interpolation with boundary conditions

Summary. Weakly coupled systems of inequalities arise frequently in the consideration of so-called direct methods for shape preserving interpolation. In this paper, a composition based staircase algorithm for bidiagonal systems subject to boundary conditions is developed. Using the compositions of the corresponding relations instead of their projections, we are able to derive a necessary and sufficient solvability criterion. Further, all solutions of the system can be constructed in a backward pass. To illustrate the general approach, we consider in detail the problem of convex interpolation by cubic splines. For this problem, an algorithm of the complexity O(n) in the number n of data points is obtained. Received August 4, 1998 / Revised version received February 5, 1999 / Published online January 27, 2000     

An asymptotically optimal algorithm for approximating bounded analytic functions

Summary. Let be the unit disk in the complex plane and let be a compact, simply connected subset of , whose boundary is assumed to belong to the class . Let be the unit ball of the Hardy space . A linear algorithm is constructed for approximating functions in . The algorithm is based on sampling functions in the Fejer points of and it produces the error Here denotes the space of continuous functions on and is the Green capacity of with respect to . Moreover it is shown that the algorithm is asymptotically optimal in the sense of -widths. Received July 7, 1994     

Compact,convex sets in R n and a new banach lattice. II.- Application: An approximation problem.

We develop a calculus structure in the Banach lattice introduced in a preceding paper, having in mind an approximation problem appearing in non-smooth optimization. We show that the essential results depend as much on the order structure as on the analytical one.     

Risk bounds for model selection via penalization

Performance bounds for criteria for model selection are developed using recent theory for sieves. The model selection criteria are based on an empirical loss or contrast function with an added penalty term motivated by empirical process theory and roughly proportional to the number of parameters needed to describe the model divided by the number of observations. Most of our examples involve density or regression estimation settings and we focus on the problem of estimating the unknown density or regression function. We show that the quadratic risk of the minimum penalized empirical contrast estimator is bounded by an index of the accuracy of the sieve. This accuracy index quantifies the trade-off among the candidate models between the approximation error and parameter dimension relative to sample size. If we choose a list of models which exhibit good approximation properties with respect to different classes of smoothness, the estimator can be simultaneously minimax rate optimal in each of those classes. This is what is usually called adaptation. The type of classes of smoothness in which one gets adaptation depends heavily on the list of models. If too many models are involved in order to get accurate approximation of many wide classes of functions simultaneously, it may happen that the estimator is only approximately adaptive (typically up to a slowly varying function of the sample size). We shall provide various illustrations of our method such as penalized maximum likelihood, projection or least squares estimation. The models will involve commonly used finite dimensional expansions such as piecewise polynomials with fixed or variable knots, trigonometric polynomials, wavelets, neural nets and related nonlinear expansions defined by superposition of ridge functions. Received: 7 July 1995 / Revised version: 1 November 1997     

Approximation of boundary element matrices

Summary. This article considers the problem of approximating a general asymptotically smooth function in two variables, typically arising in integral formulations of boundary value problems, by a sum of products of two functions in one variable. From these results an iterative algorithm for the low-rank approximation of blocks of large unstructured matrices generated by asymptotically smooth functions is developed. This algorithm uses only few entries from the original block and since it has a natural stopping criterion the approximative rank is not needed in advance. Received June 21, 1999 / Revised version received December 6, 1999 / Published online June 8, 2000     

On the structure of function spaces in optimal recovery of point functionals for ENO-schemes by radial basis functions

Summary. Radial basis functions are used in the recovery step of finite volume methods for the numerical solution of conservation laws. Being conditionally positive definite such functions generate optimal recovery splines in the sense of Micchelli and Rivlin in associated native spaces. We analyse the solvability to the recovery problem of point functionals from cell average values with radial basis functions. Furthermore, we characterise the corresponding native function spaces and provide error estimates of the recovery scheme. Finally, we explicitly list the native spaces to a selection of radial basis functions, thin plate splines included, before we provide some numerical examples of our method. Received March 14, 1995     

Combination of trust region method and simplicial decomposition for convex constrained nonlinear optimization

The algorithm presented in this article incorporates the trust region method (TR) into the restricted decomposition algorithm for convex-constrained nonlinear problems (RSDCC) to solve the master problem of RSDCC. The global convergence is proved. The computational comparison between the presented algorithm and RSDCC is given. The results show that the former is much better than the latter.     

A family of variable metric proximal methods

We consider conceptual optimization methods combining two ideas: the Moreau—Yosida regularization in convex analysis, and quasi-Newton approximations of smooth functions. We outline several approaches based on this combination, and establish their global convergence. Then we study theoretically the local convergence properties of one of these approaches, which uses quasi-Newton updates of the objective function itself. Also, we obtain a globally and superlinearly convergent BFGS proximal method. At each step of our study, we single out the assumptions that are useful to derive the result concerned.     

Residual type a posteriori error estimates for elliptic obstacle problems

Summary. A posteriori error estimators of residual type are derived for piecewise linear finite element approximations to elliptic obstacle problems. An instrumental ingredient is a new interpolation operator which requires minimal regularity, exhibits optimal approximation properties and preserves positivity. Both upper and lower bounds are proved and their optimality is explored with several examples. Sharp a priori bounds for the a posteriori estimators are given, and extensions of the results to double obstacle problems are briefly discussed. Received June 19, 1998 / Published online December 6, 1999     

An improved order of approximation for thin-plate spline interpolation in the unit disc

Summary. We show that the -norm of the error in thin-plate spline interpolation in the unit disc decays like , where , under the assumptions that the function to be approximated is and that the interpolation points contain the finite grid . Received February 13, 1998 / Published online September 24, 1999     

An error analysis for absolute and relative approximation

We consider the vectorial algorithm for finding best polynomial approximationsp P _n to a given functionf C[a, b], with respect to the norm · _s , defined byp – f _s =w ₁ (p – f)+w ₂ (p – f) A bound for the modulus of continuity of the best vectorial approximation operator is given, and using the floating point calculus of J. H. Wilkinson, a bound for the rounding error in the algorithm is derived. For givenf, these estimates provide an indication of the conditioning of the problem, an estimate of the obtainable accuracy, and a practical method for terminating the iteration.This paper was supported in part by the Canadian NCR A-8108, FCAC 74-09 and G.E.T.M.A.Part of this research was done during the first-named author's visit to theB! Chair of Applied Mathematics, University of Athens, Spring term, 1975.     

A robin-neumann problem in bounded domains with splitting boundary

We consider a mixed boundary-value problem for the homogeneous Laplace equation in a bounded domain which boundary splits up into two disjoint smooth components. On the one boundary component we pose a homogeneous Robin condition and an inhomogeneous Neumann condition on the other. We give a weak formulation, interpret this problem as a generalized spectral (eigenvalue) problem in the sense of F.Stummel (cf.[12]) and investigate existence, uniqueness and regularity of weak solutions. This problem is a cut-off version of a basic problem in water-wave theory (cf.Ramm [8], pp.394-395, Simon/Ursell [10] Stoker [11])     

Compact,convex sets in R n and a new banach lattice. I.- Theory.

The present paper shows that compact, non-empty convex sets in R ⁿ form a wedge in a well-defined Banach lattice, which turns out to be isometrically Riesz-isomorphic to the continuous functions in S ^n–1, the unit sphere of R ⁿ . Among other results, we obtain Dini-like convergence results for sets, linking order- and norm-convergence.     

The Willmore conjecture for immersed tori with small curvature integral

The Willmore conjecture states that any immersion of a 2-torus into euclidean space satisfies . We prove it under the condition that the L ^p -norm of the Gaussian curvature is sufficiently small. Received: 10 June 1999     

An algorithm for best approximate solutions ofAx=b with a smooth strictly convex norm

Summary In this paper, overdetermined systems ofm linear equations inn unknowns are considered. With ^m equipped with a smooth strictly convex norm, ·, an iterative algorithm for finding the best approximate solution of the linear system which minimizes the ·-error is given. The convergence of the algorithm is established and numerical results are presented for the case when · is anl _p norm, 1<p<.Portions of this paper are taken from the author's Ph.D. thesis at Michigan State University