Adaptive Algorithm for Constrained Least-Squares Problems

This paper is concerned with the implementation and testing of an algorithm for solving constrained least-squares problems. The algorithm is an adaptation to the least-squares case of sequential quadratic programming (SQP) trust-region methods for solving general constrained optimization problems. At each iteration, our local quadratic subproblem includes the use of the Gauss–Newton approximation but also encompasses a structured secant approximation along with tests of when to use this approximation. This method has been tested on a selection of standard problems. The results indicate that, for least-squares problems, the approach taken here is a viable alternative to standard general optimization methods such as the Byrd–Omojokun trust-region method and the Powell damped BFGS line search method.     

Mathematical programming via the least-squares method

The least-squares method is used to obtain a stable algorithm for a system of linear inequalities as well as linear and nonlinear programming. For these problems the solution with minimal norm for a system of linear inequalities is found by solving the non-negative least-squares (NNLS) problem. Approximate and exact solutions of these problems are discussed. Attention is mainly paid to finding the initial solution to an LP problem. For this purpose an NNLS problem is formulated, enabling finding the initial solution to the primal or dual problem, which may turn out to be optimal. The presented methods are primarily suitable for ill-conditioned and degenerate problems, as well as for LP problems for which the initial solution is not known. The algorithms are illustrated using some test problems.     

Backward Stability Analysis of Weighted Linear Least-Squares Problems

A provably backward stable algorithm for the solution of weighted linear least-squares problems with indefinite diagonal weighted matrices is presented. However, a similar algorithm is not necessarily backward stable, when the weighted matrices are generalized saddle-point matrices. Thus, conditions are derived under which the algorithm is provably backward stable.     

The Numerical Solution of Constrained Linear Least-squares Problems

The paper describes a numerically stable algorithm to solveconstrained linear least-squares problems and allows rank deficientor underdetermined observation matrices. The method starts withthe calculation of the rank of the observation matrix and thetransformation into a least distance problem. The proposed techniquefor solving the least distance problem can be considered asa generalization of the projection method of Stoer (1971). Startingwith a feasible point, a sequence of iterates is calculatedby minimizing the objective function on the linear boundarymanifold determined by the active constraints. Numerical examplesshow the feasibility of the algorithm.     

The Schur algorithm and its applications

The Schur algorithm and its time-domain counterpart, the fast Cholseky recursions, are some efficient signal processing algorithms which are well adapted to the study of inverse scattering problems. These algorithms use a layer stripping approach to reconstruct a lossless scattering medium described by symmetric two-component wave equations which model the interaction of right and left propagating waves. In this paper, the Schur and fast Chokesky recursions are presented and are used to study several inverse problems such as the reconstruction of nonuniform lossless transmission lines, the inverse problem for a layered acoustic medium, and the linear least-squares estimation of stationary stochastic processes. The inverse scattering problem for asymmetric two-component wave equations corresponding to lossy media is also examined and solved by using two coupled sets of Schur recursions. This procedure is then applied to the inverse problem for lossy transmission lines.The work of this author was supported by the Exxon Education FoundationThe work of this author was supported by the Air Force Office of Scientific Research under Grant AFOSR-82-0135A.     

The application of an oblique-projected Landweber method to a model of supervised learning

This paper brings together a novel information representation model for use in signal processing and computer vision problems, with a particular algorithmic development of the Landweber iterative algorithm. The information representation model allows a representation of multiple values for a variable as well as an expression for confidence. Both properties are important for effective computation using multi-level models, where a choice between models will be implementable as part of the optimization process. It is shown that in this way the algorithm can deal with a class of high-dimensional, sparse, and constrained least-squares problems, which arise in various computer vision learning tasks, such as object recognition and object pose estimation. While the algorithm has been applied to the solution of such problems, it has so far been used heuristically. In this paper we describe the properties and some of the peculiarities of the channel representation and optimization, and put them on firm mathematical ground. We consider the optimization a convexly constrained weighted least-squares problem and propose for its solution a projected Landweber method which employs oblique projections onto the closed convex constraint set. We formulate the problem, present the algorithm and work out its convergence properties, including a rate-of-convergence result. The results are put in perspective with currently available projected Landweber methods. An application to supervised learning is described, and the method is evaluated in an experiment involving function approximation, as well as application to transient signals.     

Preconditioning and globalizing conjugate gradients in dual space for quadratically penalized nonlinear-least squares problems

When solving nonlinear least-squares problems, it is often useful to regularize the problem using a quadratic term, a practice which is especially common in applications arising in inverse calculations. A solution method derived from a trust-region Gauss-Newton algorithm is analyzed for such applications, where, contrary to the standard algorithm, the least-squares subproblem solved at each iteration of the method is rewritten as a quadratic minimization subject to linear equality constraints. This allows the exploitation of duality properties of the associated linearized problems. This paper considers a recent conjugate-gradient-like method which performs the quadratic minimization in the dual space and produces, in exact arithmetic, the same iterates as those produced by a standard conjugate-gradients method in the primal space. This dual algorithm is computationally interesting whenever the dimension of the dual space is significantly smaller than that of the primal space, yielding gains in terms of both memory usage and computational cost. The relation between this dual space solver and PSAS (Physical-space Statistical Analysis System), another well-known dual space technique used in data assimilation problems, is explained. The use of an effective preconditioning technique is proposed and refined convergence bounds derived, which results in a practical solution method. Finally, stopping rules adequate for a trust-region solver are proposed in the dual space, providing iterates that are equivalent to those obtained with a Steihaug-Toint truncated conjugate-gradient method in the primal space.     

Large-scale geodetic least-squares adjustment by dissection and orthogonal decomposition

Very large-scale matrix problems currently arise in the context of accurately computing the coordinates of points on the surface of the earth. Here geodesists adjust the approximate values of these coordinates by computing least-squares solutions to large sparse systems of equations which result from relating the coordinates to certain observations such as distances or angles between points. The purpose of this paper is to suggest an alternative to the formation and solution of the normal equations for these least-squares adjustment problems. In particular, it is shown how a block-orthogonal decomposition method can be used in conjunction with a nested dissection scheme to produce an algorithm for solving such problems which combines efficient data management with numerical stability. The approach given here parallels somewhat the development of the natural factor formulation, by Argyris et al., for the use of orthogonal decomposition procedures in the finite-element analysis of structures. As an indication of the magnitude that these least-squares adjustment problems can sometimes attain, the forthcoming readjustment of the North American Datum in 1983 by the National Geodetic Survey is discussed. Here it becomes necessary to linearize and solve an overdetermined system of approximately 6,000,000 equations in 400,000 unknowns—a truly large scale matrix problem.     

The Boundary-Element Method for an Improperly Posed Problem

This paper investigates the numerical solution of an inverseLaplace problem which is improperly posed. Three different mathematicalmodels, using direct, least-squares, and minimal-energy methodsare presented for four test problems. The boundary-element methodis used, and it is found that the minimal-energy method alwaysgives a good stable approximation to the solution, whereas thedirect and least-squares methods do not.     

A least-squares minimum-cost network flow algorithm

Node-arc incidence matrices in network flow problems exhibit several special least-squares properties. We show how these properties can be leveraged in a least-squares primal-dual algorithm for solving minimum-cost network flow problems quickly. Computational results show that the performance of an upper-bounded version of the least-squares minimum-cost network flow algorithm with a special dual update operation is comparable to CPLEX Network and Dual Optimizers for solving a wide range of minimum-cost network flow problems.     

A strictly improving linear programming Phase I algorithm

Instead of trying to recognize and avoid degenerate steps in the simplex method (as some variants do), we have developed a new Phase I algorithm that is impervious to degeneracy. The new algorithm solves a non-negative least-squares problem in order to find a Phase I solution. In each iteration, a simple two-variable least-squares subproblem is used to select an incoming column to augment a set of independent columns (called basic) to get a strictly better fit to the right-hand side. Although this is analogous in many ways to the simplex method, it can be proved that strict improvement is attained at each iteration, even in the presence of degeneracy. Thus cycling cannot occur, and convergence is guaranteed. This algorithm is closely related to a number of existing algorithms proposed for non-negative least-squares and quadratic programs.When used on the 30 smallest NETLIB linear programming test problems, the computational results for the new Phase I algorithm were almost 3.5 times faster than a particular implementation of the simplex method; on some problems, it was over 10 times faster. Best results were generally seen on the more degenerate problems.     

An adaptive least-squares mixed finite element method for nonlinear parabolic problems

A least-squares mixed finite element method for nonlinear parabolic problems is investigated in terms of computational efficiency. An a posteriori error estimator, which is needed in an adaptive refinement algorithm, was composed with the least-squares functional, and a posteriori errors were effectively estimated.     

A model trust-region modification of Newton's method for nonlinear two-point boundary-value problems

The method of quasilinearization for nonlinear two-point boundary-value problems is Newton's method for a nonlinear differential operator equation. A model trust-region approach to globalizing the quasilinearization algorithm is presented. A double-dogleg implementation yields a globally convergent algorithm that is robust in solving difficult problems.This work was supported in part by DOE Contract DE-AS05-82-ER13016 and NSF Grant RII-89-17691 and was part of the author's doctoral thesis at Rice University. It is a pleasure to thank the author's thesis advisors, Professor J. E. Dennis, Jr., and Professor R. A. Tapia.     

A primal-dual interior-point method for linear programming based on a weighted barrier function

One motivation for the standard primal-dual direction used in interior-point methods is that it can be obtained by solving a least-squares problem. In this paper, we propose a primal-dual interior-point method derived through a modified least-squares problem. The direction used is equivalent to the Newton direction for a weighted barrier function method with the weights determined by the current primal-dual iterate. We demonstrate that the Newton direction for the usual, unweighted barrier function method can be derived through a weighted modified least-squares problem. The algorithm requires a polynomial number of iterations. It enjoys quadratic convergence if the optimal vertex is nondegenerate.The research of the second author was supported in part by ONR Grants N00014-90-J-1714 and N00014-94-1-0391.     

A new algorithm for nonlinear least squares

A new algorithm for the nonlinear least-squares problems is introduced and illustrated in this article. It is shown that the new algorithm is relatively more efficient compared to the other algorithms in current use and it works for problems where other methods fail. The new method is illustrated by solving a number of classical test problems. In light of the present method, improvements for some other methods in current use are also suggested in this article. Bibliography: 22 titles. Published inZapiski Nauchnykh Seminarov POMI, Vol. 207, pp. 143–157, 1993.     

Preconditioned Kaczmarz-Extended algorithm with relaxation parameters

We analyse in this paper the possibility of using preconditioning techniques as for square non-singular systems, also in the case of inconsistent least-squares problems. We find conditions in which the minimal norm solution of the preconditioned least-squares problem equals that of the original problem. We also find conditions such that the Kaczmarz-Extended algorithm with relaxation parameters (analysed by the author in [4]), can be adapted to the preconditioned least-squares problem. In the last section of the paper we present numerical experiments, with two variants of preconditioning, applied to an inconsistent linear least-squares model problem.     

Block SOR methods for rank-deficient least-squares problems

Many papers have discussed preconditioned block iterative methods for solving full rank least-squares problems. However very few papers studied iterative methods for solving rank-deficient least-squares problems. Miller and Neumann (1987) proposed the 4-block SOR method for solving the rank-deficient problem. Here a 2-block SOR method and a 3-block SOR method are proposed to solve such problem. The convergence of the block SOR methods is studied. The optimal parameters are determined. Comparison between the 2-block SOR method and the 3-block SOR method is given also.     

An adaptive domain decomposition method for the Hamilton–Jacobi–Bellman equation

In this paper, we propose an efficient algorithm for a Hamilton–Jacobi–Bellman equation governing a class of optimal feedback control and stochastic control problems. This algorithm is based on a non-overlapping domain decomposition method and an adaptive least-squares collocation radial basis function discretization with a novel matrix inversion technique. To demonstrate the efficiency of this method, numerical experiments on test problems with up to three states and two control variables have been performed. The numerical results show that the proposed algorithm is highly parallelizable and its computational cost decreases exponentially as the number of sub-domains increases.     

Optimal adaptive grids of least-squares finite element methods in two spatial dimensions

This article concerns a procedure to generate optimal adaptive grids for convection dominated problems in two spatial dimensions based on least-squares finite element approximations. The procedure extends a one dimensional equidistribution principle which minimizes the interpolation error in some norms. The idea is to select two directions which can reflect the physics of the problems and then apply the one dimensional equidistribution principle to the chosen directions. Model problems considered are the two dimensional convection-diffusion problems where boundary and interior layers occur. Numerical results of model problems illustrating the efficiency of the proposed scheme are presented. In addition, to avoid skewed mesh in the optimal grids generated by the algorithm, an unstructured local mesh smoothing will be considered in the least-squares approximations. Comparisons with the Gakerkin finite element method will also be provided.     

Block-Projections Algorithms with Blocks Containing Mutually Orthogonal Rows and Columns

In this paper we present an algorithm which, for a given (sparse) matrix, constructs a partition of its set of row-indices, such that each subset of this partition (except the last one obtained) contains indices which correspond to mutually orthogonal rows. We then use such decompositions in some classes of block-projections methods, previously extended by the author to general inconsistent linear least-squares problems. Numerical experiments on an inconsistent and rank-deficient least-squares model problem are described in the last section of the paper.