Verification and validation (V&V) of autonomous vehicles (AVs) is a challenging task. AVs must be thoroughly tested, to ensure their safe functionality in complex traffic situations including rare but safety-relevant events. Furthermore, AVs must mitigate risks and hazards that result from functional insufficiencies, as described in the Safety of the Intended Functionality (SOTIF) standard. SOTIF analysis includes iterative identification of driving scenarios that are not only unsafe, but also unknown. However, identifying SOTIF’s unknown-unsafe scenarios is an open challenge. In this paper we proposed a systematic optimization-based approach for identification of unknown-unsafe scenarios. The proposed approach consists of three main steps including data collection, feature extraction and optimization towards unknown unsafe scenarios. In the data collection step, we proposed an efficient way of data collection by focusing on key areas of the Operational Design Domain (ODD) (e.g., intersections). In step 2, the graph-based method is used to model the selected region(s) in the ODD. The generated graph is used to aggregate actor behaviors recorded during data collection in different parameter distributions (e.g. speeds or offset to center of the lane). In step 3, the generated graph for road layout and parameter distributions for actors are used in an optimization algorithm. The objective function for the optimization algorithm consists of a criticality metric, a proprietary KPI to identify unknown scenarios here called unexpectedness, multiplied by probability of scenario calculated from actor probability distributions. Using the objective function, the optimization algorithm can identify unknown-unsafe scenarios with highest probability for the selected region(s) in the ODD. The approach is implemented on an intersection and identified unknown-unsafe scenarios are reported in the paper.