A new optimization technique with uncertainty that extends the pure nested partition (NP) algorithm is presented in this thesis. This method is called the nested partition with inheritance. The basic idea of a NP algorithm is very simple. At each iteration, the most promising region is partitioned and the performance of the partitioned region is evaluated using sampling. Based on the performance evaluation, the most promising region is chosen for the next iteration. These procedures are repeated until it satisfies the termination condition.;Even though the pure NP method guarantees the convergence to the optimal solution, it has several shortcomings. To handle these shortcomings, two extensions to the pure NP are suggested. To rigorously determine the required sample effort, some statistical selection methods are implemented, which include the Nelson Matejcik procedure, the Rinott procedure, and the Dudewicz and Dalal procedure, as well as a subset procedure. In addition, Genetic Algorithms (GAs) are used to speed convergence and to overcome the difficulty in the backtracking stage of the NP algorithm.;As an application of the new methodology, this work also suggests the methods to be applied to a data clustering problem. This is a very hard problem with two of the main difficulties being lack of scalability with respect to amount of data and problems with high dimensionality. The new algorithms are found to be effective for solving this problem. Random sampling enhances scalability and the iterative partitioning addresses the dimensionality.