Moment-of-fluid (MOF) methods for interface reconstruction approximate the intersection of the region occupied by material with each mesh element. In such methods, information about the per-cell fragments of material (FOM) is given only through reference to its geometric moments. In this work, we present a 3D MOF method that represents each FOM as the convex intersection of multiple half-spaces, or by the complement of such an intersection. For each cell, the parameters of these half-spaces are selected to minimize the least-squares error between the computed moments of the approximated material and the provided reference moments.The objective function for this optimization problem is highly non-linear and non-convex, making then numerical result very sensitive to the initial guess. To create an effective initial guess in each cell, we exploit the relationship between the geometric properties of the FOM and its reference moments. In particular, an ellipsoid can be constructed from 0th-2nd order reference moments such that its position, orientation,and length along each axis correspond with the shape of the FOM. Within this ellipsoid we inscribe a convex polyhedron, and initialize the minimization problem with the half-spaces defined by each of its faces. Using this approach, the non-linear least-squares solver used can reliably converge to a near-global minimum using only a single initial guess. The intersection of up to four half-spaces with the cell may be needed to represent basic non-trivial FOMs in 3D. Each half-space is uniquely defined by 3 numerical parameters, and so the relevant non-linear least-squares problem has at minimum 12 unknowns. However, using up to 3rd order reference moments in objective function provides 20 known values. This means we can analogously define MOF methods that utilize 5 or 6 half-spaces, for which the number of unknowns is 15 or 18 respectively, without the optimization problem becoming under determined. These methods are correspondingly initialized with the faces of a single inscribed triangular prism or hexahedron. We demonstrate the accuracy and robustness of the proposed scheme using single- and multi-cell examples over a wide spectrum of geometry. In particular, we demonstrate our ability to exactly reproduce several important and complex features through the interface, such as corners, filaments, filament tips, and embedded material in the cell.