An investigation of feasible descent algorithms for estimating the condition number of a matrix (Q1939108)

The authors analyse Hager's algorithm for estimating the \(1\)-norm condition number for a given square nonsingular matrix \(A\). This algorithm (implemented in the Matlab built-in function Condest) is a gradient method for computing a stationary point of \(\max\|Ax\|_1\) s.t. \(\|x\|_1=1\), with a starting vector \(x=(1/n,1/n,\dots,1/n)^T\). It is shown that this can be equivalently formulated as a conditional gradient algorithm for computing a stationary point of \(\max\|Ax\|_1\) s.t. \(e^Tx=1\), \(x\geq0\). The authors introduce a simplex formulation of the conditional gradient algorithm, and discuss a spectral projected gradient algorithm. The results are illustrated by several numerical experiments.