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

We focus on the dominant poles of the transfer function of a descriptor system. The transfer function typically exhibits a large norm at and near the imaginary parts of the dominant poles. Consequently, the dominant poles provide information about the points on the imaginary axis where the \scrL \infty norm of the system is attained, and they are also sometimes useful to obtain crude reduced order models. For a large-scale descriptor system, we introduce a subspace framework to estimate a prescribed number of dominant poles. At every iteration, the large-scale system is projected into a small system, whose dominant poles can be computed at ease. Then the projection spaces are expanded so that the projected system after subspace expansion Hermite interpolates the large-scale system at the computed dominant poles. We prove an at-least-quadratic-convergence result for the framework, and provide numerical results confirming this. On real benchmark examples, the proposed frameworks appears to be more reliable than SAMDP in Rommes and Martins [IEEE Trans. Power Syst. 21 (2006), pp. 1471-1483], one of the widely used algorithms for the estimation of the dominant poles, for which we provide a theoretical explanation., 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

The larger the distance to instability from a matrix is, the more robustly stable the associated autonomous dynamical system is in the presence of uncertainties and typically the less severe transient behavior its solution exhibits. Motivated by these issues, we consider the maximization of the distance to instability of a matrix dependent on several parameters, a nonconvex optimization problem that is likely to be nonsmooth. In the first part we propose a globally convergent algorithm when the matrix is of small size and depends on a few parameters. In the second part we deal with the problems involving large matrices. We tailor a subspace framework that reduces the size of the matrix drastically. The strength of the tailored subspace framework is proven with a global convergence result as the subspaces grow and a superlinear rate-of-convergence result with respect to the subspace dimension., 36 pages, 6 figures

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

Optimization of convex functions subject to eigenvalue constraints is intriguing because of peculiar analytical properties of eigenvalue functions and is of practical interest because of a wide range of applications in fields such as structural design and control theory. Here we focus on the optimization of a linear objective subject to a constraint on the smallest eigenvalue of an analytic and Hermitian matrix-valued function. We propose a numerical approach based on quadratic support functions that overestimate the smallest eigenvalue function globally. The quadratic support functions are derived by employing variational properties of the smallest eigenvalue function over a set of Hermitian matrices. We establish the local convergence of the algorithm under mild assumptions and deduce a precise rate of convergence result by viewing the algorithm as a fixed point iteration. The convergence analysis reveals that the algorithm is immune to the nonsmooth nature of the smallest eigenvalue. We illustrate the practical applicability of the algorithm on the pseudospectral functions.

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.

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

We consider the 2-norm distance tau(r)(A, B) from a linear time-invariant dynamical system (A, B) of order n to the nearest system (A + Delta A(*), B + Delta B-*) whose reachable subspace is of dimension r < n. We first present a characterization to test whether the reachable subspace of the system has dimension r, which resembles and can be considered as a generalization of the Popov-Belevitch-Hautus test for controllability. Then, by exploiting this generalized Popov-Belevitch-Hautus characterization, we derive the main result of this paper, which is a singular value optimization characterization for tau(r)(A, B). A numerical technique to solve the derived singular value optimization problems is described. The numerical results on a few examples illustrate the significance of the derived singular value characterization for computational purposes., European Commision; Scientific and Technological Research Council of Turkey (TÜBİTAK)

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

Structured eigenvalue problems feature a prominent role in many algorithms for the computation of robust measures for the stability or controllability of a linear control system. Structures that typically arise are Hamiltonian, skew-Hamiltonian, and symplectic. The use of eigenvalue solvers that preserve such structures can enhance the reliability and efficiency of algorithms for robust stability and controllability measures. This aspect is the focus of the present work, which summarizes and extends existing structure-preserving eigenvalue solvers. Also, a new method for estimating the distance to uncontrollability in a cheap manner is presented. The structured eigenvalue algorithms described in this paper are intented to become part of HAPACK, a software package for solving structured eigenvalue problems and applications.

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