One-sided non-linear least squares with linear constraints

Question

I am trying to solve a one-sided non-linear least-squares problem with linear constraints, i.e the problem:

$\min_{\mathbf{x}} \quad \sum^m_{i=1} \mathbf{r}_i(\mathbf{x}) \qquad \text{ s.t } \quad A\mathbf{x} \leq \mathbf{b}$

where

$r_i(\mathbf{x})=f_i(\mathbf{x})^2$ if $f_i(\mathbf{x})>0$, and $r_i(\mathbf{x})=0$ else.

In words, this can be considered a least-squares problem where only the positive residuals (the $f$'s) are included. I cannot stress enough that this is not a datafitting case. I am aware of what would happen if used for most datafitting cases, where the result would merely be a function that is "above" all the observations. The application is for solving a very specific optimization problem that is normally solved in the minmax norm ($\min_{\mathbf{x}} ||\mathbf{f}(\mathbf{x})||_\infty$). In all practical cases, the solution does not reach zero, i.e. $||\mathbf{f}(\mathbf{x})||_\infty \neq 0$ due to the behaviour of the $f$ functions.

The $f$ functions are non-linear, and we have access to their derivatives, such that we can analytically calculate the Jacobian without much extra trouble.

We have, with some success, applied a Levenberg-Marquardt algorithm where the objective function is formulated as above, i.e. the $f$'s below 0 are removed from the sum, and with the corresponding rows of the Jacobian $J$ set to zero (i.e. $J_{i,:}=0$ if $f_i(\mathbf{x})<=0$. This is rather crude but works OK, unfortunately we have not been able to incorporate the linear constraints.

We are aware of a number of methods that solve the NLLSQ problem with only bound constraints, but those methods obviously does not solve our problem. We have found only one NLLSQ with linear constraints, called DQED, and have used that with limited succes (we are unhappy with the number of iterations/function evaluations) by modifying our objective function as we did with Levenberg Marquardt.

What I am looking for

Any suggestions for methods that solve the non-linear least squares problem with linear constraints. Also, suggestions on how to modify algorithms to incorporate the fact that we only include the positive residuals are more than welcome. Finally, any tips or thoughts are most welcome, though I must stress again that the formulation of the problem is not wrong, though I realize that it is not the most suitable one for optimization due to the lack of differentiability of $r_i(\mathbf{x})$ when $r_i(\mathbf{x})=0$.

Answer 1

A lot of my answer to this question also applies here; just ignore the PDE part and pretend I'm talking about a run-of-the-mill nonlinear optimization problem.

In general, since you have continuous functions, you can use direct search methods, though the convergence of those methods can be slower than corresponding methods that use higher-order derivative information (which, in this case, you don't have). You could also try looking at nonsmooth optimization solvers, such as those that use bundle methods. The major name in the field is Frank Clarke, who developed much of the theory behind nonsmooth optimization; I don't know much about that body of literature otherwise.

My guess is that due to the nondifferentiabilities in your objective, using methods that assume first- or second-order derivative information is causing problems with convergence.

Answer 2

(Years later) as you know, Levenberg-Marquardt optimizers take a whole vector of functions $[f_i]$ and do the summing and squaring inside. Thus
$\qquad levmar(\ max(\ [f_i ...],\ 0\ )]$
will see only the $f_i > 0$, which is what you want, is that right ?

Linear constraints $lin_i(x) \equiv A_i \cdot x - b_i \leq 0$ have the same property as your $f_i$, that only the positive terms matter. Thus you can just levmar the lot:
$\qquad levmar(\ max(\ [f_i ...\ lin_i ...],\ 0\ )]$
(with $lin_i$ multiplied by 1000 or 1000000.) Of course the $Jacobians_i(x)$ have to look at the signs of $f_i$ and $lin_i$, but that's easy. Also I'd add a term $\|x\|$ to keep $x$ from wandering off to infinity.

(Both Scipy least_squares and ceres do box constraints, but I don't see any way of mapping regions $Ax\leq b$ to boxes.)