This paper is concerned with the computational complexity analysis in robus
t control problems. We first formulate a fairly general class of nonconvex
optimization problem named "Matrix Product Eigenvalue Problem (MPEP)" and e
xplain the connection to robust control problems. We next summarize the wor
st case computational complexity results and investigate the computational
cost for the actual case. Finally, we make a comparison with an element-wis
e bounding for the BMI optimization problem and a matrix-based bounding for
the MPEP.