  Given a finite sequence of vectors $\mathcal F_0$ in $\C^d$ we describe the
spectral and geometrical structure of optimal completions of $\mathcal F_0$
obtained by adding a finite sequence of vectors with prescribed norms, where
optimality is measured with respect to a general convex potential. In
particular, our analysis includes the so-called Mean Square Error (MSE) and the
Benedetto-Fickus' frame potential. On a first step, we reduce the problem of
finding the optimal completions to the computation of the minimum of a convex
function in a convex compact polytope in $\R^d$. As a second step, we show that
there exists a finite set (that can be explicitly computed in terms of a finite
step algorithm that depends on $\cF_0$ and the sequence of prescribed norms)
such that the optimal frame completions with respect to a given convex
potential can be described in terms of a distinguished element of this set. As
a byproduct we characterize the cases of equality in Lindskii's inequality from
matrix theory.
