Eigenvalue optimization of Hermitian functions-theory, applications and algorithms

Abstract

Bu tezde parametrelerine analitik olarak bağlı Hermit bir matris fonksiyonunun belirtilen bir ?ozdeğerinin en ufak değerinin bulunması üzerine yoğunlaşıyoruz. Bu problemin global olarak en iyi çözümünü bulmak için Breiman ve Cutler algoritmasının bir uzantısını sunuyoruz. Algoritma Hermit matris fonsiyonunun özdeğerlerinin ikinci türevlerinin sınırlı olmasını kullanmakta ve global olarak en iyi çözüme yakınsıyor. Özdeğer fonksiyonunun altında yatan parçalı sürekli kuadratik fonksiyonların global minimumunu tekrar tekrar bulma fikri üzerine kurulu. Çok boyutlu durumda ise bu parçalı-kuadratik fonksiyonun global minimumu bir kuadratik optimizasyon probleminin çözümü olarak ifade edilebilir. Kuadratik fonksiyonları oluşturmak için kullanılan özdeğer fonksiyonlarının türevleri, bu algoritmanın geleneksel global optimizasyon algoritmalarına göre daha hızlı yakınsamasını sağlıyor. Ayrıca bu tezde (i) Hermit matris fonksiyonlarının özdeğerlerinin analitik özellikleri, (ii) özdeğer optimizasyon problemlerinin uygulamaları, ve (iii) varolan algoritmalar ile ilgili literatür taramalarına yer verilmekte. Son olarak algoritmanın asimtotik yakınsama özellikleri nümerik olarak dengesizlik mesafesi, Crawford numarası ve en yakındaki kusurlu bir matrise uzaklık problemleri üzerinde gösterilmiştir.

In this thesis we describe an algorithm to find the globally minimal value of a specified eigenvalue of a Hermitian matrix function depending on its parameters analytically. The algorithm exploits the boundedness of the second derivatives of the eigenvalues, and is globally convergent. It is based on the determination of the globally minimal value of a piece-wise quadratic under-estimator for the eigenvalue function repeatedly, and can be considered as an extension of an algorithm due to Breiman and Cutler. In the multi-variate case determining this globally minimal value can be posed as a quadratic program. The derivatives of the eigenvalue functions are used to construct quadratic models yielding rapid global convergence as compared to traditional global optimization algorithms. We also provide surveys on (i) the analytical properties of eigenvalues of Hermitian matrix functions, (ii) applications of the eigenvalue optimization, and (iii) existing numerical algorithms. Finally, we illustrate the asymptotic convergence behavior of the algorithm on numerical examples related to the distance to instability and distance to a nearest defective matrix from a given matrix as well as the Crawford number.