A singular value decomposition based approach to handle ill-conditioning in optimization problems with applications to portfolio theory. (December 2022) - Fassino, Claudia; Torrente, Maria-Laura; Uberti, Pierpaolo
Abstract: We identify a source of numerical instability of quadratic programming problems that is hidden in its linear equality constraints. We propose a new theoretical approach to rewrite the original optimization problem in an equivalent reformulation using the singular value decomposition and substituting the ill-conditioned original matrix of the restrictions with a suitable optimally conditioned one. The proposed novel approach is showed, both empirically and theoretically, to solve ill-conditioning related numerical issues, not only when they depend on bad scaling and are relative easy to handle, but also when they result from almost collinearity or when numerically rank-deficient matrices are involved. Furthermore, our strategy looks very promising even when additional inequality constraints are considered in the optimization problem, as it occurs in several practical applications. In this framework, even if no closed form solution is available, we show, through empirical evidence, how the equivalent reformulation of the original problem greatly improves the performances of MatLab®'s quadratic programming solver and Gurobi®. The experimental validation is provided through numerical examples performed on real financial data in the portfolio optimization context. Highlights: We identify numerical instabilities of quadratic problems due to linear constraints. We substitute the ill-conditioned linear constraints with optimally conditioned ones. We use singular value decomposition to obtain the problem's equivalent reformulation. We apply our theoretical approach to Markowitz portfolio optimization problem.