0
$\begingroup$

How to find the minimum of the following function

$$ {\rm f}\left(w\right) = {1 \over 2}\sum_{i = 1}^{n}\left({1 \over 1 + {\rm e}^{-x_{i}\,w}} -y_{i}\right)^{2} $$

where $x_{i}, y_{i} \in \left(0, 1\right)$ are constants, $w\in \mathbb{R}$?

Could you find a analytic or computational way to get the minimum of the function ?.

$\endgroup$
4
  • $\begingroup$ Please try to make use of MathJax here :) $\endgroup$
    – Shaun
    Dec 5 '13 at 12:13
  • $\begingroup$ Ok, I will try it next time.@Shaun $\endgroup$ Dec 5 '13 at 12:15
  • $\begingroup$ Check the following link ---> dlmf.nist.gov/software $\endgroup$ Dec 6 '13 at 4:20
  • $\begingroup$ Thanks for your software index.@Felix Marin $\endgroup$ Dec 6 '13 at 5:03
1
$\begingroup$

I suppose that this is a nonlinear least square fit problem in which you have data points [x(i) , y(i)] and you want to adjust the parameter w. If you establish the derivative of f(w) with respect to w, you have one (not too complex) equation to solve but it can easily be done using Newton method. The problem is to start with a reasonable value; you can have one rewriting x(i) as a function of y(i). Going to logarithms, you will see that x(i) is along a straight line of Log[y(i) / (1-y(i)] and the slope of this line is w. So, you have everything to start.

$\endgroup$
4
  • $\begingroup$ Thank you for your answer. With your method, I can find several points that the derivative of f(w) are 0. But can I find every point that the derivative of f(w) are 0? So that I can find the minimum of the whole function. $\endgroup$ Dec 5 '13 at 13:10
  • $\begingroup$ No, this is not the way. Since your data y(i) are in error, you search for the value of "w" which minimizes your function f(w) that is to say which is the solution of f'(w)=0. The solution is unique. As I told you (with a typo), a look of the plot of Log[y(i) / (1 - y(i)] versus x(i) will give you an estimate of "w" which is the root you look for. If you want, post a few points for me and I shall enter into details in such a way you can continue by yourself. If you like my answer, you can accept it. $\endgroup$ Dec 5 '13 at 15:12
  • $\begingroup$ To correct some typos (I am almost blind), plot Log[1 - 1 / y(i)] against x(i). The graph will look like a straight line the slope of which being "- w". Make a visual estimation of that (or use Excel plot with regression in the transformed space). Now, solve f'(w)=0 using Newton. You can also visualize ploting f(w) versus "w". $\endgroup$ Dec 5 '13 at 15:24
  • $\begingroup$ I don't understand why you think there is only one solution of f'(w)=0. Could you proof it prove it? And I will appreciate your answer. Change y(i) into Log[1 - 1 / y(i)] can make it into a linear regression problem. But it's meaningless for me because I need to estimate the error with the form y(i).@Claude Leibovici $\endgroup$ Dec 6 '13 at 3:24
1
$\begingroup$

To try to clarify things, I generated 10 values [x(i) = i / 10] and the corresponding values y[i] are [0.58, 0.65, 0.72, 0.78, 0.83, 0.87, 0.90, 0.92, 0.94, 0.96].

Based on these, I wrote function f(w) as given in your post (sum of 10 terms). When plotted as a function of w, f(w) exhibits (as totally normal) a paraboloid shape with a marked minimum around 3.15 (to give you an idea, for f(2.0)=0.0337713, f(2.5)=0.00852217, f(3.0)=0.000357495, f(3.5)=0.00181296, f(4.0)=0.00843496. The absolute minimum corresponds to w=3.13938 for which f(w)=0.000031942 and this is the solution.

Using the second approach, I wrote function f'(w). Ploted against w, this function has a very nice shape and becomes exactly zero at w=3.13938 and this is the solution.

You must remember than solving an equation is much simpler than minimizing a function (almost if not constrained). For illustration purposes, to solve f'(w)=0, I used Newton method starting at w=2.0 (value which is far away from the one I suggested you to generate using some changes). The successive iterates for w are 2.45293, 2.75188, 2.93280, 3.03609, 3.09582, 3.13997.

$\endgroup$
9
  • $\begingroup$ Thanks for your example. My colleagues also tried many examples and haven't find a case that has more than one relative extremum. I wonder could it be proved analytically that the function f(w) have exactly one relative extremum, or have a sufficiently large probability that has only one relative extremum, which you proved experimentally. $\endgroup$ Dec 6 '13 at 6:50
  • $\begingroup$ @YangzheLau.In the case of your model, which is extremely simple, only one extremum can exist. Forgetting mathematics, you search for a value of "w" which gives you the best compromise between the y[i] and the model. This minimum is then unique. If your model was more complex such y = a / (b + Exp[-w x]), the story would be very different and in this case, except if you can generate good estimates, several minima could exist and global optimization could be required. But, this is NOT the case for your problem. $\endgroup$ Dec 6 '13 at 7:06
  • $\begingroup$ @ClaudeLeibovici As I showed in my comment below on my answer, the functional need not have a global minimum (I.e. It is at $\pm\infty$). There are also times where it is I feasible to calculate the derivative due to its complexity, let alone root find with it! There is a reason that a great deal of research has been performed on minimisation techniques. $\endgroup$
    – Daryl
    Dec 6 '13 at 7:22
  • $\begingroup$ @Daryl x[i] and y[i] belong to (0,1). We didn't find a counterexample yet. $\endgroup$ Dec 6 '13 at 7:34
  • $\begingroup$ @ClaudeLeibovici You are right at least in any application case. Ok, I just consider it as a theorem and continue my work. $\endgroup$ Dec 6 '13 at 7:45
1
$\begingroup$

From a numerical point of view, your problem looks quite iteresting and I played with it, my concern being to get a quick estimate of the parameter "w" which has to be adjusted to your data.

What I did was to start a Newton procedure at w=0. As a result, what I obtained is that a rough estimate of "w" can be obtained using the following formula for the estimate
w = 2 (2 S3 - S1) / S2
in which S1 is the sum of the x(i), S2 is the sum of x(i)^2 and S3 is the sum of x(i) * y(i).

For an exact value of w = 1, 2 or 3, the corresponding estimates are is 0.95, 1.66 and 2.11. The corresponding "experimental" data were x(i) = i / 10 and the y(i) were calculated using the exact formula.

In the case I previously illustrated (with noise in the y data), this procedure would lead to an estimate equal to 2.16 for an excat value of 3.14.

$\endgroup$
3
  • $\begingroup$ Your estimate can be used as an good start value of w for me, and I 'm surprised at the succinct form of the derivative and second derivative of the function when w=0. By the way, I'm considering a two dimensional case. $$ {\rm f}\left(w_{1},w_{2}\right) = {1 \over 2}\sum_{i = 1}^{n}\left({1 \over 1 + {\rm e}^{-x_{i}w_{1}-z_{i}w_{2}}} -y_{i}\right)^{2} $$ Now there are more than one local extremum. $\endgroup$ Dec 8 '13 at 12:51
  • $\begingroup$ @YangzheLau. Now, we are in the serious case with two dimensions. However, you can first perform a linear regression (no intercept) for the model log(1/y - 1) = - w1 x - w2 z. This will give you very reasonable estimates and, starting from these, I am almost ready to bet that you will reach THE optimum. $\endgroup$ Dec 8 '13 at 13:30
  • $\begingroup$ Thanks for your suggestion, I will do experiments on it. $\endgroup$ Dec 8 '13 at 14:43
0
$\begingroup$

If you are finding the minimum with respect to $w$, the domain of $w$ will effect what your minimum will be. So is $w\in \mathbb{R}$ or is it that $w$ can only take a particular set of values?

$\endgroup$
4
  • $\begingroup$ Sorry, I forgot to notice that $w\in \mathbb{R}$. $\endgroup$ Dec 5 '13 at 13:02
  • $\begingroup$ In that case you can it is clear that the minimum value should be zero. Since $w=\frac{1}{x_i}\ln\left(\frac{y_i}{1-y_i}\right)$ will make all the terms inside the summation zero. $\endgroup$
    – user112535
    Dec 5 '13 at 13:06
  • 1
    $\begingroup$ But there is only one w with several $x_i$ and $y_i$.@LinearAlgebra $\endgroup$ Dec 5 '13 at 13:17
  • $\begingroup$ Oh I am sorry. I mixed up your data points as fixed constant values. :) $\endgroup$
    – user112535
    Dec 5 '13 at 13:47
0
$\begingroup$

Given your function $f(w)$, its derivative wrt $w$ is given by $$\begin{align} \frac{df}{dw}&=\sum\limits_{i=1}^n\left(\frac{1}{1+\exp(-x_iw)}-y_i\right)\cdot\frac{x_i\exp(-x_iw)}{\left(1+\exp(-x_iw)\right)^2}\\ &=\sum\limits_{i=1}^n\frac{\left(1-y_i\left(1+\exp(-x_iw)\right)\right)\cdot x_i\exp(-x_iw)}{\left(1+\exp(-x_iw)\right)^3}, \end{align}$$ which is a quite complicated expression when attempting to find the root analytically.

A number of computational methods exist for finding the minimum of $f(w)$. The class of solvers which is applicable to this problem solve unconstrained non-linear optimisation problems, of which a simple google search reveals many possibilities.

$\endgroup$
8
  • $\begingroup$ Thank you for your suggestion, I'm searching on Google. It' will be appreciated if you or other mathematicians show me more clues on solving this problem as unconstrained non-linear optimization. $\endgroup$ Dec 6 '13 at 4:17
  • $\begingroup$ @YangzheLau. You may adress the problem is two different manners : the first one would be an unconstrained minimization problem (minimize f(w) for w); the second is much simpler : back to definition, solve f'(w) = 0 for w. The second approach is much simpler. $\endgroup$ Dec 6 '13 at 4:39
  • $\begingroup$ @ClaudeLeibovici There are multiple w where f'(w) = 0. If you can find all these w, the second approach is much simpler. $\endgroup$ Dec 6 '13 at 5:13
  • $\begingroup$ @YangzheLau. I think we misunderstand : there is only one value of w which makes f'(w)=0. Please see my next answer with details on a built example. $\endgroup$ Dec 6 '13 at 5:17
  • 1
    $\begingroup$ @Daryl Thank you for your link. $\endgroup$ Dec 6 '13 at 6:54

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.