Least squares problems with inequality constraints as quadratic constraints

Linear least squares problems with box constraints are commonly solved to find model parameters within bounds based on physical considerations. Common algorithms include Bounded Variable Least Squares (BVLS) and the Matlab function lsqlin. Here, the goal is to find solutions to ill-posed inverse problems that lie within box constraints. To do this, we formulate the box constraints as quadratic constraints, and solve the corresponding unconstrained regularized least squares problem. Using box constraints as quadratic constraints is an efficient approach because the optimization problem has a closed form solution. The effectiveness of the proposed algorithm is investigated through solving three benchmark problems and one from a hydrological application. Results are compared with solutions found by lsqlin, and the quadratically constrained formulation is solved using the L-curve, maximum a posteriori estimation (MAP), and the χ² regularization method. The χ² regularization method with quadratic constraints is the most effective method for solving least squares problems with box constraints.     

L-Curve and Curvature Bounds for Tikhonov Regularization

The L-curve is a popular aid for determining a suitable value of the regularization parameter when solving linear discrete ill-posed problems by Tikhonov regularization. However, the computational effort required to determine the L-curve and its curvature can be prohibitive for large-scale problems. Recently, inexpensively computable approximations of the L-curve and its curvature, referred to as the L-ribbon and the curvature-ribbon, respectively, were proposed for the case when the regularization operator is the identity matrix. This note discusses the computation and performance of the L- and curvature-ribbons when the regularization operator is an invertible matrix.     

A maximum product criterion as a Tikhonov parameter choice rule for Kirsch’s factorization method

Kirsch’s factorization method is a fast inversion technique for visualizing the profile of a scatterer from measurements of the far-field pattern. We present a Tikhonov parameter choice approach based on a maximum product criterion (MPC) which provides a regularization parameter located in the concave part of the L-curve on a log–log scale. The performance of the method is evaluated by comparing our reconstructions with those obtained via the L-curve, Morozov’s discrepancy principle and the SVD-tail. Numerical results that illustrate the effectiveness of the MPC in reconstruction problems involving both simulated and real data are reported and analyzed.     

Estimation of the L-Curve via Lanczos Bidiagonalization

The L-curve criterion is often applied to determine a suitable value of the regularization parameter when solving ill-conditioned linear systems of equations with a right-hand side contaminated by errors of unknown norm. However, the computation of the L-curve is quite costly for large problems; the determination of a point on the L-curve requires that both the norm of the regularized approximate solution and the norm of the corresponding residual vector be available. Therefore, usually only a few points on the L-curve are computed and these values, rather than the L-curve, are used to determine a value of the regularization parameter. We propose a new approach to determine a value of the regularization parameter based on computing an L-ribbon that contains the L-curve in its interior. An L-ribbon can be computed fairly inexpensively by partial Lanczos bidiagonalization of the matrix of the given linear system of equations. A suitable value of the regularization parameter is then determined from the L-ribbon, and we show that an associated approximate solution of the linear system can be computed with little additional work.     

Fixed-point iterations in determining a Tikhonov regularization parameter in Kirsch’s factorization method

Kirsch’s factorization method is a fast inversion technique for visualizing the profile of a scatterer from measurements of the far-field pattern. The mathematical basis of this method is given by the far-field equation, which is a Fredholm integral equation of the first kind in which the data function is a known analytic function and the integral kernel is the measured (and therefore noisy) far-field pattern. We present a Tikhonov parameter choice approach based on a fast fixed-point iteration method which constructs a regularization parameter associated with the corner of the L-curve in log-log scale. The performance of the method is evaluated by comparing our reconstructions with those obtained via the L-curve and we conclude that our method yields reliable reconstructions at a lower computational cost.     

A practical method for solving large-scale TRS

We present a nearly-exact method for the large scale trust region subproblem (TRS) based on the properties of the minimal-memory BFGS method. Our study is concentrated in the case where the initial BFGS matrix can be any scaled identity matrix. The proposed method is a variant of the Moré–Sorensen method that exploits the eigenstructure of the approximate Hessian B, and incorporates both the standard and the hard case. The eigenvalues of B are expressed analytically, and consequently a direction of negative curvature can be computed immediately by performing a sequence of inner products and vector summations. Thus, the hard case is handled easily while the Cholesky factorization is completely avoided. An extensive numerical study is presented, for covering all the possible cases arising in the TRS with respect to the eigenstructure of B. Our numerical experiments confirm that the method is suitable for very large scale problems.     

Analytical study and numerical experiments for Laplace equation with overspecified boundary conditions

In this paper, the window function, e^−αk2, is applied to regularize the divergent problem which occurs in the Laplace equation with overspecified boundary conditions in an infinite strip region. To deal with this ill-posed problem, the corner of the L-curve is chosen as the compromise point to determine the optimal α of the Gaussian window, e^−αk2, so that the high wave-number (k) content can be suppressed instead of engineering judgement using the concept of a cutoff wave-number. From the examples shown, it is found that a reasonable solution of the unknown boundary potential can be reconstructed, and that both high wave-number content and divergent results can be avoided by using the proposed regularization technique.     

Conformal metrics on the ball with zero scalar curvature and prescribed mean curvature on the boundary

This paper considers the prescribed zero scalar curvature and mean curvature problem on the n-dimensional Euclidean ball for n?3. We consider the limits of solutions of the regularization obtained by decreasing the critical exponent. We characterize those subcritical solutions which blow-up at the least possible energy level, determining the points at which they can concentrate, and their Morse indices. We show that when n=3 this is the only blow-up which can occur for solutions. We use this in combination with the Morse inequalities for the subcritical problem to obtain a general existence theorem for the prescribed zero scalar curvature and mean curvature on the three-dimensional Euclidean ball. In the higher-dimensional case n?4, we give conditions on the function h to guarantee there is only one simple blow-up point.     

L1 regularization method in electrical impedance tomography by using the L1-curve (Pareto frontier curve)

Electrical impedance tomography (EIT), as an inverse problem, aims to calculate the internal conductivity distribution at the interior of an object from current-voltage measurements on its boundary. Many inverse problems are ill-posed, since the measurement data are limited and imperfect. To overcome ill-posedness in EIT, two main types of regularization techniques are widely used. One is categorized as the projection methods, such as truncated singular value decomposition (SVD or TSVD). The other categorized as penalty methods, such as Tikhonov regularization, and total variation methods. For both of these methods, a good regularization parameter should yield a fair balance between the perturbation error and regularized solution. In this paper a new method combining the least absolute shrinkage and selection operator (LASSO) and the basis pursuit denoising (BPDN) is introduced for EIT. For choosing the optimum regularization we use the L1-curve (Pareto frontier curve) which is similar to the L-curve used in optimising L2-norm problems. In the L1-curve we use the L1-norm of the solution instead of the L2 norm. The results are compared with the TSVD regularization method where the best regularization parameters are selected by observing the Picard condition and minimizing generalized cross validation (GCV) function. We show that this method yields a good regularization parameter corresponding to a regularized solution. Also, in situations where little is known about the noise level σ, it is also useful to visualize the L1-curve in order to understand the trade-offs between the norms of the residual and the solution. This method gives us a means to control the sparsity and filtering of the ill-posed EIT problem. Tracing this curve for the optimum solution can decrease the number of iterations by three times in comparison with using LASSO or BPDN separately.     

Regularization of Ill-Posed Problems by Envelope Guided Conjugate Gradients

Abstract

We propose a new way to iteratively solve large scale ill-posed problems by exploiting the relation between Tikhonov regularization and multiobjective optimization to obtain, iteratively, approximations to the Tikhonov L-curve and its corner. Monitoring the change of the approximate L-curves allows us to adjust the regularization parameter adaptively during a preconditioned conjugate gradient iteration, so that the desired solution can be reconstructed with a low number of iterations. We apply the technique to an idealized image reconstruction problem in positron emission tomography.     

正则参数求解的微分进化算法

研究了正则化方法中正则参数的求解问题,提出了利用微分进化算法获取正则参数.微分进化算法属于全局最优化算法,具有鲁棒性强、收敛速度快、计算精度高的优点.把正则参数的求解问题转化为非线性优化问题,通过保持在解空间不同区域中各个点的搜索,以最大的概率找到问题的全局最优解,同时还利用数值模拟将此方法与广义交叉原理、L-曲线准则、逆最优准则等进行了对比,数值模拟结果表明该方法具有一定的可行性和有效性.     

Regularization of outflow problems in unsaturated porous media with dry regions

We study a porous medium with saturated, unsaturated, and dry regions, described by Richards' equation for the saturation s and the pressure p. Due to a degenerate permeability coefficient k(x,s) and a degenerate capillary pressure function pc(x,s), the equations may be of elliptic, parabolic, or of ODE-type. We construct a parabolic regularization of the equations and find conditions that guarantee the convergence of the parabolic solutions to a solution of the degenerate system. An example shows that the convergence fails in general. Our approach provides an existence result for the outflow problem in the case of x-dependent coefficients and a method for a numerical approximation.     

An adaptive pruning algorithm for the discrete L-curve criterion

We describe a robust and adaptive implementation of the L-curve criterion. The algorithm locates the corner of a discrete L-curve which is a log–log plot of corresponding residual norms and solution norms of regularized solutions from a method with a discrete regularization parameter (such as truncated SVD or regularizing CG iterations). Our algorithm needs no predefined parameters, and in order to capture the global features of the curve in an adaptive fashion, we use a sequence of pruned L-curves that correspond to considering the curves at different scales. We compare our new algorithm to existing algorithms and demonstrate its robustness by numerical examples.     

A new variant of L-curve for Tikhonov regularization

In this paper we introduce a new variant of L-curve to estimate the Tikhonov regularization parameter for the regularization of discrete ill-posed problems. This method uses the solution norm versus the regularization parameter. The numerical efficiency of this new method is also discussed by considering some test problems.     

Error analysis of finite element approximations of the inverse mean curvature flow arising from the general relativity

This paper proposes and analyzes a finite element method for a nonlinear singular elliptic equation arising from the black hole theory in the general relativity. The nonlinear equation, which was derived and analyzed by Huisken and Ilmanen in (J Diff Geom 59:353–437), represents a level set formulation for the inverse mean curvature flow describing the evolution of a hypersurface whose normal velocity equals the reciprocal of its mean curvature. We first propose a finite element method for a regularized flow which involves a small parameter ɛ; a rigorous analysis is presented to study well-posedness and convergence of the scheme under certain mesh-constraints, and optimal rates of convergence are verified. We then prove uniform convergence of the finite element solution to the unique weak solution of the nonlinear singular elliptic equation as the mesh size h and the regularization parameter ɛ both tend to zero. Computational results are provided to show the efficiency of the proposed finite element method and to numerically validate the “jumping out” phenomenon of the weak solution of the inverse mean curvature flow. Numerical studies are presented to evidence the existence of a polynomial scaling law between the mesh size h and the regularization parameter ɛ for optimal convergence of the proposed scheme. Finally, a numerical convergence study for another approach recently proposed by R. Moser (The inverse mean curvature flow and p-harmonic functions. preprint U Bath, 2005) for approximating the inverse mean curvature flow via p-harmonic functions is also included.     

Brownian Motion and the Dirichlet Problem at Infinity on Two-dimensional Cartan-Hadamard Manifolds

After recalling the Dirichlet problem at infinity on a Cartan-Hadamard manifold, we describe what is known under various curvature assumptions and the difference between the two-dimensional and the higher-dimensional cases. We discuss the probabilistic formulation of the problem in terms of the asymptotic behavior of the angular component of Brownian motion. We then introduce a new (and appealing) probabilistic approach that allows us to prove that the Dirichlet problem at infinity on a two-dimensional Cartan-Hadamard manifold is solvable under the curvature condition K?≤?(1?+?ε)/(r ² logr) outside of a compact set, for some ε?>?0, in polar coordinates around some pole. This condition on the curvature is sharp, and improves upon the previously known case of quadratic curvature decay. Finally, we briefly discuss the issues which arise in trying to extend this method to higher dimensions.     

Minimal Zero Norm Solutions of Linear Complementarity Problems

In this paper, we study minimal zero norm solutions of the linear complementarity problems, defined as the solutions with smallest cardinality. Minimal zero norm solutions are often desired in some real applications such as bimatrix game and portfolio selection. We first show the uniqueness of the minimal zero norm solution for Z-matrix linear complementarity problems. To find minimal zero norm solutions is equivalent to solve a difficult zero norm minimization problem with linear complementarity constraints. We then propose a p norm regularized minimization model with p in the open interval from zero to one, and show that it can approximate minimal zero norm solutions very well by sequentially decreasing the regularization parameter. We establish a threshold lower bound for any nonzero entry in its local minimizers, that can be used to identify zero entries precisely in computed solutions. We also consider the choice of regularization parameter to get desired sparsity. Based on the theoretical results, we design a sequential smoothing gradient method to solve the model. Numerical results demonstrate that the sequential smoothing gradient method can effectively solve the regularized model and get minimal zero norm solutions of linear complementarity problems.     

Error bounds of Lanczos approach for trust-region subproblem

Because of its vital role of the trust-region subproblem (TRS) in various applications, for example, in optimization and in ill-posed problems, there are several factorization-free algorithms for solving the large-scale sparse TRS. The truncated Lanczos approach proposed by N. I. M. Gould, S. Lucidi, M. Roma, and P. L. Toint [SIAM J. Optim., 1999, 9: 504–525] is a natural extension of the classical Lanczos method for the symmetric linear system and eigenvalue problem and, indeed follows the classical Rayleigh-Ritz procedure for eigenvalue computations. It consists of 1) projecting the original TRS to the Krylov subspaces to yield smaller size TRS’s and then 2) solving the resulted TRS’s to get the approximates of the original TRS. This paper presents a posterior error bounds for both the global optimal value and the optimal solution between the original TRS and their projected counterparts. Our error bounds mainly rely on the factors from the Lanczos process as well as the data of the original TRS and, could be helpful in designing certain stopping criteria for the truncated Lanczos approach.     

L-曲线估计确定正则参数的双网格迭代法

本文考虑对不适定问题离散化得到的大规模不适定线性方程组进行Tiknonov正则化,然后用双网格迭代法求解得到的Tikhonov正则化方程组,并用L-曲线估计法来确定正则参数.试验问题的数值结果表明双网格迭代法求解正则化后的对称正定线性方程组效果很好,且L-曲线估计法确定正则参数计算量很小.     

Lanczos-Based Exponential Filtering for Discrete Ill-Posed Problems

We describe regularizing iterative methods for the solution of large ill-conditioned linear systems of equations that arise from the discretization of linear ill-posed problems. The regularization is specified by a filter function of Gaussian type. A parameter determines the amount of regularization applied. The iterative methods are based on a truncated Lanczos decomposition and the filter function is approximated by a linear combination of Lanczos polynomials. A suitable value of the regularization parameter is determined by an L-curve criterion. Computed examples that illustrate the performance of the methods are presented.