Extending a 2-dimensional nonlinear objective problem to 50-dimensions

[FOIWATER]

Hi,

I have a small two dimensional nonlinear objective that has a very well defined minimum and maximum. Here is the function:
$$f(x,y)=2(1-x)^{2}e^{-x^{2}-(y+2)^{2}}-9(\frac{x}{5}-x^{3}-y^{5})e^{-x^{2}-y^{2}}-\frac{1}{5}e^{-(x-1)^{2}-y^{2}}$$

Attached is it's plot and contour.

Notice this nonlinear function is only 2 dimensional in its arguments.

I am trying to code my own MATLAB function that will solve nonlinear optimizations (no constraints, at the moment) faster than the standard solver.

I want to test it against a large objective, I am thinking 50 or 60 arguments. I would like a function which has a well defined global minimum. Does anyone know of one which is?

I could extend the one above, but I want to be sure before I test with it..

Any help appreciated!

 

[andrewkirk]

What about the following, for $\vec{x}$ a $n$-vector?

$$f(\vec{x})\equiv \exp\left(\sum_{i=1}^n {x_i}^2\right)$$

It's nonlinear and has a global minimum at $\vec{x}=\vec{0}$.

Or did you want something that's not monotonic and hence has local extrema distinct from the global ones?

 

[FOIWATER]

That's a good function to keep in mind I will definitely do it thanks. I would love one that has various well defined local minima as well as a well defined global one, if I can find one

 

[andrewkirk]

I think this might give you what you want, for $n$ of the order of 50 or 60:

$$
f(\vec{x})\equiv \prod_{i=1}^n\left( a_i\prod_{j=1}^4 (x_i-b_{ij})\right)
$$

where $\forall i:\,a_{i}>0$. Just choose any bunch of coefficients $a_i$ and $b_{ij}$. You could get the computer to do this with random number generation, or you could choose a pattern for them. All that matters is that they are mostly different from one another.

$f$ is a product of $n$ quartic polynomials with positive leading coefficient. Each of the quartics will have a global minimum as well as possibly a local non-global minimum. Let the two local minima of the $i$th quartic be $m_i^1$ and $m_i^2$, where those two numbers are equal if the quartic has only one local minimum (eg $x^4$).

Then the set of local minima of $f$ is

$$S=\left\{(m_1^{k_1},m_2^{k_2},...,m_n^{k_n})\ |\ \forall i\ k_i\in\{1,2\}\right\}$$

$S$ has cardinality of at most $2^n$, so you can easily identify all the local minima and work out which one gives the global minimum.

You can then run it through your optimiser to see if it finds the correct minimum.

 

[FOIWATER]

That's awesome, is it a function that has any actual real world application or just something you've constructed

 

[andrewkirk]

I just made it up - especially for you.

 

[FOIWATER]

I am going to test it against this. Thankyou.

I am also trying to find a nonlinear function of about 50 variables, could be more could even be 100, that has a real world application with no constraints. Could even be a constrained problem where the constraints have been added to the objective as penalties. Do you know of any? I think most real world problems are going to be constrained at such a large number of variables, though.

 

[FOIWATER]

You see, I am trying to construct some of my own, but everytime I test them, they are unbounded. for example, I have been trying variations on:
$$\sum_{i=1}^{25}(0.25+0.5x_{i}+x_{i}^2)+constant\times \sum_{i=26}^{50}\sum_{j=26}^{50}x_{i}(x_{i}-x_{j})*constant$$
Or something like that. But when I test them in 'fminunc' it's always unbounded. I am noticing I need to make them with exp(-ve argument) so that as I move away from the origin in any direction, the function goes to zero. So the optimum is close to the origin.

 

[FOIWATER]

I am starting to realize the difficulty in constructing nonlinear functions without constraints that are bounded? Everything I am creating...is unbounded. Everything that's mostly nonlinear and not quadratic

 

[andrewkirk]

Try using sin and cos functions, which are bounded, non-linear and non-quadratic.

eg $\sum_{i=1}^n a_i\sin(b_i x_i+c_i)$ will have an infinite number of local extrema, but will be bounded by $\pm\sum_{i=1}^n |a_i|$.

If you want to ensure a unique global maximum and minimum, multiply it by
$$e^{-\sum_{i=1}^n {x_i}^2}$$.