Adaptive polynomial preconditioning for hermitian indefinite linear systems

This paper explores the use of polynomial preconditioned CG methods for hermitian indefinite linear systems,Ax=b. Polynomial preconditioning is attractive for several reasons. First, it is well-suited to vector and/or parallel architectures. It is also easy to employ, requiring only matrix-vector multiplication and vector addition. To obtain an optimum polynomial preconditioner we solve a minimax approximation problem. The preconditioning polynomial,C(), is optimum in that it minimizes a bound on the condition number of the preconditioned matrix,C(A)A. We also characterize the behavior of this minimax polynomial, which makes possible a thorough understanding of the associated CG methods. This characterization is also essential to the development of an adaptive procedure for dynamically determining the optimum polynomial preconditioner. Finally, we demonstrate the effectiveness of polynomial preconditioning in a variety of numerical experiments on a Cray X-MP/48. Our results suggest that high degree (20–50) polynomials are usually best.This research was supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Dept. of Energy, by Lawrence Livermore National Laboratory under contract W-7405-ENG-48.This research was supported in part by the Dept. of Energy and the National Science Foundation under grant DMS 8704169.This research was supported in part by U.S. Dept. of Energy grant DEFG02-87ER25026 and by National Science Foundation grant DMS 8703226.     

An adaptive Richardson iteration method for indefinite linear systems

An adaptive Richardson iteration method is presented for the solution of large linear systems of equations with a sparse, symmetric, nonsingular, indefinite matrix. The relaxation parameters for Richardson iteration are chosen to be reciprocal values of Leja points for a compact setK:=[a,b][c,d], where [a,b] is an interval on the negative real axis and [c, d] is an interval on the positive real axis. Endpoints of these intervals are determined adaptively by computing certain modified moments during the iterations. Computed examples show that this adaptive Richardson method can be competitive with the SYMMLQ and the conjugate residual methods, which are based on the Lanczos process.Dedicated to Germund Dahlquist on the occasion of his 70th birthdayResearch supported in part by the Design and Manufacturing Institute at Stevens Institute of Technology.Research supported in part by NSF grants DMS-9002884 and DMS-9205531.     

Asymptotically Optimal Tests and Optimal Designs for Testing the Mean in Regression Models with Applications to Change-Point Problems

Let a linear regression model be given with an experimental region [a, b] R and regression functions f ₁, ..., f _d+1 : [a, b] R. In practice it is an important question whether a certain regression function f _d+1, say, does or does not belong to the model. Therefore, we investigate the test problem H ₀ : "f _d+1 does not belong to the model" against K : "f _d+1 belong to the model" based on the least-squares residuals of the observations made at design points of the experimental region [a, b]. By a new functional central limit theorem given in Bischoff (1998, Ann. Statist. 26, 1398–1410), we are able to determine optimal tests in an asymptotic way. Moreover, we introduce the problem of experimental design for the optimal test statistics. Further, we compare the asymptotically optimal test with the likelihood ratio test (F-test) under the assumption that the error is normally distributed. Finally, we consider real change-point problems as examples and investigate by simulations the behavior of the asymptotic test for finite sample sizes. We determine optimal designs for these examples.     

Essentially finite algorithms for minimizing a class of convex piecewise polynomial functions

We consider minimax problems of the type min _t[a,b] max _i p _t (t), where thep _i (t) are real polynomials which are convex on an interval [a, b]. Here, the function max _i p _i (t) is a convex piecewise polynomial function. The main result is an algorithm yielding the minimum and the minimizing point, which is efficient with respect to the necessary number of computed polynomial zeros. The algorithms presented here are applicable to decision problems with convex loss. While primarily of theoretical interest, they are implementable for quadratic loss functions with finitely many states of nature. An example of this case is given. The algorithms are finite when polynomial zeros need not be approximated.The author is indebted to T. E. S. Raghavan for many stimulating discussions.     

Uniqueness of optimal controls inL ∞

We consider those functionsuL (a, b) which satisfyX=Ax+Bu, whereX satisfies certain prescribed interpolatory constraints. We show that there is au with smallest sup norm and that suchu are uniquely determined on a certain subset of [a, b]; more restrictions allow us to conclude thatX is uniquely determined on this set. An extension is given to certain linear control systems on the real line.Research supported in part by National Science Foundation Grant Nos. GP-43955 and MCS 75-05591.Research supported in part by National Science Foundation Grant Nos. GP-43955 and MPS 74-02292-A01.     

On conjugate gradient type methods and polynomial preconditioners for a class of complex non-hermitian matrices

Summary We consider conjugate gradient type methods for the solution of large linear systemsA x=b with complex coefficient matrices of the typeA=T+iI whereT is Hermitian and a real scalar. Three different conjugate gradient type approaches with iterates defined by a minimal residual property, a Galerkin type condition, and an Euclidean error minimization, respectively, are investigated. In particular, we propose numerically stable implementations based on the ideas behind Paige and Saunder's SYMMLQ and MINRES for real symmetric matrices and derive error bounds for all three methods. It is shown how the special shift structure ofA can be preserved by using polynomial preconditioning, and results on the optimal choice of the polynomial preconditioner are given. Also, we report on some numerical experiments for matrices arising from finite difference approximations to the complex Helmholtz equation.This work was supported in part by Cooperatives Agreement NCC 2-387 between the National Aeronautics and Space Administration (NASA) and the Universities Space Research Association (USRA) and by National Science Foundation Grant DCR-8412314     

Fast Cycle Canceling Algorithms for Minimum Cost Submodular Flow*

This paper presents two fast cycle canceling algorithms for the submodular ow problem. The rst uses an assignment problem whose optimal solution identies most negative node-disjoint cycles in an auxiliary network. Canceling these cycles lexicographically makes it possible to obtain an optimal submodular ow in O(n ⁴ h log(nC)) time, which almost matches the current fastest weakly polynomial time for submodular flow (where n is the number of nodes, h is the time for computing an exchange capacity, and C is the maximum absolute value of arc costs). The second algorithm generalizes Goldbergs cycle canceling algorithm for min cost flow to submodular flow to also get a running time of O(n ⁴ h log(nC)).. We show how to modify these algorithms to make them strongly polynomial, with running times of O(n ⁶ h log n), which matches the fastest strongly polynomial time bound for submodular flow. We also show how to extend both algorithms to solve submodular flow with separable convex objectives. * An extended abstract of a preliminary version of part of this paper appeared in [22]. Research supported in part by a Grant-in-Aid of the Ministry of Education, Science, Sports and Culture of Japan. Research supported by an NSERC Operating Grant. Part of this research was done during a sabbatical leave at Cornell SORIE.§ Research supported in part by a Grant-in-Aid of the Ministry of Education, Science, Sports and Culture of Japan.     

Convex Optimal Designs for Compound Polynomial Extrapolation

The extrapolation design problem for polynomial regression model on the design space [–1,1] is considered when the degree of the underlying polynomial model is with uncertainty. We investigate compound optimal extrapolation designs with two specific polynomial models, that is those with degrees |m, 2m}. We prove that to extrapolate at a point z, |z| > 1, the optimal convex combination of the two optimal extrapolation designs | _m ^* (z), _2m ^* (z)} for each model separately is a compound optimal extrapolation design to extrapolate at z. The results are applied to find the compound optimal discriminating designs for the two polynomial models with degree |m, 2m}, i.e., discriminating models by estimating the highest coefficient in each model. Finally, the relations between the compound optimal extrapolation design problem and certain nonlinear extremal problems for polynomials are worked out. It is shown that the solution of the compound optimal extrapolation design problem can be obtained by maximizing a (weighted) sum of two squared polynomials with degree m and 2m evaluated at the point z, |z| > 1, subject to the restriction that the sup-norm of the sum of squared polynomials is bounded.     

Study of linear information for classes of polynomial equations

Summary We study linear sequential (adaptive) information for approximating zeros of polynomials of unbounded degree and establish a theorem on constrained approximation of smooth functions by polynomials.For a positive we seek a pointx ^* such that|x ^* – _p | , where _p is a zero of a real polynomialp in the interval [a, b]. We assume thatp belongs to the classF ₁ of polynomials of bounded arbitrary seminorm and having a root in [a, b] or to the classF ₂ of polynomials which are nonpositive ata, nonnegative atb and have exactly one simple zero in [a, b]. The information onp consists ofn sequential (adaptive) evaluations of arbitrary linear functionals. The pointx ^* is constructed by means of an algorithm which is an arbitrary mapping depending on the information onp. We show that there exists no information and no algorithm for computingx ^* for everyp fromF ₁, no matter how large the value ofn is. This is a stronger result than that obtained by us for smooth functions.For the classF ₂ we can find a pointx ^* for arbitraryp and. Anoptimal algorithm, i.e., an algorithm with the smallest error, is thebisection of the smallest known interval containing the root ofp. We also exhibitoptimal information operators, i.e., the linear functionals for which the error of an optimal algorithm that uses them is minimal. It turns out that in the class of nonsequential (parallel) information, i.e., when the functionals are given simultaneously, optimal information consists of the evaluations of a polynomial atn-equidistant points in [a, b]. In the class of sequential continuous information, optimal information consists of evaluations of a polynomial atn points generated by thebisection method. To prove this result we establish a theorem on constrained approximation of smooth functions by polynomials. More precisely, we prove that a smooth function can be arbitrarily well uniformly approximated by a polynomial which satisfies constrains given byn arbitrary continuous linear functionals.Our results indicate that the problem of finding an -approximation to a real zero of a real polynomial (of unknown degree) is essentially of the same difficulty as the problem of finding an -approximation to a zero of an infinitely differentiable function.     

Multinomial approximations for nonparametric experiments which minimize the maximal loss of Fisher information

Summary Certain nonparametric product experimentsP _n ⁿ can asymptotically be approximated by multinomial experiments obtained by a finite interval partition of the sample space, the real line. For specific familiesP _n defined in terms of bounded Fisher information and monotone likelihood ratios with bounded derivatives we study the problem to calculate a partition which is optimal in the sense that it minimizes the maximal loss of Fisher information caused by the discretization. This leads to a minimax problem. By considering partitions of the sample space intok intervals which have equal probability under a densityh and then lettingk we obtain an expansion for the quantity loss of Fisher information which is of orderk ^-2 under regularity conditions. The corresponding minimax problem for the first order term of this expansion is shown to be the unique solution of a free boundary problem.This work has been supported by the Deutsche Forschungsgemeinschaft     

Global optimization of univariate Lipschitz functions: II. New algorithms and computational comparison

We consider the following global optimization problems for a Lipschitz functionf implicitly defined on an interval [a, b]. Problem P: find a globally-optimal value off and a corresponding point; Problem Q: find a set of disjoint subintervals of [a, b] containing only points with a globally-optimal value and the union of which contains all globally optimal points. A two-phase algorithm is proposed for Problem P. In phase I, this algorithm obtains rapidly a solution which is often globally-optimal. Moreover, a sufficient condition onf for this to be the case is given. In phase II, the algorithm proves the-optimality of the solution obtained in phase I or finds a sequence of points of increasing value containing one with a globally-optimal value. The new algorithm is empirically compared (on twenty problems from the literature) with a best possible algorithm (for which the optimal value is assumed to be known), with a passive algorithm and with the algorithms of Evtushenko, Galperin, Shen and Zhu, Piyavskii, Timonov and Schoen. For small, the new algorithm requires only a few percent more function evaluations than the best possible one. An extended version of Piyavskii's algorithm is proposed for problem Q. A sufficient condition onf is given for the globally optimal points to be in one-to-one correspondance with the obtained intervals. This result is achieved for all twenty test problems.The research of the authors has been supported by AFOSR grants 0271 and 0066 to Rutgers University. Research of the second author has been also supported by NSERC grant GP0036426, FCAR grant 89EQ4144 and partially by AFOSR grant 0066. We thank Nicole Paradis for her help in drawing the figures.     

An Extension of Sums of Squares Relaxations to Polynomial Optimization Problems Over Symmetric Cones

This paper is based on a recent work by Kojima which extended sums of squares relaxations of polynomial optimization problems to polynomial semidefinite programs. Let and be a finite dimensional real vector space and a symmetric cone embedded in ; examples of and include a pair of the N-dimensional Euclidean space and its nonnegative orthant, a pair of the N-dimensional Euclidean space and N-dimensional second-order cones, and a pair of the space of m × m real symmetric (or complex Hermitian) matrices and the cone of their positive semidefinite matrices. Sums of squares relaxations are further extended to a polynomial optimization problem over , i.e., a minimization of a real valued polynomial a(x) in the n-dimensional real variable vector x over a compact feasible region , where b(x) denotes an - valued polynomial in x. It is shown under a certain moderate assumption on the -valued polynomial b(x) that optimal values of a sequence of sums of squares relaxations of the problem, which are converted into a sequence of semidefinite programs when they are numerically solved, converge to the optimal value of the problem. Research supported by Grant-in-Aid for Scientific Research on Priority Areas 16016234.     

Nonlinearity inH ∞-control theory,causality in the commutant lifting theorem,and extension of intertwining operators

The problems studied in this note have been motivated by our work in generalizing linearH control theory to nonlinear systems. These ideas have led to a design procedure applicable to analytic nonlinear plants. Our technique is a generalization of the linearH theory. In contrast to previous work on this topic ([9], [10]), we now are able to explicitly incorporate a causality constraint into the theory. In fact, we show that it is possible to reduce a causal optimal design problem (for nonlinear systems) to a classical interpolation problem solvable by the commutant lifting theorem [8]. Here we present the complete operator theoretical background of our research together with a short control theoretical motivation.This work was supported in part by grants from the Research Fund of Indiana University, the National Science Foundation DMS-8811084 and ECS-9122106, by the Air Force Office of Scientific Research F49620-94-1-0098DEF, and by the Army Research Office DAAL03-91-G-0019 and DAAH04-93-G-0332     

The <Emphasis Type="Italic">p</Emphasis>-Centre Problem—Heuristic and Optimal Algorithms

The p-centre problem, or minimax location-allocation problem in location theory terminology, is the following: given n demand points on the plane and a weight associated with each demand point, find p new facilities on the plane that minimize the maximum weighted Euclidean distance between each demand point and its closest new facility. We present two heuristics and an optimal algorithm that solves the problem for a given p in time polynomial in n. Computational results are presented.     

Extremal polynomials related to Zolotarev polynomials

Algebraic polynomials bounded in absolute value by M > 0 in the interval [–1, 1] and taking a fixed value A at a > 1 are considered. The extremal problem of finding such a polynomial taking a maximum possible value at a given point b < ?1 is solved. The existence and uniqueness of an extremal polynomial and its independence of the point b < ?1 are proved. A characteristic property of the extremal polynomial is determined, which is the presence of an n-point alternance formed by means of active constraints. The dependence of the alternance pattern, the objective function, and the leading coefficient on the parameter A is investigated. A correspondence between the extremal polynomials in the problem under consideration and the Zolotarev polynomials is established.     

Asymptotic minimax risk for sup-norm loss: Solution via optimal recovery

Summary We study the problem of estimating an unknown function on the unit interval (or itsk-th derivative), with supremum norm loss, when the function is observed in Gaussian white noise and the unknown function is known only to obey Lipschitz- smoothness, >k0. We discuss an optimization problem associated with the theory ofoptimal recovery. Although optimal recovery is concerned with deterministic noise chosen by a clever opponent, the solution of this problem furnishes the kernel of the minimax linear estimate for Gaussian white noise. Moreover, this minimax linear estimator is asymptotically minimax among all estimates. We sketch also applications to higher dimensions and to indirect measurement (e.g. deconvolution) problems.Dedicated to R.Z. Khas'minskii for his 60th birthday     

A critical index algorithm for nearest point problems on simplicial cones

We consider the linear complementarity problem (q, M) in whichM is a positive definite symmetric matrix of ordern. This problem is equivalent to a nearest point problem [; b] in which = {A.₁,, A. _n } is a basis for R ⁿ ,b is a given point in R ⁿ ; and it is required to find the nearest point in the simplicial cone Pos() tob. We develop an algorithm for solving the linear complementarity problem (q, M) or the equivalent nearest point problem [; b]. Computational experience in comparison with an existing algorithm is presented.Research effort partially supported by the Air Force Office of Scientific Research. Air Force Systems Command, USAF, under grant No. AFOSR 78-3646. The United States Government is authorized to reproduce and distribute reprints for governmental purposes, not withstanding any copyright notation hereon.     

Efficient construction of a small hitting set for combinatorial rectangles in high dimension

We describe a deterministic algorithm which, on input integersd, m and real number (0,1), produces a subset S of [m] ^d ={1,2,3,...,m} ^d that hits every combinatorial rectangle in [m] ^d of volume at least , i.e., every subset of [m] ^d the formR ₁×R ₂×...×R _d of size at least m ^d . The cardinality of S is polynomial inm(logd)/, and the time to construct it is polynomial inmd/. The construction of such sets has applications in derandomization methods based on small sample spaces for general multivalued random variables.A preliminary version of this paper appeared in Proceedings of the 25th Annual ACM Symposium on Theory of Computing, 1993.Research partially done while visiting the International Computer Science Institute. Research supported in part by a grant from the Israel-USA Binational Science Foundation.A large portion of this research was done while still at the International Computer Science Institute in Berkeley, California. Research supported in part by National Science Foundation operating grants CCR-9304722 and NCR-9416101, and United States-Israel Binational Science Foundation grant No. 92-00226.Supported in part by NSF under grants CCR-8911388 and CCR-9215293 and by AFOSR grants AFOSR-89-0512 AFOSR-90-0008, and by DIMACS, which is supported by NSF grant STC-91-19999 and by the New Jersey Commission on Science and Technology. Research partially done while visiting the International Computer Science Institute.Partially supported by NSF NYI Grant No. CCR-9457799. Most of this research was done while the author was at MIT, partially supported by an NSF Postdoctoral Fellowship. Research partially done while visiting the International Computer Science Institute.     

Numerical solution of minimax problems of optimal control,part 1

This paper contains general transformation techniques useful to convert minimax problems of optimal control into the Mayer-Bolza problem of the calculus of variations [Problem (P)]. We consider two types of minimax problems: minimax problems of Type (Q), in which the minimax function depends on the state and does not depend on the control; and minimax problems of Type (R), in which the minimax function depends on both the state and the control. Both Problem (Q) and Problem (R) can be reduced to Problem (P).For Problem (Q), we exploit the analogy with a bounded-state problem in combination with a transformation of the Jacobson type. This requires the proper augmentation of the state vectorx(t), the control vectoru(t), and the parameter vector , as well as the proper augmentation of the constraining relations. As a result of the transformation, the unknown minimax value of the performance index becomes a component of the parameter vector being optimized.For Problem (R), we exploit the analogy with a bounded-control problem in combination with a transformation of the Valentine type. This requires the proper augmentation of the control vectoru(t) and the parameter vector , as well as the proper augmentation of the constraining relations. As a result of the transformation, the unknown minimax value of the performance index becomes a component of the parameter vector being optimized.In a subsequent paper (Part 2), the transformation techniques presented here are employed in conjunction with the sequential gradient-restoration algorithm for solving optimal control problems on a digital computer; both the single-subarc approach and the multiple-subarc approach are discussed.This research was supported by the National Science Foundation, Grant No. ENG-79-18667, and by Wright-Patterson Air Force Base, Contract No. F33615-80-C3000. This paper is a condensation of the investigations reported in Refs. 1–7. The authors are indebted to E. M. Coker and E. M. Sims for analytical and computational assistance.     

Solving sparse symmetric definite quadraticλ-matrix problems

This paper describes a method for computing all the eigenvalues in a user supplied interval [a,b], and their associated eigenvectors, of the symmetric definite quadratic-matrix problem (M ²+C+K)x=0, where the matrices ar sufficiently sparse that methods based on similarity transformations are inappropriate. Only the triangular factorization of onen ×n matrix need be computed.Research sponsored in part by the Mathematics Department, University of Linköping, Sweden, and the Applied Mathematical Sciences Research Program, Office of Energy Research, U.S. Department of Energy under contract W-7405-eng-26 with the Union Carbide Corporation.