1
$\begingroup$

PROBLEM: I got the following problem:

PLEASE, READ EDIT FIRST enter image description here

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:

enter image description here

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:

Derivation of objective function and derivatives

Set of non-linear 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 ?

$\endgroup$
  • $\begingroup$ For the $\dfrac{\partial E}{\partial ?}$ part: find the solutions $a^*$ for $\dfrac{\partial E}{\partial a}=0$ and $b^*$ for $\dfrac{\partial E}{\partial b}=0$. Also, figure out if $E$ is a convex function on $a$ and $b$ to ensure $a^*$ and $b^*$ are minima. $\endgroup$ – Rócherz Jun 2 '18 at 6:45
  • $\begingroup$ After derivation of $E$ with respect to $a$ and $b$, you just have two linear equations in $a$ and $b$. Quite simple even if the resulting expressions are a little messy. $\endgroup$ – Claude Leibovici Jun 2 '18 at 8:05
  • $\begingroup$ That is a fairly significant change to the problem, not just a small edit. $\endgroup$ – copper.hat Jun 4 '18 at 15:10
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Could you please elaborate on the second method, with the inner product ? $\endgroup$ – Martin G Jun 4 '18 at 13:13
  • $\begingroup$ The "edit" causes the last 3 terms to appear in the $\frac{\partial E}{\partial x_1} = 0$ (the last picture with the equations written by pencil). Could you please elaborate what of a big change is this ? From my point of view, the problem has the same complexity as before the edit, since the set of non-linear equations still contain $exp(x_1)$, $a^2$, $x_1^2$ ... $\endgroup$ – Martin G Jun 5 '18 at 2:23
  • $\begingroup$ The problem changed from a standard least squares problem to a non convex problem (or at least not obviously convex) . That is a significant change. Unfortunately, a few characters change can change the mathematics significantly. $\endgroup$ – copper.hat Jun 5 '18 at 6:10
0
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.