On the condition number of linear least squares problems in a weighted Frobenius norm

LetA be anm × n, m n full rank real matrix andb a real vector of sizem. We give in this paper an explicit formula for the condition number of the linear least squares problem (LLSP) defined by min Ax–b₂,x ⁿ . Let and be two positive real numbers, we choose the weighted Frobenius norm [A, b] _F on the data and the usual Euclidean norm on the solution. A straightforward generalization of the backward error of [9] to this norm is also provided. This allows us to carry out a first order estimate of the forward error for the LLSP with this norm. This enables us to perform a complete backward error analysis in the chosen norms.Finally, some numerical results are presented in the last section on matrices from the collection of [5]. Three algorithms have been tested: the QR factorization, the Normal Equations (NE), the Semi-Normal Equations (SNE).     

Least Frobenius norm updating of quadratic models that satisfy interpolation conditions

Quadratic models of objective functions are highly useful in many optimization algorithms. They are updated regularly to include new information about the objective function, such as the difference between two gradient vectors. We consider the case, however, when each model interpolates some function values, so an update is required when a new function value replaces an old one. We let the number of interpolation conditions, m say, be such that there is freedom in each new quadratic model that is taken up by minimizing the Frobenius norm of the second derivative matrix of the change to the model. This variational problem is expressed as the solution of an (m+n+1)×(m+n+1) system of linear equations, where n is the number of variables of the objective function. Further, the inverse of the matrix of the system provides the coefficients of quadratic Lagrange functions of the current interpolation problem. A method is presented for updating all these coefficients in ({m+n}²) operations, which allows the model to be updated too. An extension to the method is also described that suppresses the constant terms of the Lagrange functions. These techniques have a useful stability property that is investigated in some numerical experiments.     

Nonsmooth optimization via quasi-Newton methods

We investigate the behavior of quasi-Newton algorithms applied to minimize a nonsmooth function f, not necessarily convex. We introduce an inexact line search that generates a sequence of nested intervals containing a set of points of nonzero measure that satisfy the Armijo and Wolfe conditions if f is absolutely continuous along the line. Furthermore, the line search is guaranteed to terminate if f is semi-algebraic. It seems quite difficult to establish a convergence theorem for quasi-Newton methods applied to such general classes of functions, so we give a careful analysis of a special but illuminating case, the Euclidean norm, in one variable using the inexact line search and in two variables assuming that the line search is exact. In practice, we find that when f is locally Lipschitz and semi-algebraic with bounded sublevel sets, the BFGS (Broyden–Fletcher–Goldfarb–Shanno) method with the inexact line search almost always generates sequences whose cluster points are Clarke stationary and with function values converging R-linearly to a Clarke stationary value. We give references documenting the successful use of BFGS in a variety of nonsmooth applications, particularly the design of low-order controllers for linear dynamical systems. We conclude with a challenging open question.     

Factorized quasi-Newton methods for nonlinear least squares problems

This paper provides a modification to the Gauss—Newton method for nonlinear least squares problems. The new method is based on structured quasi-Newton methods which yield a good approximation to the second derivative matrix of the objective function. In particular, we propose BFGS-like and DFP-like updates in a factorized form which give descent search directions for the objective function. We prove local and q-superlinear convergence of our methods, and give results of computational experiments for the BFGS-like and DFP-like updates.This work was supported in part by the Grant-in-Aid for Encouragement of Young Scientists of the Japanese Ministry of Education: (A)61740133 and (A)62740137.     

Commutators with maximal Frobenius norm

It is known that for any nonzero complex n×n matrices X and Y the quotient of Frobenius norms

     

New quasi-Newton methods via higher order tensor models

Many researches attempt to improve the efficiency of the usual quasi-Newton (QN) methods by accelerating the performance of the algorithm without causing more storage demand. They aim to employ more available information from the function values and gradient to approximate the curvature of the objective function. In this paper we derive a new QN method of this type using a fourth order tensor model and show that it is superior with respect to the prior modification of Wei et al. (2006) [4]. Convergence analysis gives the local convergence property of this method and numerical results show the advantage of the modified QN method.     

A continuous updating weighted least squares estimator of tail dependence in high dimensions

Likelihood-based procedures are a common way to estimate tail dependence parameters. They are not applicable, however, in non-differentiable models such as those arising from recent max-linear structural equation models. Moreover, they can be hard to compute in higher dimensions. An adaptive weighted least-squares procedure matching nonparametric estimates of the stable tail dependence function with the corresponding values of a parametrically specified proposal yields a novel minimum-distance estimator. The estimator is easy to calculate and applies to a wide range of sampling schemes and tail dependence models. In large samples, it is asymptotically normal with an explicit and estimable covariance matrix. The minimum distance obtained forms the basis of a goodness-of-fit statistic whose asymptotic distribution is chi-square. Extensive Monte Carlo simulations confirm the excellent finite-sample performance of the estimator and demonstrate that it is a strong competitor to currently available methods. The estimator is then applied to disentangle sources of tail dependence in European stock markets.     

Nonsmooth multiobjective programming with quasi-Newton methods

This paper proposes a new algorithm to solve nonsmooth multiobjective programming. The algorithm is a descent direction method to obtain the critical point (a necessary condition for Pareto optimality). We analyze both global and local convergence results under some assumptions. Numerical tests are also given.     

Preconditioned GAOR methods for solving weighted linear least squares problems

In this paper, we present the preconditioned generalized accelerated overrelaxation (GAOR) method for solving linear systems based on a class of weighted linear least square problems. Two kinds of preconditioning are proposed, and each one contains three preconditioners. We compare the spectral radii of the iteration matrices of the preconditioned and the original methods. The comparison results show that the convergence rate of the preconditioned GAOR methods is indeed better than the rate of the original method, whenever the original method is convergent. Finally, a numerical example is presented in order to confirm these theoretical results.     

An iterative algorithm for the least Frobenius norm Hermitian and generalized skew Hamiltonian solutions of the generalized coupled Sylvester-conjugate matrix equations

The iterative method of the generalized coupled Sylvester-conjugate matrix equations \(\sum\limits _{j=1}^{l}\left (A_{ij}X_{j}B_{ij}+C_{ij}\overline {X}_{j}D_{ij}\right )=E_{i} (i=1,2,\cdots ,s)\) over Hermitian and generalized skew Hamiltonian solution is presented. When these systems of matrix equations are consistent, for arbitrary initial Hermitian and generalized skew Hamiltonian matrices X _j (1), j = 1,2,? , l, the exact solutions can be obtained by iterative algorithm within finite iterative steps in the absence of round-off errors. Furthermore, we provide a method for choosing the initial matrices to obtain the least Frobenius norm Hermitian and generalized skew Hamiltonian solution of the problem. Finally, numerical examples are presented to demonstrate the proposed algorithm is efficient.     

Zeros of functions in weighted spaces with mixed norm

In the spaces of analytic functions f in the unit disk with mixed norm and measure satisfying the Δ₂-condition, sharp necessary conditions on subsequences of zeros $\{ z_{n_k } (f)\} $ of the function f are obtained in terms of subsequences of numbers {n _k }. These conditions can be used to define, in the spaces with mixed norm, subsets of functions with certain extremal properties; these subsets provide answers to a number of questions about the zero sets of the spaces under consideration and, in particular, about weighted Bergman spaces.     

Composition operators with maximal norm on weighted Bergman spaces

We prove that any composition operator with maximal norm on one of the weighted Bergman spaces (in particular, on the space ) is induced by a disk automorphism or a map that fixes the origin. This result demonstrates a major difference between the weighted Bergman spaces and the Hardy space , where every inner function induces a composition operator with maximal norm.

     

Direct-prediction quasi-Newton methods in Hilbert space with applications to control problems

In this paper, the Hilbert-space analogue of a result of Huang, that all the methods in the Huang class generate the same sequence of points when applied to a quadratic functional with exact linear searches, is established. The convergence of a class of direct prediction methods based on some work of Dixon is then proved, and these methods are then applied to some control problems. Their performance is found to be comparable with methods involving exact linear searches.     

Forcing sparsity by projecting with respect to a non-diagonally weighted frobenius norm

This note deals with the computational problem of determining the projection of a given symmetric matrix onto the subspace of symmetric matrices that have a fixed sparsity pattern. This projection is performed with respect to a weighted Frobenius norm involving a metric that is not diagonal. It is shown that the solution to this question is computationally feasible when the metric appearing in the norm is a low rank modification to the identity. Also, generalization to perturbations of higher rank is shown to be increasingly costly in terms of computation.     

The principle of least constraint for systems with non-restoring constraints

Two new versions of the principle of least constraint are derived from the D'Alembert-Lagrange principle for systems with ideal holonomic and non-holonomic restoring and non-restoring constraints. The first version is similar to Boltzmann's and Bolotov's modification of Gauss's principle for systems with non-restoring constraints. The difference is that here the actual motion is determined in a certain bounded set of possible motions as the one that deviates least from the motion of the system with all non-restoring constraints and any part of the restoring constraints disengaged. According to the second version of the principle, the actual motion is found by comparing certain distinguished possible motions as to their deviation from the motion of the system obtained by eliminating any part of the non-restoring and any part of the restoring constraints. Examples are given.     

Condition numbers with their condition numbers for the weighted moore-penrose inverse and the weighted least squares solution

In this paper, the authors investigate the condition number with their condition numbers for weighted Moore-Penrose inverse and weighted least squares solution of $\mathop {\min }\limits_x ||Ax - b||_M $ , whereA is a rank-deficient complex matrix in ?^{m × n} andb a vector of lengthm in ?^m,x a vector of length n in ?ⁿ. For the normwise condition number, the sensitivity of the relative condition number itself is studied, the componentwise perturbation is also investigated.