We investigate a method for computing the value of a polyconvex envelope at a given feed A0∈Rm×n . The method generalizes an approach for computing convex envelopes proposed by Michelsen (Fluid Phase Equilibria 9:1–19, 1982; Fluid Phase Equilibria 9:21–40, 1982) and later implemented by McKinnon and Mongeau (J Glob Optim 12(4):325–351, 1998). We formulate the problem as a primal-dual nonlinear optimization task in p(1 + mn) variables (Λ,A)∈Rp×(Rm×n)p subject to (τ+1)≡binom(m+n,n) equality constraints; and we prove that under reasonable assumptions, the global minimum of the dual problem is attained so that as a consequence, the polyconvex envelope value can be computed pointwise. A similar alternating procedure based on linear programming and adaptive mesh refinements was investigated in Bartels (SIAM J Numer Anal 43(1):363–385, 2005). The underlying function E is assumed to be at least lower semicontinuous and coercive for the existence theory. For the algorithm we require continuous differentiability.