Multiple functional and hard-to-quantify sensorial product attributes that can be satisfied by a large number of cosmetic ingredients are required in the design of cosmetics. To overcome this challenge, a new optimization-based approach for expediting cosmetic formulation is presented. It exploits the use of a hierarchy of models in an iterative manner to refine the search for creating the highest-quality cosmetic product. First, a systematic procedure is proposed for optimization problem formulation, where the cosmetic formulation problem is defined, design variables are specified, and a set of models for sensorial perception and desired product properties are identified. Then, a solution strategy that involves iterative model adoption and two numerical techniques (i.e., generalized disjunctive programming reformulation and model substitution) is applied to improve the efficiency of solving the optimization problem and to find better solutions. The applicability of the proposed procedure and solution strategy is illustrated with a perfume formulation example.