In this paper, we develop a new class of parameter estimation techniques for the Gaussian Continuous-Density Hidden Markov Model (CDHMM), where the discriminative margin among a set of HMMs is used as the objective function for optimization. In addition to optimizing the mean parameters of the large-margin CDHMM, which was attempted in the past, our new technique is able to optimize the variance parameters as well. We show that the joint mean and variance estimation problem is a difficult optimization problem but can be approximated by a convex relaxation method. We provide some simulation results using synthetic data which possess key properties of speech signals to validate the effectiveness of the new method. In particular, we show that with joint optimization of the mean and variance parameters, the CDHMMs under model mismatch are much more discriminative than with only the mean parameters.