For the multidisciplinary analysis and optimization the use of metamodels or so-called surrogates is the most popular approach. These models are built by approximation of the results of time-consuming numerical experiments, which are performed using some appropriate plan – design of experiments (DoE). The most effective of these are Latin hypercube type designs (LH) [1, 2], optimized according to some space filling criterion – maximum distance (Maximin, Minimax), Mean Squared Error (MSE), entropy, discrepancy and others [3]. In the past years, some generalizations of LH, balanced designs were proposed, as well as designs based on combined optimization criteria, which attempt to combine the space filling properties in whole space and 1-2-3 dimensional subspaces without the requirement of absolute uniformity in one-dimensional subspaces like traditional Latin hypercubes [4]. The last approach gives the possibility of building of sequential DoEs, which have better space filling properties than traditional quasi-random sequences. The optimization of experimental designs according to the above criteria is a difficult task of constrained discrete and continuous optimization with a large number of variables. The most widely used methods for the optimization of DoE are multistart coordinate exchange algorithms. In this work we propose the improved multistart method with coordinate exchange and univariate relaxation. In this method, the previously obtained locally optimal design is „corrupted” in a special way, which allows a subsequent improvement. In some cases the exact criterion, for example, Maximin criterion, is replaced with a similar criterion, which can be improved by simultaneous change of only one pair of experimental points. The method is similar to the simulated annealing method, but does not accept solutions with criterion values that are worse than the values before “corruption”. This optimization method gave the possibility to find experimental designs with better criteria values than known in the literature for the Maximin, MSE, discrepancy criteria as well as for combined criteria and sequential DoEs. For the Maximin criterion we also created an exhaustive search program using branch and bound method. We carried out an exhaustive search for some numbers of experimental points for designs with 2-12 variables. At last we demonstrate the comparison of several experimental designs for optimization of test benchmarks.