Convex programs with an additional reverse convex constraint

A method is presented for solving a class of global optimization problems of the form (P): minimizef(x), subject toxD,g(x)0, whereD is a closed convex subset ofR ⁿ andf,g are convex finite functionsR ⁿ . Under suitable stability hypotheses, it is shown that a feasible point is optimal if and only if 0=max{g(x):xD,f(x)f( )}. On the basis of this optimality criterion, the problem is reduced to a sequence of subproblemsQ _k ,k=1, 2, ..., each of which consists in maximizing the convex functiong(x) over some polyhedronS _k . The method is similar to the outer approximation method for maximizing a convex function over a compact convex set.     

Ein konvergentes Iterationsverfahren zur Bestimmung der Nullstellen eines Polynoms

Summary In order to determine the roots of a polynomialp, a sequence of numbers {x _k} is constructed such that the associated sequence {|p(x _k)|} decreases monotonically. To determine a new iteration pointx _k+1 such that |p(x _k+1)|<-|p(x _k)| ( is a positive real constant, <1, depending only on the degree ofp), we determine a circleK aroundx _k which contains no root ofp and compute the values ofp atN points which are distributed equally on the circumference ofK (N again depends only on the degree ofp); at least one of theN points is shown to satisfy the given condition. Computing the function values by means of Fourier synthesis according to Cooley-Tukey [2] and combining our iteration step with the normal step of the method of Nickel [1], we obtain a numerically safe and fast algorithm for determining the roots of arbitrary polynomials.     

The reverse spelling of an FPrt-universal word in two letters

ForX a set the expression Prt(X) denotes the composition monoid of all functionsf X ×X. Fork a positive integer the letterk denotes also the set of all nonnegative integers less thank. Whenk > 1 the expression r_k denotes the connected injective element {<i, i + 1>i k – 1} in Prt (k). We show for every word w=w(x,y) in a two-letter alphabet that if the equation w(x, y)=r_k has a solution =y) ²Prt(k) then ¯w(x,y)=r_k also has a solution in²Prt(k), where ¯w is the word obtained by spelling the wordw backwards. It is a consequence of this theorem that if for every finite setX and for everyf Prt(X) the equation w(x,y)=f has a solution in²Prt(X) then for every suchX andf the equation ¯w(x, y)=f has a solution in²Prt(X).Presented by J. Mycielski.     

Full ideals of polynomial rings

An idealI of the ringK[x ₁, ...,x _n ] of polynomials over a fieldK inn indeterminates is a full ideal ifI is closed under substitution,f I,g ₁...g_n K[x ₁, ...,x _n ] implyf(g ₁, ...,g _n ) I. In this paper we continue the investigation of full ideals ofK[x ₁, ...,x _n ]. In particular we determine several classes of full ideals ofK[x, y] (K a finite field) and investigate properties of these classes.The first author gratefully acknowledges support from theDeutsche Forschungsgemeinschaft     

A note on certain functional determinants

Summary We consider the problem when a scalar function ofn variables can be represented in the form of a determinant det(f _i (x _j )), the so-called Casorati determinant off ₁,f ₂,,f _n . The result is applied to the solution of some functional equations with unknown functionsH of two variables that involve determinants det(H(x _i ,x _j )).     

On disjointly representable sets

A system of setsE ₁,E ₂, ...,E _k ⊂X is said to be disjointly representable if there existx ₁,x ₂, ...,x _k teX such thatx _i teE _j ⇔i=j. Letf(r, k) denote the maximal size of anr-uniform set-system containing nok disjointly representable members. In the first section the exact value off(r, 3) is determined and (asymptotically sharp) bounds onf(r, k),k>3 are established. The last two sections contain some generalizations, in particular we prove an analogue of Sauer’ theorem [16] for uniform set-systems. Dedicated to Paul Erdős on his seventieth birthday     

Über allgemeine Hyperflächenschnitte einer algebraischen Varietät

LetV/k be an irreducible algebraic variety over a fieldk in an affinen-space andF _u a generic hypersurface defined byu ₁ f ₁ (X)+...+u r f _r(X)=0, whereu ₁...,u _r are indeterminates overk andf ₁(X), ...,f _r(X) are polynomials ink[X ₁, ...,X _n]. Let (E) be a property which an arbitrary algebraic variety could have, e. g. irreducibility, normality (local or global), ... Then it will be studied under which conditions off ₁(X), ...,f _r(X) (E) may be transfered fromV/k toVF _u /k(u) (and conversely).     

Generalized derivations with Engel condition on multilinear polynomials

Let R be a prime ring with extended centroid C, δ a nonzero generalized derivation of R, f(x ₁, ..., x _n ) a nonzero multilinear polynomial over C, I a nonzero right ideal of R and k ≥ a fixed integer. If [δ(f(r ₁, ..., r _n )), f(r ₁, ..., r _n )] _k = 0, for all r ₁, ..., r _n ∈ I, then either δ(x) = ax, with (a-γ)I = 0 and a suitable γ ∈ C or there exists an idempotent element e ∈ soc(RC) such that IC = eRC and one of the following holds (1) if char(R) = 0 then f(x ₁, ..., x _n ) is central valued in eRCe (2) if char(R) = p > 0 then is central valued in eRCe, for a suitable s ≥ 0, unless when char(R) = 2 and eRCe satisfies the standard identity s ₄ (3) δ(x) = ax−xb, where (a+b+α)e = 0, for α ∈ C, and f(x ₁, ..., x _n )² is central valued in eRCe.     

On theL 1 exact penalty function with locally lipschitz functions

In this paper, we discuss the following inequality constrained optimization problem (P) minf(x) subject tog(x)0,g(x)=(g ₁(x), ...,g _r (x)) , wheref(x),g _j (x)(j=1, ...,r) are locally Lipschitz functions. TheL ₁ exact penalty function of the problem (P) is (PC) minf(x)+cp(x) subject tox R ⁿ , wherep(x)=max {0,g ₁(x), ...,g _r (x)},c>0. We will discuss the relationships between (P) and (PC). In particular, we will prove that under some (mild) conditions a local minimum of (PC) is also a local minimum of (P).     

An Erdös-Ko-Rado theorem for the subcubes of a cube

LetP be that partially ordered set whose elements are vectors x=(x ₁, ...,x _n ) withx _i ε {0, ...,k} (i=1, ...,n) and in which the order is given byx≦y iffx _i =y _i orx _i =0 for alli. LetN _i (P)={x εP : |{j:x _j ≠ 0}|=i}. A subsetF ofP is called an Erdös-Ko-Rado family, if for allx, y εF it holdsx ≮y, x ≯ y, and there exists az εN ₁(P) such thatz≦x andz≦y. Let ? be the set of all vectorsf=(f ₀, ...,f _n ) for which there is an Erdös-Ko-Rado familyF inP such that |N _i (P) ∩F|=f _i (i=0, ...,n) and let 〈?〉 be its convex closure in the (n+1)-dimensional Euclidean space. It is proved that fork≧2 (0, ..., 0) and \(\left( {0,...,0,\overbrace {i - component}^{\left( {\begin{array}{*{20}c} {n - 1} \\ {i - 1} \\ \end{array} } \right)}k^{i - 1} ,0,...,0} \right)\) (i=1, ...,n) are the vertices of 〈?〉.     

Kernel-type density and failure rate estimation for associated sequences

Let {X _n ,n1} be a strictly stationary sequence of associated random variables defined on a probability space (,B, P) with probability density functionf(x) and failure rate functionr(x) forX ₁. Letf _n (x) be a kerneltype estimator off(x) based onX ₁,...,X _n . Properties off _n (x) are studied. Pointwise strong consistency and strong uniform consistency are established under a certain set of conditions. An estimatorr _n (x) ofr(x) based onf _n (x) andF _n (x), the empirical survival function, is proposed. The estimatorr _n (x) is shown to be pointwise strongly consistent as well as uniformly strongly consistent over some sets.     

A generalized inverse ∈-algorithm for constructing intersection projection matrices,with applications

Givenk linear manifolds ₁, ..., _k and corresponding perpendicular projection matricesP ₁, ...,P _k , a closed formula is derived for the perpendicular projection matrix with range. The derivation uses results taken from the theory of generalized inverses together with an application ofWynn's -Algorithm to a convergent sequence of matrices. A variant of this formula is then used in solving arbitrary complex linear systems by iteration and in computing generalized inverses; the latter application provides a solution to least squares linear regression problems.A preliminary version of this paper, MRC Technical Summary Report 604, was sponsored by the Mathematics Research Center, United States Army, Madison, Wisconsin, under Contract No.: DA-11-022-ORD-20$9.     

The kernel,the bargaining set and the reduced game

We present an example showing that forxK(N, v, B) the section ofK(N, v, B) atx| _{N-B k} may be a proper subset ofK(B _k, v_x, X_k). Further we prove that under appropriate conditions these two sets coincide. For the bargaining set we prove a similar result.We are grateful to an anonymous referee for valuable comments.     

Fractional dimension of partial orders

Given a partially ordered setP=(X, ), a collection of linear extensions {L ₁,L ₂,...,L _r } is arealizer if, for every incomparable pair of elementsx andy, we havex<y in someL _i (andy<x in someL _j ). For a positive integerk, we call a multiset {L ₁,L ₂,...,L _t } ak-fold realizer if for every incomparable pairx andy we havex<y in at leastk of theL _i 's. Lett(k) be the size of a smallestk-fold realizer ofP; we define thefractional dimension ofP, denoted fdim(P), to be the limit oft(k)/k ask. We prove various results about the fractional dimension of a poset.Research supported in part by the Office of Naval Research.     

Construction of polynomials that are orthogonal with respect to a discrete bilinear form

We describe a new algorithm for the computation of recursion coefficients of monic polynomials {p _j } _j ^=0/n that are orthogonal with respect to a discrete bilinear form (f, g) := _k ^=1/m f(x _k )g(x _k )w _k ,m n, with real distinct nodesx _k and real nonvanishing weightsw _k . The algorithm proceeds by applying a judiciously chosen sequence of real or complex Givens rotations to the diagonal matrix diag[x ₁,x ₂, ...,x _m ] in order to determine an orthogonally similar complex symmetric tridiagonal matrixT, from whose entries the recursion coefficients of the monic orthogonal polynomials can easily be computed. Fourier coefficients of given functions can conveniently be computed simultaneously with the recursion coefficients. Our scheme generalizes methods by Elhay et al. [6] based on Givens rotations for updating and downdating polynomials that are orthogonal with respect to a discrete inner product. Our scheme also extends an algorithm for the solution of an inverse eigenvalue problem for real symmetric tridiagonal matrices proposed by Rutishauser [20], Gragg and Harrod [17], and a method for generating orthogonal polynomials based theoron [18]. Computed examples that compare our algorithm with the Stieltjes procedure show the former to generally yield higher accuracy except whenn m. Ifn is sufficiently much smaller thanm, then both the Stieltjes procedure and our algorithm yield accurate results.Research supported in part by the Center for Research on Parallel Computation at Rice University and NSF Grant No. DMS-9002884.     

Global optimization and stochastic differential equations

Let ⁿ be then-dimensional real Euclidean space,x=(x ₁,x ₂, ...,x _n)^{T n} , and letf: ⁿ R be a real-valued function. We consider the problem of finding the global minimizers off. A new method to compute numerically the global minimizers by following the paths of a system of stochastic differential equations is proposed. This method is motivated by quantum mechanics. Some numerical experience on a set of test problems is presented. The method compares favorably with other existing methods for global optimization.This research has been supported by the European Research Office of the US Army under Contract No. DAJA-37-81-C-0740.The third author gratefully acknowledges Prof. A. Rinnooy Kan for bringing to his attention Ref. 4.     

Ordering distributions by scaled order statistics

Motivated by applications in reliability theory, we define a preordering (X ₁, ...,X _n) (Y ₁ ...,Y _n) of nonnegative random vectors by requiring thek-th order statistic ofa ₁ X ₁,..., a _n X _n to be stochastically smaller than thek-th order statistic ofa ₁ Y ₁, ...,a _n Y _n for all choices ofa _i >0,i=1, 2, ...,n. We identify a class of functionsM _{k, n} such that if and only ifE(X)E(Y) for allM _k,n. Some preservation results related to the ordering are obtained. Some applications of the results in reliability theory are given.Supported by the Air Force Office of Scientific Research, U.S.A.F., under Grant AFOSR-84-0205.     

On the numerical evaluation of singular integrals

Product-integration rules of the form _–1 ¹ k(x)f(x)dx _i ⁼¹ⁿ w _ni f(x _ni ) are studied, with the points {w _ni } chosen to be the zeros of certain orthogonal polynomials, and the weights {w _ni } chosen to make the rule exact iff is any polynomial of degree less thann. If, in particular, the points are the Chebyshev points, and ifk L _p [–1, 1] for somep>1, then it is shown that the rule converges to the exact result for all continuous functionsf. With this choice of points, the practical application of the rule is shown to be straightforward in many cases, and to yield satisfactory rates of convergence. The casek(x)=|–x|, >–1, is studied in detail. Results of a similar, but weaker, kind are also obtained for other choices of the points {x _ni }.     

Extremal property of some surfaces in n-dimensional Euclidean space

A surface Γ=(f ₁(X₁,..., x_m),...,f _n(x₁,..., x_m)) is said to be extremal if for almost all points of Γ the inequality $$\parallel a_1 f_1 (x_1 , \ldots ,x_m ) + \ldots + a_n f_n (x_1 , \ldots ,x_m )\parallel< H^{ - n - \varepsilon } ,$$ , where H=max(¦a _i¦) (i=1, 2, ..., n), has only a finite number of solutions in the integersa ₁, ...,a _n. In this note we prove, for a specific relationship between m and n and a functional condition on the functionsf ₁, ...,f _n, the extremality of a class of surfaces in n-dimensional Euclidean space.     

Error estimates for a class of quadrature formulae

The problem considered is that of estimating the error of a class of quadrature formulae for _–1 ¹ w _r (x)f(x)dx, (w _r (x) being a positive weight-function), where only values off(x) in (–1,1) and off(x) and its derivatives at the end-points of the interval are considered.