Should I Express Optimization Goals via Objective or via Constraints?

Question

I have $k$ reasonably smooth functions $f_i : \mathbb{R}^n \to \mathbb{R}$ and corresponding targets $t_i \in \mathbb{R}$ as well as a regularization term $r : \mathbb{R}^n \to \mathbb{R}$. I want to find a position $x^* \in \mathbb{R}^n$ that makes each function hit their target value and minimizes the regularization term.

Assuming I have access to a constrained optimization algorithm, I could express this goal either via the objective function by minimizing the squared errors between the functions and their target values

$$ \begin{align} x^* = &\operatorname*{argmin}_{x \in \mathbb{R}^n} \left(\left(\sum_{i < k} (f_i(x) - t_i)^2\right) + \lambda r(x)\right)\\ &\text{st.} \: \text{True} \end{align} \tag{1} $$

or directly via the constraints $$ \begin{align} x^* = &\operatorname*{argmin}_{x \in \mathbb{R}^n} \: r(x) \:\:\\ &\text{st.} \: \forall \: i < k. f_i(x) = t_i \end{align} \tag{2} $$

1. Which approach is better? My intuition tells me that (2) gives the optimizer more independent ($n$ separate constraints rather than single scalar value) and also more direct (no squaring of the values) access to the quantities of interest. If so, how can an optimization algorithm make use of this additional information?
2. I assume that the answer to question 1 depends to some extent on the chosen optimization algorithm. If so, which algorithms would be best for this type of problem and/or each way of expressing it?
3. Assuming that (2) is preferable, how can I deal with a situation in which the constraints are not completely satisfiable, but there is a solution that gets very close?

Answer 1

Which is better depends on context.

In cases where it is absolutely essential that $f_{i}(x) = t_{i}$ then the constrained version is required.

In general (and contrary to your first point), the squared error term will be preferable over the equality constraints when $f_{i}$ is nonlinear. If we ignore the regularizer for a moment, such a formulation would be amenable to nonlinear least squares algorithms, such as the Levenberg–Marquardt algorithm. Beyond that, it's hard to know what to recommend without knowing more about your $f_{i}$ and $r$ functions.

For your third point, the typical answer is to use the least squares formulation you've written. One could also consider using least absolute deviation, with the primary distinction between the two being that least absolute deviation is more robust to outliers but sacrifices differentiability. For nonlinear $f_{i}$, the least squares formulation will give you more options for algorithms over least absolute deviation since it is a more commonly studied formulation.

Note that nonlinear least squares algorithms like Levenberg-Marquardt can converge to non-global minima, so there's no assurance that you have a global minimizer. Even experts often forget this fact. For a spectacular failure case see section 3.2 of this paper (disclaimer: I coauthored the paper) which shows that a popular method in computer vision doesn't work as advertised because the authors failed to account for these local minima.