Nested matrices and the existence of least majorized elements

We characterize the matrices A for which X(b)={x∣x∈Rⁿ, x?0, Ax?b, σⁿ_i=1x_i=1} contains a least majorized element for all vectors b satisfying X(b)≠?.     

Convergence of a subgradient method for computing the bound norm of matrices

Let φ and ψ be any norms on $\text{R}$^m and $\text{R}$ⁿ respectively. We study a subgradient method for computing the associated bound norm S_φψ(A) = sup{φ(Ax), ψ(x)?1} (a nonconvex optimization problem). It is proved that homodual method converges when one of the norms φ and ψ is polyhedral.     

On a generalization of Minkowski's convex body theorem

Given a lattice $\text{Λ ? R}{}^{\mathrm{n}}$ and a bounded function g(x), x ∈ Rⁿ, vanishing outside of a bounded set, the functions ?(x)$\text{g}\text{?}\text{(x)?}$max_u∈Λg(u +x), ?(x)?Σ_{u∈Λ g(u +x)}, and ?₊(x)?Σ_u∈Λ max_{v∈Λ min {g(v + x); g(u + v + x)}} are defined and periodic mod Λ on Rⁿ. In the paper we prove that ?(x) + ?₊(x) ? 2?(x) ≥ ?(x) + h?₊(x) ? 2?(x) holds for all x ∈ Rⁿ, where h(x) is any “truncation” of g by a constant c ≥ 0, i.e., any function of the form h(x)?g(x) if g(x) ≤ c and h(x)?c if g(x) > c. This inequality easily implies some known estimations in the geometry of numbers due to Rado [1] and Cassels [2]. Moreover, some sharper and more general results are also derived from it. In the paper another inequality of a similar type is also proved.     

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.     

Retraction spaces and the homotopy metric

Let X be a finite-dimensional compactum. Let $\text{R}$(X) and $\text{N}$(X) be the spaces of retractions and non-deformation retractions of X, respectively, with the compact-open (=sup-metric) topology. Let 2^X_h be the space of non-empty compact ANR subsets of X with topology induced by the homotopy metric. Let R^X_h be the subspace of 2^X_h consisting of the ANR's in X that are retracts of X.We show that $\text{N}$(S^m) is simply-connected for m > 1. We show that if X is an ANR and A₀?R^X_h, then lim_i→∞A_i=A₀ in 2^X_h if and only if for every retraction r₀ of X onto A₀ there are, for almost all i, retractions r_i of X onto A_i such that lim_i→∞r_i=r_o in $\text{R}$(X). We show that if X is an ANR, then the local connectedness of $\text{R}$(X) implies that of R^X_h. We prove that $\text{R}$(M) is locally connected if M is a closed surface. We give examples to show how some of our results weaken when X is not assumed to be an ANR.     

A maximum principle in Rn + 1

In this paper we establish maximum principles of the Cauchy problem for hyperbolic equations in $\text{R}$³ and $\text{R}$^{n + 1}(n ? 2). Our maximum principles generalize the results of Weinberger [5], and Sather [3, 4] for a class of equations such that the coefficients can be allowed to depend upon t, as well, in {x₁, x₂, t}-space and {x₁, x₂,…, x_n, t}-space. Throughout this paper, the influence of the work of Douglis [1] is apparent. See [2].     

Perturbations with several independent parameters

In this paper we discuss the problem of determining a T-periodic solution $\text{x}{}^1\text{(·, λ)}$ of the differential equation x = A(t)x + f(t, x, λ) + b(t), where the perturbation parameter λ is a vector in a parameter-space R^k. The customary approach assumes that λ = λ(?), ??R. One then establishes the existence of an ?₀ > 0 such that the differential equation has a T-periodic solution $\text{x}{}^1\text{(·, λ(?))}$ for all ? satisfying 0 < ? < ?₀. More specifically it is usually assumed that λ(?) has the form λ(?) = ?λ₀ where λ₀ is a fixed vector in R^k. This means that attention is confined in the perturbation procedure to examining the dependence of $\text{x}{}^1\text{(·, λ)}$ on λ as λ varies along a line segment terminating at the origin in the parameter-space R^k. The results established here generalize this previous work by allowing one to study the dependence of $\text{x}{}^1\text{(·, λ)}$ on λ as λ varies through a “conical-horn” whose vertex rests at the origin in R^k. In the process an implicit-function formula is developed which is of some interest in its own right.     

On solutions of “equations in symmetric groups”

Let x?S_n, the symmetric group on n symbols. Let θ? Aut(S_n) and let the automorphim order of x with respect to θ be defined by

$\text{γθ(x)=}\text{min}\text{{k:x xθ xθ}{}^2\text{? xθ}{}^{\mathrm{k?1}}\text{=1}}$

where xθ is the image of x under θ. Let α_g? Aut(S_n) denote conjugation by the element g?S_n. Let where s and k are positive integers and $\text{a}\text{b}$ denotes a divides b. Further h(s, k : n) ≡ b(1; s, k : n), where 1 denotes the identity automorphim. If g?S_n let c = f(g, s) denote the number of symbols in g which are in cycles of length not dividing the integer s, and let g_s denote the product of all cycles in g whose lengths do not divide s. Then g_s moves c symbols. The main results proved are: (1) recursion: if n ? c + 1 and t = n ? c ? 1 then $\text{b(g; s, 1:n)=∑}{}_{\mathrm{<mtext>i</mtext><mtext>s</mtext>}}\text{b(g; s, 1:n?1)(}{}^{\mathrm{t}}{}_{\mathrm{i?1}}\text{(i?1)!}$ (2) reduction: b(g; s, 1 : c)h(s, 1 : i) = b(g; s, 1 : i + c); (3) distribution: let D(θ, n) ≡ {(k, b) : k?Z⁺ and b = b(θ; 1, k : n) ≠ 0}; then D(θ, m) = D(φ, m) ∨ m ? N = N(θ, φ) iff θ is conjugate to φ; (4) evaluation: the number of cycles in g_s^s of any given length is smaller than the smallest prime dividing s iff b(g_s; s, 1 : c) = 1. If g = (12 … p^m)^t and $\text{sk}\text{p}{}^{\mathrm{m}}$ then $\text{b(g;s,k:p}{}^{\mathrm{m}}\text{) {}{}^0{}_{\mathrm{\pm 1}}\text{(}\text{mod}\text{p)}$.     

Phase reconstruction from magnitude of band-limited multidimensional signals

In this paper, the problem of phase reconstruction from magnitude of multidimensional band-limited functions is considered. It is shown that any irreducible band-limited function f(z₁…,z_n), z_i ? $\text{C}$, i=1, …, n, is uniquely determined from the magnitude of f(x₁…,x_n): | f(x₁…,x_n)|, x_i ? $\text{R}$, i=1,…, n, except for (1) linear shifts: ^{i(α1z1+…+α_n2n+β}), β, α_i?$\text{R}$, i=1,…, n; and (2) conjugation: $\text{f}{}^1\text{(z}{}_1{}^1\text{,…,z}{}_{\mathrm{n}}{}^1\text{)}$.     

Solutions de type multi-soliton des équations de KdV généralisées

We consider the generalized Korteweg–de Vries equations in the subcritical and critical cases. Let R_j(t,x)=Q_cj(x?c_jt?x_j) be N soliton solutions of this equation, with corresponding speeds 0<c₁<c₂<?<c_N. In this Note, we give a sketch of the proof of the following result. Given $\text{{c}{}_{\mathrm{j}}\text{},}\text{{x}{}_{\mathrm{j}}\text{}}$, there exists one and only one solution ? of the generalized KdV equation such that 6?(t)?∑R_j(t)6_H¹→0 as t→+∞. Complete proofs will appear later. To cite this article: Y. Martel, C. R. Acad. Sci. Paris, Ser. I 338 (2004).     

A continuation method for solving separable nonlinear least squares problems

Given the data (x_i, y_i), i=1, 2, …, n, the problem is to find the values of the linear and nonlinear parameters â and b? which minimize the nonlinear functional |F(b)a?y|₂² over $\text{a ?}\text{R}{}^{\mathrm{p}}\text{, b ?}\text{R}{}^{\mathrm{q}}\text{,}\text{where}\text{F ?}\text{R}{}^{\mathrm{n\times p}}$ is a variable matrix and assumed to be of full rank, and $\text{y ?}\text{R}{}^{\mathrm{n}}$ is a constant vector.In this paper, we present a method for solving this problem by imbedding it into a one-parameter family of problems and by following its solution path using a predictor-corrector algorithm. In the course of iterations, the original problem containing p+q+1 variables is transformed into a problem with q+1 nonlinear variables by taking the separable structure of the problem into account. By doing so, the method reduces to solving a series of equations of smaller size and a considerable saving in the storage is obtained.Results of numerical experiments are reported to demonstrate the effectiveness of the proposed method.     

Some explicit formulae in simultaneous padé approximation

Using old results on the explicit calculation of determinants, formulae are given for the coefficients of P₀(z) and P₀(z)f_i(z) ? P_i(z), where P_i(z) are polynomials of degree σ ? ρ_i (i=0,1,…,n), P₀(z)f_i(z) ? P_i(z) are power series in which the terms with z^k, 0?k?σ, vanish (i=1,2,…,n), (ρ₀,ρ₁,…,ρ_n) is an (n+1)-tuple of nonnegative integers, σ=ρ₀+ρ₁+?+ρ_n, and {f_i}ⁿ_i=1 is the set of hypergeometric functions {₁F₁(1;c_i;z)}ⁿ_i=1$\text{(c}{}_{\mathrm{i}}\text{?}\text{Z}\text{z.drule;}\text{N}\text{, c}{}_{\mathrm{i}}\text{? c}{}_{\mathrm{j}}\text{?}\text{Z}\text{)}$ or {₂F₀(a_i,1;z)}ⁿ_i=1$\text{(a}{}_{\mathrm{i}}\text{?}\text{Z}\text{?}\text{N}\text{, a}{}_{\mathrm{i}}\text{? a}{}_{\mathrm{j}}\text{?}\text{Z}\text{)}$ under the condition ρ₀?ρ_i ? 1 (i=1,2,…,n).     

On constant discrete programming problems

Let H be a subset of the set S_n of all permutations

$\text{1}\text{2}\text{???}\text{n}\text{s(1)}\text{s(2)}\text{???}\text{s(n)}$

C=6c_ij6 a real n?n matrix L_c(s)=c_1s(1)+c_2s(2)+???+c_ns(n) for s ? H. A pair (H, C) is the existencee of reals a₁,b₁,a₂,b₂,…a_n,b_n, for which c_ij=a₁+b_j if (i,j)?D(H), where D(H)={(i,j):(?h?H)(j=h(i))}.For a pair (H,C) the specifity of it is proved in the case, when H is either a special cyclic class of permutations or a special union of cyclic classes. Specific pairs with minimal sets H are in some sense described.     

Solution of a system of functional-differential equations arising from an optimization problem

In connection with an optimization problem, all functions ?: Iⁿ → $\text{R}$ with continuous nonzero partial derivatives and satisfying

$\text{??}\text{?x,}{}_{\mathrm{i}}\text{??}\text{?x}{}_{\mathrm{j}}$

for all x_i, x_j ≠ I, i, j = 1,2,…, n (n > 2) are determined (I is an interval of positive real numbers).     

Asymptotics for the blow-up boundary solution of the logistic equation with absorption

Let $\text{Ω}$ be a smooth bounded domain in $\text{R}{}^{\mathrm{N}}$. Assume that f?0 is a C¹-function on [0,∞) such that f(u)/u is increasing on (0,+∞). Let a be a real number and let b?0, b?0 be a continuous function such that b≡0 on $\text{?Ω}$. The purpose of this Note is to establish the asymptotic behaviour of the unique positive solution of the logistic problem Δu+au=b(x)f(u) in $\text{Ω}$, subject to the singular boundary condition u(x)→+∞ as $\text{dist}\text{(x,?Ω)→0}$. Our analysis is based on the Karamata regular variation theory. To cite this article: F.-C. Cîrstea, V. R?dulescu, C. R. Acad. Sci. Paris, Ser. I 336 (2003).     

Existence of stable equilibrium point for dynamical systems of Volterra type

This paper presents sufficient conditions for the existence of a nonnegative and stable equilibrium point of a dynamical system of Volterra type, (1) $\text{(}\text{d}\text{dt}\text{) x}{}_{\mathrm{i}}\text{(t) = ?x}{}_{\mathrm{i}}\text{(t)[f}{}_{\mathrm{i}}\text{(x}{}_1\text{(t),…, x}{}_{\mathrm{n}}\text{(t)) ? q}{}_{\mathrm{i}}\text{], i = 1,…, n}$, for every q = (q₁,…, q_n)^T?Rⁿ. Results of a nonlinear complementarity problem are applied to obtain the conditions. System (1) has a nonnegative and stable equilibrium point if (i) f(x) = (f₁(x),…,f_n(x))^T is a continuous and differentiable M-function and it satisfies a certain surjectivity property, or (ii), f(x) is continuous and strongly monotone on R₊₀ⁿ.     

Restoring rank and consistency by orthogonal projection

Let A₀x=b₀ be a consistent (but possibly unknown) linear algebraic system of m equations in n unknowns, with rank(A₀)=k (likewise possibly unknown). Let Ax=b be a known (but possibly inconsistent) nearby system. Procedures for “solving” Ax=b usually replace it (at least in principle) by a nearby consistent system $\text{A}\text{?}\text{x=}\text{b}\text{?}$ of (hopefully) rank k, and solve that one instead. We consider consistent systems $\text{A}\text{?}\text{x=}\text{b}\text{?}$ with rank$\text{(}\text{A}\text{?}\text{)=k}$ such that (Ã,b?) is the orthogonal projection of (A,b) on span(Ã) [i.e., the columns of (Ã┆b?) are the projections of those of (A ┆ b)]. Under suitable circumstances the rank k pair (Ã,b?) nearest to (A,b) in the sense of minimizing $\text{6(}\text{A}\text{?}\text{┆}\text{b}\text{?}\text{) ? (}\text{A}\text{?}\text{┆}\text{b}\text{?}\text{)6}{}_{\mathrm{F}}$ belongs to this class, as well as the pair delivered by the ordinary least squares method (if k=n?m) or, more generally, the pair delivered by a well-known algorithm (viz. HFTI). If $\text{?:= |(A┆b)?(A}{}_0\text{┆b}{}_0\text{)6}{}_{\mathrm{F}}$, then the minimum length solutions of all systems $\text{A}\text{?}\text{x=}\text{b}\text{?}$ so related to (A,b) are shown to differ mutually only by O(?²). This means, e.g., that itwill usually not pay to compute the solution of the nearest system.     

Duality theorems for perturbed convex optimization

We show that if F, X are two locally convex spaces and $\text{h: F →}\text{R}\text{?}\text{, ?: F × X → R}$ are two convex functionals satisfying h(y) = ?(y, x₀) (y?F) for some x₀?X, then, under suitable assumptions, the computation of inf h(F) can be reduced to the computation of inf ?(H) on certain hyperplanes H of F × X. We give some applications.     

On orthogonal matrices with constant diagonal

In connection with the problem of finding the best projections of k-dimensional spaces embedded in n-dimensional spaces Hermann König asked: Given m∈$\text{R}$ and n∈$\text{N}$, are there n×n matrices C=(c_ij), i, j=1,…,n, such that c_ii=m for all i, |c_ij|=1 for i≠j, and C²=(m²+n?1)I_n? König was especially interested in symmetric C, and we find some families of matrices satisfying this condition. We also find some families of matrices satisfying the less restrictive condition CC^T=(m²+n?1)I_n.