Optimization of fermentation media and processes is a difficult task due to the potential for high dimensionality and non-linearity. Two novel and highly efficient experimental design methods were developed and evaluated for experimental fermentation optimization. The first approach is based on using a truncated genetic algorithm with a developing neural network model to choose the best experiments to run for process optimization. The second approach uses information theory, along with Bayesian regularized neural network models, for experiment selection. To evaluate these methods experimentally, we used them to develop new chemically-defined media for high cell density growth of Lactococcus lactis IL1403. A leave-one-out approach was employed to identify the necessity of each of the 57 chemical components used in the medium development. The final fermentation system included 19 defined components or groups of components, along with an optimal temperature and initial pH. The maximum cell growth from the optimal process resulting from each novel method is generally comparable to or higher than that achieved using a traditional statistical experimental design method, but these optima are reached in about half of the experiments (73 to 94 vs. 161, depending on the method). All the optimal chemically-defined media developed in this work can support high cell density growth for L. lactis, generally 2.5 to 3 times higher than the best previously reported synthetic medium (SA) and 72% higher than the commonly-used complex medium (M17) at optimization scale. The best chemically-defined medium developed was evaluated and compared to other media at flask- and fermentor-scales. All optimal chemically-defined media can be used for the growth of eight other L. lactis ssp and other organisms (e.g., enterococci, and streptococci) for which M17 is a common complex growth medium.