Nonlinear programming and an optimization problem on infinitely differentiable functions

A nonnegative, infinitely differentiable function ø defined on the real line is called a Friedrichs mollifier function if it has support in [0, 1] and ₀ ¹ ø(t)dt=1. In this article the following problem is considered. Determine _k =inf ₀ ¹ vø^(k)(t)dt, k=1,..., where ø^(k) denotes thekth derivative of ø and the infimum is taken over the set of all mollifier functions. This problem has applications to monotone polynomial approximation as shown by this author elsewhere. In this article, the structure of the problem of determining _k is analyzed, and it is shown that the problem is reducible to a nonlinear programming problem involving the minimization of a strictly convex function of [(k–1)/2] variables, subject to a simple ordering restriction on the variables. An optimization problem on the functions of bounded variation, which is equivalent to the nonlinear programming problem, is also developed. The results of this article and those from approximation of functions theory are applied elsewhere to derive numerical values of various mathematical quantities involved in this article, e.g., _k =k~2^2k–1 for allk=1, 2, ..., and to establish certain inequalities of independent interest. This article concentrates on problem reduction and equivalence, and not numerical value.This research was supported in part by the National Science Foundation under Grant No. GK-32712.     

Weak and quasi-polynomial tractability of approximation of infinitely differentiable functions

We comment on recent results in the field of information based complexity, which state (in a number of different settings), that the approximation of infinitely differentiable functions is intractable and suffers from the curse of dimensionality. We show that renorming the space of infinitely differentiable functions in a suitable way allows weakly tractable uniform approximation by using only function values. Moreover, the approximating algorithm is based on a simple application of Taylor’s expansion about the center of the unit cube. We discuss also the approximation on the Euclidean ball and the approximation in the _L1$L_1$-norm.     

Analytic implementation of the duals of some spaces of infinitely differentiable functions

Using the Fourier-Laplace transform for functionals, we describe the duals of some spaces of the infinitely differentiable functions given on convex compact sets or convex domains in ?^N and such that the growth of their derivatives is determined by weight sequences of a general form.     

Smooth positive extensions and nonlinear programming

We establish a smooth positive extension theorem: Given any closed subset of a finite-dimensional real Euclidean space, a function zero on the closed set can be extended to a function smooth on the whole space and positive on the complement of the closed set. This result was stimulated by nonlinear programming. We give several applications of this result to nonlinear programming.This paper is dedicated to the memory of Emily Sue Merkle Waite, Ph.D.The author wishes to thank W. Cunningham for suggesting the question about constraint qualifications, A. Karr for noticing the example of a Brownian motion sample path, R. Byrd and P. Hartman for discussions, and E. Waite for support and encouragement.     

Approximation of infinitely differentiable multivariate functions is intractable

We prove that L_∞-approximation of C^∞-functions defined on [0,1]^d is intractable and suffers from the curse of dimensionality. This is done by showing that the minimal number of linear functionals needed to obtain an algorithm with worst case error at most ε(0,1) is exponential in d. This holds despite the fact that the rate of convergence is infinite.     

A note on solving nonlinear minimax problems via a differentiable penalty function

The note demonstrates that modeling a nonlinear minimax problem as a nonlinear programming problem and applying a classical differentiable penalty function to attempt to solve the problem can lead to convergence to a stationary point of the penalty function which is not a feasible point of the nonlinear programming problem. This occurred naturally in an application from statistical reliability theory. The note resolves the problem through modification of both the problem formulation and the iterative penalty function method.     

Korovkin-type approximation in spaces of vector-valued and set-valued functions

We consider some Korovkin-type approximation results for sequences of linear continuous operators in spaces of vector-valued and set-valued continuous functions without assuming the existence of the limit operator. Even in spaces of real continuous functions, where similar results have already been established, we replace the positivity assumption with a weaker condition. We also give some quantitative estimate of the convergence and some applications where previous results cannot be applied.     

A recursive quadratic programming algorithm that uses differentiable exact penalty functions

In this paper, a recursive quadratic programming algorithm for solving equality constrained optimization problems is proposed and studied. The line search functions used are approximations to Fletcher's differentiable exact penalty function. Global convergence and local superlinear convergence results are proved, and some numerical results are given.     

Irregular sampling, Toeplitz matrices, and the approximation of entire functions of exponential type

In many applications one seeks to recover an entire function of exponential type from its non-uniformly spaced samples. Whereas the mathematical theory usually addresses the question of when such a function in can be recovered, numerical methods operate with a finite-dimensional model. The numerical reconstruction or approximation of the original function amounts to the solution of a large linear system. We show that the solutions of a particularly efficient discrete model in which the data are fit by trigonometric polynomials converge to the solution of the original infinite-dimensional reconstruction problem. This legitimatizes the numerical computations and explains why the algorithms employed produce reasonable results. The main mathematical result is a new type of approximation theorem for entire functions of exponential type from a finite number of values. From another point of view our approach provides a new method for proving sampling theorems.

     

Nonlinear programming and nonsmooth optimization by successive linear programming

Methods are considered for solving nonlinear programming problems using an exactl ₁ penalty function. LP-like subproblems incorporating a trust region constraint are solved successively both to estimate the active set and to provide a foundation for proving global convergence. In one particular method, second order information is represented by approximating the reduced Hessian matrix, and Coleman-Conn steps are taken. A criterion for accepting these steps is given which enables the superlinear convergence properties of the Coleman-Conn method to be retained whilst preserving global convergence and avoiding the Maratos effect. The methods generalize to solve a wide range of composite nonsmooth optimization problems and the theory is presented in this general setting. A range of numerical experiments on small test problems is described.     

Nonlinear programming using minimax techniques

A minimax approach to nonlinear programming is presented. The original nonlinear programming problem is formulated as an unconstrained minimax problem. Under reasonable restrictions, it is shown that a point satisfying the necessary conditions for a minimax optimum also satisfies the Kuhn-Tucker necessary conditions for the original problem. A leastpth type of objective function for minimization with extremely large values ofp is proposed to solve the problem. Several numerical examples compare the present approach with the well-known SUMT method of Fiacco and McCormick. In both cases, a recent minimization algorithm by Fletcher is used.This paper is based on work presented at the 5th Hawaii International Conference on System Sciences, Honolulu, Hawaii, 1972. The authors are greatly indebted to V. K. Jha for his programming assistance and J. H. K. Chen who obtained some of the numerical results. This work was supported in part by the National Research Council of Canada under Grant No. A7239, by a Frederick Gardner Cottrell Grant from the Research Corporation, and through facilities and support from the Communications Research Laboratory of McMaster University.     

On an outer approximation concept in global optimization

A simple outer approximation concept for global optimization problems is presented that simplifies and generalizes several previous approaches. Unbounded feasible regions and non-affine cuts are admitted. Constraint dropping strategies and a large class of cutting plane methods are derived.     

Piece-wise linear approximation of functions of two variables

The goal of increasing computational efficiency is one of the fundamental challenges of both theoretical and applied research in mathematical modeling. The pursuit of this goal has lead to wide diversity of efforts to transform a specific mathematical problem into one that can be solved efficiently. Recent years have seen the emergence of highly efficient methods and software for solving Mixed Integer Programming Problems, such as those embodied in the packages CPLEX, MINTO, XPRESS-MP. The paper presents a method to develop a piece-wise linear approximation of an any desired accuracy to an arbitrary continuous function of two variables. The approximation generalizes the widely known model for approximating single variable functions, and significantly expands the set of nonlinear problems that can be efficiently solved by reducing them to Mixed Integer Programming Problems. By our development, any nonlinear programming problem, including non-convex ones, with an objective function (and/or constraints) that can be expressed as sums of component nonlinear functions of no more than two variables, can be efficiently approximated by a corresponding Mixed Integer Programming Problem.     

On the Fourier-Laplace transform of functionals on a space of infinitely differentiable functions on a convex compact

Classes of ultradifferentiable functions are classically defined by imposing growth conditions on the derivatives of the functions. Following this approach we consider a Fréchet-Schwartz space of infinitely differentiable functions on a closure of a bounded convex domain of multidimensional real space with uniform bounds on their partial derivatives. Our aim is to obtain Paley-Wiener-Schwartz type theorem connecting properties of linear continuous functionals on this space with the behaviour of their Fourier-Laplace transforms. Very similar problems were considered by M. Neymark, B.A. Taylor, M. Langenbruch, A.V. Abanin.     

Nonlinear approximation of functions based on nonnegative least squares solver

In computational practice, most attention is paid to rational approximations of functions and approximations by the sum of exponents. We consider a wide enough class of nonlinear approximations characterized by a set of two required parameters. The approximating function is linear in the first parameter; these parameters are assumed to be positive. The individual terms of the approximating function represent a fixed function that depends nonlinearly on the second parameter. A numerical approximation minimizes the residual functional by approximating function values at individual points. The second parameter's value is set on a more extensive set of points of the interval of permissible values. The proposed approach's key feature consists in determining the first parameter on each separate iteration of the classical nonnegative least squares method. The computational algorithm is used to rational approximate the function . The second example concerns the approximation of the stretching exponential function at $x\ge 0$ by the sum of exponents.     

An improved estimate of PSWF approximation and approximation by Mathieu functions

In this paper, an error estimate of spectral approximations by prolate spheroidal wave functions (PSWFs) with explicit dependence on the bandwidth parameter and optimal order of convergence is derived, which improves the existing result in [Chen et al., Spectral methods based on prolate spheroidal wave functions for hyperbolic PDEs, SIAM J. Numer. Anal. 43 (5) (2005) 1912-1933]. The underlying argument is applied to analyze spectral approximations of periodic functions by Mathieu functions, which leads to new estimates featured with explicit dependence on the intrinsic parameter.     

Nonlinear approximation using Gaussian kernels

It is well known that nonlinear approximation has an advantage over linear schemes in the sense that it provides comparable approximation rates to those of the linear schemes, but to a larger class of approximands. This was established for spline approximations and for wavelet approximations, and more recently by DeVore and Ron (in press) [2] for homogeneous radial basis function (surface spline) approximations. However, no such results are known for the Gaussian function, the preferred kernel in machine learning and several engineering problems. We introduce and analyze in this paper a new algorithm for approximating functions using translates of Gaussian functions with varying tension parameters. At heart it employs the strategy for nonlinear approximation of DeVore-Ron, but it selects kernels by a method that is not straightforward. The crux of the difficulty lies in the necessity to vary the tension parameter in the Gaussian function spatially according to local information about the approximand: error analysis of Gaussian approximation schemes with varying tension are, by and large, an elusive target for approximators. We show that our algorithm is suitably optimal in the sense that it provides approximation rates similar to other established nonlinear methodologies like spline and wavelet approximations. As expected and desired, the approximation rates can be as high as needed and are essentially saturated only by the smoothness of the approximand.