  We address the problem of finding the nearest graph Laplacian to a given
matrix, with the distance measured using the Frobenius norm. Specifically, for
the directed graph Laplacian, we propose two novel algorithms by reformulating
the problem as convex quadratic optimization problems with a special structure:
one based on the active set method and the other on direct computation of
Karush-Kuhn-Tucker (KKT) points. The proposed algorithms can be applied to
system identification and model reduction problems involving Laplacian
dynamics. We demonstrate that these algorithms possess lower time complexities
and the finite termination property, unlike the interior point method and
V-FISTA, the latter of which is an accelerated projected gradient method. Our
numerical experiments confirm the effectiveness of the proposed algorithms.
