Nonlinear programming,approximation, and optimization 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 ₀ ¹ |^(k)(t)|dt,k=1, 2, ..., where ^(k) denotes thekth derivative of and the infimum is taken over the set of all mollifier functions , which is a convex set. This problem has applications to monotone polynomial approximation as shown by this author elsewhere. The problem is reducible to three equivalent problems, a nonlinear programming problem, a problem on the functions of bounded variation, and an approximation problem involving Tchebycheff polynomials. One of the results of this article shows that _k =k!2^2k–1,k=1, 2, .... The numerical values of the optimal solutions of the three problems are obtained as a function ofk. Some inequalities of independent interest are also derived.This research was supported in part by the National Science Foundation, Grant No. GK-32712.     

Nonlinear eigenvalue approximation

Summary For each in some domainD in the complex plane, letF() be a linear, compact operator on a Banach spaceX and letF be holomorphic in . Assuming that there is a so thatI–F() is not one-to-one, we examine two local methods for approximating the nonlinear eigenvalue . In the Newton method the smallest eigenvalue of the operator pencil [I–F(),F()] is used as increment. We show that under suitable hypotheses the sequence of Newton iterates is locally, quadratically convergent. Second, suppose 0 is an eigenvalue of the operator pencil [I–F(),I] with algebraic multiplicitym. For fixed leth() denote the arithmetic mean of them eigenvalues of the pencil [I–F(),I] which are closest to 0. Thenh is holomorphic in a neighborhood of andh()=0. Under suitable hypotheses the classical Muller's method applied toh converges locally with order approximately 1.84.     

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.     

Nonlinear approximation by renormalized trigonometric system

We study the convergence of greedy algorithmwith regard to renormalized trigonometric system. Necessary and sufficient conditions are found for system’s normalization to guarantee almost everywhere convergence, and convergence in L ^p (T) for 1 < p < ∞ of the greedy algorithm, where T is the unit torus. Also the non existence is proved for normalization which guarantees convergence almost everywhere for functions from L ¹(T), or uniform convergence for continuous functions.     

Nonlinear tensor product approximation of functions

We are interested in approximation of a multivariate function $f(x_1,\dots ,x_d)$ by linear combinations of products $u^1\left(x_1\right)\cdots u^d\left(x_d\right)$ of univariate functions $u^i\left(x_i\right)$, $i=1,\dots ,d$. In the case $d=2$ it is the classical problem of bilinear approximation. In the case of approximation in the $L_2$ space the bilinear approximation problem is closely related to the problem of singular value decomposition (also called Schmidt expansion) of the corresponding integral operator with the kernel $f(x_1,x_2)$. There are known results on the rate of decay of errors of best bilinear approximation in $L_p$ under different smoothness assumptions on $f$. The problem of multilinear approximation (nonlinear tensor product approximation) in the case $d\ge 3$ is more difficult and much less studied than the bilinear approximation problem. We will present results on best multilinear approximation in $L_p$ under mixed smoothness assumption on $f$.     

Nonlinear approximation with nonstationary Gabor frames

We consider sparseness properties of adaptive time-frequency representations obtained using nonstationary Gabor frames (NSGFs). NSGFs generalize classical Gabor frames by allowing for adaptivity in either time or frequency. It is known that the concept of painless nonorthogonal expansions generalizes to the nonstationary case, providing perfect reconstruction and an FFT based implementation for compactly supported window functions sampled at a certain density. It is also known that for some signal classes, NSGFs with flexible time resolution tend to provide sparser expansions than can be obtained with classical Gabor frames. In this article we show, for the continuous case, that sparseness of a nonstationary Gabor expansion is equivalent to smoothness in an associated decomposition space. In this way we characterize signals with sparse expansions relative to NSGFs with flexible time resolution. Based on this characterization we prove an upper bound on the approximation error occurring when thresholding the coefficients of the corresponding frame expansions. We complement the theoretical results with numerical experiments, estimating the rate of approximation obtained from thresholding the coefficients of both stationary and nonstationary Gabor expansions.     

Nonlinear Chebyshev approximation to set-valued functions

In this paper, we give a characterization of best Chebyshev approximation to set-valued functions from a family of continuous functions with the weak betweeness property. As a consequence, we obtain a characterization of Kolmogorov type for best simultaneous approximation to an infinity set of functions. We introduce the concept of a set-sun and give a characterization of it. In addition, we prove a property of Amir–Ziegler type for a family of real functions and we get a characterization of best simultaneous approximation to two functions     

Nonlinear approximation with general wave packets

We study nonlinear approximation in the Triebel-Lizorkin spaces with dictionaries formed by dilating and translating one single function g. A general Jackson inequality is derived for best m-term approximation with such dictionaries. In some special cases where g has a special structure, a complete characterization of the approximation spaces is derived.     

Nonlinear approximation using rapidly increasing functions

Fix a positive integern and σ>0. ForF continuous and positive on [0, ∞), we consider the spaceW(n, σ; F) of functions of the form σF(α_jx) P_j(x) where there arem(≤n) terms in the sum; theP _j's are polynomials of total degree not exceedingn — m; and 0≤α_j≤α_j+1-α, j=1, 2,?, m-1. Under certain conditions onF (primarily that it increase rapidly enough to ∞ asx goes to ∞),W(n, σ; F) is an existence space forC[0,1].     

Nonlinear approximation theory on compact groups

In this article we extend to the setting of band-limited functions on compact groups previous results bounding from below the percentage of energy, contained in the low frequency portion of the spectrum of a positive function defined on a cyclic group. Connections to signal recovery for positive functions, as well as partial spectral analysis, are also discussed.     

Best proximity points: approximation and optimization

A best proximity point theorem explores the existence of an optimal approximate solution, known as a best proximity point, to the equations of the form Tx = x where T is a non-self mapping. The purpose of this article is to establish some best proximity point theorems for non-self non-expansive mappings, non-self Kannan- type mappings and non-self Chatterjea-type mappings, thereby producing optimal approximate solutions to some fixed point equations. Also, algorithms for determining such optimal approximate solutions are furnished in some cases.     

Robust optimization approximation for joint chance constrained optimization problem

Chance constraint is widely used for modeling solution reliability in optimization problems with uncertainty. Due to the difficulties in checking the feasibility of the probabilistic constraint and the non-convexity of the feasible region, chance constrained problems are generally solved through approximations. Joint chance constrained problem enforces that several constraints are satisfied simultaneously and it is more complicated than individual chance constrained problem. This work investigates the tractable robust optimization approximation framework for solving the joint chance constrained problem. Various robust counterpart optimization formulations are derived based on different types of uncertainty set. To improve the quality of robust optimization approximation, a two-layer algorithm is proposed. The inner layer optimizes over the size of the uncertainty set, and the outer layer optimizes over the parameter t which is used for the indicator function upper bounding. Numerical studies demonstrate that the proposed method can lead to solutions close to the true solution of a joint chance constrained problem.     

Functional optimization by variable-basis approximation schemes

This is a summary of the author’s PhD thesis, supervised by Marcello Sanguineti and defended on April 2, 2009 at Università degli Studi di Genova. The thesis is written in English and a copy is available from the author upon request. Functional optimization problems arising in Operations Research are investigated. In such problems, a cost functional Φ has to be minimized over an admissible set S of d-variable functions. As, in general, closed-form solutions cannot be derived, suboptimal solutions are searched for, having the form of variable-basis functions, i.e., elements of the set span _n   G of linear combinations of at most n elements from a set G of computational units. Upper bounds on inf_{f ? S ?spann G}F(f)-inf_{f ? S}F(f){inf_{f in S cap {rm span}_n, G}Phi(f)-inf_{f in S}Phi(f)} are obtained. Conditions are derived, under which the estimates do not exhibit the so-called “curse of dimensionality” in the number n of computational units, when the number d of variables grows. The problems considered include dynamic optimization, team optimization, and supervised learning from data.     

Polyhedral approximation in mixed-integer convex optimization

Generalizing both mixed-integer linear optimization and convex optimization, mixed-integer convex optimization possesses broad modeling power but has seen relatively few advances in general-purpose solvers in recent years. In this paper, we intend to provide a broadly accessible introduction to our recent work in developing algorithms and software for this problem class. Our approach is based on constructing polyhedral outer approximations of the convex constraints, resulting in a global solution by solving a finite number of mixed-integer linear and continuous convex subproblems. The key advance we present is to strengthen the polyhedral approximations by constructing them in a higher-dimensional space. In order to automate this extended formulation we rely on the algebraic modeling technique of disciplined convex programming (DCP), and for generality and ease of implementation we use conic representations of the convex constraints. Although our framework requires a manual translation of existing models into DCP form, after performing this transformation on the MINLPLIB2 benchmark library we were able to solve a number of unsolved instances and on many other instances achieve superior performance compared with state-of-the-art solvers like Bonmin, SCIP, and Artelys Knitro.     

On the approximation and the optimization of plates

This work is devoted to the study of simply supported and of clamped plates together with related variational inequalitiesand optimization problems. We introduce a new unitary approach based on distributed optimal control problems governed by second order elliptic boundary value problems and their penalization. This approach gives the possibility to approximate the solution via piecewise linear continuous finite elements and is simpler than other methods considered in the literature.The convergence with respect to the penalization parameter (?) is proved under very general assumptions.

In order to solve the obtained control problems, optimization procedures of steepest descent type are considered. Relevantnumerical examples illustrate the applicability of the proposed methods.     

Global and mid-range function approximation for engineering optimization

Global and mid-range approximation concepts are used in engineering optimisation in those cases were the commonly used local approximations are not available or applicable. In this paper the response surface method is discussed as a method to build both global and mid-range approximations of the objective and constraint functions. In this method analysis results in multiple design points are fitted on a chosen approximation model function by means of regression techniques. Especially global approximations rely heavily on appropriate choices of the model functions. This builds a serious bottleneck in applying the method. In mid-range approximations the model selection is much less critical. The response surface method is illustrated at two relatively simple design problems. For building global approximations a new method was developed by Sacks and co-workers, especially regarding the nature of computer experiments. Here, the analysis results in the design sites are exactly predicted, and model selection is more flexible compared to the response surface method. The method will be applied to an analytical test function and a simple design problem. Finally the methods are discussed and compared.     

On semi-infinite optimization and chebyshev approximation with contraints

The main purpose of this paper is to use the methods of semi-infinite optimization in order to study best Chebyshev approximation problems with constraints. We consider problems which do not satisfy the Haar condition. Characterization theorems of best approximations and an algorithm which computes these approximations are given.     

Nonlinear wavelet approximation and the space C P α

We obtain a Jackson estimate for nonlinear wavelet approximation in the space C _p ^α and some results about the interpolation for C _p ^α