A method of feasible directions using function approximations,with applications to min max problems

This paper presents a demonstrably convergent method of feasible directions for solving the problem min{φ(ξ)| gⁱ(ξ)?0i=1,2,…,m}, which approximates, adaptively, both φ(x) and ▽φ(x). These approximations are necessitated by the fact that in certain problems, such as when $\text{φ(x) =}\text{max}\text{{f(x, y) ¦ y ? Ω}{}_{\mathrm{y}}\text{}}$, a precise evaluation of φ(x) and ▽φ(x) is extremely costly. The adaptive procedure progressively refines the precision of the approximations as an optimum is approached and as a result should be much more efficient than fixed precision algorithms.It is outlined how this new algorithm can be used for solving problems of the form $\text{min}{}_{\mathrm{y}}\text{? Ω}{}_{\mathrm{x}}\text{max}{}_{\mathrm{y}}\text{? Ω}{}_{\mathrm{y}}\text{f(x, y)}$ under the assumption that Ωm_ξ={x|gⁱ(x)?0, j=1,…,s} ∩$\text{R}$ⁿ, Ω_y={y|ζ_i(y)?0, i-1,…,t} ∩ $\text{R}$^m, with f, g^j, ζⁱ continuously differentiable, f(x, ·) concave, ζⁱ convex for $\text{i = 1,…, t,}\text{and}\text{Ω}{}_{\mathrm{x}}\text{, Ω}{}_{\mathrm{y}}$ compact.     

Sublinear perturbations of the differential equation y(n) = 0 and of the analogous difference equation

According to a result of A. Ghizzetti, for any solution y(t) of the differential equation where $\text{y}{}^{\mathrm{(n)}}\text{(t)+}\text{∑}\text{i=0}\text{n?1}\text{g}{}_{\mathrm{i}}\text{(t) y}{}^{\mathrm{i}}\text{(t)=0}\text{(t ? 1)}$, $\text{∝}{}_1{}^{\mathrm{\infty }}\text{¦g}{}_{\mathrm{i}}\text{(x)¦x}{}^{\mathrm{n?I?1}}\text{dx < ∞}$ (0 ?i ? n ?1, either y(t) = 0 for t ? 1 or there is an integer r with 0 ? r ? n ? 1 such that $\text{lim}\text{t → ∞}\text{y(t)}\text{t}{}^{\mathrm{r}}$ exists and ≠0. Related results are obtained for difference and differential inequalities. A special case of the former has interesting applications in the study of orthogonal polynomials.     

Numerical approximation of product integrals

A technique for the numerical approximation of matrix-valued Riemann product integrals is developed. For a ? x < y ? b, I_m(x, y) denotes

$\text{∫}\text{χ}\text{y}\text{∫}\text{χ}\text{v}{}_2\text{?}\text{∫}\text{χ}\text{v}{}_2\text{∏}\text{i=1}\text{m}\text{F(ν}{}_{\mathrm{i}}\text{)dν}{}_1\text{dν}{}_2\text{?dν}{}_{\mathrm{m}}$

, and A_m(x, y) denotes an approximation of I_m(x, y) of the form

$\text{(y?x)}{}^{\mathrm{m}}\text{∑}\text{k=1}\text{n}\text{a}{}_{\mathrm{k}}\text{∏}\text{i=1}\text{m}\text{F(χ}{}_{\mathrm{ik}}\text{)}$

, where a_k and y_ik are fixed numbers for i = 1, 2,…, m and k = 1, 2,…, N and x_ik = x + (y ? x)y_ik. The following result is established. If p is a positive integer, F is a function from the real numbers to the set of w × w matrices with real elements and F⁽¹⁾ exists and is continuous on [a, b], then there exists a bounded interval function H such that, if n, r, and s are positive integers, $\text{(b ? a)}\text{n}\text{= h < 1, x}{}_{\mathrm{i}}\text{= a + hi}\text{for}\text{i = 0, 1,…, n}\text{and}\text{0 < r ? s ? n}$, then

$\text{∏}\text{χ}{}_{\mathrm{r?}}\text{χ}{}_{\mathrm{s}}\text{(I+F dχ)?}\text{∏}\text{i=r}\text{s}\text{I+}\text{∑}\text{j=1}\text{p}\text{I}{}_{\mathrm{j}}\text{(χ}{}_{\mathrm{i?1}}\text{,χ}{}_{\mathrm{i}}\text{)}$

$\text{=h}{}^{\mathrm{p}}\text{H(χ}{}_{\mathrm{r?1}}\text{,χ}{}_{\mathrm{s}}\text{)+O(h}{}^{\mathrm{p+1}}\text{)}$

Further, if F^(j) exists and is continuous on [a, b] for j = 1, 2,…, p + 1 and A is exact for polynomials of degree less than p + 1 ? j for j = 1, 2,…, p, then the preceding result remains valid when A_j is substituted for I_j.     

Construction of a recurrence relation for modified moments

In this paper we are constructing a recurrence relation of the form

$\text{∑}\text{i=0}\text{r}\text{ω}{}_{\mathrm{i}}\text{(k)m}{}_{\mathrm{k+i}}{}^{\mathrm{\{\lambda \}}}\text{[f] = ω(k)}$

for integrals (called modified moments)

$\text{m}{}_{\mathrm{k}}{}^{\mathrm{\{\lambda \}}}\text{[f]df=}\text{∫}\text{?1}\text{1}\text{f(x)C}{}_{\mathrm{k}}{}^{\mathrm{(\lambda )}}\text{(x)dx (k = 0,1,…)}$

in which C_k^(λ) is the k-th Gegenbauer polynomial of order $\text{λ(λ > ?}\text{1}\text{2}\text{)}$, and f is a function satisfying the differential equation

$\text{∑}\text{i=0}\text{n}\text{P}{}_{\mathrm{i}}\text{(x)f}{}^{\mathrm{(i)}}\text{(x) = p(x) (?1?x?1)}$

of order n, where p₀, p₁, …, p_n ? 0 are polynomials, and m_k^〈λ〉[p] is known for every k. We give three methods of construction of such a recurrence relation. The first of them (called Method I) is optimum in a certain sense.     

“Integer-making” theorems

Let X = {x₁, x₂,…} be a finite set and associate to every x_i a real number α_i. Let f(n) [g (n)] be the least value such that given any family $\text{F}$ of subsets of X having maximum degree n [cardinality n], one can find integers α_i, i=1,2,… so that α_i ? α_i|<1 and

$\text{∑}\text{x}{}_{\mathrm{i\; ?\; E}}\text{a}{}_{\mathrm{i}}\text{?}\text{∑}\text{x}{}_{\mathrm{i\; ?\; E}}\text{α}{}_{\mathrm{i}}\text{≤?(n)}\text{∑}\text{x}{}_{\mathrm{i\; ?\; E}}\text{a}{}_{\mathrm{i}}\text{?}\text{∑}\text{x}{}_{\mathrm{i\; ?\; E}}\text{α}{}_{\mathrm{i}}\text{≤}\text{g(n)}$

for all $\text{E ?}\text{F}$. We prove

$\text{f(n)≤n ? 1 and g(n)≤c(n}\text{log}\text{n)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$

.     

A combinatorial interpretation for two transformations of series that commute with compositional inversion

For a formal power series $\text{g(t) =}\text{1}\text{[1 + ∑}{}_{\mathrm{n=1}}{}^{\mathrm{\infty }}\text{h}{}_{\mathrm{n}}\text{t}{}^{\mathrm{n}}\text{]}$ with nonnegative integer coefficients, the compositional inverse $\text{f}\text{(t) = t · f(t)}$ of $\text{g}\text{(t) = t · g(t)}$ is shown to be the generating function for the colored planted plane trees in which each vertex of degree i + 1 is colored one of h_i colors. Since the compositional inverse of the Euler transformation of f(t) is the star transformation [[g(t)]^?1 ? 1]^?1 of g(t), [2], it follows that the Euler transformation of f(t) is the generating function for the colored planted plane trees in which each internal vertex of degree i + 1 is colored one of h_i colors for i > 1, and h₁ ? 1 colors for i = 1.     

On matrix functions which commute with their derivative

We improve several results published from 1950 up to 1982 on matrix functions commuting with their derivative, and establish two results of general interest. The first one gives a condition for a finite-dimensional vector subspace E(t) of a normed space not to depend on t, when t varies in a normed space. The second one asserts that if A is a matrix function, defined on a set ?, of the form A(t)= U diag(B₁(t),…,B_p(t)) U^-1, t ∈ ?, and if each matrix function B_k has the polynomial form

$\text{B}{}_{\mathrm{k}}\text{(t)=}\text{∑}\text{i=0}\text{α}{}_{\mathrm{k}}\text{f}{}_{\mathrm{ki}}\text{(t)C}{}_{\mathrm{k}}{}^{\mathrm{i}}\text{, t∈ ?, k∈{1,…,p}}$

then A itself has the polynomial form

$\text{A(t)=}\text{∑}\text{i=0}\text{d?1}\text{f}{}_{\mathrm{i}}\text{(t)C}{}^{\mathrm{i}}\text{,t∈?}$

, where

$\text{d=}\text{∑}\text{k=1}\text{p}\text{d}{}_{\mathrm{k}}$

, d_k being the degree of the minimal polynomial of the matrix C_k, for every k ∈ {1,…,p}.     

Generalizations of two inequalities involving hermitian forms

Let λ₁ and λ_N be, respectively, the greatest and smallest eigenvalues of an N×N hermitian matrix H=(h_ij), and x=(x₁,x₂,…,x_N) with (x,x)=1. Then, it is known that (1) λ₁?(x,Hx)?λ_N and (2) if, in addition, H is positive definite, $\text{(λ}{}_1\text{+λ}{}_{\mathrm{N}}\text{)}{}^2\text{4λ}{}_1\text{λ}{}_{\mathrm{N}}\text{?(x,Hx)(x,H}{}^{\mathrm{?1}}\text{x)?1}$. Assuming that y=(y₁,y₂,…, y_N) and |y_i|?1, i=1,2,…,N, it is shown in this paper that these inequalities remain true if H and H^?1 are, respectively, replaced by the Hadamard products $\text{M(y)1H}$ and $\text{M(y)1H}{}^{\mathrm{?1}}$, where M(y) is a matrix defined by $\text{M(y)=(δ}{}_{\mathrm{ij}}\text{+(1?δ}{}_{\mathrm{ij}}\text{)}\text{y}{}_{\mathrm{i}}\text{y}{}_{\mathrm{j}}$. Subsequently, these results are extended to improve the spectral bounds of $\text{M(y)1H}$.     

On the closability of some positive definite symmetric differential forms on c0∞(ω)

Let $\text{S}$ be a Dirichlet form in $\text{L}{}^2\text{(Ω; m)}$, where Ω is an open subset of $\text{R}$ⁿ, n ? 2, and m a Radon measure on Ω; for each integer k with 1 ? k < n, let $\text{S}$_k be a Dirichlet form on some k-dimensional submanifold $\text{Ω}{}_{\mathrm{k}}$ of Ω. The paper is devoted to the study of the closability of the forms E with domain $\text{C}{}_0{}^{\mathrm{\infty }}\text{(Ω)}$ and defined by: $\text{(?,g)=}$$\text{E}$$\text{(?, g)+}\text{∑}\text{i}\text{p}\text{=1}$$\text{E}$k_i where 1 ? k_p < ? < n, and where , g^k_i denote restrictions of ?, g in $\text{C}{}_0{}^{\mathrm{\infty }}\text{(Ω)}$ to . Conditions are given for E to be closable if, for each i = 1,…, p, one has k_i = n ? i. Other conditions are given for E to be nonclosable if, for some i, k_i < n ? i.     

A divided difference inequality for n-convex functions

For a₍₁₎ ? a₍₂₎ ? ··· ? a_(n) ? 0, b₍₁₎ ? b₍₂₎ ? ··· ? b_(n) ? 0, the ordered values of a_i, b_i, i = 1, 2,…, n, m fixed, m ? n, and p ? 1 it is shown that

$\text{∑}\text{1}\text{n}\text{a}{}_{\mathrm{i}}\text{b}{}_{\mathrm{i}}\text{?}\text{∑}\text{1}\text{m}\text{a}{}^{\mathrm{p}}{}_{\mathrm{(i)}}{}^{\mathrm{<mtext>1</mtext><mtext>p</mtext>}}\text{∑}\text{1}\text{m?k?1}\text{b}{}^{\mathrm{q}}{}_{\mathrm{(i)}}\text{+}\text{b}{}^{\mathrm{q}}{}_{\mathrm{[m?k]}}\text{(k+1)}{}^{\mathrm{<mtext>q</mtext><mtext>p</mtext>}}{}^{\mathrm{<mtext>1</mtext><mtext>q</mtext>}}$

where $\text{1}\text{p}\text{+}\text{1}\text{q}\text{= 1, b}{}_{\mathrm{[j]}}\text{= b}{}_{\mathrm{(j)}}\text{+ b}{}_{\mathrm{(j\; +\; 1)}}\text{+ ··· + b}{}_{\mathrm{(n)}}\text{,}\text{and}\text{k}$ is the integer such that $\text{b}{}_{\mathrm{(m\; ?\; k\; ?\; 1)}}\text{?}\text{b[m ? k]}\text{(k + 1)}$ and $\text{b}{}_{\mathrm{(m\; ?\; k)}}\text{<}\text{b}{}_{\mathrm{[m\; ?\; k\; +\; 1]}}\text{k}$. The inequality is shown to be sharp. When p < 1 and a_(i)'s are in increasing order then the inequality is reversed.     

Two transformations of series that commute with compositional inversion

It is shown that the compositional inverse of either of two transformations of a given series can be determined from the compositional inverse of the series. Specifically, if t · f(t) and t · g(t) are compositional inverses, then so are t · f_k(t) and $\text{t · g}{}_{\mathrm{k}}{}^1\text{(t)}$, where f_k(t) is the kth Euler transformation of f(t) and $\text{g}{}_{\mathrm{k}}{}^1\text{(t) =}\text{g(t)}\text{(1 ? kt · g(t))}$.     

The existence,uniqueness, and instability of spherically symmetric solutions of a system of reaction—Diffusion equations

The system $\text{?x}\text{?t}\text{= Δx + F(x,y),}\text{?y}\text{?t}\text{= G(x,y)}$ is investigated, where x and y are scalar functions of time (t ? 0), and n space variables $\text{(ξ}{}_1\text{,…, ξ}{}_{\mathrm{n}}\text{), Δx ≡ ∑}{}_{\mathrm{i\; =\; 1}}{}^{\mathrm{n}}\text{?}{}^2\text{x}\text{?ξ}{}_{\mathrm{i}}{}^2$, and F and G are nonlinear functions. Under certain hypotheses on F and G it is proved that there exists a unique spherically symmetric solution $\text{(x(r),y(r)),}\text{where}\text{r = (ξ}{}_1{}^2\text{+ … + ξ}{}_{\mathrm{n}}{}^2\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$, which is bounded for r ? 0 and satisfies x(0) >x₀, y(0) > y₀, x′(0) = 0, y′(0) = 0, and x′ < 0, y′ > 0, ?r > 0. Thus, (x(r), y(r)) represents a time independent equilibrium solution of the system. Further, the linearization of the system restricted to spherically symmetric solutions, around (x(r), y(r)), has a unique positive eigenvalue. This is in contrast to the case n = 1 (i.e., one space dimension) in which zero is an eigenvalue. The uniqueness of the positive eigenvalue is used in the proof that the spherically symmetric solution described is unique.     

On the probability that given polynomials have a specified highest common factor

The polynomial functions f₁, f₂,…, f_m are found to have highest common factor h for a set of values of the variables x₁, x₂,…,x_m whose asymptotic density is

$\text{1}\text{h}{}^{\mathrm{n}}\text{∑}\text{d∣h}\text{μ(d)Π}{}^{\mathrm{m}}{}_{\mathrm{l\; =\; 1}}\text{?(f}{}_1\text{, dh)}\text{d}{}^{\mathrm{m}}\text{Π}\text{p∣h}\text{1?}\text{Π}{}^{\mathrm{m}}{}_{\mathrm{l\; =\; 1}}\text{?(f}{}_1\text{, p)}\text{p}{}^{\mathrm{m}}$

For the special case f₁(x) = f₂(x) = … = f_m(x) = x and h = 1 the above formula reduces to $\text{Π}{}_{\mathrm{?}}\text{(1 ?}\text{1}\text{p}{}^{\mathrm{m}}\text{) =}\text{1}\text{ζ}\text{(m)}$, the density if m-tuples with highest common factor 1. Necessary and sufficient conditions on the polynomials f₁, f₂,…, f_m for the asymptotic density to be zero are found. In particular it is shown that either the polynomials may never have highest common factor h or else h is the highest common factor infinitely often and in fact with positive density.     

Some divided difference inequalities for n-convex functions

Using results from the theory of B-splines, various inequalities involving the nth order divided differences of a function f with convex nth derivative are proved; notably, $\text{f}{}^{\mathrm{(n)}}\text{(z)}\text{n! ? [x}{}_0\text{,…, x}{}_{\mathrm{n}}\text{]f}\text{?}\text{∑}{}_{\mathrm{i\; =\; 0}}{}^{\mathrm{n}}\text{(f}{}^{\mathrm{(n)}}\text{(x}{}_{\mathrm{i}}\text{)}\text{(n + 1)!)}$, where z is the center of mass $\text{(}\text{1}\text{(n + 1))}\text{∑}{}_{\mathrm{i\; =\; 0}}{}^{\mathrm{n}}\text{x}{}_{\mathrm{i}}$.     

La valeur optimale des programmes entiersThe optimal value of integer programs

We present a formula for the optimal value f_c(y) of the integer program $\text{max}\text{{c′x∣x∈}\text{Ω}\text{(y)∩}\text{N}{}^{\mathrm{n}}\text{}}$ where $\text{Ω}\text{(y)}$ is the convex polyhedron $\text{{x∈}\text{R}{}^{\mathrm{n}}\text{∣Ax=y,}\text{x?0}}$. It is a consequence of Brion and Vergne's formula which evaluates the sum . As in linear programming, f_c(y) can be obtained by inspection of the reduced-costs at the vertices of the polyhedron. We also provide an explicit result that relates f_c(ty) and the optimal value of the associated continous linear program, for large values of $\text{t∈}\text{N}$. To cite this article: J.B. Lasserre, C. R. Acad. Sci. Paris, Ser. I 335 (2002) 863–866.     

On asymptotic solutions of the renewal equation

Consider the renewal equation in the form (¹) $\text{u(t) = g(t) + ∝}{}_{\mathrm{o}}{}^{\mathrm{t}}\text{u(t ? τ) ?(τ) dτ}$, where $\text{?(t)}$ is a probability density on [0, ∞) and lim_{t → ∞}g(t) = g₀. Asymptotic solutions of (¹) are given in the case when f(t) has no expectation, i.e., $\text{∝}{}_0{}^{\mathrm{\infty }}\text{t?(t)dt = ∞}$. These results complement the classical theorem of Feller under the assumption that f(t) possesses finite expectation.     

Arithmetic in generalized Artin-Schreier extensions of k(x)

If k is a perfect field of characteristic p ≠ 0 and k(x) is the rational function field over k, it is possible to construct cyclic extensions K_n over k(x) such that [K : k(x)] = pⁿ using the concept of Witt vectors. This is accomplished in the following way; if [β₁, β₂,…, β_n] is a Witt vector over k(x) = K₀, then the Witt equation $\text{y}{}^{\mathrm{p}}\text{?}\text{y}\text{= β}$ generates a tower of extensions through $\text{K}{}_{\mathrm{i}}\text{= K}{}_{\mathrm{i?1}}\text{(}\text{y}{}_{\mathrm{i}}\text{)}$ where $\text{y}\text{= [}\text{y}{}_1\text{,}\text{y}{}_2\text{,…,}\text{y}{}_{\mathrm{n}}\text{]}$. In this paper, it is shown that there exists an alternate method of generating this tower which lends itself better for further constructions in K_n. This alternate generation has the form K_i = K_i?1(y_i); y_i^p ? y_i = B_i, where, as a divisor in K_i?1, B_i has the form . In this form q is prime to Πp_j^λ_j and each λ_j is positive and prime to p. As an application of this, the alternate generation is used to construct a lower-triangular form of the Hasse-Witt matrix of such a field K_n over an algebraically closed field of constants.     

Sur quelques résultats de convergence dans l'inférence d'une classe de processus ponctuelsConvergence results for point processes estimators

Our aim is to generalize some results obtained for a Poisson point process in [7], to a general point process. Those results are in field of complete convergence of two like Parzen–Rosenblatt estimates of density of mean measure function and regression curves. Those estimates are defined from the superposition of n i.i.d. point processes as:

$\text{f}{}_{\mathrm{n}}\text{(x)=}\text{1}\text{nh}\text{∑}\text{i=1}\text{m}\text{K}\text{x?X}{}_{\mathrm{i}}{}^{\mathrm{(n)}}\text{h(n)}\text{and}\text{Ψ}{}_{\mathrm{n}}\text{(x)=}\text{∑}{}_{\mathrm{i=1}}{}^{\mathrm{m}}\text{Y}{}_{\mathrm{i}}\text{K}\text{x?X}{}_{\mathrm{i}}{}^{\mathrm{(n)}}\text{h(n)}\text{∑}{}_{\mathrm{i=1}}{}^{\mathrm{m}}\text{K}\text{x?X}{}_{\mathrm{i}}{}^{\mathrm{(n)}}\text{h(n)}\text{,}$

where m is the number of seem generics points of the superposition. We give some sufficient conditions for the convergence of those kernel-like estimators. To cite this article: A. Diakhaby, C. R. Acad. Sci. Paris, Ser. I 334 (2002) 597–602.     

Coding theory in white Gaussian channel with feedback

The message m = {m(t)} is a Gaussian process that is to be transmitted through the white Gaussian channel with feedback: $\text{Y(t) = ∫}{}_0{}^{\mathrm{t}}\text{F(s, Y}{}_0{}^{\mathrm{s}}\text{, m)ds + W(t)}$. Under the average power constraint, $\text{E[F}{}^2\text{(s, Y}{}_0{}^{\mathrm{s}}\text{, m)] ≤ P}{}_0$, we construct causally the optimal coding, in the sense that the mutual information I_t(m, Y) between the message m and the channel output Y (up to t) is maximized. The optimal coding is presented by $\text{Y(t) = ∫}{}_0{}^{\mathrm{t}}\text{A(s)[m(s) ?}\text{m}\text{?}\text{(s)] ds + W(t)}$, where $\text{m}\text{?}\text{(s) = E[m(s) ¦ Y(u), 0 ≤ u ≤ s]}$ and A(s) is a positive function such that $\text{A}{}^2\text{(s) E |m(s) ?}\text{m}\text{?}\text{(s)|}{}^2\text{= P}{}_0$.     

Infinite-variate wide-sense Markov processes and functional analysis for bounded operator-forming vectors

Let p, q be arbitrary parameter sets, and let $\text{H}$ be a Hilbert space. We say that x = (xⁱ)_i?q, xⁱ ? $\text{H}$, is a bounded operator-forming vector (?$\text{H}$_F^q) if the Gram matrix 〈x, x〉 = [(xⁱ, x^j)]_i?q,j?q is the matrix of a bounded (necessarily ≥ 0) operator on $\text{l}{}_{\mathrm{q}}{}^2$, the Hilbert space of square-summable complex-valued functions on q. Let A be p × q, i.e., let A be a linear operator from $\text{l}{}_{\mathrm{q}}{}^2$ to $\text{l}{}_{\mathrm{p}}{}^2$. Then exists a linear operator ǎ from (the Banach space) $\text{H}$_F^q to $\text{H}$_F^p on $\text{D}$(A) = {x:x ? $\text{H}$_F^q, $\text{A〈x, x〉}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$ is p × q bounded on $\text{l}{}_{\mathrm{q}}{}^2$} such that y = ǎx satisfies y^j?σ(x) = {space spanned by the xⁱ}, 〈y, x〉 = A〈x, x〉 and $\text{〈y, y〉 = A〈x, x〉}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{(A〈x, x〉}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{)}{}^1$. This is a generalization of our earlier [J. Multivariate Anal.4 (1974), 166–209; 6 (1976), 538–571] results for the case of a spectral measure concentrated on one point. We apply these tools to investigate q-variate wide-sense Markov processes.