2
$\begingroup$

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?
$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Unfortunately, my $f_i$ and $r$ depend on a user-supplied model, so it is difficult to say much about them. So, it sounds like the reason to use constraints would not be optimization performance/convergence, but rather to ensure that the (hard) constraints always take precedence over any improvements in the objective. Although I assume a similar effect could be achieved by appropriate weights in the objective. $\endgroup$
    – Jules
    Commented Feb 8, 2022 at 17:33
  • $\begingroup$ About the local vs. global minima problem: The apparent absence of helpful (general) techniques and the fact that people always stress how hard finding global optima is, leads me to believe that this is something that can only be tackled by having knowledge about the specific optimization problem that one is trying to solve, unfortunately. I will read the section in the paper you linked, it does sound interesting, thank you. $\endgroup$
    – Jules
    Commented Feb 8, 2022 at 17:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .