This is not a direct answer, but a closely related problem is known to be NP-hard:

> Das, Goodrich.
"On the Complexity of Approximating and Illuminating Three-Dimensional Convex Polyhedra."
1995. ([ACM link][1]; [PDF download][2])

This paper establishes several results, including this:

> <b>Theorem 4.2</b>. The problem of fitting a polyhedron with a minimum number of faces between 
two given nested convex polyhedra is NP-hard. 

This question was first posed by Victor Klee, and I coauthored a paper that provided an
efficient algorithm in $\mathbb{R}^2$. But the above result shows it is already intractable
in $\mathbb{R}^3$. I do not remember the Das-Goodrich proof well enough to know if it can achieve the
same result with the outer polyhedron a cube.

There are many approximation algorithms available, as this is an important practical problem.
For example:

> Mitchell, Suri. "Separation and approximation of polyhedral surfaces."
In *Proc. 3rd ACM-SIAM Sympos. Discrete Algorithms*, pages 296-306, 1992. ([CiteSeer link][3])


  [1]: http://dl.acm.org/citation.cfm?id=645930.672852
  [2]: http://ranger.uta.edu/~gdas/websitepages/preprints-papers/approx-illum.pdf
  [3]: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.160.2500