In this paper, we propose to use a new optimization method, i.e., semidefinite programming (SDP), to solve large margin estimation (LME) problem of continuous density hidden Markov models (CDHMM) for speech recognition. First of all, we introduce a new constraint into the LME to guarantee the boundedness of the margin of CDHMM. Secondly, we show that the LME problem under this new constraint can be formulated as an SDP problem under some relaxation conditions and it can be solved very efficiently by using some fast optimization algorithms specially designed for SDP. The new method is evaluated in a continuous digit string recognition task by using the TIDIGITS database. Experimental results clearly demonstrate that the new SDP-based method outperforms the previously proposed optimization methods using gradient descent search in both recognition accuracy and convergence speed. With the SDP-based optimization method, the best LME models achieves 0.53% in string error rate and 0.18% in WER on the TIDIGITS task. To our best knowledge, this is the best result ever reported in this task.