Accuracy and Stability of the Null Space Method for Solving the Equality Constrained Least Squares Problem

The null space method is a standard method for solving the linear least squares problem subject to equality constraints (the LSE problem). We show that three variants of the method, including one used in LAPACK that is based on the generalized QR factorization, are numerically stable. We derive two perturbation bounds for the LSE problem: one of standard form that is not attainable, and a bound that yields the condition number of the LSE problem to within a small constant factor. By combining the backward error analysis and perturbation bounds we derive an approximate forward error bound suitable for practical computation. Numerical experiments are given to illustrate the sharpness of this bound.     

Learning heuristics for basic block instruction scheduling

Instruction scheduling is an important step for improving the performance of object code produced by a compiler. A fundamental problem that arises in instruction scheduling is to find a minimum length schedule for a basic block—a straight-line sequence of code with a single entry point and a single exit point—subject to precedence, latency, and resource constraints. Solving the problem exactly is known to be difficult, and most compilers use a greedy list scheduling algorithm coupled with a heuristic. The heuristic is usually hand-crafted, a potentially time-consuming process. In contrast, we present a study on automatically learning good heuristics using techniques from machine learning. In our study, a recently proposed optimal basic block scheduler was used to generate the machine learning training data. A decision tree learning algorithm was then used to induce a simple heuristic from the training data. The automatically constructed decision tree heuristic was compared against a popular critical-path heuristic on the SPEC 2000 benchmarks. On this benchmark suite, the decision tree heuristic reduced the number of basic blocks that were not optimally scheduled by up to 55% compared to the critical-path heuristic, and gave improved performance guarantees in terms of the worst-case factor from optimality.     

The achievable region method in the optimal control of queueing systems; formulations,bounds and policies

We survey a new approach that the author and his co-workers have developed to formulate stochastic control problems (predominantly queueing systems) asmathematical programming problems. The central idea is to characterize the region of achievable performance in a stochastic control problem, i.e., find linear or nonlinear constraints on the performance vectors that all policies satisfy. We present linear and nonlinear relaxations of the performance space for the following problems: Indexable systems (multiclass single station queues and multiarmed bandit problems), restless bandit problems, polling systems, multiclass queueing and loss networks. These relaxations lead to bounds on the performance of an optimal policy. Using information from the relaxations we construct heuristic nearly optimal policies. The theme in the paper is the thesis that better formulations lead to deeper understanding and better solution methods. Overall the proposed approach for stochastic control problems parallels efforts of the mathematical programming community in the last twenty years to develop sharper formulations (polyhedral combinatorics and more recently nonlinear relaxations) and leads to new insights ranging from a complete characterization and new algorithms for indexable systems to tight lower bounds and nearly optimal algorithms for restless bandit problems, polling systems, multiclass queueing and loss networks.     

On the complexity of computing the handicap of a sufficient matrix

The class of sufficient matrices is important in the study of the linear complementarity problem (LCP)—some interior point methods (IPM’s) for LCP’s with sufficient data matrices have complexity polynomial in the bit size of the matrix and its handicap.In this paper we show that the handicap of a sufficient matrix may be exponential in its bit size, implying that the known complexity bounds of interior point methods are not polynomial in the input size of the LCP problem. We also introduce a semidefinite programming based heuristic, that provides a finite upper bond on the handicap, for the sub-class of P{\mathcal{P}} -matrices (where all principal minors are positive).     

Sequential location of two facilities: comparing random to optimal location of the first facility

We review our recent results in the development of optimal algorithms for the minimization of a strictly convex quadratic function subject to separable convex inequality constraints and/or linear equality constraints. A unique feature of our algorithms is the theoretically supported bound on the rate of convergence in terms of the bounds on the spectrum of the Hessian of the cost function, independent of representation of the constraints. When applied to the class of convex QP or QPQC problems with the spectrum in a given positive interval and a sparse Hessian matrix, the algorithms enjoy optimal complexity, i.e., they can find an approximate solution at the cost that is proportional to the number of unknowns. The algorithms do not assume representation of the linear equality constraints by full rank matrices. The efficiency of our algorithms is demonstrated by the evaluation of the projection of a point to the intersection of the unit cube and unit sphere with hyperplanes.     

Lower Bounds for Fixed Spectrum Frequency Assignment

Determining lower bounds for the sum of weighted constraint violations in fixed spectrum frequency assignment problems is important in order to evaluate the performance of heuristic algorithms. It is well known that, when adopting a binary constraints model, clique and near-clique subproblems have a dominant role in the theory of lower bounds for minimum span problems. In this paper we highlight their importance for fixed spectrum problems. We present a method based on the linear relaxation of an integer programming formulation of the problem, reinforced with constraints derived from clique-like subproblems. The results obtained are encouraging both in terms of quality and in terms of computation time.     

Telecommunication Link Restoration Planning with Multiple Facility Types

To ensure uninterrupted service, telecommunication networks contain excess (spare) capacity for rerouting (restoring) traffic in the event of a link failure. We study the NP-hard capacity planning problem of economically installing spare capacity on a network to permit link restoration of steady-state traffic. We present a planning model that incorporates multiple facility types, and develop optimization-based heuristic solution methods based on solving a linear programming relaxation and minimum cost network flow subproblems. We establish bounds on the performance of the algorithms, and discuss problem instances that nearly achieve these worst-case bounds. In tests on three real-world problems and numerous randomly-generated problems containing up to 50 nodes and 150 edges, the heuristics provide good solutions (often within 0.5% of optimality) to problems with single facility type, in equivalent or less time than methods from the literature. For multi-facility problems, the gap between our heuristic solution values and the linear programming bounds are larger. However, for small graphs, we show that the optimal linear programming value does not provide a tight bound on the optimal integer value, and our heuristic solutions are closer to optimality than implied by the gaps.     

Numerical Evaluation of the Evans Function by Magnus Integration

We use Magnus methods to compute the Evans function for spectral problems as arise when determining the linear stability of travelling wave solutions to reaction-diffusion and related partial differential equations. In a typical application scenario, we need to repeatedly sample the solution to a system of linear non-autonomous ordinary differential equations for different values of one or more parameters as we detect and locate the zeros of the Evans function in the right half of the complex plane. In this situation, a substantial portion of the computational effort—the numerical evaluation of the iterated integrals which appear in the Magnus series—can be performed independent of the parameters and hence needs to be done only once. More importantly, for any given tolerance Magnus integrators possess lower bounds on the step size which are uniform across large regions of parameter space and which can be estimated a priori. We demonstrate, analytically as well as through numerical experiment, that these features render Magnus integrators extremely robust and, depending on the regime of interest, efficient in comparison with standard ODE solvers. AMS subject classification (2000) 65F20     

On rank and null space computation of the generalized Sylvester matrix

In this paper, we present new approaches computing the rank and the null space of the (m n + p)×(n + p) generalized Sylvester matrix of (m + 1) polynomials of maximal degrees n,p. We introduce an algorithm which handles directly a modification of the generalized Sylvester matrix, computing efficiently its rank and null space and replacing n by log ₂ n in the required complexity of the classical methods. We propose also a modification of the Gauss-Jordan factorization method applied to the appropriately modified Sylvester matrix of two polynomials for computing simultaneously its rank and null space. The methods can work numerically and symbolically as well and are compared in respect of their error analysis, complexity and efficiency. Applications where the computation of the null space of the generalized Sylvester matrix is required, are also given.     

Convex programming with single separable constraint and bounded variables

In this paper a minimization problem with convex objective function subject to a separable convex inequality constraint “≤” and bounded variables (box constraints) is considered. We propose an iterative algorithm for solving this problem based on line search and convergence of this algorithm is proved. At each iteration, a separable convex programming problem with the same constraint set is solved using Karush-Kuhn-Tucker conditions. Convex minimization problems subject to linear equality/ linear inequality “≥” constraint and bounds on the variables are also considered. Numerical illustration is included in support of theory.     

An implementable proximal point algorithmic framework for nuclear norm minimization

The nuclear norm minimization problem is to find a matrix with the minimum nuclear norm subject to linear and second order cone constraints. Such a problem often arises from the convex relaxation of a rank minimization problem with noisy data, and arises in many fields of engineering and science. In this paper, we study inexact proximal point algorithms in the primal, dual and primal-dual forms for solving the nuclear norm minimization with linear equality and second order cone constraints. We design efficient implementations of these algorithms and present comprehensive convergence results. In particular, we investigate the performance of our proposed algorithms in which the inner sub-problems are approximately solved by the gradient projection method or the accelerated proximal gradient method. Our numerical results for solving randomly generated matrix completion problems and real matrix completion problems show that our algorithms perform favorably in comparison to several recently proposed state-of-the-art algorithms. Interestingly, our proposed algorithms are connected with other algorithms that have been studied in the literature.     

Forming and scheduling jobs with capacitated containers in semiconductor manufacturing: Single machine problem

We study a scheduling problem motivated by the challenges observed in the newest semiconductor manufacturing wafer fabrication facilities. As wafers are larger and heavier in these wafer fabs, it is becoming more common to use specialized material handling containers that carry multiple orders coming from different customers and to schedule the containers as jobs in the fab. The system performance is a function of the completion times of orders, which ultimately depend on both (1) how the orders are assigned to such containers (“job formation”), and (2) how the containers are scheduled in the fab (“job scheduling”). The overall problem is to find the best way to form and schedule the jobs subject to complicating constraints, including the restrictions on the number of containers that can be used at one time and on the number of wafers the containers can carry. We focus on the single machine job formation and scheduling problem with the total completion time objective. We show that this problem is quite different from conventional parallel and serial batching scenarios and prove that the uncapacitated special case is polynomially solvable and the capacitated case is strongly NP-hard. We use a dynamic programming algorithm to solve the uncapacitated problem, which not only provides tight lower bounds for the capacitated problem, but also becomes a basis for a heuristic approach for the capacitated problem. The computational results show that this approach is very effective, leading to small optimality gaps that get even smaller as the problems become larger.     

Estimations of parametric functions under a system of linear regression equations with correlated errors

Estimations of parametric functions under a system of linear regression equations with correlated errors across equations involve many complicated operations of matrices and their generalized inverses. In the past several years, a useful tool -- the matrix rank method was utilized to simplify various complicated operations of matrices and their generalized inverses. In this paper, we use the matrix rank method to derive a variety of new algebraic and statistical properties for the best linear unbiased estimators （BLUEs） of parametric functions under the system. In particular, we give the necessary and sufficient conditions for some equalities, additive and block decompositions of BLUEs of parametric functions under the system to hold.     

A fast approximation algorithm for the multicovering problem

The multicovering problem is: MIN cx subject to Ax≥b, xϵ{0, 1}ⁿ, where A is a matrix whose elements are all zero or one and b is a vector of positive integers. We present a fast heuristic for this important class of problems and analyze its worst-case performance: the ratio of the heuristic value to the optimum does not exceed the maximum row sum of the matrix A. The heuristic algorithm also provides a feasible dual solution vector that is useful in generating lower bounds on the value of the optimum.     

A new method of moving asymptotes for large-scale linearly equality-constrained minimization

A new method of moving asymptotes for large-scale minimization subject to linear equality constraints is discussed.In this method,linear equality constraints are deleted with null space technique and the descending direction is obtained by solving a convex separable subproblem of moving asymptotes in each iteration. New rules for controlling the asymptotes parameters are designed and the global convergence of the method under some reasonable conditions is established and proved.The numerical results show that the new method may be capable of processing some large scale problems.     

Multivariate linear rank statistics for profile analysis

For some general multivariate linear models, linear rank statistics are used in conjunction with Roy's Union-Intersection Principle to develop some tests for inference on the parameter (vector) when they are subject to certain linear constraints. More powerful tests are designed by incorporating the a priori information on these constraints. Profile analysis is an important application of this type of hypothesis testing problem; it consists of a set of hypothesis testing problem for the p responses q-sample model, where it is a priori assumed that the response-sample interactions are null.     

Generalization of Primal—Dual Interior-Point Methods to Convex Optimization Problems in Conic Form

We generalize primal—dual interior-point methods for linear programming (LP) problems to the convex optimization problems in conic form. Previously, the most comprehensive theory of symmetric primal—dual interior-point algorithms was given by Nesterov and Todd for feasible regions expressed as the intersection of a symmetric cone with an affine subspace. In our setting, we allow an arbitrary convex cone in place of the symmetric cone. Even though some of the impressive properties attained by Nesterov—Todd algorithms are impossible in this general setting of convex optimization problems, we show that essentially all primal—dual interior-point algorithms for LP can be extended easily to the general setting. We provide three frameworks for primal—dual algorithms, each framework corresponding to a different level of sophistication in the algorithms. As the level of sophistication increases, we demand better formulations of the feasible solution sets. Our algorithms, in return, attain provably better theoretical properties. We also make a very strong connection to quasi-Newton methods by expressing the square of the symmetric primal—dual linear transformation (the so-called scaling) as a quasi-Newton update in the case of the least sophisticated framework. August 25, 1999. Final version received: March 7, 2001.     

Solving large set covering problems for crew scheduling

This paper presents a computationally effective heuristic method which produces good-quality solutions for large-scale set covering problems with thousands of constraints and about one million variables. The need to solve such large-scale problems arises from a crew scheduling problem of mass transit agencies where the number of work shifts required has to be minimized. This problem may be formulated as a large-scale non-unicost set covering problem whose rows are trips to be performed while columns stand for round trips. The proposed method is mainly based on lagragian relaxation and sub-gradient optimization. After the reduction of the number of rows and columns by the logical tests, “greedy” heuristic algorithms provide upper and lower bounds which are continuously improved to produce goodquality solutions. Computational results, regarding randomly generated problems and real life problems concerning crew scheduling at Italian Railways Company, show that good-quality solutions can be obtained at an acceptable computational cost. This work was supported by the project “Progetto Finalizzato Transporti 2” of National Research Council of Italy (C.N.R.) contract No. 94.01436PF74 and by “Ferrovie dello Stato S.p.A.”     

体上线性映射的子空间的维数及其应用

本文给出体上左向量空间的线性映射的某些子空间的维数恒等式,并讨论了它在体上矩阵秩的理论上的应用,其中一个有趣的应用是,由体上矩阵秩的恒等式来刻划体上某些矩阵的特征性质。 以下设Ω是一个体。对Ω上左向量空间V映入Ω上左向量空间V′的线性映射σ:V V~σ,记σ的核空间为:     

Partitioned matrices satisfying certain null space properties

Partitioned matrices satisfying certain null space properties for all leading principal submatrices are shown to be equivalent to a sequence of generalized Schur complements satisfying the same null space properties with respect to their (1, 1) entry. It is shown that a matrix with these null space properties has nonsingular principal submatrices of all orders less than or equal to its rank. Also, a theorem of Carlson, Haynsworth, and Markham concerning the quotient property for Schur complements is extended.