Majorization and k-majorization as an approach to some problems in optimization and eigenvalue estimation

Abstract

Ekonomistien pyrkimykset määritellä mitta tulonjaon epätasaisuudelle ja toisaalta matemaatikkojen eräitä epäyhtälöitä koskevat tutkimukset johtivat majoroinnin teorian syntymiseen 1900-luvun alkupuolella. Majorointi asettaa osittaiseen järjestykseen sellaiset vektorit x = (x[1], x[2], ,x[n]), joiden alkioiden summa x[1]+ x[2]+ +x[n] on sama. Jos vektorit x ja y ovat verrattavissa, niin y majoroi x:n, jos x:n alkiot ovat tasaisemmin jakautuneet kuin y:n. Väitöskirjassa sovelletaan majorointia ja sille esitettävää yleistystä eräiden optimointitehtävien ratkaisemisessa ja matriisin ominaisarvojen arvioimisessa.

Oletetaan, että vektoreissa on n alkiota, jotka on järjestetty vähenevästi. Merkinnällä S(x) tarkoitetaan vektorin x kaikkien alkioiden summaa ja merkinnällä S[i,j](x) osasummaa x[i]+x[i+1]+ +x[j]. Majorointi voidaan määritellä vektorien alkioiden osasummien avulla seuraavasti: y majoroi x:n, jos S(y) = S(x) ja S[1,j](y) on suurempi tai yhtäsuuri kuin S[1,j](x), kun j=1,2, ,n. Väitöskirjassa kehitelty k-majorointi on eräs luonteva majoroinnin yleistys. Sen lähtökohtana on seuraava vaihtoehtoinen määritelmä majoroinnille: vektori y majoroi vektorin x, jos ja vain jos y saadaan x:stä soveltamalla siihen peräkkäisiä positiivisia siirtoja. Jälkimmäisellä tarkoitetaan operaatiota, joka kasvattaa alkiota x[i] ja vähentää alkiota x[j] (j Myös k-majorointi määrää vektoreiden joukossa osittaisen järjestyksen. Alkutilanne on vain mutkikkaampi. Ensinnäkin tarkasteltavilla vektoreilla ajatellaan olevan muitakin yhteisiä relevantteja ominaisuuksia kuin alkioiden summa. Toiseksi, kun majorointia vastaavassa positiivisessa siirrossa muuttuu kahden alkion arvo, niin k-siirrossa muuttuu k:n alkion arvo. Vastatkoon relevantteja yhteisiä ominaisuuksia vektorijoukko Z. Positiivisessa Z-konsistentissa k-siirrossa valitaan k alkiota ja muutetaan vuorotellen niiden arvoja niin, että suurinta niistä kasvatetaan, toiseksi suurinta vähennetään, kolmanneksi suurinta taas kasvatetaan jne. Saadun vektorin alkioiden on oltava edelleen vähenevästi järjestetty (eli muutokset eivät saa olla liian suuria), ja senkin on kuuluttava joukkoon Z. Positiivinen siirto on tämän määritelmän näkökulmasta positiivinen {x : S(x)=a}-konsistentti 2-siirto. Väitöskirjassa määritellään, että vektori y k-majoroi vektorin x joukossa Z, jos y saadaan x:stä peräkkäisillä positiivisilla Z-konsistenteilla k-siirroilla.

Erityisesti tutkitaan 3-majorointia joukossa Z(S,a;G,b) = {x : S(x)=a ja G(x)=b}. Tässä G on Schur-konveksi funktio eli funktio, joka säilyttää järjestyksen majoroinnin suhteen. Väitöskirjassa johdetaan tätä 3-majorointia koskevia tuloksia ja sovelletaan niitä. Tärkeimpiä tuloksia ovat luonnehdinnat funktioista, jotka säilyttävät järjestyksen tämänkaltaisen 3-majoroinnin suhteen.

Väitöskirjassa sovelletaan ensin majoroinnin teoriaa optimointitehtäviin, joissa etsitään vektorin x alkioiden osasummien S[i,j](x) maksimi ja minimi rajoitteilla S(x)=a ja G(x)=b. Näiden optimointitehtävien ratkaisujen kautta konstruoidaan myös suurin alaraja eli infimum ja pienin yläraja eli supremum joukolle Z(S,a;G,b) sekä majoroinnin että tavallisen (alkioittaisen) järjestyksen suhteen. Sen jälkeen sovelletaan 3-majorointia optimointitehtäviin rajoitteilla S(x)=a, G(x)=b ja F(x)=c. Tässä F on funktio, joka säilyttää järjestyksen 3-majoroinnin suhteen joukossa Z(S,a;G,b).

Matriisin A jälki tr A on ominaisarvojen summa. Edellä mainittuja optimointitehtävien ratkaisuja voidaankin soveltaa matriisin A reaalisten ominaisarvojen arvioimiseen valitsemalla sopivat ominaisarvojen funktiot G ja F. Esimerkiksi voidaan johtaa parhaat mahdolliset ala- ja ylärajat matriisin A ominaisarvoille, kun tunnetaan vain tr A, tr A^2 ja joko tr A^3 tai tr A^4.

This thesis consists of three parts. In the first part, we survey relevant results on majorization and Schur-convexity and produce some auxiliary results needed later.

In the second part, we study the set In↓ of decreasingly ordered n-tuples of elements of a real interval I, under the elementwise (partial) order ≤ and the majorization (partial) order \preceq. We find the supremums and infimums of the set { x ∈ In↓ | S(x) = a, G(x) = b }, relative to these orders. Here G is a Schur-convex function and S(x) denotes the sum of the elements of x. Besides the constraint G(x) = b, we also consider the constraint G(x) ≤ b as well as G(x) ≥ b. We tie this discussion to eigenvalue estimation.

In the third part, we generalize the majorization order to what we call k-majorization. We find the supremum and infimum relative to ≤ of the set {x ∈ Rn↓ | S(x) = a, G(x) = b, x is majorized by c}, where c ∈ Rn. We consider the question about the extreme values of the function f(xk, xl) in the {x ∈ In↓ | S(x) = a, G(x) = b}. Particularly, we solve the problem max { xk/xl | x ∈ Rn+, ∑ixi = a, ∏ixi = d }. An equivalent problem is the following: Let A be an n×n-matrix with real eigenvalues. Find the best possible upper bound for the ratio of its kth and lth largest positive eigenvalues, using n, tr A, and det A.

In this part, we also characterize functions which are increasing relative to 3-majorization. As an application, we find the maximum and minimum of xk subject to x ∈ In↓, S(x) = a, G(x) = b, and F(x) = c, where F is increasing relative to 3-majorization in the set {x ∈ In↓ | S(x) = a, G(x) = b}. As an example, we present the best possible bounds for the kth largest eigenvalue of A, using besides n, tr A, and tr A2, also either tr A3 or, when the eigenvalues are nonnegative, tr A4.