Search

We deal with the minimization of the ${\mathcal H}_\infty$-norm of the transfer function of a parameter-dependent descriptor system over the set of admissible parameter values. Subspace frameworks ...

Nonsmoothness at optimal points is a common phenomenon in many eigenvalue optimization problems. We consider two recent algorithms to minimize the largest eigenvalue of a Hermitian matrix dependent on one parameter, both proven to be globally convergent unaffected by nonsmoothness. One of these algorithms models the eigenvalue function with a piece-wise quadratic function and is effective in dealing with nonconvex problems. The other algorithm projects the Hermitian matrix into subspaces formed of eigenvectors and is effective in dealing with large-scale problems. We generalize the latter slightly to cope with nonsmoothness. For both algorithms we analyze the rate of convergence in the nonsmooth setting, when the largest eigenvalue is multiple at the minimizer and zero is strictly in the interior of the generalized Clarke derivative, and prove that both algorithms converge rapidly. The algorithms are applied to, and the deduced results are illustrated on the computation of the inner numerical radius, the modulus of the point on the boundary of the field of values closest to the origin, which carries significance for instance for the numerical solution of a symmetric definite generalized eigenvalue problem and the iterative solution of a saddle point linear system., NA

A linear time-invariant dissipative Hamiltonian (DH) system (x) over dot = (J-R)Qx, with a skew-Hermitian J, a Hermitian positive semidefinite R, and a Hermitian positive definite Q, is always Lyapunov stable and under further weak conditions even asymptotically stable. By exploiting the characterizations from Mehl et al. (SIAM J. Matrix Anal. Appl. 37(4), 1625-1654, 2016), we focus on the estimation of two stability radii for large-scale DH systems, one with respect to non-Hermitian perturbations of R in the form R + B Delta C-H for given matrices B, C, and another with respect to Hermitian perturbations in the form R + B Delta B-H, Delta = Delta(H). We propose subspace frameworks for both stability radii that converge at a superlinear rate in theory. The one for the non-Hermitian stability radius benefits from the DH structure-preserving model order reduction techniques, whereas for the Hermitian stability radius we derive subspaces yielding a Hermite interpolation property between the full and projected problems. With the proposed frameworks, we are able to estimate the two stability radii accurately and efficiently for large-scale systems which include a finite-element model of an industrial disk brake., Deutsche Forschungsgemeinschaft, Project ME 40-1 of Priority Program 1897, Calm, Smooth and Smart; Deutsche Forschungsgemeinschaft, Project A02 of Sonderforschungsbereich 910

We present a method for the certification of algorithms that approximate the L-infinity or H-infinity-norm of transfer functions of large-scale (descriptor) systems. This certification is needed because such algorithms depend heavily on user input, and may converge to a local maximizer of the related singular value function leading to an incorrect value, much lower than the actual norm. Hence, we design an algorithm that determines whether a given value is less than the L-infinity-norm of the transfer function under consideration, and that does not require user input other than the system matrices. In the algorithm, we check whether a certain structured matrix pencil has any purely imaginary eigenvalues by repeatedly applying a structure-preserving shift-and-invert Arnoldi iteration combined with an appropriate shifting strategy. Our algorithm consists of two stages. First, an interval on the imaginary axis which may contain imaginary eigenvalues is determined. Then, in the second stage, a shift is chosen on this interval and the eigenvalues closest to this shift are computed. If none of these eigenvalues is purely imaginary, then an imaginary interval around the shift of appropriate length is removed such that two subintervals remain. This second stage is then repeated on the remaining two subintervals until either a purely imaginary eigenvalue is found or no critical subintervals are left. We show the effectiveness of our method by testing it without any parameter adaptation on a benchmark collection of large-scale systems., German Research Foundation (DFG); Berlin International Graduate School in Model and Simulation Based Research (BIMoS)

We are concerned with the computation of the ${\mathcal L}_\infty$-norm for an ${\mathcal L}_\infty$-function of the form $H(s) = C(s) D(s)^{-1} B(s)$, where the middle factor is the inverse of a meromorphic matrix-valued function, and $C(s),\, B(s)$ are meromorphic functions mapping to short-and-fat and tall-and-skinny matrices, respectively. For instance, transfer functions of descriptor systems and delay systems fall into this family. We focus on the case where the middle factor is large-scale. We propose a subspace projection method to obtain approximations of the function $H$ where the middle factor is of much smaller dimension. The ${\mathcal L}_\infty$-norms are computed for the resulting reduced functions, then the subspaces are refined by means of the optimal points on the imaginary axis where the ${\mathcal L}_\infty$-norm of the reduced function is attained. The subspace method is designed so that certain Hermite interpolation properties hold between the largest singular values of the original and reduced functions. This leads to a locally superlinearly convergent algorithm with respect to the subspace dimension, which we prove and illustrate on various numerical examples., Comment: 23 pages, 3 figures

We propose subspace methods for three-parameter eigenvalue problems. Such problems arise when separation of variables is applied to separable boundary value problems; a particular example is the Helmholtz equation in ellipsoidal and paraboloidal coordinates. While several subspace methods for two-parameter eigenvalue problems exist, their extensions to a three-parameter setting seem challenging. An inherent difficulty is that, while for two-parameter eigenvalue problems, we can exploit a relation to Sylvester equations to obtain a fast Arnoldi-type method, such a relation does not seem to exist when there are three or more parameters. Instead, we introduce a subspace iteration method with projections onto generalized Krylov subspaces that are constructed from scratch at every iteration using certain Ritz vectors as the initial vectors. Another possibility is a Jacobi-Davidson-type method for three or more parameters, which we generalize from its two-parameter counterpart. For both approaches, we introduce a selection criterion for deflation that is based on the angles between left and right eigenvectors. The Jacobi-Davidson approach is devised to locate eigenvalues close to a prescribed target; yet, it often also performs well when eigenvalues are sought based on the proximity of one of the components to a prescribed target. The subspace iteration method is devised specifically for the latter task. The proposed approaches are suitable especially for problems where the computation of several eigenvalues is required with high accuracy. MATLAB implementations of both methods have been made available in the package MultiParEig (see https://www.mathworks.com/matlabcentral/fileexchange/47844-multipareig)., Scientific and Technological Research Council of Turkey (TÜBİTAK); Slovenian Research Agency; Slovenia and Turkey bilateral project; NWO Vidi research grant

Purpose: To quantitatively analyze in vivo morphology of subfoveal choroid during an acute attack of Behçet uveitis. Methods: In this prospective study, 28 patients with Behçet uveitis of, Istanbul University

We present an algorithm to compute the pseudospectral abscissa for a nonlinear eigenvalue problem. The algorithm relies on global under-estimator and over-estimator functions for the eigenvalue and singular value functions involved. These global models follow from eigenvalue perturbation theory. The algorithm has three particular features. First, it converges to the globally rightmost point of the pseudospectrum, and it is immune to nonsmoothness. The global convergence assertion is under the assumption that a global lower bound is available for the second derivative of a singular value function depending on one parameter. It may not be easy to deduce such a lower bound analytically, but assigning large negative values works robustly in practice. Second, it is applicable to large-scale problems since the dominant cost per iteration stems from computing the smallest singular value and associated singular vectors, for which efficient iterative solvers can be used. Furthermore, a significant increase in computational efficiency can be obtained by subspace acceleration, that is, by restricting the domains of the linear maps associated with the matrices involved to small but suitable subspaces, and solving the resulting reduced problems. Occasional restarts of these subspaces further enhance the efficiency for large-scale problems. Finally, in contrast to existing iterative approaches based on constructing low-rank perturbations and rightmost eigenvalue computations, the algorithm relies on computing only singular values of complex matrices. Hence, the algorithm does not require solutions of nonlinear eigenvalue problems, thereby further increasing efficiency and reliability. This work is accompanied by a robust implementation of the algorithm that is publicly available., The Optimization in Engineering Center of the KU Leuven; Research Foundation-Flanders (FWO); Research Executive Agency of the European Union; Scientific and Technological Research Council of Turkey (TÜBİTAK); BAGEP Program of Science Academy

We consider the distance from a (square or rectangular) matrix pencil to the nearest matrix pencil in 2-norm that has a set of specified eigenvalues. We derive a singular value optimization characterization for this problem and illustrate its usefulness for two applications. First, the characterization yields a singular value formula for determining the nearest pencil whose eigenvalues lie in a specified region in the complex plane. For instance, this enables the numerical computation of the nearest stable descriptor system in control theory. Second, the characterization partially solves the problem posed in [Boutry et al. 2005] regarding the distance from a general rectangular pencil to the nearest pencil with a complete set of eigenvalues. The involved singular value optimization problems are solved by means of BFGS and Lipschitz-based global optimization algorithms., Comment: 23 pages with 3 pdf figures

The Wilkinson distance of a matrix A is the two-norm of the smallest perturbation E so that A + E has a multiple eigenvalue. Malyshev derived a singular value optimization characterization for the Wilkinson distance. In this work we generalize the definition of the Wilkinson distance as the two-norm of the smallest perturbation so that the perturbed matrix has an eigenvalue of prespecified algebraic multiplicity. We provide a singular value characterization for this generalized Wilkinson distance. Then we outline a numerical technique to solve the derived singular value optimization problems. In particular the numerical technique is applicable to Malyshev's formula to compute the Wilkinson distance as well as to retrieve a nearest matrix with a multiple eigenvalue.

The distance to uncontrollability for a linear control system is the distance (in the 2-norm) to the nearest uncontrollable system. We present an algorithm based on methods of Gu and Burke-Lewis-Overton that estimates the distance to uncontrollability to any prescribed accuracy. The new method requires O(n4) operations on average, which is an improvement over previous methods which have complexity O(n6), where n is the order of the system. Numerical experiments indicate that the new method is reliable in practice.

Two useful measures of the robust stability of the discrete-time dynamical system xk+1 = Axk are the � -pseudospectral radius and the numerical radius of A. The � -pseudospectral radius of A is the largest of the moduli of the points in the � -pseudospectrum of A, while the numerical radius is the largest of the moduli of the points in the field of values. We present globally convergent algorithms for computing the � -pseudospectral radius and the numerical radius. For the former algorithm, we discuss conditions under which it is quadratically convergent and provide a detailed accuracy analysis giving conditions under which the algorithm is backward stable. The algorithms are inspired by methods of Byers, Boyd– Balakrishnan, He–Watson and Burke–Lewis–Overton for related problems and depend on computing eigenvalues of symplectic pencils and Hamiltonian matrices.

This work considers eigenvalue problems that are nonlinear in the eigenvalue parameter. Given such a nonlinear eigenvalue problem T, we are concerned with finding the minimal backward error such that T has a set of prescribed eigenvalues with prescribed algebraic multiplicities. We consider backward errors that only allow constant perturbations, which do not depend on the eigenvalue parameter. While the usual resolvent norm addresses this question for a single eigenvalue of multiplicity one, the general setting involving several eigenvalues is significantly more difficult. Under mild assumptions, we derive a singular value optimization characterization for the minimal perturbation that addresses the general case., European Commission; Scientific and Technological Research Council of Turkey (TÜBİTAK); BAGEP program of Turkish Academy of Science

This work concerns the distance in 2-norm from a matrix polynomial to a nearest polynomial with a specified number of its eigenvalues at specified locations in the complex plane. Perturbations are allowed only on the constant coefficient matrix. Singular value optimization formulas are derived for these distances facilitating their computation. The singular value optimization problems, when the number of specified eigenvalues is small, can be solved numerically by exploiting the Lipschitzness and piece-wise analyticity of the singular values with respect to the parameters., Comment: 19 pages, 2 figures

This work concerns the global minimization of a prescribed eigenvalue or a weighted sum of prescribed eigenvalues of a Hermitian matrix-valued function depending on its parameters analytically in a box. We describe how the analytical properties of eigenvalue functions can be put into use to derive piece-wise quadratic functions that underestimate the eigenvalue functions. These piece-wise quadratic under-estimators lead us to a global minimization algorithm, originally due to Breiman and Cutler. We prove the global convergence of the algorithm, and show that it can be effectively used for the minimization of extreme eigenvalues, e.g., the largest eigenvalue or the sum of the largest specified number of eigenvalues. This is particularly facilitated by the analytical formulas for the first derivatives of eigenvalues, as well as analytical lower bounds on the second derivatives that can be deduced for extreme eigenvalue functions. The applications that we have in mind also include the ${\rm H}_\infty$-norm of a linear dynamical system, numerical radius, distance to uncontrollability and various other non-convex eigenvalue optimization problems, for which, generically, the eigenvalue function involved is simple at all points., 25 pages, 3 figures

We consider the minimization or maximization of the Jth largest eigenvalue of an analytic and Hermitian matrix-valued function, and build on Mengi, Yildirim, and Kilic [SIAM T. Matrix Anal. Appl., 35, pp. 699-724, 2014]. This work addresses the setting when the matrix-valued function involved is very large. We describe subspace procedures that convert the original problem into a small-scale one by means of orthogonal projections and restrictions to certain subspaces, and that gradually expand these subspaces based on the optimal solutions of small-scale problems. Global convergence and superlinear rate-of-convergence results with respect to the dimensions of the subspaces are presented in the infinite dimensional setting, where the matrix-valued function is replaced by a compact operator depending on parameters. In practice, it suffices to solve eigenvalue optimization problems involving matrices with sizes on the scale of tens, instead of the original problem involving matrices with sizes on the scale of thousands., OPTEC; Optimization in Engineering Center of KU Leuven; Research Foundation Flanders; project UCoCoS; European Union; European Commision; Scientific and Technological Research Council of Turkey (TÜBİTAK) - FWO (Scientific and Technological Research Council of Turkey (TÜBİTAK) - Belgian Research Foundation, Flanders); BAGEP program of The Science Academy of Turkey