On a class of extremal problems

In the paper we introduce a class of trigonometrical polynomial extremal problems depending on a continuous parameter 0≤r≤1. It turns out that the two border cases r=0 and r=1 are known problems investigated earlier by Kamae, Mendes-France, Ruzsa and the present author. We also introduce another set of extremal problems for measures with similar parametrization, and prove a duality relationship between the two type of extremal quantities. The proof relies on a minimax theorem proved earlier by the author. The known duality results are proved as corollaries. 1980 MS Classification. Primary 42A05; Secondary 46B25, 46N05.     

On conditions for optimality of a class of nondifferentiable functions

The purpose of this paper is to derive first-order necessary conditions for optimality of a class of nondifferentiable functions. The first-order necessary conditions for optimality for the minimax function and thel ₁-function can be considered as special cases of the present method. Furthermore, the optimality conditions obtained are used to obtain threshold values for the controlling parameters of a class of exact penalty functions.     

Approximation characteristics for diagonal operators in different computational settings

First we study several extremal problems on minimax, and prove that they are equivalent. Then we connect this result with the exact values of some approximation characteristics of diagonal operators in different settings, such as the best n-term approximation, the linear average and stochastic n-widths, and the Kolmogorov and linear n-widths. Most of these exact values were known before, but in terms of equivalence of these extremal problems, we present a unified approach to give them a direct proof.     

Linear best approximation using a class of polyhedral norms

A class of polyhedral norms is introduced, which contains thel ₁ andl norms as special cases. Of primary interest is the solution of linear best approximation problems using these norms. Best approximations are characterized, and an algorithm is developed. This is a methods of descent type which may be interpreted as a generalization of existing well-known methods for solving thel ₁ andl problems. Numerical results are given to illustrate the performance of two variants of the algorithm on some problems.Communicated by C. Brezinski     

Extremum problems in minimax signal detection forl q -ellipsoids with anl p -ball removed

An asymptotic minimax problem of signal detection for signals froml _q -ellipsoids with an l_p-ball removed (p>2 or q<p<2) in a Gaussian white noise is considered. Asymptotically sharp distinguishability conditions and some estimates of the minimax probability of errors of signal detection for ellipsoids with axes a_n≈n^−λ λ>0, are obtained. The proofs use results and techniques developed by Yu. I. Ingster. Bibliography:6 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 228, 1996, pp. 312–332     

An extremal problem for paths in bipartite graphs

A formula is found for the maximum number of edges in a graph G ? K(a, b) which contains no path P_2l for l > c. A similar formula is found for the maximum number of edges in G ? K(a, b) containing no P_{2l + 1} for l > c. In addition, all extremal graphs are determined.     

On the minimax control problem for nonlinear operator-differential equations

We consider the problem of minimax control for objects describable by nonlinear operator-differential equations in Banach spaces with restrictions on the phase variables and controls. We prove solvability theorems. The method of proof is based on the theory of extremal problems for generalized operator-differential equations.Translated fromVychislitel'naya i Prikladnaya Matematika, Issue 71, 1990, pp. 114–119.     

A primal‐dual method for the Meyer model of cartoon and texture decomposition

In this paper, we study the original Meyer model of cartoon and texture decomposition in image processing. The model, which is a minimization problem, contains an l₁‐based TV‐norm and an l_∞‐based G‐norm. The main idea of this paper is to use the dual formulation to represent both TV‐norm and G‐norm. The resulting minimization problem of the Meyer model can be given as a minimax problem. A first‐order primal‐dual algorithm can be developed to compute the saddle point of the minimax problem. The convergence of the proposed algorithm is theoretically shown. Numerical results are presented to show that the original Meyer model can decompose better cartoon and texture components than the other testing methods.     

Projections of convex bodies and the fourier transform

The Fourier analytic approach to sections of convex bodies has recently been developed and has led to several results, including a complete analytic solution to the Busemann-Petty problem, characterizations of intersection bodies, extremal sections ofl _p-balls. In this article, we extend this approach to projections of convex bodies and show that the projection counterparts of the results mentioned above can be proved using similar methods. In particular, we present a Fourier analytic proof of the recent result of Barthe and Naor on extremal projections ofl _p-balls, and give a Fourier analytic solution to Shephard’s problem, originally solved by Petty and Schneider and asking whether symmetric convex bodies with smaller hyperplane projections necessarily have smaller volume. The proofs are based on a formula expressing the volume of hyperplane projections in terms of the Fourier transform of the curvature function.     

Extreme values statistics for Markov chains via the (pseudo-) regenerative method

This paper is devoted to the study of specific statistical methods for extremal events in the markovian setup, based on the regenerative method and the Nummelin technique. Exploiting ideas developed in Rootzén (Adv Appl Probab 20:371–390, 1988), the principle underlying our methodology consists of first generating a random number l of approximate pseudo-renewal times τ ₁, τ ₂, ..., τ _l for a sample path X ₁, ..., X _n drawn from a Harris chain X with state space E, from the parameters of a minorization condition fulfilled by its transition kernel, and then computing submaxima over the approximate cycles thus obtained: $\max_{1+\tau_1\leq i \leq \tau_2}f(X_i),\;\ldots ,\;\max_{1+\tau_{l-1}\leq i \leq \tau_l}f(X_i)This paper is devoted to the study of specific statistical methods for extremal events in the markovian setup, based on the regenerative method and the Nummelin technique. Exploiting ideas developed in Rootzén (Adv Appl Probab 20:371–390, 1988), the principle underlying our methodology consists of first generating a random number l of approximate pseudo-renewal times τ ₁, τ ₂, ..., τ _l for a sample path X ₁, ..., X _n drawn from a Harris chain X with state space E, from the parameters of a minorization condition fulfilled by its transition kernel, and then computing submaxima over the approximate cycles thus obtained: max_{1+t1 ￡ i ￡ t2}f(X_i),  ?,  max_{1+tl-1 ￡ i ￡ tl}f(X_i)\max_{1+\tau_1\leq i \leq \tau_2}f(X_i),\;\ldots ,\;\max_{1+\tau_{l-1}\leq i \leq \tau_l}f(X_i) for any measurable function f:E→ℝ. Estimators of tail features of the sample maximum max_{1 ≤ i ≤ n} f(X _i ) are then constructed by applying standard statistical methods, tailored for the i.i.d. setting, to the submaxima as if they were independent and identically distributed. In particular, the asymptotic properties of extensions of popular inference procedures based on the conditional maximum likelihood theory, such as Hill’s method for the index of regular variation, are thoroughly investigated. Using the same approach, we also consider the problem of estimating the extremal index of the sequence {f(X _n )} _{n ∈ ℕ} under suitable assumptions. Eventually, practical issues related to the application of the methodology we propose are discussed and preliminary simulation results are displayed.     

On solving three classes of nonlinear programming problems via simple differentiable penalty functions

We consider the following classes of nonlinear programming problems: the minimization of smooth functions subject to general constraints and simple bounds on the variables; the nonlinearl ₁-problem; and the minimax problem. Numerically reliable methods for solving problems in each of these classes, based upon exploiting the structure of the problem in constructing simple differentiable penalty functions, are presented.This research was made possible by NSERC Grant No. A8442.The author would like to thank Mrs. J. Selwood of the Department of Combinatories and Optimization, University of Waterloo, Ontario, Canada for her excellent typesetting.This work was carried out in the Department of Combinatories and Optimization, University of Waterloo, Waterloo, Ontario, Canada.     

Adaptive minimax test of independence

The paper is concerned with the adaptive minimax problem of testing the independence of the components of a d-dimensional random vector. The functions under alternatives consist of smooth densities supported on [0, 1]d and separated away from the product of their marginals in L2-norm. We are interested in finding the adaptive minimax rate of testing and a test that attains this rate. We focus mainly on the tests for which the error of the first kind an can decrease to zero as the number of observations increases. We show also how this property of the test affects its error of the second kind.     

Some extremal problems for functions of bounded boundary rotation

A variational method is developed within the class of functions of boundary rotation not exceedingkπ which is based on the fact that the set of representing measuresμ is convex. It shows that an extremal problem related to a functional with Gateaux derivative and some constraints leads to extremal measuresμ ₀ with finite support. The positive and negative part of aμ ₀ is located at points where a functionJ (depending onμ ₀) reaches its maximum and minimum respectively. The method is tested successfully on various problems.     

Nonsmooth minimax programming under locally Lipschitz (Φ, ρ)-invexity

Minimax programming problems involving locally Lipschitz (Φ, ρ)-invex functions are considered. The parametric and non-parametric necessary and sufficient optimality conditions for a class of nonsmooth minimax programming problems are obtained under nondifferentiable (Φ, ρ)-invexity assumption imposed on objective and constraint functions. When the sufficient conditions are utilized, parametric and non-parametric dual problems in the sense of Mond-Weir and Wolfe may be formulated and duality results are derived for the considered nonsmooth minimax programming problem. With the reference to the said functions we extend some results of optimality and duality for a larger class of nonsmooth minimax programming problems.     

Design Approximation Problems for Linear-Phase Nonrecursive Digital Filters

The topic of this paper is the study of four real, linear, possibly constrained minimum norm approximation problems, which arise in connection with the design of linear-phase nonrecursive digital filters and are distinguished by the type of used trigonometric approximation functions. In the case of unconstrained minimax designs these problems are normally solved by the Parks–McClellan algorithm, which is an application of the second algorithm of Remez to these problems and which is one of the most popular tools in filter design. In this paper the four types of approximation problems are investigated for all L^p and l^p norms, respectively. It is especially proved that the assumptions for the Remez algorithm are satisfied in all four cases, which has been claimed, but is not obvious for three of them. Furthermore, results on the existence and uniqueness of solutions and on the convergence and the rate of convergence of the approximation errors are derived.     

Minimax estimates of a linear parameter function in a regression model under restrictions on the parameters and variance-covariance matrix

Minimax nonhomogeneous linear estimators of scalar linear parameter functions are studied in the paper under restrictions on the parameters and variance-covariance matrix. The variance-covariance matrix of the linear model under consideration is assumed to be unknown but from a specific set R of nonnegativedefinite matrices. It is shown under this assumption that, without any restriction on the parameters, minimax estimators correspond to the least-squares estimators of the parameter functions for the “worst” variance-covariance matrix. Then the minimax mean-square error of the estimator is derived using the Bayes approach, and finally the exact formulas are derived for the calculation of minimax estimators under elliptical restrictions on the parameter space and for two special classes of possible variance-covariance matrices R. For example, it is shown that a special choice of a constant q ₀ and a matrixW ₀ defining one of the above classes R leads to the well known Kuks—Olman admissible estimator (see [16]) with a known variance-covariance matrixW ₀. Bibliography:32 titles. Translated fromObchyslyuval'na ta Prykladna Matematyka, No. 81, 1997, pp. 79–92.     

Optimal synthesis in an infinite-dimensional space

For a class of optimal control problems and Hamiltonian systems generated by these problems in the space l ₂, we prove the existence of extremals with a countable number of switchings on a finite time interval. The optimal synthesis that we construct in the space l ₂ forms a fiber bundle with piecewise smooth two-dimensional fibers consisting of extremals with a countable number of switchings over an infinite-dimensional basis of singular extremals.