Density computations for real quadratic units

In order to study the density of the set of positive integers for which the negative Pell equation is solvable in integers, we compute the norm of the fundamental unit in certain well-chosen families of real quadratic orders. A fast algorithm that computes 2-class groups rather than units is used. It is random polynomial-time in as the factorization of is a natural part of the input for the values of we encounter. The data obtained provide convincing numerical evidence for the density heuristics for the negative Pell equation proposed by the second author. In particular, an irrational proportion of the real quadratic fields without discriminantal prime divisors congruent to 3 mod 4 should have a fundamental unit of norm .

     

On quadratic forms of height two and a theorem of Wadsworth

Let and be anisotropic quadratic forms over a field of characteristic not . Their function fields and are said to be equivalent (over ) if and are isotropic. We consider the case where and is divisible by an -fold Pfister form. We determine those forms for which becomes isotropic over if , and provide partial results for . These results imply that if and are equivalent and , then is similar to over . This together with already known results yields that if is of height and degree or , and if , then and are equivalent iff and are isomorphic over .

     

Primal-dual interior point approach for computingl 1-solutions andl ∞-solutions of overdetermined linear systems

This paper concerns solving an overdetermined linear systemA ^T x=b in the leastl ₁-norm orl -norm sense, whereA ^m×n ,m<n. We show that the primal-dual interior point approach for linear programming can be applied, in an effective manner, to linear programming versions of thel ₁ andl -problems. The resulting algorithms are simple to implement and can attain quadratic or superlinear convergence rate. At each iteration, the algorithms must solve a linear system with anm×m positive-definite coefficient matrix of the formADA ^T , whereD is a positive diagonal matrix. The preliminary numerical results indicate that the proposed algorithms offer considerable promise.This research was supported in part by Grants NSF DMS-91-02761 and DOE DE-FG05-91-ER25100.     

Interior-point algorithm for quadratically constrained entropy minimization problems

In this paper, we develop an interior point algorithm for quadratically constrained entropy problems. The algorithm uses a variation of Newton's method to follow a central path trajectory in the interior of the feasible set. The primal-dual gap is made less than a given in at most steps, wheren is the dimension of the problem andm is the number of quadratic inequality constraints.     

Stochastic dominance with nonadditive probabilities

Choquet expected utility which uses capacities (i.e. nonadditive probability measures) in place of-additive probability measures has been introduced to decision making under uncertainty to cope with observed effects of ambiguity aversion like the Ellsberg paradox. In this paper we present necessary and sufficient conditions for stochastic dominance between capacities (i.e. the expected utility with respect to one capacity exceeds that with respect to the other one for a given class of utility functions). One wide class of conditions refers to probability inequalities on certain families of sets. To yield another general class of conditions we present sufficient conditions for the existence of a probability measureP with f dC= f dP for all increasing functionsf whenC is a given capacity. Examples includen-th degree stochastic dominance on the reals and many cases of so-called set dominance. Finally, applications to decision making are given including anticipated utility with unknown distortion function.     

A quadratically convergent O(\sqrt n L)-iteration algorithm for linear programming

Recently, Ye, Tapia and Zhang (1991) demonstrated that Mizuno—Todd—Ye's predictor—corrector interior-point algorithm for linear programming maintains the O( L)-iteration complexity while exhibiting superlinear convergence of the duality gap to zero under the assumption that the iteration sequence converges, and quadratic convergence of the duality gap to zero under the assumption of nondegeneracy. In this paper we establish the quadratic convergence result without any assumption concerning the convergence of the iteration sequence or nondegeneracy. This surprising result, to our knowledge, is the first instance of a demonstration of polynomiality and superlinear (or quadratic) convergence for an interior-point algorithm which does not assume the convergence of the iteration sequence or nondegeneracy.Supported in part by NSF Grant DDM-8922636 and NSF Coop. Agr. No. CCR-8809615, the Iowa Business School Summer Grant, and the Interdisciplinary Research Grant of the University of Iowa Center for Advanced Studies.Supported in part by NSF Coop. Agr. No. CCR-8809615, AFOSR 89-0363, DOE DEFG05-86ER25017 and ARO 9DAAL03-90-G-0093.Supported in part by NSF Grant DMS-9102761 and DOE Grant DE-FG05-91ER25100.     

Ketu and the second invariant of a quadratic space

Using the Chern classes defined by Grothendieck, we map aK-theoretic invariant of invertible symmetric matrices defined by Giffen to the Clifford invariant.According to Herrmann Graßman'sWörterbuch zum Rig-veda, Ketu may not be connected with K₂ but es bezeichnet das, was sich sichtbar oder kenntlich macht ...     

C 1 surface interpolation with constraints

Givenn pairwise distinct and arbitrarily spaced pointsP _i in a domainD of thex–y plane andn real numbersf _i, consider the problem of computing a bivariate functionf(x, y) of classC ¹ inD whose values inP _i are exactlyf _i,i=1,,n, and whose first or second order partial derivatives satisfy appropriate equality and inequality constraints on a given set ofp pointsQ _l inD.In this paper we present a method for solving the above problem, which is designed for extremely large data sets. A step of this method requires the solution of a large scale quadratic programming (QP) problem.The main purpose of this work is to analyse an iterative method for determining the solution of this QP problem: such a method is very efficient and well suited for parallel implementation on a multiprocessor system.Work supported by MURST Project of Computational Mathematics, Italy.     

Mixed strategy solutions forN-person quadratic games

Mixed strategy -equilibrium points are given forN-person games with cost functions consisting of quadratic, bilinear, and linear terms and strategy spaces consisting of closed balls in Hilbert spaces. The results are applied to linear-quadratic differential games with no information and quadratic integral constraints on the control functions.This work was supported by a Commonwealth of Australia, Postgraduate Research Award.     

Efficient algorithms for solving rank two and rank three bilinear programming problems

Finitely convergent algorithms for solving rank two and three bilinear programming problems are proposed. A rank k bilinear programming problem is a nonconvex quadratic programming problem with the following structure: % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4baFfea0dXde9vqpa0lb9% cq0dXdb9IqFHe9FjuP0-iq0dXdbba9pe0lb9hs0dXda91qaq-xfr-x% fj-hmeGabaqaciGacaGaaeqabaWaaeaaeaaakeaaieaacaWFTbGaa8% xAaiaa-5gacaWFPbGaa8xBaiaa-LgacaWF6bGaa8xzaiaa-bcacaWF% 7bacbiGaa43yamaaDaaaleaacaGFWaaabaGaa4hDaaaakiaa+Hhaca% GFRaGaa4hzamaaDaaaleaacaGFWaaabaGaa4hDaaaakiaa+LhacaGF% RaWaaabuaeaacaGFJbWaa0baaSqaaiaa+PgaaeaacaGF0baaaOGaam% iEaiabl+y6NjaadsgadaqhaaWcbaGaamOAaaqaaiaadshaaaGccaWG% 5bGaaiiFaaWcbaGaa8NAaiaa-1dacaWFXaaabeqdcqGHris5aOGaa4% hEaiabgIGiolaa+HfacaGFSaGaa4xEaiabgIGiolaa+LfacaWF9bGa% a8hlaaaa!5D2E!\[minimize \{ c_0^t x + d_0^t y + \sum\limits_{j = 1} {c_j^t xd_j^t y|} x \in X,y \in Y\} ,\]where X Rⁿ¹ and Y R ⁿ² are non-empty and bounded polytopes. We show that a variant of parametric simplex algorithm can solve large scale rank two bilinear programming problems efficiently. Also, we show that a cutting-cake algorithm, a more elaborate variant of parametric simplex algorithm can solve medium scale rank three problems.This research was supported in part by Grant-in-Aid for Scientific Research of the Ministry of Education, Science and Culture, Grant No. 63490010.