A semidefinite framework for trust region subproblems with applications to large scale minimization

Primal-dual pairs of semidefinite programs provide a general framework for the theory and algorithms for the trust region subproblem (TRS). This latter problem consists in minimizing a general quadratic function subject to a convex quadratic constraint and, therefore, it is a generalization of the minimum eigenvalue problem. The importance of (TRS) is due to the fact that it provides the step in trust region minimization algorithms. The semidefinite framework is studied as an interesting instance of semidefinite programming as well as a tool for viewing known algorithms and deriving new algorithms for (TRS). In particular, a dual simplex type method is studied that solves (TRS) as a parametric eigenvalue problem. This method uses the Lanczos algorithm for the smallest eigenvalue as a black box. Therefore, the essential cost of the algorithm is the matrix-vector multiplication and, thus, sparsity can be exploited. A primal simplex type method provides steps for the so-called hard case. Extensive numerical tests for large sparse problems are discussed. These tests show that the cost of the algorithm is 1 +α(n) times the cost of finding a minimum eigenvalue using the Lanczos algorithm, where 0<α(n)<1 is a fraction which decreases as the dimension increases. Research supported by the National Science and Engineering Research Council Canada.     

Parametric linear programming and anti-cycling pivoting rules

The traditional perturbation (or lexicographic) methods for resolving degeneracy in linear programming impose decision rules that eliminate ties in the simplex ratio rule and, therefore, restrict the choice of exiting basic variables. Bland's combinatorial pivoting rule also restricts the choice of exiting variables. Using ideas from parametric linear programming, we develop anticycling pivoting rules that do not limit the choice of exiting variables beyond the simplex ratio rule. That is, any variable that ties for the ratio rule can leave the basis. A similar approach gives pivoting rules for the dual simplex method that do not restrict the choice of entering variables.Supported in part by grant ECS-83-6224 from the Systems Theory and Operations Research Division of the National Science Foundation.Supported in part by Presidential Young Investigator grant 8451517-ECS of the National Science Foundation.     

Note model-checking in non-stationary poisson processes

An approach to assessing the fit of a parametric non-stationary Poisson process model to data is presented. The approach uses kernel estimation in conjunction with a parametric bootstrap. An example is given.     

Reliability analysis of repairable systems from in–service failure count data

Point maximum likelihood estimators for parameters, mean number of failures, and failure rate in a non–homogeneous Poisson process are derived, when only count data from k identical processes are available. Approximate confidence intervals based on the parametric bootstrap technique are considered. The performances of both the point and interval estimation procedures are assessed via Monte Carlo simulation.     

On strongly polynomial dual simplex algorithms for the maximum flow problem

Several pivot rules for the dual network simplex algorithm that enable it to solve a maximum flow problem on ann-node,m-arc network in at most 2nm pivots and O(n ² m) time are presented. These rules are based on the concept of apreflow and depend upon the use of node labels which are either the lengths of a shortestpseudoaugmenting path from those nodes to the sink node orvalid underestimates of those lengths. Extended versions of our algorithms are shown to solve an important class of parametric maximum flow problems with no increase in the worst-case pivot and time bounds of these algorithms. This research was supported in part by NSF Grants DMS 91-06195, DMS 94-14438, and CDR 84-21402 and DOE Grant DE-FG02-92ER25126.     

Nonlinear Oscillations and Stability of Parametrically Excited Cylindrical Shells

Based on Donnell shallow shell equations, the nonlinear vibrations and dynamic instability of axially loaded circular cylindrical shells under both static and harmonic forces is theoretically analyzed. First the problem is reduced to a finite degree-of-freedom one by using the Galerkin method; then the resulting set of coupled nonlinear ordinary differential equations of motion are solved by the Runge–Kutta method. To study the nonlinear behavior of the shell, several numerical strategies were used to obtain Poincaré maps, Lyapunov exponents, stable and unstable fixed points, bifurcation diagrams, and basins of attraction. Particular attention is paid to two dynamic instability phenomena that may arise under these loading conditions: parametric excitation of flexural modes and escape from the pre-buckling potential well. Calculations are carried out for the principal and secondary instability regions associated with the lowest natural frequency of the shell. Special attention is given to the determination of the instability boundaries in control space and the identification of the bifurcational events connected with these boundaries. The results clarify the importance of modal coupling in the post-buckling solution and the strong role of nonlinearities on the dynamics of cylindrical shells.     

Weak Chebyshev Subspaces and Continuous Selections for Parametric Projections

We examine the existence of continuous selections for the parametric projection onto weak Chebyshev subspaces. In particular, we show that if is the class of polynomial splines of degree n with the k fixed knots then the parametric projection admits a continuous selection if and only if the number of knots does not exceed the degree of splines plus one. February 15, 1996. Date revised: September 16, 1996.     

A general parametric analysis approach and its implication to sensitivity analysis in interior point methods

Adler and Monteiro (1992) developed a parametric analysis approach that is naturally related to the geometry of the linear program. This approach is based on the availability of primal and dual optimal solutions satisfying strong complementarity. In this paper, we develop an alternative geometric approach for parametric analysis which does not require the strong complementarity condition. This parametric analysis approach is used to develop range and marginal analysis techniques which are suitable for interior point methods. Two approaches are developed, namely the LU factorization approach and the affine scaling approach. Presented at the ORSA/TIMS, Nashville, TN, USA, May 1991. Supported by the National Science Foundation (NSF) under Grant No. DDM-9109404 and Grant No. DMI-9496178. This work was done while the author was a faculty member of the Systems and Industrial Engineering Department at The University of Arizona. Supported in part by the GTE Laboratories and the National Science Foundation (NSF) under Grant No. CCR-9019469.     

Differentiability with respect to parameters of solutions to convex programming problems

We consider a family of convex programming problems that depend on a vector parameter, characterizing those values of parameters at which solutions and associated Lagrange multipliers are Gâteaux differentiable.These results are specialized to the problem of the metric projection onto a convex set. At those points where the projection mapping is not differentiable the form of Clarke's generalized derivative of this mapping is derived.     

One way to solve the parametric quadratic programming problem

A method is presented for the solution of the parametric quadratic programming problem by the use of conjugate directions. It is based on the method for quadratic programming proposed by the author in [1].While engaged in this research the author had a part-time post with the Manpower Services Commission.