# Solve multi-dimensional optimization problem using basinhopping

I am searching for an optimization solution, which is a 8d vector representing 4 complex elements, where each element is within the complex circle with maximal radius 1.2.

The objective function is:

$$f: \left\|\mathbf{c}_{ref}-\mathbf{c}\right\|_{2}+\left|2-\|\mathbf{c}\|_{2}\right|$$

I am using the scipy.optimize.basinhopping module.

import numpy as np
from scipy import optimize

class MyBounds(object):
def __init__(self, xmax=[360, 360, 360, 360, 1.2, 1.2, 1.2, 1.2], xmin=[0, 0, 0, 0, 0, 0, 0, 0] ):
self.xmax = np.array(xmax)
self.xmin = np.array(xmin)

def __call__(self, **kwargs):
x    = kwargs["x_new"]
tmax = bool(np.all(x <= self.xmax))
tmin = bool(np.all(x >= self.xmin))
return tmax and tmin

class MyTakeStep(object):
def __init__(self, stepsize=45):
self.stepsize = stepsize
def __call__(self, x):
s = self.stepsize
x += np.random.uniform(0, 1*s)
x += np.random.uniform(0, 2*s)
x += np.random.uniform(0, 3*s)
x += np.random.uniform(0, 4*s)
s = 1
x += np.random.uniform(0, 1*s)
x += np.random.uniform(0, 1*s)
x += np.random.uniform(0, 1*s)
x += np.random.uniform(0, 1*s)
return x

def f(input_list):
polar_form = [rphi for rphi in zip(input_list[4:], input_list[:4])]
x          = np.array([z(e, e) for e in polar_form])
# objective function componenets
result  = abs(2 - np.linalg.norm(x, 2)) + np.linalg.norm(cref-x, 2)
return result

def hopping_solver(min_f, min_x):
comb             = np.array([0, 0, 0, 0, 0, 0, 0, 0])
# define bounds
mybounds   = MyBounds()
mytakestep = MyTakeStep()
optimal_c  = optimize.basinhopping(f, x0 = comb, niter=50000, T=45, stepsize=1, minimizer_kwargs=minimizer_kwargs, take_step=None, accept_test=mybounds, callback=None, interval=5000, disp=False, niter_success=None)

min_x, min_f = optimal_c['x'], optimal_c['fun']
print(optimal_c)
return min_x, min_f

min_f = 10**10
min_x = []
min_x, min_f = hopping_solver(min_f, min_x)


My questions relate to the step essentially: My first elements are angles in [0, 360] and the others are in [0, 1.2]. What is a suitable way to define a good step here to balance between precision and fast processing?

I am aware that this code does not return the global minimum.

Also here I chose the center of my solutions space as $$x_0$$, are there recommendations on how to choose the starting point?

• I would suggest you change from degrees to radians since it would give a better scaling of your problem, although I am not that sure it matters for Nelder-Mead. You could also use a higher order method when you are far away from the kinks in your objective function. – nicoguaro Mar 21 '19 at 13:44
• Actually, I think that the polar representation of complex numbers is singularly unsuitable to the problem here. It makes the problem non-unique (because you can add $2\pi$ to the angles and get another solution), and the spacing of points separated by a certain $(dr,d\phi)$ is non-uniform depending on where you are in the complex plane. – Wolfgang Bangerth Mar 21 '19 at 14:17
• @nicoguaro Thank you for the suggestion, I am currently experimenting with angles in radians, which helped a bit with the scalibility. However, I still cannot get the correct solution despite trying different steps and the scipy iterations terminate successfully but do not get close enough to my solution. For example final f(x) = 1.34 where as it should get close to 0. – SuperKogito Mar 21 '19 at 16:35
• @WolfgangBangerth well I agree but if you take a look at my bounds you will notice that I am limiting my solution's space to complex numbers with amplitude =< 1.2 and phases within [0, 360]. So I am only interested in solutions in that space and those should be unique. – SuperKogito Mar 21 '19 at 16:37
• But step length determination becomes more complicated in polar coordinates. And you have to deal with bounds. When you have a bounds limited problem, you may also end up with multiple local minima where before you had only one global minimum. – Wolfgang Bangerth Mar 21 '19 at 17:10

Geometrically, you are trying to find a point that is (i) as close as possible to the point $$\mathbf c_{ref}$$ and (ii) as close as possible to the sphere of radius 2. Your objective function is the sum of these two distances. The solution is that point $$\mathbf c$$ that is half-way between $$\mathbf c_{ref}$$ and the (closest point on the) sphere of radius 2, i.e., the solution if the vector $$\mathbf c = \frac 12 \left( \mathbf c_{ref} + 2 \frac{\mathbf c_{ref}}{\|\mathbf c_{ref}\|}\right).$$ Written differently, you get that $$\mathbf c = \left( \frac 12 + \frac{1}{\|\mathbf c_{ref}\|}\right) \mathbf c_{ref}.$$
• Actually, any point on the connecting line between $\mathbf c_{ref}$ and the closest point on the sphere of radius 2 is a solution. – Wolfgang Bangerth Mar 20 '19 at 22:26
• Well thank you for you suggestion, but it doesn't answer my question. Actually, my function is more complex than what I included, therefore my main concern here is proper initialization of the parameters. According to your solution my c is just $c_{ref}$ since I already have $\|c_{ref}\|_{2} = 2$. – SuperKogito Mar 21 '19 at 12:42