Two properties of condition numbers for convex programs via implicitly defined barrier functions

We study two issues on condition numbers for convex programs: one has to do with the growth of the condition numbers of the linear equations arising in interior-point algorithms; the other deals with solving conic systems and estimating their distance to infeasibility.?These two issues share a common ground: the key tool for their development is a simple, novel perspective based on implicitly-defined barrier functions. This tool has potential use in optimization beyond the context of condition numbers. Received: October 2000 / Accepted: October 2001?Published online March 27, 2002     

Computing approximate solutions for convex conic systems of constraints

We propose a way to reformulate a conic system of constraints as an optimization problem. When an appropriate interior-point method (ipm) is applied to the reformulation, the ipm iterates yield backward-approximate solutions, that is, solutions for nearby conic systems. In addition, once the number of ipm iterations passes a certain threshold, the ipm iterates yield forward-approximate solutions, that is, points close to an exact solution of the original conic system. The threshold is proportional to the reciprocal of distance to ill-posedness of the original conic system.?The condition numbers of the linear equations encountered when applying an ipm influence the computational cost at each iteration. We show that for the reformulation, the condition numbers of the linear equations are uniformly bounded both when computing reasonably-accurate backward-approximate solutions to arbitrary conic systems and when computing forward-approximate solutions to well-conditioned conic systems. Received: July 11, 1997 / Accepted: August 18, 1999?Published online March 15, 2000     

Convergence of Newton's method for convex best interpolation

Summary. In this paper, we consider the problem of finding a convex function which interpolates given points and has a minimal norm of the second derivative. This problem reduces to a system of equations involving semismooth functions. We study a Newton-type method utilizing Clarke's generalized Jacobian and prove that its local convergence is superlinear. For a special choice of a matrix in the generalized Jacobian, we obtain the Newton method proposed by Irvine et al. [17] and settle the question of its convergence. By using a line search strategy, we present a global extension of the Newton method considered. The efficiency of the proposed global strategy is confirmed with numerical experiments. Received October 26, 1998 / Revised version received October 20, 1999 / Published online August 2, 2000     

Existence and uniqueness of splittings for stationary iterative methods with applications to alternating methods

Summary. Given a nonsingular matrix , and a matrix of the same order, under certain very mild conditions, there is a unique splitting , such that . Moreover, all properties of the splitting are derived directly from the iteration matrix . These results do not hold when the matrix is singular. In this case, given a matrix and a splitting such that , there are infinitely many other splittings corresponding to the same matrices and , and different splittings can have different properties. For instance, when is nonnegative, some of these splittings can be regular splittings, while others can be only weak splittings. Analogous results hold in the symmetric positive semidefinite case. Given a singular matrix , not for all iteration matrices there is a splitting corresponding to them. Necessary and sufficient conditions for the existence of such splittings are examined. As an illustration of the theory developed, the convergence of certain alternating iterations is analyzed. Different cases where the matrix is monotone, singular, and positive (semi)definite are studied. Received September 5, 1995 / Revised version received April 3, 1996     

Comparison theorems for splittings of matrices

Summary. This paper investigates the comparisons of asymptotic rates of convergence of two iteration matrices. On the basis of nonnegative matrix theory, comparisons between two nonnegative splittings and between two parallel multisplitting methods are derived. When the coefficient matrix A is Hermitian positive (semi)definite, comparison theorems about two P-regular splittings and two parallel multisplitting methods are proved. Received April 4, 1998 / Revised version received October 18, 1999 / Published online November 15, 2001     

Scaled total least squares fundamentals

Summary. The standard approaches to solving overdetermined linear systems construct minimal corrections to the vector c and/or the matrix B such that the corrected system is compatible. In ordinary least squares (LS) the correction is restricted to c, while in data least squares (DLS) it is restricted to B. In scaled total least squares (STLS) [22], corrections to both c and B are allowed, and their relative sizes depend on a real positive parameter . STLS unifies several formulations since it becomes total least squares (TLS) when , and in the limit corresponds to LS when , and DLS when . This paper analyzes a particularly useful formulation of the STLS problem. The analysis is based on a new assumption that guarantees existence and uniqueness of meaningful STLS solutions for all parameters . It makes the whole STLS theory consistent. Our theory reveals the necessary and sufficient condition for preserving the smallest singular value of a matrix while appending (or deleting) a column. This condition represents a basic matrix theory result for updating the singular value decomposition, as well as the rank-one modification of the Hermitian eigenproblem. The paper allows complex data, and the equivalences in the limit of STLS with DLS and LS are proven for such data. It is shown how any linear system can be reduced to a minimally dimensioned core system satisfying our assumption. Consequently, our theory and algorithms can be applied to fully general systems. The basics of practical algorithms for both the STLS and DLS problems are indicated for either dense or large sparse systems. Our assumption and its consequences are compared with earlier approaches. Received June 2, 1999 / Revised version received July 3, 2000 / Published online July 25, 2001     

Componentwise perturbation analyses for the QR factorization

Summary. This paper gives componentwise perturbation analyses for Q and R in the QR factorization A=QR, , R upper triangular, for a given real $m\times n$ matrix A of rank n. Such specific analyses are important for example when the columns of A are badly scaled. First order perturbation bounds are given for both Q and R. The analyses more accurately reflect the sensitivity of the problem than previous such results. The condition number for R is bounded for a fixed n when the standard column pivoting strategy is used. This strategy also tends to improve the condition of Q, so usually the computed Q and R will both have higher accuracy when we use the standard column pivoting strategy. Practical condition estimators are derived. The assumptions on the form of the perturbation are explained and extended. Weaker rigorous bounds are also given. Received April 11, 1999 / Published online October 16, 2000     

Convex programming for disjunctive convex optimization

Given a finite number of closed convex sets whose algebraic representation is known, we study the problem of finding the minimum of a convex function on the closure of the convex hull of the union of those sets. We derive an algebraic characterization of the feasible region in a higher-dimensional space and propose a solution procedure akin to the interior-point approach for convex programming. Received November 27, 1996 / Revised version received June 11, 1999?Published online November 9, 1999     

Integrated simulation and optimization models for tracking international fixed income indices

Portfolio managers in the international fixed income markets must address jointly the interest rate risk in each market and the exchange rate volatility across markets. This paper develops integrated simulation and optimization models that address these issues in a common framework. Monte Carlo simulation procedures generate jointly scenarios of interest and exchange rates and, thereby, scenarios of holding period returns of the available securities. The portfolio manager’s risk tolerance is incorporated either through a utility function or a (modified) mean absolute deviation function. The optimization models prescribe asset allocation weights among the different markets and also resolve bond-picking decisions. Therefore several interrelated decisions are cast in a common framework. Two models – an expected utility maximization and a mean absolute deviation minimization – are implemented and tested empirically in tracking a composite index of the international bond markets. Backtesting over the period January 1997 to July 1998 illustrate the efficacy of the optimization models in dealing with uncertainty and tracking effectively the volatile index. Of particular interest is the empirical demostration that the integrative models generate portfolios that dominate the portfolios obtained using classical disintegrated approaches. Received: November 24, 1998 / Accepted: October 1, 2000?Published online December 15, 2000     

Moment inequalities and central limit properties of isotropic convex bodies

The object of our investigations are isotropic convex bodies , centred at the origin and normed to volume one, in arbitrary dimensions. We show that a certain subset of these bodies – specified by bounds on the second and fourth moments – is invariant under forming ‘expanded joinsrsquo;. Considering a body K as above as a probability space and taking , we define random variables on K. It is known that for subclasses of isotropic convex bodies satisfying a ‘concentration of mass property’, the distributions of these random variables are close to Gaussian distributions, for high dimensions n and ‘most’ directions . We show that this ‘central limit property’, which is known to hold with respect to convergence in law, is also true with respect to -convergence and -convergence of the corresponding densities. Received: 21 March 2001 / in final form: 17 October 2001 / Published online: 4 April 2002     

Backward errors for eigenvalue and singular value decompositions

Summary. We present bounds on the backward errors for the symmetric eigenvalue decomposition and the singular value decomposition in the two-norm and in the Frobenius norm. Through different orthogonal decompositions of the computed eigenvectors we can define different symmetric backward errors for the eigenvalue decomposition. When the computed eigenvectors have a small residual and are close to orthonormal then all backward errors tend to be small. Consequently it does not matter how exactly a backward error is defined and how exactly residual and deviation from orthogonality are measured. Analogous results hold for the singular vectors. We indicate the effect of our error bounds on implementations for eigenvector and singular vector computation. In a more general context we prove that the distance of an appropriately scaled matrix to its orthogonal QR factor is not much larger than its distance to the closest orthogonal matrix. Received July 19, 1993     

Superlinear convergence rates for the Lanczos method applied to elliptic operators

Summary. This paper investigates the convergence of the Lanczos method for computing the smallest eigenpair of a selfadjoint elliptic differential operator via inverse iteration (without shifts). Superlinear convergence rates are established, and their sharpness is investigated for a simple model problem. These results are illustrated numerically for a more difficult problem. Received March 8, 1996     

Bounds for the least squares distance using scaled total least squares

Summary. The standard approaches to solving overdetermined linear systems construct minimal corrections to the data to make the corrected system compatible. In ordinary least squares (LS) the correction is restricted to the right hand side c, while in scaled total least squares (STLS) [14,12] corrections to both c and B are allowed, and their relative sizes are determined by a real positive parameter . As , the STLS solution approaches the LS solution. Our paper [12] analyzed fundamentals of the STLS problem. This paper presents a theoretical analysis of the relationship between the sizes of the LS and STLS corrections (called the LS and STLS distances) in terms of . We give new upper and lower bounds on the LS distance in terms of the STLS distance, compare these to existing bounds, and examine the tightness of the new bounds. This work can be applied to the analysis of iterative methods which minimize the residual norm, and the generalized minimum residual method (GMRES) [15] is used here to illustrate our theory. Received July 20, 2000 / Revised version received February 28, 2001 / Published online July 25, 2001     

Conditioning analysis of block incomplete factorizations and its application to elliptic equations

Summary. The paper deals with eigenvalue estimates for block incomplete factorization methods for symmetric matrices. First, some previous results on upper bounds for the maximum eigenvalue of preconditioned matrices are generalized to each eigenvalue. Second, upper bounds for the maximum eigenvalue of the preconditioned matrix are further estimated, which presents a substantial improvement of earlier results. Finally, the results are used to estimate bounds for every eigenvalue of the preconditioned matrices, in particular, for the maximum eigenvalue, when a modified block incomplete factorization is used to solve an elliptic equation with variable coefficients in two dimensions. The analysis yields a new upper bound of type for the condition number of the preconditioned matrix and shows clearly how the coefficients of the differential equation influence the positive constant . Received March 27, 1996 / Revised version received December 27, 1996     

Orthogonal polynomials and semi-iterative methods for the Drazin-inverse solution of singular linear systems

Summary. In this work we present a novel class of semi-iterative methods for the Drazin-inverse solution of singular linear systems, whether consistent or inconsistent. The matrices of these systems are allowed to have arbitrary index and arbitrary spectra in the complex plane. The methods we develop are based on orthogonal polynomials and can all be implemented by 4-term recursion relations independently of the index. We give all the computational details of the associated algorithms. We also give a complete convergence analysis for all methods. Received June 28, 2000 / Revised version received May 23, 2001 / Published online January 30, 2002     

Solving the Gleason problem on linearly convex domains

Let be a bounded, connected linearly convex set in with boundary. We show that the maximal ideal (both in ) and ) consisting of all functions vanishing at is generated by the coordinate functions . Received: 2 July 2001; in final form: 26 September 2001 / Published online: 28 February 2002     

An always successful method in univariate convex C^2 interpolation

Summary. We consider convex interpolation with cubic splines on grids built by adding two knots in each subinterval of neighbouring data sites. The additional knots have to be variable in order to get a chance to always retain convexity. By means of the staircase algorithm we provide computable intervals for the added knots such that all knots from these intervals allow convexity preserving spline interpolation of continuity. Received May 31, 1994 / Revised version received December 22, 1994     

Line search termination criteria for collinear scaling algorithms for minimizing a class of convex functions

Summary. Many successful quasi-Newton methods for optimization are based on positive definite local quadratic approximations to the objective function that interpolate the values of the gradient at the current and new iterates. Line search termination criteria used in such quasi-Newton methods usually possess two important properties. First, they guarantee the existence of such a local quadratic approximation. Second, under suitable conditions, they allow one to prove that the limit of the component of the gradient in the normalized search direction is zero. This is usually an intermediate result in proving convergence. Collinear scaling algorithms proposed initially by Davidon in 1980 are natural extensions of quasi-Newton methods in the sense that they are based on normal conic local approximations that extend positive definite local quadratic approximations, and that they interpolate values of both the gradient and the function at the current and new iterates. Line search termination criteria that guarantee the existence of such a normal conic local approximation, which also allow one to prove that the component of the gradient in the normalized search direction tends to zero, are not known. In this paper, we propose such line search termination criteria for an important special case where the function being minimized belongs to a certain class of convex functions. Received February 1, 1997 / Revised version received September 8, 1997     

Local convergence of the (exact and inexact) iterative aggregation method for linear systems and Markov operators

Summary. The iterative aggregation method for the solution of linear systems is extended in several directions: to operators on Banach spaces; to the method with inexact correction, i.e., to methods where the (inner) linear system is in turn solved iteratively; and to the problem of finding stationary distributions of Markov operators. Local convergence is shown in all cases. Convergence results apply to the particular case of stochastic matrices. Moreover, an argument is given which suggests why the iterative aggregation method works so well for nearly uncoupled Markov chains, as well as for Markov chains with other zero-nonzero structures. Received May 25, 1991/Revised version received February 23, 1994     

A numerically stable, structure preserving method for computing the eigenvalues of real Hamiltonian or symplectic pencils

A new method is presented for the numerical computation of the generalized eigenvalues of real Hamiltonian or symplectic pencils and matrices. The method is numerically backward stable and preserves the structure (i.e., Hamiltonian or symplectic). In the case of a Hamiltonian matrix the method is closely related to the square reduced method of Van Loan, but in contrast to that method which may suffer from a loss of accuracy of order , where is the machine precision, the new method computes the eigenvalues to full possible accuracy. Received April 8, 1996 / Revised version received December 20, 1996