exponential fitting with line - minimizing error

Question

PROBLEM: I got the following problem:

PLEASE, READ EDIT FIRST

Where the $f_2$ needs to fit $f$ over a certain interval $[a,b]$, minimizing the error $E$ (red area).

---

THOUGHTS:

My idea is to define the error $E$ as:

$E = \int_{x1}^{x2} (f-f_2)^2 dx$

and then $\frac{\partial E}{\partial ?}$, but because the line $f = a*x + b$ has 2 parameters $\{a,b\}$, I am not sure how define the derivative, since I have 2 parameters.

What reasonable condition I can establish, to get another equation to get an optimal fit ? I have considered the $\frac{\partial f}{\partial x} = \frac{\partial f_2}{\partial x}$ at some point $x \in [x1, x2]$, but this seems like a guessing game (there is no particular $x$ that is an optimal choice, right ?)

---

QUESTION 1: How do I get optimal fit of $f_2$ to $f$ over interval $[x1,x2]$ ?

QUESTION 2: (related to question 1) What could be the second condition, to get the optimal fit ?

QUESTION 3: Is there any other way to get optimal fit in explicit form (no iterative methods, like gradient decent) ?

P.S. I want to avoid line fitting to number of points (sampling the exponential) and using least squares.

---

EDIT:

I have slightly changed the problem, by including the orange part in the objective function:

The objective function is then :

$E = \int_{0}^{x1} (f)^2 dx + \int_{x1}^{x2} (f-f_2)^2 dx$

Then I am looking for :

$\frac{\partial E}{\partial a} = 0$

and since I define $f_2 = a*(x-x_1)$, then $x_1$ is the other parameter

$\frac{\partial E}{\partial x_1} = 0$

This leads to quite complex non-linear set of equations:

Set of non-linear equations:

At the moment I am not able to solve this numerically using Matlab. Mind that $x2, K, Q$ are known constants, therefore the only variables are $a$ and $x_1$.

Am I doing something wrong ? Because this seems such a simple problem, even the set of equations is not that horrible, just long and unfortunately very non-linear. Any advice ?

Answer 1

SOLUTION:

I have solved the problem using initial guess and stochastic search.

1) Initial guess is such, that the 2 points where $f_{(x)} = f_{2(x)}$ are set to $f_{(x)} = f_{2(x)} = 0.1*Y_{max}$ and $f_{(x)} = f_{1(x)} = 0.9*Y_{max}$ respectively

2) Stochastic search in immediate distance around the initial guess, where I evaluate the $E_{(x)}$ and then iteratively shrink the search region until I got $\frac{\partial E}{\partial a} < limit$ and $\frac{\partial E}{\partial x_{1}} < limit$

3) I have investigated and the immediate region around the solution is convex, when I reach the 2), so I check whether the region is convex (checking the Hessian to be semi-definite positive) to certainly get the right solution

This works a lot better than gradient descent, since the function is only locally convex (not proved, but checked by investigating the convex/concave parts of the error function, there is only 1 minimum in the convex region).

The gradient descent converges but a lot slower (for linear step, diminishing over time, AdaGrad, AdaDelta) than the stochastic search.

---

This solution breaks the assumption about the use of non-iterative methods, but works so precisely and fast that it meets all my expectations.

Answer 2

Note: The problem changed significantly after this answer was added.

If you evaluate the integral you will obtain a function $(a,b) \mapsto E((a,b))$.

If you evaluate the second (matrix) derivative, you will obtain $(x_2-x_1)\begin{bmatrix} {2 \over 3} (x_1^2+x_1x_2 + x_2^2)& x_1+x_2\\ x_1+x_2& 2\end{bmatrix}$, and if $x_2>x_1$, it is straightforward to check (look at the trace & determinant) that the matrix is positive definite.

In particular, the function $E$ is a strictly convex quadratic, so it has a unique minimiser $(a,b)$.

We can solve for the minimiser by solving the linear system ${\partial E(a,b) \over \partial a} = 0$, ${\partial E(a,b) \over \partial b} = 0$.

The answer is not pretty, but it is explicit, no need for iterative methods.

Another way to look at the problem is that you are trying to find the best fit of $f$ in terms of the functions $v_1(x)= 1, v_2(x)= x$, where the best fit is defined as one that minimises the norm $\|g\|^2 = \int_{x_1}^{x_2} |g(x)|^2 dx$ (which comes from the inner product $\langle g,h\rangle = \int_{x_1}^{x_2} g(x)h(x) dx$).

This can be expressed as finding the $a,b$ that minimise $\|f-av_2+b v_1\|^2$, which is a linear least squares problem.

Another way (essentially equivalent) is to use Gram Schmidt to orthonormalise $v_1,v_2$ to get $e_1,e_2$, then the best approximation can be read off as $\langle e_1, f\rangle e_1 + \langle e_2, f\rangle e_2$.

Alternative:

Here is an approach to the modified problem:

Define the inner product $\langle f,g\rangle = \int_0^{x_2} f(x)g(x) dx$.

First fix $x_1$, let $v_{x_1}(x) = \sqrt{3 \over (x_2-x_1)^2} \max(0, x-x_1)$ and then the optimal fit (for a fixed $x_1$) will be given by $g_{x_1}(x)=\langle v_{x_1}, f \rangle v_{x_1}(x)$.

Not pretty, but not too bad.

The problem is now reduced to a single variable optimization.

Now minimise $\int_0^{x_2} (f(x)-g_{x_1}(x))^2 dx$ over $x_1 \in [0,x_2]$. (Note that this is not a convex problem, however it has a solution since the domain is compact and the cost continuous.