0
$\begingroup$

I have a system $Fw=b$ that can be underdetermined, square or overdetermined. The matrix $F$ contains known scalar functions $f_i(t)$ evaluated at unknown values $t_j$. The vector $w$ contains unknown coefficients $w_j$, whereas the vector $b$ is known. All unknowns $t_j$ and $w_j$ should lie in the open unit interval $(0,1)$. As example, let's consider the following system —

$$\left(\begin{array}{cc}f_1(t_1) & f_1(t_2)\\ f_2(t_1) & f_2(t_2)\\ f_3(t_1) & f_3(t_2)\end{array}\right) \left(\begin{array}{c}w_1\\ w_2\end{array}\right) = \left(\begin{array}{c}b_1\\ b_2\\ b_3\end{array}\right).$$

My first attempt at solving this is to try a least-square-like approach. That is, minimize $S = r^T r$, where $r = Fw - b$. For this, we need $\nabla S$. The partial derivatives w.r.t. $\;t_1$ and $t_2$ are

$$2 \left(\begin{array}{cc}w_1 & 0 \\ 0 & w_2\end{array}\right) \frac{d{F}^T}{dt} \left( {F}{w} - {b} \right),$$

where

$$\frac{dF_{ij}}{dt} = \frac{df_i(t_j)}{dt}.$$

For the partial derivatives w.r.t. $\;w_1$ and $w_2$ we obtain the familiar linear least-squares expression

$$2 {F}^T \left( {F} {w} - {b} \right).$$

Furthermore, the functions $f_i(t)$ are twice differentiable, so if required we could also compute the exact Hessian.

Now, for an unconstrained system, I'd use some combination of (Gauss-)Newton and Gradient Descent to find the root(s)/zero(s) of $\nabla S$. Though even in this case, I'd worry a bit about the fact that we have two different types of unknowns, whose corresponding gradients might differ by one or more orders of magnitude such that they are not `equally' optimized for.

Main issue — what about the inequality constraints (or rather, bounds on the variables)? I'm not familiar solving constrained systems. I've read bits about the active set method, projected gradient method, and stumbled upon some other keywords as well (bound constrained optimization problems, methods of feasible directions, ...). Implementation of those does seem a bit challenging, so I was wondering whether there are more straightforward methods for solving these nonlinear least squares problems with box constraints? Or should I approach this from a completely different angle?

One more thought about the constraints. Each $t_j$ is associated with a $w_j$, so we could think about each pair of unknowns as a point in the unit square (defined by the inequality constraints, $0 \leqslant t_j \leqslant 1$ and $0 \leqslant w_j \leqslant 1$). Is that helpful somehow?

$\endgroup$
  • $\begingroup$ There are off-the-shelf solvers to solve bound (box) constrained nonlinear least squares, such as mathworks.com/help/optim/ug/lsqnonlin.html . Or you can use a general optimization solver for bound-constrained (or linearly constrained) nonlinear optimization. $\endgroup$ – Mark L. Stone Aug 11 '18 at 17:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.