Ontology debugging is one of the non-standard reasoning tasks in artificial intelligence, and is important for ontology engineering. In this work, the complementary concepts and search graph are combined to optimize the calculation of minimal unsatisfiability preserving sub-TBox (MUPS) for the unsatisfiable concepts. Firstly, the necessity of checking the satisfaction of the concept for the expanded terminology is determined by whether it contains the complementary concepts to reduce the number of calling reasoners to some extent. Then, a search graph is constructed according to the terminology expanding process to quick search the node which is corresponding to the unsatisfiable sub-terminologies by breadth-first-search and depth-first-search strategies. This optimization reduces the number of axioms in terminologies to be checked, and it also improves the searching efficiency of the nodes corresponding to the unsatisfiable sub-terminologies. Finally, the optimized algorithms are realized and compared with existing black box algorithm. The experimental results show that the proposed method is superior to existing MUPS calculation in the calling number of reasoners and the number of axioms in the terminologies, which may effectively improve the efficiency of MUPS calculation.