Abstract: In this study, a way to design the optimal weights associated with edges of undirected graph composed of multi-agent systems is presented. The optimal weights are designed to make the states of the multi-agent systems converge to consensus with a fast speed as well as the maximum communication time-delay can be tolerated. The method used in our research is based on linear matrix inequality theory. The convergence speed which is determined by the second-smallest eigenvalue of graph Laplacian matrix is assumed to be a given value, at the same time the maximum communication time-delay which is decided by the maximum eigenvalue of Laplacian matrix can be got. In order to get required second-smallest eigenvalue and optimal maximum eigenvalue, the order of Laplacian matrix is reduced by variable decomposition. Moreover, designing the optimal weights is equivalent to minimizing condition number of a positive-definite matrix. Simulation results are coincidental with theoretical analysis.