# Minimum of biconjugate of a nonconvex $f(x)$ is the minimum of $f(x)$ also?

In Fazel (2002) Matrix rank minimization with applications, Ch. 5.1.4-5.1.5, the author finds an analytic expression for the convex biconjugate of their nonconvex function; however, they state that minimizing the biconjugate only provides a lower bound on the original problem. (Specifically, that $\text{conv rank} X = \|X\|_*$)

By my understanding,

• The biconjugate of a function is its convex hull (point-wise greatest convex envelope) $$f^{**}(x) = \mbox{conv} f(x)$$

• The minimizer of the convex hull of a function is also the minimizer of the function itself $$\arg\min f(x) = \arg\min \mbox{conv} f(x) = \arg\min f^{**}(x)$$

If so, why does the double conjugate only provide a lower bound and not the true minimum?

## 1 Answer

Your mistake is making this claim: $$\mathop{\textrm{conv}} \mathop{\textrm{rank}} X = \|X\|_*$$ That is incorrect, and not an accurate reflection of the dissertation. This is the claim made, expressed in extended-value form: $$\phi(X) = \begin{cases} \mathop{\textrm{rank}} X & \|X\|\leq 1 \\ +\infty & \text{otherwise} \end{cases} \quad\Longrightarrow\quad \phi^{**}(X) = \|X\|_*$$ Even if you know that $\|X\|\leq 1$, this wouldn't be enough to give you a true minimum. After all, the problems you really want to solve are like this: \begin{array}{ll} \text{minimize} & \mathop{\textrm{rank}}(X) \\ \text{subject to} & X \in \mathcal{C} \end{array} where $\mathcal{C}$ is a more general convex set. To get a true minimum you need the convex envelope for this function: $$\phi(X) = \begin{cases} \mathop{\textrm{rank}} X & X \in \mathcal{C} \\ +\infty & \text{otherwise} \end{cases}$$ And the likelihood that you can compute that for any useful $\mathcal{C}$ is small.