Circulant matrix embedding is one of the most popular and efficient methods for the exact generation of Gaussian stationary univariate series. Although the idea of circulant matrix embedding has also been used for the generation of Gaussian stationary random fields, there are many practical covariance structures of random fields where classical embedding methods break down. In this work, we propose a novel methodology that adaptively constructs feasible circulant embeddings based on convex optimization with an objective function measuring the distance of the covariance embedding to the targeted covariance structure over the domain of interest. The optimal value of the objective function will be zero if and only if there exists a feasible embedding for the a priori chosen embedding size.