Semidefinite diagonal directions Monte Carlo algorithms for detecting necessary linear matrix inequality constraints

Hit-and-run algorithms are Monte Carlo methods for detecting necessary constraints in convex programming including semidefinite programming. The well known of these in semidefinite programming are semidefinite coordinate directions (SCD), semidefinite hypersphere directions (SHD) and semidefinite stand-and-hit (SSH) algorithms. SCD is considered to be the best on average and hence we use it for comparison. We develop two new hit-and-run algorithms in semidefinite programming that use diagonal directions. They are the uniform semidefinite diagonal directions (uniform SDD) and the original semidefinite diagonal directions (original SDD) algorithms. We analyze the costs and benefits of this change in comparison with SCD. We also show that both uniform SDD and original SDD generate points that are asymptotically uniform in the interior of the feasible region defined by the constraints.