The Space Decomposition Method For Several Classes Of Eigenvalue Optimizations

For twenty years, eigenvalue optimization problems have caused the researchers a wide focus. many practical problems can be converted into optimization problem of minimizing the eigenvalue functions, such as optimal control, combinatorial optimization, signal recov-ery, optimal system design, robotics, experimental design, shape optimization, and much more. Therefore the algorithm research on solving the class of problems possesses theoretical signif-cance and practical value. Although this class of functions generally are nonsmooth, due to its good structure properties, they have some smooth substructure. In light of uv-decomposition theory, via the intermediate function:u-Lagrangian function, this yields the second-order ex-pansion of the function along some smooth manifold.Presently, there are mainly two methods for solving eigenvalue optimization:subgradient methods and bundle methods. However, these two methods converge slowly(at most linear), and the uv-decomposition method for solving several classes of eigenvalue optimization studied in this paper, possesses superlinear convergence. The main results can be summarized as follows:1. Chapter2presents uv theory about a special class of eigenvalue function, the sum of the largest eigenvalues. u-Lagrangian theory is applied to the class of the functions here, when transversality condition holds, we can obtain the f rst-and second-order derivatives of u-Lagrangian. Then the second-order expansion of the function along some smooth trajectory can be gained.2. In Chapter3we study the uV theory of a general class of eigenvalue function:arbitrary eigenvalue function λ1which is a class of D.C. functions.u-Lagrangian theory is applied to the class of the functions. When transversality condition.holds, we can obtain the f rst-and second-order derivatives ofu-Lagrangian. Moreover, we present a conceptual algorithm which is proved to have local fast convergence. In addition, we apply our results to some practical optimization problem:low rank matrix problems.3. Chapter4applies the space decomposition theory to a special class of eigenvalue func-tion, the largest eigenvalues with the matrix convex mapping.u-Lagrangian theory is applied to the class of the functions here, when regular condition holds, we can obtain the f rst-and second-order derivatives of u-Lagrangian. We present the second-order analysis of λ1using the uv-decomposition method. Through the smooth track X(u) satisfying the transversality condition, there is a second-order expansion of λ1along the x(u). Furthermore, we present a conceptual algorithm which is proved to have local superlinear convergence. In addition, this procedure suggests that our results may be used to deal with some practical optimization problems:nonlinear convex semidef nite programming. Besides, we provide the good uv-decomposition results for bilinear matrix inequality problems and the maximum eigenvalue with respect to matrix variables.4. Chapter5considers minimizing optimization problems involving eigenvalues of sym-metric matrices. We present a nonsmooth optimization technique for a class of nonsmooth func-tions which are semi-inf nite maxima of eigenvalue functions. Our strategy uses generalized gradients and uv space decomposition techniques suited for the norm and other nonsmooth performance criteria. For the class of max-functions, which possesses the so-called primal-dual gradient structure, we compute smooth trajectories along which certain second-order ex-pansions can be obtained. We also give the frst-and second-order derivatives of primal-dual function in the space of decision variables R’" under some assumptions.