Analysis of switched linear systems in the plane,part 2: Global behavior of trajectories,controllability and attainability

The controllability and attainability properties of switched linear systems in the plane are investigated. A main result is the state-space decomposition theorem which classifies various convex regions inR ² according to their controllability properties. A preliminary investigation into the problem of determining minimum switch trajectories between two points inR ² is also presented.This research was supported by the Office of Naval Research, ONR Contract No. N0014-80-C-0199, and the United States Department of Energy, DOE Contract No. DE-AC01-79-ET-29363.     

Properties of a representation of a basis for the null space

Given a rectangular matrixA(x) that depends on the independent variablesx, many constrained optimization methods involve computations withZ(x), a matrix whose columns form a basis for the null space ofA ^T(x). WhenA is evaluated at a given point, it is well known that a suitableZ (satisfyingA ^T Z = 0) can be obtained from standard matrix factorizations. However, Coleman and Sorensen have recently shown that standard orthogonal factorization methods may produce orthogonal bases that do not vary continuously withx; they also suggest several techniques for adapting these schemes so as to ensure continuity ofZ in the neighborhood of a given point.This paper is an extension of an earlier note that defines the procedure for computingZ. Here, we first describe howZ can be obtained byupdating an explicit QR factorization with Householder transformations. The properties of this representation ofZ with respect to perturbations inA are discussed, including explicit bounds on the change inZ. We then introduceregularized Householder transformations, and show that their use implies continuity of the full matrixQ. The convergence ofZ andQ under appropriate assumptions is then proved. Finally, we indicate why the chosen form ofZ is convenient in certain methods for nonlinearly constrained optimization.The research of the Stanford authors was supported by the U.S. Department of Energy Contract DE-AM03-76SF00326, PA No. DE-AT03-76ER72018; the National Science Foundation Grants MCS-7926009 and ECS-8312142; the Office of Naval Research Contract N00014-75-C-0267; and the U.S. Army Research Office Contract DAAG29-84-K-0156.The research of G.W. Stewart was supported by the Air Force Office of Scientific Research Contract AFOSR-82-0078.     

Accurate SVDs of weakly diagonally dominant M-matrices

Summary. We present a new O(n³) algorithm which computes the SVD of a weakly diagonally dominant M-matrix to high relative accuracy. The algorithm takes as an input the offdiagonal entries of the matrix and its row sums.Mathematics Subject Classification (1991): 65F15Revised version received September 19, 2003This material is based in part upon work supported by the LLNL Memorandum Agreement No. B504962 under DOE Contract No. W-7405-ENG-48, DOE Grants No. DE-FG03-94ER25219, DE-FC03-98ER25351 and DE-FC02-01ER25478, NSF Grant No. ASC-9813362, and Cooperative Agreement No. ACI-9619020.     

Error bounds for strongly convex programs and (super)linearly convergent iterative schemes for the least 2-norm solution of linear programs

Given an arbitrary point (x, u) inR ⁿ × R ₊ ^m , we give bounds on the Euclidean distance betweenx and the unique solution to a strongly convex program in terms of the violations of the Karush-Kuhn-Tucker conditions by the arbitrary point (x, u). These bounds are then used to derive linearly and superlinearly convergent iterative schemes for obtaining the unique least 2-norm solution of a linear program. These schemes can be used effectively in conjunction with the successive overrelaxation (SOR) methods for solving very large sparse linear programs.Sponsored by the United States Army under Contract No. DAAG29-80-C-0041. This material is based on research sponsored by National Science Foundation Grant No. DCR-8420963 and Air Force Office of Scientific Research Grant No. AFOSR-ISSA-85-00080.On leave from CRAI, via Bernini 5, Rende, Cosenza, Italy.     

Use of dynamic trees in a network simplex algorithm for the maximum flow problem

Goldfarb and Hao (1990) have proposed a pivot rule for the primal network simplex algorithm that will solve a maximum flow problem on ann-vertex,m-arc network in at mostnm pivots and O(n ² m) time. In this paper we describe how to extend the dynamic tree data structure of Sleator and Tarjan (1983, 1985) to reduce the running time of this algorithm to O(nm logn). This bound is less than a logarithmic factor larger than those of the fastest known algorithms for the problem. Our extension of dynamic trees is interesting in its own right and may well have additional applications.Research partially supported by a Presidential Young Investigator Award from the National Science Foundation, Grant No. CCR-8858097, an IBM Faculty Development Award, and AT&T Bell Laboratories.Research partially supported by the Office of Naval Research, Contract No. N00014-87-K-0467.Research partially supported by the National Science Foundation, Grant No. DCR-8605961, and the Office of Naval Research, Contract No. N00014-87-K-0467.     

Computation of period matrices of real algebraic curves

In this paper we derive a numerical method which allows us to compute periods of differentials on areal algebraic curve with real points. This leads to an algorithm which can be implemented on a computer and can be used to study the Torelli mapping numerically. Dedicated to the memory of Mario Raimondo This work was supported by the EC Science Plan Contract No. SC1^*-CT91-0716 and the Academy of Finland.     

On the convergence of the conjugate gradient method for singular capacitance matrix equations from the Neumann problem of the Poisson equation

Summary It is shown analytically in this work that the conjugate gradient method is an efficient means of solving the singular capacitance matrix equations arising from the Neumann problem of the Poisson equation. The total operation count of the algorithm does not exceed constant timesN ²logN(N=1/h) for any bounded domain with sufficiently smooth boundary.Sponsored by the United States Army under Contract No. DAAG29-75-C-0024 and the National Science Foundation under Grant No. MCS75-17385. Also partially supported by the Energy Research and Development Administration     

Remarks on generators of analytic semigroups

This paper contains two new characterizations of generators of analytic semigroups of linear operators in a Banach space. These characterizations do not require use of complex numbers. One is used to give a new proof that strongly elliptic second order partial differential operators generate analytic semigroups inL ^p , 1<p<∞, while the sufficient condition in the other characterization is meaningful in the case of nonlinear operators. Sponsored by the United States Army under Contract No. DAAG29-75-C-0024 and the National Science Foundation under Grant No. MCS78-01245.     

On functions whose stationary points are global minima

In this paper, a characterization of functions whose stationary points are global minima is studied. By considering the level sets of a real function as a point-to-set mapping, and by examining its semicontinuity properties, we obtain the result that a real function, defined on a subset ofR ⁿ and satisfying some mild regularity conditions, belongs to the above family iff the point-to-set mapping of its level sets is strictly lower semicontinuous. Mathematical programming applications are also mentioned.The authors are thankful to an anonymous referee of an earlier version of this paper for his valuable comments. This research was partially supported by the Office of Naval Research, Contract No. N-00014-75-C-0267, by the National Science Foundation, Grant No. MPS-71-03341-A03, and by the US Energy Research and Development Administration, Contract No. E(04-3)-326 PA-18. An earlier version of this paper appeared as CORE Discussion Paper No. 7502. Part of this research was carried out while the first author was at CORE, Louvain, Belgium.     

Homotopies for computation of fixed points

Given a point to set mapf on a simplex with certain conditions, an algorithm for computing fixed points is described. The algorithm operates by following the fixed point as an initially affine function is deformed towardsf. This research was supported in part by Army Research Office Durham Contract DAHC-04-67-C-0028 and in part by NSF Grant GK-5695.     

Properties of the random search in global optimization

From theorems which we prove about the behavior of gaps in a set ofN uniformly random points on the interval [0, 1], we determine properties of the random search procedure in one-dimensional global optimization. In particular, we show that the uniform grid search is better than the random search when the optimum is chosen using the deterministic strategy, that a significant proportion of large gaps are contained in the uniformly random search, and that the error in the determination of the point at which the optimum occurs, assuming that it is unique, will on the average be twice as large using the uniformly random search compared with the uniform grid. In addition, some of the properties of the largest gap are verified numerically, and some extensions to higher dimensions are discussed. The latter show that not all of the conclusions derived concerning the inadequacies of the one-dimensional random search extend to higher dimensions, and thaton average the random search is better than the uniform grid for dimensions greater than 6.This paper is based on work started in the Statistics Department of Princeton University when the first author was visiting as a Research Associate. Part of this research was supported by the Office of Naval Research, Contract No. 0014-67-A-0151-0017, and by the US Army Research Office—Durham, Contract No. DA-31-124-ARO-D-215.2 The authors wish to thank B. Omodei for his careful work in preparing the programs for the results of Figs. 1–2 and Table 1. The computations were performed on the IBM 360/50 of the Australian National University's Computer Centre. Thanks are also due to R. Miles for suggestions regarding the extension of the results to multidimensional regions, and to P. A. P. Moran and R. Brent for suggestions regarding the evaluation of the integral ₀ ¹ ... ^0/1 (x ₁ ² + ... +x _n ^/2 )^1/2 dx ₁ ...dx _n.     

On stochastic integration by series of Wiener integrals

Stochastic integrals of random functions with respect to a white-noise random measure are defined in terms of random series of usual Wiener integrals. Conditions for the existence of such integrals are obtained in terms of the nuclearity of certain operators onL ² -spaces. The relation with the Fisk-Stratonovich symmetric integral is also discussed.This research was supported by AFOSR Contract No. F49620 82 C 0009.     

Geometric optimization andD P -completeness

In this paper we show a number of natural geometric optimization problems in the plane to becomplete for a classD ^P . The classD ^p contains both NP and Co-NP and is contained in ₂ ^P =P ^NP. Completeness inD ^p is exhibited under many-one and positive reductions. Further anOptP(O(logn)) result is also obtained for some of these optimization problems.Work on this paper by the first author was supported in part by NSF Grant No. MIP 85-21356 and ARO Contract No. DAAG29-85-C-0018 under Cornell/MSI. Work by the second author was supported in part by NSF Grant No. DCR 86-06366 at Ohio State and ONR Grant No. N00014-k-0045 at Harvard.On leave from Ohio State University.     

On explicit solutions of interval linear programs

An interval linear program is the problem of maximizing {(c, x):a≦A x≦b} for given matrixA and vectorsa, b andc. The explicit (noniterative) solutions of interval programs given here, extend earlier results of Ben-Israel and Charnes. The contribution of Sanjo Zlobec is part of his Ph.D. dissertation in Applied Mathematics at Northwestern University (in preparation). Part of the research underlying this report was undertaken for the Office of Nava Research, Contract NONR-1228(10), Project NR 047-021, for the U.S. Army Research Office — Durham, Contract No. DA-31-124-ARO-D-322, and for the National Science Foundation, Project GP 7550 at Northwestern University. Reproduction of this paper in whole or in part i^S permitted for any purpose of the United States Government.     

An existence theorem for solutions tof(x) = 0

InR ¹, if a continuous function has opposite signs at the endpoints of an interval, then the function has a zero in the interval. If the function has a nonvanishing derivative at a zero, then there is an interval such that the function has opposite signs at the endpoints. In this paper each of these results is extended toR ⁿ .The research of this author has been partially supported by ONR Contract N000-14-67-A-0285-0019 (NR #047-095) and by NSF Contract SOC-7402516.     

The almost sure representation of intermediate order statistics

Summary Let {X _n} be independent and identically distributed and let X _kn ⁽ⁿ⁾ denote the k _n-th order statistic for X ₁ ..., X _n, where k _n but k _n/n0. A representation for X _kn ⁽ⁿ⁾ in terms of the empirical distribution function is developed. The conditions include those under which X _kn ⁽ⁿ⁾ is asymptotically normal.Research partially supported by the University of North Carolina at Chapel Hill under Office of Naval Research Contract No. N00014-75-C-0809 and by The Florida State University under Office of Naval Research Contract No. N00014-76-C-0608.     

Methods of conjugate directions versus quasi-Newton methods

It is shown that algorithms for minimizing an unconstrained functionF(x), x E ⁿ , which are solely methods of conjugate directions can be expected to exhibit only ann or (n–1) step superlinear rate of convergence to an isolated local minimizer. This is contrasted with quasi-Newton methods which can be expected to exhibit every step superlinear convergence. Similar statements about a quadratic rate of convergence hold when a Lipschitz condition is placed on the second derivatives ofF(x). Research was supported in part by Army Research Office, Contract Number DAHC 19-69-C-0017 and the Office of Naval Research, Contract Number N00014-71-C-0116 (NR 047-99).     

A new approach to the dynamic maintenance of maximal points in a plane

A pointp _i=(x _i, y_i) in thex–y plane ismaximal if there is no pointp _j=(x _j, y_j) such thatx _j>x_i andy _j>y_i. We present a simple data structure, a dynamic contour search tree, which contains all the points in the plane and maintains an embedded linked list of maximal points so thatm maximal points are accessible inO(m) time. Our data structure dynamically maintains the set of points so that insertions takeO(logn) time, a speedup ofO(logn) over previous results, and deletions takeO((logn)²) time.The research of the first author was partially supported by the National Science Foundation under Grant No. DCR-8320214 and by the Office of Naval Research on Contract No. N 00014-86-K-0689. The research of the second author was partially supported by the Office of Naval Research on Contract No. N 00014-86-K-0689.     

Projection method for unconstrained optimization

A method of conjugate directions, the projection method, for solving unconstrained minimization problems is presented. Under the assumption of uniform strict convexity, the method is shown to converge to the global minimizer of the unconstrained problem and to have an (n – 1)-step superlinear rate of convergence. With a Lipschitz condition on the second derivatives, the rate of convergence is shown to be a modifiedn-step quadratic one.This research was supported in part by the Army Research Office, Contract No. DAHC 19-69-C-0017, and the Office of Naval Research, Contract No. N00014-71-C-0116(NR-047-099).     

A quadratically-convergent algorithm for general nonlinear programming problems

This paper presents an algorithm for solving nonlinearly constrained nonlinear programming problems. The algorithm reduces the original problem to a sequence of linearly-constrained minimization problems, for which efficient algorithms are available. A convergence theorem is given which states that if the process is started sufficiently close to a strict second-order Kuhn—Tucker point, then the sequence produced by the algorithm exists and convergesR-quadratically to that point.Work sponsored by the United States Army under Contract No. DA-31-124-ARO-D-462.