On iterative methods for solving nonlinear least squares problems over convex sets

Nonlinear least squares problems over convex sets inR ⁿ are treated here by iterative methods which extend the classical Newton, gradient and steepest descent methods and the methods studied recently by Pereyra and the author. Applications are given to nonlinear least squares problems under linear constraint, and to linear and nonlinear inequalities. Part of the research underlying this report was undertaken for the Office of Naval Research, Contract Nonr-1228(10), Project NR047-021, and for the U.S. Army Research Office — Durham, Contract No. DA-31-124-ARO-D-322 at Northwestern University. Reproduction of this paper in whole or in part is permitted for any purpose of the United States Government.     

Intersections ofk-element sets

LetF be a collection ofk-element sets with the property that the intersection of no two should be included in a third. We show that such a collection of maximum size satisfies .2715k+o(k)≦≦log₂ |F|≦.7549k+o(k) settling a question raised by Erdős. The lower bound is probabilistic, the upper bound is deduced via an entropy argument. Some open questions are posed. This research has been supported in part by the Office of Naval Research under Contract N00014-76-C-0366. Supported in part by a NSF postdoctoral Fellowship.     

On a difference equation arising in a learning-theory model

An analysis is presented of the equationf(x+a)−f(x)=e ^−x {f(x)−f(x−b)}. Herea andb denote arbitrary positive constants, and a solution is sought which satisfies the following conditions:f(−∞)=0,f(+∞)=1, 0≦f(x)≦1. Existence and uniqueness of solution are established, and then an analytical form of the solution is obtained by use of bilateral Laplace transform. Research supported by the National Science Foundation, Grant GP-2558.     

Asymptotic expansions for oscillatory integrals using inverse functions

We treat finite oscillatory integrals of the form ∫ _a ^b F(x)e ^ikG(x) dx in which both F and G are real on the real line, are analytic over the open integration interval, and may have algebraic singularities at either or both interval end points. For many of these, we establish asymptotic expansions in inverse powers of k. No appeal to the theories of stationary phase or steepest descent is involved. We simply apply theory involving inverse functions and expansions for a Fourier coefficient ∫ _a ^b φ(t)e ^ikt dt. To this end, we have assembled several results involving inverse functions. Moreover, we have derived a new asymptotic expansion for this integral, valid when , −1<σ ₁<σ ₂<⋅⋅⋅. The authors were supported by the Office of Advanced Scientific Computing Research, Office of Science, US Department of Energy, under Contract DE-AC02-06CH11357.     

On order preserving contractions

Let (Ω,Σ,μ) be a measure space and letP be an operator onL ₂(Ω,Σ,μ) with ‖P‖≦1,Pf≧0 a.e. wheneverf≧0. If the subspaceK is defined byK={x| ||P ⁿ x||=||P ^*n x||=||x||,n=1,2,...} thenK=L ₂(Ω,Σ₁,μ), where Σ₁ ⊂ Σ and onK the operatorP is “essentially” a measure preserving transformation. Thus the eigenvalues ofP of modulus one, form a group under multiplication. This last result was proved by Rota for finiteμ here finiteness is not assumed) and is a generalization of a theorem of Frobenius and Perron on positive matrices. The research reported in this document has been sponsored in part by Air Force Office of Scientific Research, OAR through the European Office, Aerospace Research, United States Air Force.     

Matrices with the edmonds—Johnson property

A matrixA=(a _ij ) has theEdmonds—Johnson property if, for each choice of integral vectorsd ₁,d ₂,b ₁,b ₂, the convex hull of the integral solutions ofd ₁≦x≦d ₂,b ₁≦Ax≦b ₂ is obtained by adding the inequalitiescx≦|δ|, wherec is an integral vector andcx≦δ holds for each solution ofd ₁≦x≦d ₂,b ₁≦Ax≦b ₂. We characterize the Edmonds—Johnson property for integral matricesA which satisfy for each (row index)i. A corollary is that ifG is an undirected graph which does not contain any homeomorph ofK ₄ in which all triangles ofK ₄ have become odd circuits, thenG ist-perfect. This extends results of Boulala, Fonlupt, Sbihi and Uhry. First author’s research supported by the Netherlands Organization for the Advancement of Pure Research (Z.W.O.).     

On the variation of co-ordinates in subspaces

Summary Let1≦k≦n−1, 2≦n. This paper examines the vectors δ_p(L_k), where L_k is a k-dimensional subspace of an n-dimensional space, and the co-ordinates of δ_p(L_k) are given below by (1.1). For fixed k, the set of such vectors as L_k varies is determined for p=2. For general p, information is given on upper and lower bounds for the sum of the co-ordinates of δ_p(L_k). Dedicated to the sixtieth birthday of Prof. Edgar R. Lorch This research was supported in part by the Office of Naval Research under contract number Nonr 3775(09), NR 047040.     

Large sample theory for distributions on the hypersphere with rotational symmetries

Summary A distribution on the unit sphere inℝ ^q with a densityf(‖x _v ‖) is considered where is ans(<q) dimensional subspace andx _v is the part ofx in . For a large sample the estimation of , a test that and a test for rotational symmetry within is given. For several samples with possibly different subspaces but the samef, a test that is given. For all tests power functions for contiguous alternatives are given. For the special density proportional to expk‖x _v ‖ ², additional results are given. Research supported in part by a Contract with the Office of Naval Research N00014-81-K-0146 awarded to Princeton University, Princeton, New Jersey 08544.     

Reflection principles for linear elliptic second order partial differential equations with constant coefflcients

Summary Reflection principles, analogous to the classicalSchwarz reflection principle for harmonic functions, are obtained for solutions of linear elliptic second order partial differential equations with constant coefficients. The boundary conditions employed are supposed to be satisfied in a limiting sense only, and do not require (a priori) the existence of derivatives on the boundary. To Mauro Picone on his 70^th birth day. This research was supported in part by the United States Air Force under Contract N^o. AF(600)-573 — monitored by the Office of Scientific Research, Air Research and Development Command. The work of this author was sponsored by the Office of Ordnance Research, U.S. Army, under the Contract DA-36-034-ORD-1486.     

Generalized convexity and concavity of the optimal value function in nonlinear programming

In this paper we consider generalized convexity and concavity properties of the optimal value functionf ^* for the general parametric optimization problemP(_ε) of the form min _x f(x, ε) s.t.x∈R(ε). Many results on convexity and concavity characterizations off ^* were presented by the authors in a previous paper. Such properties off ^* and the solution set mapS ^* form an important part of the theoretical basis for sensitivity, stability and parametric analysis in mathematical optimization. We give sufficient conditions for several types of generalized convexity and concavity off ^*, in terms of respective generalized convexity and concavity assumptions onf and convexity and concavity assumptions on the feasible region point-to-set mapR. Specializations of these results to the parametric inequality-equality constrained nonlinear programming problem are provided. Research supported by Grant ECS-8619859, National Science Foundation and Contract N00014-86-K-0052, Office of Naval Research.     

Goodness of fit of an assigned set of scores for the analysis of association in a contingency table

The problem of association between two attributes in ap×q contingency table can be looked upon as the problem of relationship between two vector variablesx andy. If there is only one true non-zero canonical correlation betweenx andy, the association between the two attributes is of rank 1 and in this case, one set of scores is adequate to describe the association completely; these scores are nothing but the coefficients in the canonical variates corresponding to the true non-zero canonical correlation. Given a set of hypothetical scoresα ₁,α₁,⋯,α_p for the rows, one is interested in testing their goodness of fit. Tests for this are suggested in this paper. For obtaining these tests, a preliminary result about direction and collinearity factors in discriminant analysis, whenS irrelevant variables are eliminated, is needed. This is derived in part one of this paper. This research was sponsored by the Office of Naval Research, Contract No. N00014-68-A-0515, Project No. NR042-260. Reproduction in whole or in part is permitted for any purpose of the United States Government.     

Martingales with given maxima and terminal distributions

Let μ be any probability measure onR with λ |x|dμ(x)<∞, and let μ^* denote its associated Hardy and Littlewood maximal p.m. It is shown that for any p.m.v for which μ<ν<μ^* in the usual stochastic order, there is a martingale (X _t)_0≦t≦1 for which sup_0≦t≦1 X _t andX ₁ have respective p.m. 'sv and μ. The proof uses induction and weak convergence arguments; in special cases, explicit martingale constructions are given. These results provide a converse to results of Dubins and Gilat [6]; applications are made to give sharp martingale and ‘prophet’ inequalities. Supported in part by NSF grants DMS-86-01153 and DMS-88-01818.     

Nonparametric estimation of mean and variance when a few “sample” values possibly outliers

The data (continuous) aren independent observations that are believed to be a random sample. The possibility exists, however, that as many asJ of the largest observations, and as many asK of the smallest observations, are outliers. That is, these observations are from populations that are different from the population yielding the other observations (which number at leastn−J−K). The interest is in obtaining suitable estimates for the mean and variance of the population yielding the other observations.J andK are given and relatively small, with both ≦2n ^A , whereA is specified and ≦1/4. When the population yielding the other observations is continuous, has moments of all orders, and is well-behaved in some other ways, estimates are developed that are unbiased if terms of ordern ^−1+A +2ɛ are neglected. Here, ɛ can be arbitrarily small but is positive. Research partially supported by NASA Grant NGR 44-007-028 and by Mobil Research and Development Corporation. Also associated with ONR Contract N00014-68-A-0515 and Dept. of Labor Grant 31-46-70-06.     

Regressions and monotone chains: A ramsey-type extremal problem for partial orders

Aregression is a functiong from a partially ordered set to itself such thatg(x)≦x for allz. Amonotone k-chain is a chain ofk elementsx ₁<x ₂ <...<x _k such thatg(x ₁)≦g(x ₂)≦...≦g(x _k ). If a partial order has sufficiently many elements compared to the size of its largest antichain, every regression on it will have a monotone (k + 1)-chain. Fixingw, letf(w, k) be the smallest number such that every regression on every partial order with size leastf(w, k) but no antichain larger thanw has a monotone (k + 1)-chain. We show thatf(w, k)=(w+1) ^k . Dedicated to Paul Erdős on his seventieth birthday Research supported in part by the National Science Foundation under ISP-80-11451.     

Linear programming under uncertainty: A basic property of the optimal solution

Summary We show that if the two-stage linear programming problem under uncertainty has an optimal solution, then it has an optimal solution in which the column vectors corresponding to the positive first stage decision variables are linearly independent. This leads to the result that if an optimal solution exists, then there exists an optimal solution in which not more than m + ¯m of the first stage decision variables are positive. These results extend to the multi-stage case.This research was partially supported by the Office of Naval Research under Contract Nonr-222(83), the National Science Foundation under Contract GP-4593, the Army Research Office under Contract DA-31-124-ARO-D-331 and the University of California. Reproduction in whole or part is permitted for any purpose of the United States Government.     

Cayley’s decomposition and pólya’sW-property of ordinary linear differential equations

A proof is given for the equivalence of Pólya’sW- property of a linear differential equationL _n (D) y=0 to the possibility of decomposingL _n (D) ≡ Π _n ¹ [D+λ_i(x)] in a given interval. In this case a set ofn independent solutions form a Chebyshev system in the interval. An application determines intervals of non-oscillation for solutions of linear equations of the second order. Research supported by the National Science Foundation Grant No. GP-3897 with the University of Maryland.     

On the value set of the Ramanujan function

We give lower bounds on the number of distinct values of the Ramanujan function τ(n), n ≦ x, and on the number of distinct residues of τ(n), n ≦ x, modulo a prime ℓ. We also show that for any prime ℓ the values τ(n), n ≦ ℓ⁴, form a finite additive basis modulo ℓ. Received: 6 October 2004     

Properties of a representation of a basis for the null space

Given a rectangular matrixA(x) that depends on the independent variablesx, many constrained optimization methods involve computations withZ(x), a matrix whose columns form a basis for the null space ofA ^T(x). WhenA is evaluated at a given point, it is well known that a suitableZ (satisfyingA ^T Z = 0) can be obtained from standard matrix factorizations. However, Coleman and Sorensen have recently shown that standard orthogonal factorization methods may produce orthogonal bases that do not vary continuously withx; they also suggest several techniques for adapting these schemes so as to ensure continuity ofZ in the neighborhood of a given point.This paper is an extension of an earlier note that defines the procedure for computingZ. Here, we first describe howZ can be obtained byupdating an explicit QR factorization with Householder transformations. The properties of this representation ofZ with respect to perturbations inA are discussed, including explicit bounds on the change inZ. We then introduceregularized Householder transformations, and show that their use implies continuity of the full matrixQ. The convergence ofZ andQ under appropriate assumptions is then proved. Finally, we indicate why the chosen form ofZ is convenient in certain methods for nonlinearly constrained optimization.The research of the Stanford authors was supported by the U.S. Department of Energy Contract DE-AM03-76SF00326, PA No. DE-AT03-76ER72018; the National Science Foundation Grants MCS-7926009 and ECS-8312142; the Office of Naval Research Contract N00014-75-C-0267; and the U.S. Army Research Office Contract DAAG29-84-K-0156.The research of G.W. Stewart was supported by the Air Force Office of Scientific Research Contract AFOSR-82-0078.     

Symmetric block bases of sequences with large average growth

We show that if 0<ε≦1, 1≦p<2 andx ₁, …,x _n is a sequence of unit vectors in a normed spaceX such thatE ‖∑ _l ⁿ ε_i x _l‖≧n ^1/p, then one can find a block basisy ₁, …,y _m ofx ₁, …,x _n which is (1+ε)-symmetric and has cardinality at leastγn ^2/p-1(logn)⁻¹, where γ depends on ε only. Two examples are given which show that this bound is close to being best possible. The first is a sequencex ₁, …,x _n satisfying the above conditions with no 2-symmetric block basis of cardinality exceeding 2n ^2/p-1. This sequence is not linearly independent. The second example is a sequence which satisfies a lowerp-estimate but which has no 2-symmetric block basis of cardinality exceedingCn ^2/p-1(logn)^4/3, whereC is an absolute constant. This applies when 1≦p≦3/2. Finally, we obtain improvements of the lower bound when the spaceX containing the sequence satisfies certain type-condition. These results extend results of Amir and Milman in [1] and [2]. We include an appendix giving a simple counterexample to a question about norm-attaining operators.     

Nonlinear evolution equations in Banach spaces

The evolution problem 0∈du/dt+A(t)u(t),u(s)=x, where theA(t) are nonlinear operators acting in a Banach space, is studied. Evolution operators are constructed from theA(t) under various assumptions. Basic properties of these evolution operators are established and their relationship to the evolution equation is determined. The results obtained extend several known existence theorems and provide generalized solutions of the evolution equation in more general cases. Sponsored by the United States Army under Contract No. DA-31-124-ARO-D-462. and in part by the Office of Naval Research under Contract N000-14-69-A-0200-4022. Reproduction in whole or in part is permitted for any purpose of the United States Government. This research was partially supported by the NSF Grant #GP-18127.