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.     

A characterization of brownian motion in a lipschitz domain by its killing distributions

Let (Y _t, Q^x) be a strong Markov process in a bounded Lipschitz domainD with continuous paths up to its lifetime , and let (X _t, P^x) be a Brownian motion inD. IfY _– exists in D andQ ^x(Y_– C)=P^x(X_– C) for all Borel subsetsC of D and allx, thenY is a time change ofX.     

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.     

Smoothness of solutions of a nonlinear ode

Smoothness of aC -functionf is measured by (Carleman) sequence {M _k} ₀ ; we sayfC _M [0, 1] if|f ^(k) (t)|CR ^k M _k,k=0, 1, ... withC, R>0. A typical statement proven in this paper isTHEOREM: Let u, b be two C -functions on [0, 1]such that (a) u=u ²+b, (b) |b ^(k) (t)|CR ^k (k!) , >1,k_–.Then |u^(k)(t)|C₁R^k((k–1)!),k_–.The first author acknowledges the hospitality of Mathematical Research Institute of the Ohio State University during his one month visit there in the spring of 1999     

Galerkin methods for parabolic equations with nonlinear boundary conditions

A variety of Galerkin methods are studied for the parabolic equationu _t =(a(x) u),x ⁿ ,t (O,T], subject to the nonlinear boundary conditionu _v =g(x,t,u),x,t (O,T] and the usual initial condition. Optimal order error estimates are derived both inL ² () andH ¹ () norms for all methods treated, including several that produce linear computational procedures.The authors were partially supported by The National Science Foundation during the preparation of this paper.     

Left linear theories — A generalization of module theory

In this paper we introduce left linear theories of exponentN (a set) on the setL as mapsL ×L ^N (l, ) l · L such that for alll L and , L ^N the relation (l · ) =l( · ) holds, where · L ^N is given by ( · )(i) = (i),i N. We assume thatL has a unit, that is an element L ^N withl · =l, for alll L, and · = , for all L ^N . Next, left (resp. right)L-modules andL-M-bimodules and their homomorphisms are defined and lead to categoriesL-Mod, Mod-L, andL-M-Mod. These categories are algebraic categories and their free objects are described explicitly. Finally, Hom(X, Y) andX Y are introduced and their properties are investigated.Herrn Professor Dr. D. Pumplün zum 60. Geburtstag gewidmet     

Induktive Definitionen und Dilatoren

Summary In this paper we give a new and comparatively simple proof of the following theorem by Girard [1]:If x y (x,y) (where the relation is arithmetic and positive in Kleene's ), then there exists a recursive DilatorD such that x ^<y ^{(x, y).The essential feature of our proof is its very direct definition of the dilatorD. Within a certain infinitary cutfree system of inductive logic (which in fact is a modification of Girard's system in [1]) we construct in a uniform way for each ordinal a derivation T of the formula x <y (x, y), and then defineD immediately from the family (T)_On. Especially we set D():=Kleene-Brouwer length of (T).}     

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.     

L p Spectral Independence of Elliptic Operators via Commutator Estimates

Let {T _p:q ₁ p q ₂} be a family of consistent C ₀ semigroups on L ^p(), with q ₁,q ₂ [1,) and open. We show that certain commutator conditions on T _p and on the resolvent of its generator A _p ensure the p independence of the spectrum of A _p for p [q ₁,q ₂.Applications include the case of Petrovskij correct systems with Hölder continuous coefficients, Schrödinger operators, and certain elliptic operators in divergence form with real, but not necessarily symmetric, or complex coefficients.     

Note on angle-preserving mappings

Summary Let (V, K, q) be aq-regular metric vector space over a commutative field with quadratic formq and letA(V, K, q) be the corresponding affine-metric space. A metric collineation ofA(V, K, q) is a product of a translation and a semilinear bijection ( ₁, ₂) (where ₂ AutK) such that, for a K\{0}, we haveq ₁ = ₂ q. For linesA + KB, A + KC whereA, B, C V\{X Vq(X) = 0} we define an angle-measure < _q (A +KB, A +KC) f(B, C)² q(B)^–1 q(C)^–1 wheref is the bilinear form corresponding toq. For a point tripleA, B, C we define < _q ABC < _q (K(A – B),K(C – B)) whenever the right-hand side is defined. Now assume |K| > 5. In order to get minimal conditions for metric collineations we prove: If 0, 4 is an occurring angle-measure and if is a permutation of the point set such that exactly the point triples with measure are mapped to point triples with measure 0, 4, then is already a metric collineation.     

Generalized sequencing problem “Towers of Hanoi”

ForpN certain integer-valued functionsA _p (x), defined forx N {0}, are studied. These functions occur in a functional equation system corresponding to a generalized version of the transportation game Towers of Hanoi and their values may be interpreted as minimum numbers of moves. An explicit representation ofA _p (x) is given and so-called minimum partitions ofx with respect top are determined for allx N. The minimum partitions ofx are of interest concerning the realisation of the minimum number of moves by optimal policies.

---

Zusammenfassung Es werden fürp N gewisse ganzzahlige für allex N {0} erklärte FunktionenA _p (x) untersucht, die bei einer Verallgemeinerung des unter dem Namen Türme zu Hanoi bekannten Transportspiels in einem entsprechenden Funktionalgleichungssystem auftreten und deren Funktionswerte sich als Mindestzugzahlen interpretieren. Es werden fürA _p (x) eine explizite Darstellung und sogenannte Minimalzerlegungen vonx bezüglichp für allex N bestimmt. Die Minimalzerlegungen vonx spielen eine besondere Rolle bei der Angabe von optimalen Strategien zur Realisierung der Mindestzugzahl.

     

Isometries of symmetric operator spaces associated with AFD factors of typeII and symmetric vector-valued spaces

If is a surjective isometry of the separable symmetric operator spaceE(M, ) associated with the approximately finite-dimensional semifinite factorM and if · _E(M,) is not proportional to · _{L 2}, then there exist a unitary operatorUM and a Jordan automorphismJ ofM such that(x)=UJ(x) for allxME(M, ). We characterize also surjective isometries of vector-valued symmetric spacesF((0, 1), E(M, )).Research supported by the Australian Research Council     

On Gauss quadrature formulas with equal weights

Summary It is well known that the Chebyshev weight function (1–x ²)^–1/2 is the only weight function (up to a linear transformation) for which then point Gauss quadrature formula has equal weights for alln. In this paper we describe all weight functions for which thenm point Gauss quadrature formula has equal weights for alln, wherem is fixed.     

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.     

Q-matrices and boundedness of solutions to linear complementarity problems

This paper is concerned with the existence and boundedness of the solutions to the linear complementarity problemw=Mz+q,w0,z0,w ^T z=0, for eachq ⁿ . It has been previously established that, ifM is copositive plus, then the solution set is nonempty and bounded for eachq ⁿ iffM is aQ-matrix. This result is shown to be valid also forL ₂-matrices,P ₀-matrices, nonnegative matrices, andZ-matrices.     

On a classical Nicoletti boundary value problem

We shall derive existence, uniqueness and comparison results for the functional differential equationx(t)=f(t, x), a. e.tI, with classical Nicoletti boundary conditionsx _i(t_i)=y _iX, iA, whereI is a real interval,A is a nonempty set andX is a Banach space.     

On weakly mixing Markov operators and non-singular transformations

Summary Let P be a Markov operator on L (X, , m). Theorem 1: (i) P is weakly mixing (ii) For every fL there is a sequence {n_t} of density 1 such that all w ^*-cluster points of are constants (iii) For every fL there is a {k_j} with w ^*-convergent to a constant. Theorem 2: If P is induced by a non-singular transformation , P is weakly mixing For every A, { ^–n(A)} has a remotely trivial subsequence. The existence of a finite invariant measure is not required in these results.     

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.     

Second-Order Subexponential Sequences and the Asymptotic Behavior of Their De Pril Transform

Suppose that { f(n), n N ₀ } is a sequence of positive real numbers and suppose that the sequence { a(n), n N ₀ } is given by a(0) = 0, and, for n 1, by the convolution equation nf(n) = a* f(n). The resulting sequence is denoted by a(n) = _f (n) and is called the De Pril transform of { f(n), n N ₀ } . In this paper, we consider first- and second-order asymptotic behavior of { _{f (n), n N 0} } for a large class of subexponential sequences { f(n), n N ₀ } . We also discuss some applications.     

Shape-preserving Kolmogorov widths of classes of <Emphasis Type="Italic">s</Emphasis>-monotone integrable functions

Let s ₀ and let ₊ ^s be the set of functions x defined on a finite interval I and such that, for all collections of s + 1 pairwise different points t ₀,..., t _s I, the corresponding divided differences [x; t ₀,...,t _s ] of order s are nonnegative. Let ₊ ^s B _{p +} ^s B _p, 1 p where B _p is a unit ball in the space L _p, and let ₊ ^s L _{q +} ^s L _q, 1 q . For every s 3 and 1 q p , we determine the exact orders of the shape-preserving Kolmogorov widths {x - y} \right\ L_q , $$]]>, where M ⁿ is the collection of all affine linear manifolds M ⁿ in L _q such that dim M ⁿ n and M ⁿ ₊ ^s L _q .Translated from Ukrainskyi Matematychnyi Zhurnal, Vol. 56, No. 7, pp. 901–926, July, 2004.