UC Berkeley

In this paper, we propose novel algorithms for solving the worst-case robust optimization of the generalized eigenvalue problem with positive semi-definite constraint, a highly non-convex problem that has eluded traditional optimization solvers. We consider the rank-one case and the general-rank case saparately. For the rank-one case, we first present a relaxation of the KKT system, transforming the problem into a more tractable nonlinear system of equations. We then prove the tightness of the relaxation at the optimal point and introduce two algorithms for solving the relaxed system of equations. Our approach is the first to guarantee finding the global optimal solution for the problem at hand. For the general-rank case, we first solve the KKT system with one variable fixed. We then describe an algorithm searching for the variable. We then showed that our algorithm converges to a stationary point of the problem. We showcase the potential applications of our algorithms in robust adaptive beamforming and semi-supervised Fisher discriminant analysis. This work contributes significantly to the field by providing a globally optimal solution to a highly non-convex problem with broad applicability in various disciplines.