Thesis (Ph. D.)--University of Chicago, 1918. / "Reprinted from Dickson's History of the Theory of Numbers, Vol. III, Ch. VI. The Carnegie Institution of Washington." Includes bibliographical references and index.

Thesis (Ph.D.)--University of Chicago, 1918. / "Reprinted from Dickson's History of the theory of numbers, vol. III, ch. VI. The Carnegie Institution of Washington."

Thesis (Ph. D.)--University of Chicago, 1918. / "Reprinted from Dickson's History of the Theory of Numbers, Vol. III, Ch. VI. The Carnegie Institution of Washington." Includes bibliographical references and index. Also available on the Internet.

We study sums of squares formulae from the perspective of normed bilinear maps and their Hopf constructions. We begin with the geometric properties of quadratic forms between euclidean spheres. Let F: Sm → Sn be a quadratic form. For every point q in the image, the inverse image F⁻¹ (q) is the intersection of Sm with a linear subspace wq, whose dimension can be determined easily. In fact, for every k ≤ m+1 with nonempty Yk = {q ∈ Sn: dim Wq = k}, the restriction F⁻¹ (Yk) → Yk is a great (k-1) - sphere bundle. The quadratic form F is the Hopf construction of a normed bilinear map if and only if it admits a pair of "poles" ±p such that dim Wp + dim W₋p = m+1. In this case, the inverse images of points on a "meridian", save possibly the poles, are mutually isoclinic. Furthermore, the collection of all poles forms a great sphere of relatively low dimension. We also prove that the classical Hopf fibrations are the only nonconstant quadratic forms which are harmonic morphisms in the sense that the composite with every real valued harmonic function is again harmonic. Hidden in a quadratic form F: Sm → Sn are nonsingular bilinear maps Rk x Rm-k⁺¹ → Rn, one for each point in the image, all representing the homotopy class of F, which lies in Im J. Moreover, every hidden nonsingular bilinear map can be homotoped to a normed bilinear map. The existence of one sums of squares formula, therefore, anticipates others which cannot be obtained simply by setting some of the indeterminates to zero. These geometric and topological properties of quadratic forms are then used, together with homotopy theory results in the literature, to deduce that certain sums of squares formulae cannot exist, notably of types [12,12,20] and [16,16,24]. We also prove that there is no nonconstant quadratic form S²⁵ → S²³. Sums of squares formulae with integer coefficients are equivalent to "intercalate matrices of colors with appropriate signs". This combinatorial nature enables us to establish a stronger nonexistence result: no sums of squares formula of type [16,16, 28] can exist if only integer coefficients are permitted. We also classify integral [10,10,16] formulae, and show that they all represent ±2Ʋ∈ π [s over 3]. With the aid of the KO theory of real projective spaces, we determine, for given δ ≤ 5 and s, the greatest possible r for which there exists an [r,s,s+δ] formula. An explicit solution of the classical Hurwitz-Radon matrix equations is also recorded. / Science, Faculty of / Mathematics, Department of / Graduate

Many problems in economics, statistics and numerical analysis can be formulated as the optimization of a convex quadratic function over a polyhedral set. A polynomial algorithm for solving convex quadratic programming problems was first developed by Kozlov at al. (1979). Tardos (1986) was the first to present a polynomial algorithm for solving linear programming problems in which the number of arithmetic steps depends only on the size of the numbers in the constraint matrix and is independent of the size of the numbers in the right hand side and the cost coefficients. In the first part of the thesis we extended Tardos' results to strictly convex quadratic programming of the form max {cTx-½xTDx : Ax ≤ b, x ≥0} with D being symmetric positive definite matrix. In our algorithm the number of arithmetic steps is independent of c and b but depends on the size of the entries of the matrices A and D. Another part of the thesis is concerned with proximity and sensitivity of integer and mixed-integer quadratic programs. We have shown that for any optimal solution z̅ for a given separable quadratic integer programming problem there exist an optimal solution x̅ for its continuous relaxation such that / z̅ - x̅ / ∞≤n∆(A) where n is the number of variables and ∆(A) is the largest absolute sub-determinant of the integer constraint matrix A . We have further shown that for any feasible solution z, which is not optimal for the separable quadratic integer programming problem, there exists a feasible solution z̅ having greater objective function value and with / z - z̅ / ∞≤n∆(A). Under some additional assumptions the distance between a pair of optimal solutions to the integer quadratic programming problem with right hand side vectors b and b', respectively, depends linearly on / b — b' / ₁. The extension to the mixed-integer nonseparable quadratic case is also given. Some sensitivity analysis results for nonlinear integer programming problems are given. We assume that the nonlinear 0 — 1 problem was solved by implicit enumeration and that some small changes have been made in the right hand side or objective function coefficients. We then established what additional information to keep in the implicit enumeration tree, when solving the original problem, in order to provide us with bounds on the optimal value of a perturbed problem. Also, suppose that after solving the original problem to optimality the problem was enlarged by introducing a new 0 — 1 variable, say xn+1. We determined a lower bound on the added objective function coefficients for which the new integer variable xn+1 remains at zero level in the optimal solution for the modified integer nonlinear program. We discuss the extensions to the mixed-integer case as well as to the case when integer variables are not restricted to be 0 or 1. The computational results for an example with quadratic objective function, linear constraints and 0—1 variables are provided. Finally, we have shown how to replace the objective function of a quadratic program with 0—1 variables ( by an integer objective function whose size is polynomially bounded by the number of variables) without changing the set of optimal solutions. This was done by making use of the algorithm given by Frank and Tardos (1985) which in turn uses the simultaneous approximation algorithm of Lenstra, Lenstra and Lovász (1982). / Business, Sauder School of / Graduate

The research addresses the problem of maximizing a zero-one quadratic function. The report falls into three main sections. The first section uses results from Hammer [12] and Picard and Ratliff [23] to develop a new test for fixing the value of a variable in some solution and to provide a means for calculating a new upper bound on the maximum of the function. In addition the convergence of the method of calculation for the bounds is explored in an investigation of its sharpness. The second section proposes a branch and bound algorithm that uses the ideas of the first along with a heuristic solution procedure. It is shown that one advantage of this is that it may now be possible to identify how successful this algorithm will be in finding the maximum of a specified problem. The third section gives a basis for a new heuristic solution procedure. The method defines a concept of gradient which enables a simple steepest ascent technique to be used. It is shown that in general this will find a local maximum of the function. A further procedure to help distinguish between local and global maxima is also given. / Business, Sauder School of / Graduate

No description available.

No description available.

We consider the convex parametric quadratic programming problem when the end of the parametric interval is caused by a multiplicity of possibilities ("ties"). In such cases, there is no clear way for the proper active set to be determined for the parametric analysis to continue. In this thesis, we show that the proper active set may be determined in general by solving a certain non-parametric quadratic programming problem. We simplify the parametric quadratic programming problem with a parameter both in the linear part of the objective function and in the right-hand side of the constraints to a quadratic programming without a parameter. We break the analysis into three parts. We first study the parametric quadratic programming problem with a parameter only in the linear part of the objective function, and then a parameter only in the right-hand side of the constraints. Each of these special cases is transformed into a quadratic programming problem having no parameters. A similar approach is then applied to the parametric quadratic programming problem having a parameter both in the linear part of the objective function and in the right-hand side of the constraints.

The purpose of this thesis is to investigate the properties of ideals in quadratic number fields, A field F is said to be an algebraic number field if F is a finite extension of R, the field of rational numbers. A field F is said to be a quadratic number field if F is an extension of degree 2 over R. The set 1 of integers of R will be called the rational integers.