In incomplete financial markets not every contingent claim can be replicated by a self-financing strategy. The risk of the resulting shortfall can be measured by convex risk measures, recently introduced by Fllmer and Schied (2002). The dynamic optimization problem of finding a self-financing strategy that minimizes the convex risk of the shortfall can be split into a static optimization problem and a representation problem. It follows that the optimal strategy consists in superhedging the modified claim   , where H is the payoff of the claim and   is a solution of the static optimization problem, an optimal randomized test. In this paper, necessary and sufficient optimality conditions are deduced for the static problem using convex duality methods. The solution of the static optimization problem turns out to be a randomized test with a typical 0-1-structure.