An algorithm for linear least squares problems with equality and nonnegativity constraints

We present a new algorithm for solving a linear least squares problem with linear constraints. These are equality constraint equations and nonnegativity constraints on selected variables. This problem, while appearing to be quite special, is the core problem arising in the solution of the general linearly constrained linear least squares problem. The reduction process of the general problem to the core problem can be done in many ways. We discuss three such techniques.The method employed for solving the core problem is based on combining the equality constraints with differentially weighted least squares equations to form an augmented least squares system. This weighted least squares system, which is equivalent to a penalty function method, is solved with nonnegativity constraints on selected variables.Three types of examples are presented that illustrate applications of the algorithm. The first is rank deficient, constrained least squares curve fitting. The second is concerned with solving linear systems of algebraic equations with Hilbert matrices and bounds on the variables. The third illustrates a constrained curve fitting problem with inconsistent inequality constraints.     

AN ALGORITHM FOR SOLVING SYSTEM OF LINEAR INEQUALITIES

A new algorithm is presented for solving a system of linear inequalities. Starting at any point by solving a least squares problem we can either obtain a feasible point or determine that no solution exists.     

Stability analysis of the G-algorithm and a note on its application to sparse least squares problems

The G-algorithm was proposed by Bareiss [1] as a method for solving the weighted linear least squares problem. It is a square root free algorithm similar to the fast Givens method except that it triangularizes a rectangular matrix a column at a time instead of one element at a time.In this paper an error analysis of the G-algorithm is presented which shows that it is as stable as any of the standard orthogonal decomposition methods for solving least squares problems. The algorithm is shown to be a competitive method for sparse least squares problems.A pivoting strategy is given for heavily weighted problems similar to that in [14] for the Householder-Golub algorithm. The strategy is prohibitively expensive, but it is not necessary for most of the least squares problems that arise in practice.The research was supported by the National Science Foundation under contract no. MCS-8201065 and by the Office of Naval Research under contract no. N0014-80-0517.     

The Equality Constrained Indefinite Least Squares Problem: Theory and Algorithms

We present theory and algorithms for the equality constrained indefinite least squares problem, which requires minimization of an indefinite quadratic form subject to a linear equality constraint. A generalized hyperbolic QR factorization is introduced and used in the derivation of perturbation bounds and to construct a numerical method. An alternative method is obtained by employing a generalized QR factorization in combination with a Cholesky factorization. Rounding error analysis is given to show that both methods have satisfactory numerical stability properties and numerical experiments are given for illustration. This work builds on recent work on the unconstrained indefinite least squares problem by Chandrasekaran, Gu, and Sayed and by the present authors.     

Solving Quadratically Constrained Least Squares Problems Using a Differential-Geometric Approach

A quadratically constrained linear least squares problem is usually solved using a Lagrange multiplier for the constraint and then solving iteratively a nonlinear secular equation for the optimal Lagrange multiplier. It is well-known that, due to the closeness to a pole for the secular equation, standard methods for solving the secular equation can be slow, and sometimes it is not easy to select a good starting value for the iteration. The problem can be reformulated as that of minimizing the residual of the least squares problem on the unit sphere. Using a differential-geometric approach we formulate Newton's method on the sphere, and thereby avoid the difficulties associated with the Lagrange multiplier formulation. This Newton method on the sphere can be implemented efficiently, and since it is easy to find a good starting value for the iteration, and the convergence is often quite fast, it has a clear advantage over the Lagrange multiplier method. A numerical example is given.     

On greedy randomized coordinate descent methods for solving large linear least‐squares problems

For solving large scale linear least‐squares problem by iteration methods, we introduce an effective probability criterion for selecting the working columns from the coefficient matrix and construct a greedy randomized coordinate descent method. It is proved that this method converges to the unique solution of the linear least‐squares problem when its coefficient matrix is of full rank, with the number of rows being no less than the number of columns. Numerical results show that the greedy randomized coordinate descent method is more efficient than the randomized coordinate descent method.     

On the weighting method for least squares problems with linear equality constraints

The weighting method for solving a least squares problem with linear equality constraints multiplies the constraints by a large number and appends them to the top of the least squares problem, which is then solved by standard techniques. In this paper we give a new analysis of the method, based on the QR decomposition, that exhibits many features of the algorithm. In particular it suggests a natural criterion for chosing the weighting factor. This work was supported in part by the National Science Foundation under grant CCR 95503126.     

New Optimization Approach to Multiphase Flow

A new optimization formulation for simulating multiphase flow in porous media is introduced. A locally mass-conservative, mixed finite-element method is employed for the spatial discretization. An unconditionally stable, fully-implicit time discretization is used and leads to a coupled system of nonlinear equations that must be solved at each time step. We reformulate this system as a least squares problem with simple bounds involving only one of the phase saturations. Both a Gauss–Newton method and a quasi-Newton secant method are considered as potential solvers for the optimization problem. Each evaluation of the least squares objective function and gradient requires solving two single-phase self-adjoint, linear, uniformly-elliptic partial differential equations for which very efficient solution techniques have been developed.     

非线性最小二乘法的算法

本给出非线性最小二乘的优化条件和几何特征．     

SUBSPACE SEARCH METHOD FOR A CLASS OF LEAST SQUARES PROBLEM

1. IntroductionNow the least squares problem is considered as follows:1Mid r(x,y) ~ SllAx By ~ bll' s.t. x 2 0 (1.1)where A E Rm",, B E R"q, and b E Re are given constant matrices and vectors,respectively.These problems arise in many areas of applications, such as scientific and engineering computing, physics, statistics, flited curve, economic, mathematical programming,social science, and as a component part of some large computation problem, as anexample, a nonlinear least squares pr…     

A SELF-ADAPTIVE ALGORITHM FOR NONLINEAR LEAST SQUARES WITH LINEAR CONSTRAINTS

An algorithm for solving nonlinear least squares problems with general linear inequality constraints is described.At each step,the problem is reduced to an unconstrained linear least squares problem in a subs pace defined by the active constraints,which is solved using the quasi-Newton method.The major update formula is similar to the one given by Dennis,Gay and Welsch (1981).In this paper,we state the detailed implement of the algorithm,such as the choice of active set,the solution of subproblem and the avoidance of zigzagging.We also prove the globally convergent property of the algorithm.     

A Riemannian variant of the Fletcher–Reeves conjugate gradient method for stochastic inverse eigenvalue problems with partial eigendata

In this paper, we focus on the stochastic inverse eigenvalue problem with partial eigendata of constructing a stochastic matrix from the prescribed partial eigendata. A Riemannian variant of the Fletcher–Reeves conjugate gradient method is proposed for solving a general unconstrained minimization problem on a Riemannian manifold, and the corresponding global convergence is established under some assumptions. Then, we reformulate the inverse problem as a nonlinear least squares problem over a matrix oblique manifold, and the application of the proposed geometric method to the nonlinear least squares problem is investigated. The proposed geometric method is also applied to the case of prescribed entries and the case of column stochastic matrix. Finally, some numerical tests are reported to illustrate that the proposed geometric method is effective for solving the inverse problem.     

An iterative penalty method for the least squares solution of boundary value problems

This article is concerned with iterative techniques for linear systems of equations arising from a least squares formulation of boundary value problems. In its classical form, the solution of the least squares method is obtained by solving the traditional normal equation. However, for nonsmooth boundary conditions or in the case of refinement at a selected set of interior points, the matrix associated with the normal equation tends to be ill-conditioned. In this case, the least squares method may be formulated as a Powell multiplier method and the equations solved iteratively. Therein we use and compare two different iterative algorithms. The first algorithm is the preconditioned conjugate gradient method applied to the normal equation, while the second is a new algorithm based on the Powell method and formulated on the stabilized dual problem. The two algorithms are first compared on a one-dimensional problem with poorly conditioned matrices. Results show that, for such problems, the new algorithm gives more accurate results. The new algorithm is then applied to a two-dimensional steady state diffusion problem and a boundary layer problem. A comparison between the least squares method of Bramble and Schatz and the new algorithm demonstrates the ability of the new method to give highly accurate results on the boundary, or at a set of given interior collocation points without the deterioration of the condition number of the matrix. Conditions for convergence of the proposed algorithm are discussed. © 1997 John Wiley & Sons, Inc.     

线性子空间上求解AX=B的最小二乘问题的迭代算法

应用共轭梯度方法和线性投影算子,给出迭代算法求解了线性矩阵方程AX=B在任意线性子空间上的最小二乘解问题.在不考虑舍入误差的情况下,可以证明,所给迭代算法经过有限步迭代可得到矩阵方程AX=B的最小二乘解、极小范数最小二乘解及其最佳逼近.文中的数值例子证实了该算法的有效性.     

Perturbation Identities for Regularized Tikhonov Inverses and Weighted Pseudoinverses

We consider the perturbation analysis of two important problems for solving ill-conditioned or rank-deficient linear least squares problems. The Tikhonov regularized problem is a linear least squares problem with a regularization term balancing the size of the residual against the size of the weighted solution. The weight matrix can be a non-square matrix (usually with fewer rows than columns). The minimum-norm problem is the minimization of the size of the weighted solutions given by the set of solutions to the, possibly rank-deficient, linear least squares problem.It is well known that the solution of the Tikhonov problem tends to the minimum-norm solution as the regularization parameter of the Tikhonov problem tends to zero. Using this fact and the generalized singular value decomposition enable us to make a perturbation analysis of the minimum-norm problem with perturbation results for the Tikhonov problem. From the analysis we attain perturbation identities for Tikhonov inverses and weighted pseudoinverses.     

Semidiscrete least squares methods for linear hyperbolic systems

Some approximate methods for solving linear hyperbolic systems are presented and analyzed. The methods consist of discretizing with respect to time and solving the resulting hyperbolic system for fixed time by least squares finite element methods. An analysis of least squares approximations is given, including optimal order estimates for piecewise polynomial approximation spaces. Numerical results for the inviscid Burgers' equation are also presented. © 1992 John Wiley & Sons, Inc.     

关于用拉格朗日乘子法求解线性等式约束最小二乘问题

本文讨论用拉格朗日乘子法求解线性等式约束最小二乘问题(简称 LSE 问题)的优点.应用此法能细致地讨论约束条件与变量之间的关系,据此并可证明 LSE 问题与某一个无约束最小二乘问题的等价性.此外,尚可得到参数和拉格朗日乘子的协方差矩阵.最后给出一个数值稳定的解 LSE 问题的算法.     

Fitting Parametric Curves and Surfaces by <Emphasis Type="Italic">l</Emphasis><Subscript>∞</Subscript> Distance Regression

For fitting curves or surfaces to observed or measured data, a common criterion is orthogonal distance regression. We consider here a natural generalization of a particular formulation of that problem which involves the replacement of least squares by the Chebyshev norm. For example, this criterion may be a more appropriate one in the context of accept/reject decisions for manufactured parts. The resulting problem has some interesting features: it has much structure which can be exploited, but generally the solution is not unique. We consider a method of Gauss-Newton type and show that if the non-uniqueness is resolved in a way which is consistent with a particular way of exploiting the structure in the linear subproblem, this can not only allow the method to be properly defined, but can permit a second order rate of convergence. Numerical examples are given to illustrate this. AMS subject classification (2000) 65D10, 65K05     

Numerical method for the simultaneous determination of the hydraulic properties of unsaturated porous media

This paper presents a numerical algorithm for solving the inverse coefficient problem for nonlinear parabolic equations. This problem arises in simultaneous determination of the hydraulic properties of unsaturated porous media from a simple outflow experiment. The novel feature of the method is that it is not based on output least squares. In this method, the unknown functions are represented as polygons (continuous and piecewise linear functions) every new linear pieces that are determined in each time step by using information based only on previous time intervals. The results of some numerical experiments are displayed.     

Spectral collocation and radial basis function methods for one-dimensional interface problems

Differential equations with singular sources or discontinuous coefficients yield non-smooth or even discontinuous solutions. This problem is known as the interface problem. High-order numerical solutions suffer from the Gibbs phenomenon in that the accuracy deteriorates if the discontinuity is not properly treated. In this work, we use the spectral and radial basis function methods and present a least squares collocation method to solve the interface problem for one-dimensional elliptic equations. The domain is decomposed into multiple sub-domains; in each sub-domain, the collocation solution is sought. The solution should satisfy more conditions than the given conditions associated with the differential equations, which makes the problem over-determined. To solve the over-determined system, the least squares method is adopted. For the spectral method, the weighted norm method with different scaling factors and the mixed formulation are used. For the radial basis function method, the weighted shape parameter method is presented. Numerical results show that the least squares collocation method provides an accurate solution with high efficacy and that better accuracy is obtained with the spectral method.