Search

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

Bu tez çalışmasında bir takım parametrelere analitik olarak bağlı Hermit bir matrisin belirtilen bir özdeğerininin optimizasyonu üzerine yoğunlaşıyoruz. Bu yoğunlaştığımız çerçeve, sabit iz varsayımı altında doğrusal yarı belirgin programlama, şekil optimizasyonu ve yapısal tasarım problemleri, kontrol teorideki güçlü dengelilik ölçekleri gibi klasik uygulamalar tarafından motive ediliyor. Ana olarak ilgilendiğimiz bu tip büyük Hermit matrisler içeren özdeğer optimizasyonu problemleri, özellikle uygun alt uzaylara dik izdüşümler sayesinde bahsi geçen büyük Hermit matrislerinin boyutlarının indirgenmesi. Ama tez çalışmasında ek olarak bu özdeğer problemlerinin konveks olmayan doğaları ile de ilgileniyoruz.Çalışmaya iyi alt uzaylar üreten alt uzay çerçeveleri geliştirerek başlıyoruz. Her adımda dik izdüşümle elde edilen indirgenmiş ufak bir özdeğer optimizasyonu problemi çözülüyor, ardından alt uzaylar indirgenmiş problem ile orijinal büyük çaplı problem arasında indirgenmiş problemi optimize eden parametre değerlerinde bir takım Hermit özellikleri sağlanacak şekilde genişletiliyor. Alt uzay çerçeveleri için yakınsama analizini sonsuz boyutta, yani bu çerçevelerin parametrelere bağlı kendine eşlenik kompakt bir operatörün özdeğerlerinin optimizasyonu için uygulandığı durumda, gerçekleştiriyoruz. Bu sonsuz boyuttaki analizde (i) çerçevelerin Jinci en büyük özdeğerin mini- mizasyonu için uygulandığında boyut sonsuza yaklaştıkça global olarak en iyi çözüme yakınsadığını, (ii) yakınsama hızının alt uzayın boyutuna göre ve türevlenebilir durumda en az süper-doğrusal olduğunu kanıtlıyoruz. İkinci hızlı yakınsama sonucunun pratikteki etkisi önemli; büyüklüğü onbinler mertebesinde olan matrisler içeren özdeğer optimizasyonu problemleri, büyüklüğü onlar mertebesinde matrisler içeren indirgenmiş özdeğer optimizasyonu problemleri tarafından yaklaşık olarak ama yüksek doğruluk ile temsil edilebiliyor.Çalışmanın ikinci kısımını türevlenemeyen durumda, yani optimal parametre değerlerinde özdeğerin çoklu katsayıya sahip olduğu durumda, yakınsama hızı analizlerine adıyoruz. Buradaki analizler özel olarak tek bir parametreye bağlı bir Hermit matris fonksiyonunun en büyük özdeğerinin minimizasyonu problemi üzerinde gerçekleştiriliyor. İlk kısımdaki alt uzay çerçevelerinin genelleştirilmiş bir hali için kuadratik yakınsama sonucunu kanıtlıyoruz. Ayrıca, yine bu türevlenemeyen durumda, indirgenmiş problemlerin global çözümü için kullanılan ve parçalı kuadratik model fonksiyon tabanlı yöntemin hızlı yakınsadığını gösteriyoruz. Elde edilen teorik yakınsama hızı sonuçlarının, pratikte iç sayısal yarıçap hesabından kaynaklanan bir takım türevlenemeyen örnekler üzerinde sağlandığını gözlemliyoruz.En son olarak en büyük özdeğer fonksiyonunun amaç fonksiyonununda belirdiği minimum-maksimum türü optimizasyon problemlerinin üzerine yoğunlaşıyoruz. Ufak problemler için global olarak en iyi çözüme yakınsayan bir yöntem, ve büyük çaplı problemler için de, ilk kısımdaki çerçevelerden de ilham alarak, alt uzay çerçeveleri tasarlıyoruz. Tasarlanan alt uzay çerçevelerinin yine hızlı yakınsadığını kanıtlıyoruz. Bu teorik sonuçları pratikte sayısal yarıçapın minimizasyonu problemi üzerinde teyit ediyoruz. We deal with the optimization of a prescribed eigenvalue of a Hermitian matrix that depends onseveral parameters analytically. This setting is motivated by classical problems such as a linearsemidefinite program under a constant trace assumption, shape optimization and structural design problems, robust stability measures in control theory. Our primary interest is in the problemsinvolving large Hermitian matrices, in particular reducing their sizes by means of orthogonal projectionsonto appropriate subspaces. But some attention is also paid to the nonconvex nature of these problems.We start by devising subspace frameworks that yield good subspaces for orthogonal projections.At every step, a projected eigenvalue optimization problem is solved, then the subspaces areexpanded so that Hermite interpolation properties are attained between the projected problemand the original large-scale problem at the optimizer of the projected problem. Convergence analyses are conducted in the infinite dimensionalsetting when the eigenvalues of a self-adjoint compact operator dependent on parameters are optimized, specifically (i) convergence to a global minimizer is proven for the minimizationof the $J$th largest eigenvalue as the subspace dimension goes to infinity, (ii) a superlinear rate-of-convergence result is deduced in the smooth setting with respect to the subspace dimension. We observe the dramatic effects of the latter result in practice; problems on the order of tens of thousands are approximated accurately with projected problems in terms of matrices of sizes on the order of tens.The second part is devoted to rate-of-convergence analyses in the nonsmooth setting when the eigenvalue is not simple at the optimal parameter value. The analyses here are restrictedto the minimization of the largest eigenvalue of a Hermitian matrix dependent on one parameter.We establish a quadratic rate-of-convergence for a generalized version of the subspace frameworkfrom the first part. Additionally, for an algorithm to solve the projected problems that is guaranteed toconverge to globally optimal solutions and that is based on piece-wise quadratic model functions,a rapid convergence result is proven in this nonsmooth setting. The rate-of-convergence results are illustrated on several nonsmooth examples arising from the computation of the inner numerical radius, the modulus of the point on the boundary of the field of values closest to the origin.The third and the final part concerns the minimax problems with the largest eigenvalue in theobjective. We tailor a globally convergent algorithm for small problems, and a subspace frameworkinspired by the ones from the first part for large-scale problems. Once again we prove therapid convergence of the subspace framework. The theoretical results proven are confirmedin practice on an application, namely the minimization of the numerical radius, which is themodulus of the point in the field of values furthest away from the origin. 192

Wilkinson çoklu özdeğere sahip olmayan bir matristen çoklu özdeğere sahip matrislerkümesine uzaklığı, uzaklığın özdeğerlerin duyarlılığı ile ilintili olması yüzünden, 1960'ların sonunda çalıştı. Malyshev uzaklık için bir tekil değeri karakterizasyonu geliştirdi. Yakın zamanda Alam ve Bora uzaklığın yaklaşık spektrumunun bileşenlerinin birbirine değdiği en ufak değerine karşılık geldiğini kanıtladı. Ana amacımız uzaklık ile yaklaşık spektrum arasındaki bu ilintiyi genellemek. Önce Malyshev'in cebirsel karakterizasyonu ile Alam ve Bora'nin geometrik karakterizasyonunu ilişkilendirmeye calışıyoruz. Sonra bu tezin ana teması üzerine yoğunlaşıyoruz, genelleşmiş Wilkinson uzaklığı diye adlandırdığımız, verilen bir çokluk değerine sahip bir özdeğeri olan matrisler kümesine uzaklık ve bu uzaklığın yaklaşık spektrum cinsinden geometrik karakterizasyonu. Genelleşmiş yaklaşık spektrumu, verilen bir komşulukta bulunan bütün matrislerin verilen çokluk değerine sahip özdeğerler kümesi olarak tanımlıyoruz. Alam ve Bora'nın çalışmasının bir genellemesi olarak, genelleşmiş Wilkinson uzaklığı için genelleşmiş yaklaşık spektrumunun bileşenleri cinsinden bir üst sınırçıkarımı sunuyoruz. Wilkinson studied the distance from a square matrix with distinct eigenvalues to the set of defective matrices in 1960s due to its connection with the sensitivity of eigenvalues. Malyshev derived a singular value optimization characterization for the distance. Recently, Alam and Bora established that the distance to defectiveness from a matrix corresponds to the smallest epsilon such that two components of the epsilon-pseudospectrum of the matrix coalesce. Our main aim is to generalize this relation between the distance to defectiveness and the pseudospectra. First we attempt to relate the algebraic characterization of Malyshev and geometric characterization of Alam and Bora. Then we focus on the main theme of this thesis, the distance to the set of matrices with a multiple eigenvalue of prescribed algebraic multiplicity, which we call generalized Wilkinson distance, and its geometric characterization in terms of pseudospectra. We introduce the generalized pseudospectrum as the set comprised of eigenvalues of prescribed multiplicity of all matrices within a given neighborhood. As a generalization of the work of Alam and Bora, we derive an upper bound for the generalized Wilkinson distance in terms of the coalescence of components of the generalized pseudospectra. 53