2
$\begingroup$

Good day.

I am trying to implement the EGO optimization algorithm. The algorithm itself is rather long to describe here in full. It is presented here, with another example of usage here.

But before I implement the algorithm, I have decided to test the DACE model on a simple 1-d function.

I am receiving strange results; I believe I have located the problem, but am uncertain, whether my implementation is wrong, or if what I found is a weak point in the model.

To initiate the algorithm, we need first to determine a set of parameters $\theta = \{\theta_h\}$ and $p = \{p_h\}$ from some sample data we measure.

The way we do so is as follows:

Assume we have $X = \{X^1, ..., X^n\}$ a set of points we have evaluated the function at, and $Y = \{y_1, ..., y_n\}$ the values at those points. Denote $X^i = (x^i_1, ... x^i_k)$.

Then define $$ d_{ij} = \sum_{h=1}^k \theta_h |x_h^i - x_h^j|^{p_h}$$ $$R_{ij} = e^{-d_{ij}}$$

We estimate the values $\theta, p$ by maximizing the likelihood function $$\frac1{(2\pi)^{n/2}(\sigma^2)^{n/2}|R|^{1/2}} e^{-\frac{(...)R^{-1}(...)}{\sigma^2}}$$

(The exact expression in the exponent does not matter for what I am about to say, but is present in the files linked to in the beginning. Also, $\sigma^2 = \sigma^2(\theta,p)$).

I carry the maximization of the likelihood by the Nelder-Meads algorithm (fminsearch in MATLAB). But here is my problem: in some cases, when the initial data set is too large (I am minimizing $-sin(x)$ on $[0,\pi]$, and 'too large' is ~10) what happens, is that the values the algorithm goes for are such, that the matrix $R$ becomes nearly singular ($cond(R)$ ~ $1e^{16}$). This can be explained, since we have a determinant of the matrix in negative power in the likelihood function. Thus, for a singular matrix the determinant becomes zero, and the likelihood function itself diverges to infinity. But because my calculations also feature $R^{-1}$, having a nearly-singular matrix is problematic for the algorithm (and that is indeed the case, the returned estimated function behaves nothing like the original).

Note, that this does not happen always, and for some initial data of ~4 points, the aprroximation to the function behaves very well, so I have reason to believe that the mistake is not simply a coding mistake.

Thus I ask again: is there another way to estimate the parameters? Am I doing something wrong? Is this a weak point in the algorithm?

$\endgroup$
  • $\begingroup$ Hi - I have done quite a lot of development on the DACE matlab toolbox. Can you copy and paste the result from the DACEFIT routine, i.e., the dmodel? I would suspect that the problem is your use of the correxp function as correlation function. corrgauss is probably better. $\endgroup$ – OscarB Jun 12 '14 at 20:06
  • $\begingroup$ @OscarB I am not using the DACE matlab toolbox, I wrote all the codes myself. Actually, didn't even know it existed. Also, I have used neither correxp nor corrgaus. The correlation matrix is computed exactly the way I wrote in the question. Thanks! $\endgroup$ – Aahz Jun 12 '14 at 20:28
  • $\begingroup$ When I remove the determinant from the denominator in the expression I maximize (the likelihood), the algorithm seems to fit the function much better. Also, I have set $p = (2,2,...,2)$, so now I am working with Gaussian correlation, if I am not mistaken. $\endgroup$ – Aahz Jun 13 '14 at 7:14
  • 1
    $\begingroup$ Ok, in DACE, I believe this problem is solved by adding a very low value to the diagonal of R. This is called Ridge Regression, and I believe that there is some statistical foundation that suggests it to be a fair thing to do. I believe the added value is (100+m)*eps, where m is the number of samples and eps=2^(-52) in Matlab. Also, note that R is SPD, so therefore a Cholesky Factorization can be used, which I believe adds stability and also can be used to more rapidly compute the determinant. See the DACE toolbox, function objfunc. $\endgroup$ – OscarB Jun 13 '14 at 7:15
  • $\begingroup$ Thanks, I will try that. But in any case, removing the determinant seems to work as well, at least for the test cases I have tried. I will write here, once I try your modification. $\endgroup$ – Aahz Jun 13 '14 at 8:59

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.