Quadratically constrained quadratic programming: Some applications and a method for solution

The problem (QPQR) considered here is: minimizeQ ₁ (x) subject toQ _i (x) 0,i M ₁ {2,...,m},x P R ⁿ, whereQ _i (x), i M {1} M ₁ are quadratic forms with positive semi-definite matrices, andP a compact nonempty polyhedron of Rⁿ. Applications of (QPQR) and a new method to solve it are presented.Letu S={u R ^m;u 0, u _i= l}be fixed;then the problem:iM minimize u _iQ_i (x (u)) overP, always has an optimal solutionx (u), which is either feasible, iM i.e. u C₁ {u S;Q _i (x (u)) 0,i M ₁} or unfeasible, i.e. there exists ani M ₁ withu C {u S; Q_i(x(u)) 0}.Let us defineC _i C_i S _i withS _i {u S; u _i=0}, i M. A constructive method is used to prove that C _i is not empty and thatx (û) withiM û C _i characterizes an optimal solution to (QPQR). Quite attractive numerical results have been reached with this method.

---

Zusammenfassung Die vorliegende Arbeit befaßt sich mit Anwendungen und einer neuen Lösungsmethode der folgenden Aufgabe (QPQR): man minimiere eine konvexe quadratische ZielfunktionQ _i (x) unter Berücksichtigung konvexer quadratischer RestriktionenQ _i (x) 0, iM ₁ {2,...,m}, und/oder linearer Restriktionen.·Für ein festesu S {u R ^m;u 0, u _i=1},M {1} M₁ besitzt das Problem:iM minimiere die konvexe quadratische Zielfunktion u _i Q_i (x (u)) über dem durch die lineareniM Restriktionen von (QPQR) erzeugten, kompakten und nicht leeren PolyederP R ⁿ, immer eine Optimallösungx (u), die entweder zulässig ist: u C₁ {u S;Q ₁ (x (u)) 0,i M ₁} oder unzulässig ist, d.h. es existiert eini M ₁ mitu C_i {u S;Q _i (x(u))0}.Es seien folgende MengenC _i C_i S _i definiert, mitS _i {u S;u _i=0}, i M. Es wird konstruktiv bewiesen, daß C _i 0 undx (û) mitû C _i eine Optimallösung voniM iM (QPQR) ist; damit ergibt sich eine Methode zur Lösung von (QPQR), die sich als sehr effizient erwiesen hat. Ein einfaches Beispiel ist angegeben, mit dem alle Schritte des Algorithmus und dessen Arbeitsweise graphisch dargestellt werden können.

---

---

An earlier version of this paper was written during the author's stay at the Institute for Operations Research, Swiss Federal Institute of Technology, Zürich.     

On the complete solution of ∈y″=y 3

In Ref. 1, the author claimed that the problem y=y ³ is soluble only for a certain range of the parameter . An analytic approach, as adopted in the following contribution, reveals that a unique solution exists for any positive value of . The solution is given in closed form by means of Jacobian elliptic functions, which can be numerically computed very efficiently. In the limit 0+, the solutions exhibit boundary-layer behavior at both endpoints. An easily interpretable approximate solution for small is obtained using a three-variable approach.     

On signpost systems and connected graphs

By a signpost system we mean an ordered pair (W, P), where W is a finite nonempty set, P W × W × W and the following statements hold: if (u, v, w) P, then (v, u, u) P and (v, u, w) P, for all u, v, w W; if u v; then there exists r W such that (u, r, v) P, for all u, v W. We say that a signpost system (W, P) is smooth if the folowing statement holds for all u, v, x, y, z W: if (u, v, x), (u, v, z), (x, y, z) P, then (u, v, y) P. We say thay a signpost system (W, P) is simple if the following statement holds for all u, v, x, y W: if (u, v, x), (x, y, v) P, then (u, v, y), (x, y, u) P.By the underlying graph of a signpost system (W, P) we mean the graph G with V(G) = W and such that the following statement holds for all distinct u, v W: u and v are adjacent in G if and only if (u, v, v) P. The main result of this paper is as follows: If G is a graph, then the following three statements are equivalent: G is connected; G is the underlying graph of a simple smooth signpost system; G is the underlying graph of a smooth signpost system.Research was supported by Grant Agency of the Czech Republic, grant No. 401/01/0218.     

A generalization of a theorem of M. Riesz to the case of functions of several variables

The following theorem was proved by M. Riesz: Iff(x) L(–,),f(x) 0 and the conjugate functionf (x) is also integrable on [-, ], thenf(x) L log⁺L. The analog of this theorem for functions of several variables is established.Translated from Matematicheskie Zametki, Vol. 4, No. 3, pp. 269–280, November, 1968.     

Kite-freeP- andQ-polynomial schemes

LetY = (X, {R _i } _oid) denote aP-polynomial association scheme. By a kite of lengthi (2 i d) inY, we mean a 4-tuplexyzu (x, y, z, u X) such that(x, y) R ₁,(x, z) R ₁,(y, z) R ₁,(u, y) R _i–1,(u, z) R _i–1,(u, x) R _i. Our main result in this paper is the following.     

Reconstructing dimensions of intersections of convex sets

Denoting by dimA the dimension of the affine hull of the setA, we prove that if {K _i:i T} and {K _i ^j :i T} are two finite families of convex sets inR ⁿ and if dim {K _i :i S} = dim {K _i ^j :i S}for eachS T such that|S| n + 1 then dim {K _i :i T} = dim {K _i : {i T}}.     

Ergodic properties of Poisson processes with almost periodic intensity

Summary We discuss in this paper a non-homogeneous Poisson process A driven by an almost periodic intensity function. We give the stationary version A ^* and the Palm version A ⁰ corresponding to A ^*. Let (T _i ,i) be the inter-point distance sequence in A and (T _i ⁰ ,i) in A ⁰. We prove that forj, the sequence (T _i+j,i) converges in distribution to (T _i ⁰ ,i). If the intensity function is periodic then the convergence is in variation.     

The Adjoints of Dilation Operators on H-Cones

If S is an H-cone and P:SS is a localizable dilation operator on S (i.e., P is additive increasing, contractive, continuous in order from below and s(Ps+t–Pt+Pf)S, s,tS,f(S–S)₊), then it is proved that its adjoint P ^*:S ^*S ^* (i.e., P ^*=P) is also a localizable dilation operator. This is an improvement of a result obtained by G. Mokobodzki in the frame of excessive functions.     

Equazioni ellittiche in forma di divergenza con 2∘ membro misura su domini non limitati

Summary Let a regular open set of R n, a measure with compact support and L a second order elliptic operator in divergence form. If L is coercive we prove a theorem of existence and uniqueness for the solution of Lu=, uH ₀ ¹+H₀ ^1,p()where p is the conjugate of p[n, ].     

Partial applicability of Moser's method to nonlinear elliptic systems

We consider nonlinear elliptic systems of divergent-type second-order partial differential equations with solutionsu W _p ¹ . It is proved thatDu L _q with someq (p; +) and it is explicitly shown howq depends on the ellipticity modulus of the system. Some conditions on the ellipticity modulus are obtained under which the solutions satisfy the Hölder conditions and the Liouville theorem holds.Translated fromMatematicheskie Zametki, Vol. 58, No. 4, pp. 547–557, October, 1995.     

On unconditional bases in certain Banach function spaces

Let X be a Banach space, L ([0,1])XL ¹([0,1]), with an unconditional basis. By the well-known stability property in X, there exists a unconditional basis {f _n} _m=1 , where f _n in C([0,1]), nN. In this paper, we introduce the notion that X ^*has the singularity property of X ^*at a point t ₀[0,1]. It is proved that if X ^*has the singularity property at a point t ₀ [0,1], then there exists no orthonormal, fundamental system in C([0,1]) which forms an unconditional basis in X.     

On semiregular conditional distributions

Let (,A,P) denote some probability space and some sub--algebra ofA. It is shown that there exists a semiregular versionQ (A),A, , of the conditional distributionP(A|), AA, i.e., Q (A), (AA fixed) is andAQ (A),AA ( fixed), is a probability charge satisfyingQ (N)=0, , for allP-zero setsN, if and only ifL ₁(,P|) has a lifting, which exists for any sub--algebra ofA ifL ₁(,A P) is separable. Separability ofL ₁(,A,P) implies also the existence of a strongly semiregular versionQ (A),A, , ofP(A|), A , i.e., Q (A), (AA fixed), is -measurable andAQ (A),A ( fixed), is a probability charge. Furthermore,P can be written as P ₁+(1–)P ₂, 01, whereP ₁ are probability measures onA such thatP ₁(A|),AA, has a semiregular version vanishing for anyP-zero setN andP ₂ is singular with respect to any probability measure onA of the type ofP ₁. In the case 0<<1 the probability measuresP _j ,j=1, 2, are uniquely determined. The decomposition can be carried over to the case, where the additional condition thatQ (N)=0 for all and anyP-zero setN is valid, is omitted respectively semiregularity is replaced by (i) strong semiregularity, or (ii) classical regularity. In the last mentioned case (ii) the decomposition is multiplicative.     

Algorithms for proportional matrices in reals and integers

LetR be the set of nonnegative matrices whose row and column sums fall between specific limits and whose entries sum to some fixedh > 0. Closely related axiomatic approaches have been developed to ascribe meanings to the statements: the real matrixf R and the integer matrixa R are proportional to a given matrixp 0.These approaches are described, conditions under which proportional solutions exist are characterized, and algorithms are given for finding proportional solutions in each case.     

Convergence des solutions formelles de certaines équations fonctionnelles

Résumé Soitq un nombre algébrique de module 1, qui ne soit pas une racine de l'unité, etP [X, Y ₀,Y ₁] un polynôme non nul. Dans cet article, nous montrons que toute solution de l'équation fonctionnelleP(z, (z), (qz))=0, qui est une série formelle (z) dansQ[[z]], a un rayon de convergence non nul.

---

Summary Letq Q be an algebraic number of modulus one that is not a root of unity. LetP Q[X, Y ₀,Y ₁] be a non zero polynomial. In this paper, we show that every formal power series,(z) Q[[z]], solution of the functional equationP(z), (z), (qz)) = 0 has a non zero radius of convergence.

     

A general minimax theorem

This paper is concerned with minimax theorems for two-person zero-sum games (X, Y, f) with payofff and as main result the minimax equality inf supf (x, y)=sup inff (x, y) is obtained under a new condition onf. This condition is based on the concept of averaging functions, i.e. real-valued functions defined on some subset of the plane with min {x, y}< (x, y)x, y} forx y and (x, x)=x. After establishing some simple facts on averaging functions, we prove a minimax theorem for payoffsf with the following property: Forf there exist averaging functions and such that for any x₁, x₂ X, > 0 there exists x₀ X withf (x₀, y) > f (x₁,y),f (x₂,y))– for ally Y, and for any y₁, y₂ Y, > 0 there exists y₀ Y withf (x, y₀) (f (x, y₁),f (x, y₂))+. This result contains as a special case the Fan-König result for concave-convex-like payoffs in a general version, when we take linear averaging with (x, y)=x+(1–)y, (x, y)=x+(1–)y, 0 <, < 1.Then a class of hide-and-seek games is introduced, and we derive conditions for applying the minimax result of this paper.

---

Zusammenfassung In dieser Arbeit werden Minimaxsätze für Zwei-Personen-Nullsummenspiele (X, Y,f) mit Auszahlungsfunktionf behandelt, und als Hauptresultat wird die Gültigkeit der Minimaxgleichung inf supf (x, y)=sup inff (x, y) unter einer neuen Bedingung an f nachgewiesen. Diese Bedingung basiert auf dem Konzept mittelnder Funktionen, d.h. reellwertiger Funktionen, welche auf einer Teilmenge der Ebene definiert sind und dort der Eigenschaft min {x, y} < < (x, y)x, y} fürx y, (x, x)=x, genügen. Nach der Herleitung einiger einfacher Aussagen über mittelnde Funktionen beweisen wir einen Minimaxsatz für Auszahlungsfunktionenf mit folgender Eigenschaft: Zuf existieren mittelnde Funktionen und, so daß zu beliebigen x₁, x₂ X, > 0 mindestens ein x₀ X existiert mitf (x₀,y) (f (x ₁,y),f (x₂,y)) – für alley Y und zu beliebigen y₁, y₂ Y, > 0 mindestens ein y₀ Y existiert mitf (x, y₀) (f (x, y₁),f (x, y ₂))+ für allex X. Dieses Resultat enthält als Spezialfall den Fan-König'schen Minimaxsatz für konkav-konvev-ähnliche Auszahlungsfunktionen in einer allgemeinen Version, wenn wir lineare Mittelung mit (x, y)=x+(1–)y, (x, y)= x+(1–)y, 0 <, < 1, betrachten.Es wird eine Klasse von Suchspielen eingeführt, welche mit dem vorstehenden Resultat behandelt werden können.

     

Mittelwert der Eulerschen φ-Funktion und des Quadrates der Dirichletschen Teilerfunktion in algebraischen Zahlkörpern

LetK be an algebraic number field, and for every integer K let () andd(), respectively, denote the number of relatively prime residue classes and the number of divisors of the principal ideal (). Asymptotic equalities are proved for the sums () and d ²(), where runs through certain finite sets of integers ofK.     

Large-Deviation Local Theorem for Additive Functionals of a Markov Gaussian Field. I

We prove a local limit theorem (LLT) on Cramer-type large deviations for sums S _V = _t V ( _t ), where _t , t Z , 1, is a Markov Gaussian random field, V Z , and is a bounded Borel function. We get an estimate from below for the variance of S _V and construct two classes of functions , for which the LLT of large deviations holds.     

On functions having Cauchy differences in some prescribed sets

Summary AssumeE is a real topological vector space,F is a real Banach space,K is a discrete subgroup ofF andC is a symmetric, convex and compact subset ofF such thatK (6C) = {0}. If a functionh:E F is continuous at at least one point andh(x + y) – h(x) – h(y) K + C for allx, y E, then there exists a continuous linear functiona:E F such thath(x) – a(x) K + C for everyx E.     

On recurrence

Summary LetT be a non-singular ergodic automorphism of a Lebesgue space (X,L,) and letf: X be a measurable function. We define the notion of recurrence of such a functionf and introduce the recurrence setR(f)={:f– is recurrent}. If , then R()={0}, but in general recurrence sets can be very complicated. We prove various conditions for a number to lie in R(f) and, more generally, forR(f) to be non-empty. The results in this paper have applications to the theory of random walks with stationary increments.     

Downward Sets and their separation and approximation properties

We develop a theory of downward subsets of the space ^I, where I is a finite index set. Downward sets arise as the set of all solutions of a system of inequalities x^I,f_t(x)0 (tT), where T is an arbitrary index set and each f _t (tT) is an increasing function defined on ^I. These sets play an important role in some parts of mathematical economics and game theory. We examine some functions related to a downward set (the distance to this set and the plus-Minkowski gauge of this set, which we introduce here) and study lattices of closed downward sets and of corresponding distance functions. We discuss two kinds of duality for downward sets, based on multiplicative and additive min-type functions, respectively, and corresponding separation properties, and we give some characterizations of best approximations by downward sets. Some links between the multiplicative and additive cases are established.