Abstract Portfolio optimization under a risk measure consists of finding the efficient curve of the given measure in the plane of expected return vs risk. The portfolios corresponding to points of this curve are portfolios which minimize the risk under the given measure and whose expected total return is greater than a pre-specificied level (benchmark). The optimization problems involved are mostly non-convex and therefore cumbersome. In this paper, we provide a method to approximate the efficient frontier under a law-invariant coherent risk measure by relaxing these optimization problems involved to a finite-dimensional linear model. Our method is based on three tools: the Kusuokas’s representation of the risk measure, the properties of the conditional value at risk functions and the finite elements theory. Finally, we mention the strong connection that the former kind of optimization have with problems in statistical mechanics following the classic framework of simulating annealing.