October 3 2021
import numpy as np
from collections import Counter
import matplotlib.pyplot as plt
Build random adjacency matrix
N = 300
p = 1/500
def get_A():
A = (np.random.random((N, N)) < p).astype('float')
for i in range(N):
A[i,i] = 0
for i in range(N):
for j in range(N):
A[i,j] = A[j,i]
return A
Start with random state
def random_state():
return 2*((np.random.random(N) > 0.5).astype('float') - 0.5)
def cost(E, A, x):
return E + x.T @ A @ x
Test values that we get from random states
ctr = Counter()
A = get_A()
E = np.sum(A)
for _ in range(1000):
c = cost(E, A, random_state())
ctr[c] += 1
sorted(ctr.keys())[:5]
[92.0, 100.0, 108.0, 112.0, 116.0]
Try minimizing with simple local search
def local_search(A, f, x):
E = np.sum(A)
best = f(E, A, x)
loops = 0
print('-')
print('start cost:', best)
while True:
if loops % 20 == 0:
print('loop', loops, 'cost:', best)
bestpos = None
for i in range(N):
x[i] *= -1
newcost = f(E, A, x)
if newcost < best:
best = newcost
bestpos = i
x[i] *= -1
if bestpos == None:
break
x[bestpos] *= -1
loops += 1
print('final cost:', best)
return x
x = random_state()
x = local_search(A, cost, x)
- start cost: 164.0 loop 0 cost: 164.0 loop 20 cost: 64.0 final cost: 12.0
New idea: try the functional
def g(b, f):
return lambda *args: f(*args) * (b - f(*args)**2)
cost2 = g(N, cost)
for _ in range(2):
x_old = np.copy(x)
x2 = local_search(A, cost2, x)
print(np.sum(x2 - x_old), 'diff from cost2')
x = local_search(A, cost, x2)
- start cost: 1872.0 loop 0 cost: 1872.0 loop 20 cost: -4691232.0 loop 40 cost: -15178592.0 final cost: -24809488.0 22.0 diff from cost2 - start cost: 292.0 loop 0 cost: 292.0 loop 20 cost: 124.0 loop 40 cost: 44.0 final cost: 0.0 - start cost: 0.0 loop 0 cost: 0.0 final cost: 0.0 0.0 diff from cost2 - start cost: 0.0 loop 0 cost: 0.0 final cost: 0.0
The above works, but only if you end up at 0.
What about a simple 1-D function?
def func(x):
return -30*np.cos(x)*np.minimum(9/x/x, 3) + 90
inps = np.linspace(-20, 20, 100000)
plt.plot(inps, func(inps))
plt.grid()
inps = np.linspace(-20, 20, 100000)
func2 = g(0.3, func)
plt.plot(inps, func2(inps))
plt.grid()
plt.figure()
inps = np.linspace(-0.1, +0.1)
plt.plot(inps, func2(inps))
plt.grid()
Now try minimizing:
from scipy.optimize import fmin_bfgs
output = fmin_bfgs(func, np.random.random()*100)
output
Optimization terminated successfully. Current function value: 89.860280 Iterations: 5 Function evaluations: 12 Gradient evaluations: 6
array([43.93680628])
perturbation = 0.002
i = 0
while i < 200:
output = fmin_bfgs(func2, output[0] + (np.random.random()-0.5)*perturbation, disp=False)
print('f2:', output[0])
output = fmin_bfgs(func, output[0] + (np.random.random()-0.5)*perturbation, disp=False)
print('f:', output[0])
i += 1
f2: 40.791713368857685 f: 37.646039959742446 f2: 34.499612763860256 f: 43.93678638616231 f2: 47.08143253552639 f: 43.93681548161869 f2: 47.0814365274836 f: 43.93681438759613 f2: 47.08143437008191 f: 50.22568323596555 f2: 47.08144050768827 f: 47.081410821902644 f2: 47.08143543894255 f: 43.93686060069825 f2: 40.79171667620592 f: 37.64604460355624 f2: 34.4996126890453 f: 31.35221981497576 f2: 31.35222029916411 f: 31.352220943027163 f2: 28.203539150973803 f: 25.053079361077984 f2: 21.900077619729817 f: 12.406541444066196 f2: 15.580294407337428 f: 18.743252373453963 f2: 21.900078467482757 f: 25.0530795700924 f2: 21.900076720580216 f: 18.743252122005565 f2: 15.580294356421883 f: 18.743252979090745 f2: 9.210964519819845 f: 18.743252803422546 f2: 21.900077179121773 f: 18.743253556081196 f2: 21.900076821941006 f: 12.406543856320107 f2: 15.580294276885754 f: 12.406539741078568 f2: 15.580294361919822 f: 12.40653742120357 f2: 9.210964368916205 f: 12.406540720974439 f2: 15.580294140482058 f: 18.743253751425396 f2: 21.900077475480106 f: 25.053061861039964 f2: 28.203539396247777 f: 18.74325233054155 f2: 15.580294315661964 f: 12.406542966790052 f2: 9.210964376543624 f: 5.959392064131659 f2: 2.4587141785207045 f: -1.364988533164196e-08 f2: -1.420277156408731e-08 f: 2.6769595365763472e-08 f2: -1.1065216845389931e-08 f: 2.0699121355853213e-09 f2: -4.642402529588502e-09 f: 2.8982190991414837e-08 f2: -1.4627309644172472e-08 f: -8.400396173552935e-08 f2: -2.64918108201697e-07 f: -1.3388893765062443e-08 f2: -5.139203839181136e-09 f: -1.2844235434389106e-08 f2: -3.230666744091478e-08 f: -9.891516080725719e-09 f2: 2.206920859096806e-07 f: 2.1714522805326255e-09 f2: -1.1586400450935596e-08 f: -5.171013750372255e-09 f2: 3.0132224382913714e-07 f: -7.272002909658958e-09 f2: -1.3085403081701007e-08 f: -1.77899174096368e-08 f2: -6.7322820670598905e-09 f: 1.3159100591575868e-08 f2: 6.693980392051286e-08 f: -1.4022832137930864e-08 f2: -1.2071704732293138e-08 f: -8.25495738304817e-09 f2: 1.0633257102403947e-08 f: -1.1683278285082162e-08 f2: -6.243205755531497e-08 f: -8.350345054026868e-08 f2: -2.8437893595143707e-08 f: -8.163364511432632e-09 f2: -6.216204790512933e-09 f: -5.655789398530944e-09 f2: -9.661811313138922e-09 f: 3.598051711651076e-08 f2: 6.268555243769533e-09 f: -5.7406046920271e-09 f2: -3.392058295428608e-09 f: -1.109977809501722e-08 f2: 4.563220053503594e-09 f: 6.634165625982484e-08 f2: -1.1427658703629176e-08 f: 2.2960178409982527e-09 f2: -1.5451631957977624e-08 f: 2.2440805260685285e-09 f2: 9.057872032243698e-10 f: -5.565694449153474e-09 f2: -1.52730583992173e-08 f: -1.0920806425862052e-07 f2: -2.5598219679406117e-07 f: -1.2730880424388175e-08 f2: 1.9451934030537132e-09 f: -9.601680827807033e-08 f2: -3.6875406433521836e-07 f: -1.2678497484730836e-08 f2: -1.7217105723224813e-08 f: 7.582300707664833e-08 f2: -7.068155214035168e-09 f: 2.115127521574381e-09 f2: -1.7085611922003638e-08 f: -9.721972497769675e-08 f2: -3.697885671256158e-08 f: -1.6922178880418944e-08 f2: -4.285980664468624e-09 f: 6.579634918553543e-09 f2: -3.6368483943361243e-08 f: 3.386141405952673e-09 f2: -8.735534053679484e-08 f: -1.1606435261691432e-08 f2: -3.3007132626132235e-09 f: -2.9983529059604912e-09 f2: 4.071682137269388e-09 f: -3.6375489826620836e-10 f2: -5.4223292350168975e-09 f: 5.251004979353038e-08 f2: -8.596584629969433e-09 f: -5.062358603227958e-09 f2: -4.216799407609568e-10 f: 4.2154842922891185e-08 f2: -1.168520352948245e-08 f: -1.4192324119697597e-08 f2: 8.487203125067061e-08 f: -1.7042133419464117e-08 f2: -9.322491923223154e-09 f: -9.100708683396422e-09 f2: 4.713600969209666e-08 f: -2.307461871202339e-08 f2: -1.1365528177653033e-07 f: 3.209744516002996e-08 f2: 5.996512064771419e-09 f: -6.894220507072554e-09 f2: -1.4027091830871039e-08 f: 8.637822869700281e-10 f2: -9.417506796842056e-09 f: -4.425719319289204e-08 f2: -2.973455180983378e-09 f: -1.3986919402112562e-08 f2: -1.1013941575484395e-08 f: -8.399301461148772e-09 f2: -8.142661436322208e-08 f: 7.542169531098283e-08 f2: -1.1166415398291229e-08 f: -3.825637825929549e-09 f2: -1.1194117005440852e-08 f: -1.3370341921424079e-09 f2: -5.9302628851334404e-09 f: -9.005911722384627e-09 f2: 3.194455001256181e-09 f: -1.560377821931467e-08 f2: -8.374334296393412e-09 f: -6.14001229068632e-09 f2: -4.663435353211637e-09 f: 5.563994689029156e-09 f2: -9.749648420521138e-09 f: -1.905295946191453e-08 f2: -1.6795677533303676e-09 f: -7.528442945615699e-09 f2: -1.765222818036951e-08 f: -4.715651983246121e-09 f2: -1.4377265781889793e-08 f: -1.1026839719791428e-09 f2: 3.2345750212808383e-09 f: -2.6939126677114493e-09 f2: -3.11374433618135e-08 f: -1.0893529185259132e-09 f2: -3.973853410021251e-08 f: -1.4594040198328759e-09 f2: -4.634489247258222e-09 f: -1.0735658699723887e-08 f2: 1.0890923189546889e-08 f: 1.4956722205422632e-09 f2: -1.3987045092945464e-08 f: 6.646534862525706e-09 f2: -1.2322703617452878e-08 f: -1.600638650783989e-08 f2: -3.776005560803215e-09 f: -6.7836312225242915e-09 f2: 2.4446392737199745e-09 f: -6.4114966841796826e-09 f2: -4.850900962029452e-09 f: -1.2104112759368877e-07 f2: -2.0112656864458307e-08 f: -8.861531855191816e-09 f2: 1.140976919352223e-08 f: -3.6793790019688365e-09 f2: 2.1228932729311194e-07 f: -8.053365681547379e-09 f2: 5.930841935665397e-09 f: -5.424153287631036e-09 f2: 5.400724312155849e-09 f: -7.3517567332202406e-09 f2: 9.14631191951433e-08 f: -6.466985612228082e-09 f2: -9.275310447405842e-09 f: -4.154188215399783e-09 f2: -6.742127580450826e-09 f: -1.4799980484802782e-08 f2: -7.103135550476066e-08 f: -2.329704011143281e-10 f2: 2.8424044673405584e-09 f: -1.2821913995710453e-08 f2: -5.49853564528248e-09 f: -1.4372455167545182e-08 f2: -7.244505216154431e-09 f: -1.303467829825251e-08 f2: -1.1007437495817512e-07 f: -1.112574366145193e-08 f2: -5.668612302714188e-09 f: -8.453383592548823e-09 f2: -3.934256878585179e-09 f: 7.247809139150369e-08 f2: -5.843366281459717e-09 f: -1.9475639253818527e-08 f2: -6.370833178225077e-09 f: -4.747147169646842e-09 f2: -1.4553840305770306e-08 f: -3.6075279131152216e-09 f2: -1.1303986751661705e-08 f: -1.0577874514348419e-07 f2: -7.069732528707593e-09 f: -4.5796876537579356e-08 f2: -1.3767478324660695e-08 f: -9.251115607507993e-08 f2: -6.068352829784185e-09 f: 1.1370675209016433e-08 f2: -1.3466840815762978e-08 f: -3.2530271250048697e-08 f2: 4.394804462032449e-09 f: -7.492247625873433e-09 f2: -1.708519781039284e-08 f: 1.5057517774034877e-09 f2: -7.968063867893303e-09 f: 9.187608093156469e-09 f2: -1.7232581209599092e-09 f: -6.836641366129983e-09 f2: -2.0294430112712935e-07 f: -8.044509940050409e-09 f2: -8.579015702575728e-09 f: 1.9675936183654587e-09 f2: -1.4923589112419457e-08 f: -1.2435184704459168e-08 f2: 2.0091967303933426e-08 f: -9.451712130418167e-08 f2: -7.334484054903048e-09 f: 4.896384021759598e-09 f2: -1.4893722599063574e-08 f: -6.481262115157373e-09 f2: 2.694833716430662e-08 f: -3.465813358803941e-08 f2: -3.2954346999565336e-07 f: -6.526750330474572e-09 f2: 3.2830709701618183e-09 f: -2.6460795221074605e-08 f2: -5.052289904516373e-08 f: -8.095261866818725e-09 f2: 4.535813725742824e-09 f: 6.055000483472239e-08 f2: -2.40798460144964e-09 f: -1.1346936560328608e-08 f2: -9.800432018605264e-09 f: -8.70861525181446e-09 f2: -1.0009379910471419e-08 f: 2.1298770130223372e-08 f2: -1.566233841031841e-08 f: -2.108419073116332e-08 f2: -8.976576003711684e-09 f: -1.1339996105532715e-08 f2: -1.757372995145638e-08 f: -1.0455655323092158e-07 f2: -1.2386068048568814e-08 f: 5.034127528701212e-10 f2: 1.389918765287235e-09 f: -1.535603747882894e-08 f2: -6.321627255494828e-09 f: -1.0781224754441117e-08 f2: -9.399376786800995e-09 f: -3.3526180908817194e-09 f2: -5.146904091248698e-09 f: -3.311534832663722e-09 f2: -9.340528750724149e-09 f: 7.285909377636448e-09 f2: 6.36585597110122e-09 f: -6.751652565560552e-09 f2: -8.017542028101872e-09 f: -1.2016695357667814e-08 f2: -1.0866303465695776e-08 f: 1.8680625178083433e-08 f2: -4.284257949880184e-09 f: -1.0317748994472051e-07 f2: -4.1974206054035205e-09 f: -2.0457148379741854e-08 f2: 8.608336425088535e-09 f: -2.3805334461779242e-08 f2: -1.1086259635442434e-08 f: -6.666133516709071e-09 f2: 5.365042458980065e-10 f: 5.340582574591378e-09 f2: -1.7069062866034625e-07 f: -6.002989835681611e-09 f2: -7.47035339122277e-09 f: -1.3799717741736915e-08 f2: -1.6297840460921402e-08 f: -2.1959284553454626e-08 f2: -1.0769307856047612e-08 f: -3.81826119207041e-08 f2: -1.576105321248074e-08 f: -3.422195229943328e-09 f2: -1.0683106186825059e-08 f: -6.808237109075612e-09 f2: -5.509591628905181e-09 f: -2.9406205990525035e-08 f2: -1.2339597811990278e-08 f: 5.439592140930134e-08 f2: -2.3054901828712076e-09 f: -1.2209200756899918e-08 f2: -1.6806186876196065e-08 f: -5.364079217940985e-09 f2: 3.139223114627127e-08 f: 4.121766903789981e-08 f2: -1.4748409223491968e-08 f: -2.0078069565558805e-09 f2: -7.256273197163866e-09 f: 6.537850822828026e-08 f2: -7.532943036993632e-09 f: -1.0856285903011399e-08 f2: 1.1661171583286474e-08 f: 5.97958529637249e-08 f2: 7.819752006360016e-08 f: -1.1915277052401783e-08 f2: -4.430548669554845e-09 f: -9.711261680977717e-09 f2: -1.6913694509623e-09 f: 6.954297353126485e-08 f2: 1.9788642806632326e-08 f: -1.3794430152312137e-08 f2: -1.0783807684726387e-08 f: 4.285185114789956e-09 f2: -1.535856097571622e-08 f: -3.5008507944032756e-08 f2: -1.076692342011547e-08 f: -6.026605233320097e-09 f2: -8.793473533141513e-08 f: 6.473650136074429e-08 f2: -1.1759083504365295e-08 f: -2.9025178192995313e-09 f2: -2.0318600236568854e-08 f: -1.1058159120854912e-08 f2: 6.190312578995775e-09 f: -5.203049648614712e-08 f2: -1.93231005125442e-09 f: -5.1117676228912756e-09 f2: 4.110603399220305e-09 f: -7.550027145223617e-08 f2: -1.015167438233305e-08 f: 2.849391529338328e-09 f2: -4.271368350113032e-09 f: 1.2146743883821392e-09 f2: -1.1842691164907891e-08 f: 5.986920042095603e-08 f2: 1.3358218003777346e-08 f: -1.2561462247299591e-08 f2: 2.9756132328430905e-08 f: 5.1055239478400155e-09 f2: 1.258604523055062e-07 f: 8.408029184058061e-08 f2: -4.5337031819584405e-09 f: 1.1409406391784115e-09 f2: -9.363096078627031e-09 f: -8.12807069187297e-09 f2: -6.407271688619432e-09 f: -1.6451198173286817e-08 f2: -8.982165635000732e-09 f: -1.3441297029136173e-08 f2: -1.311143235865524e-08 f: -1.5719277920523282e-08 f2: 1.8119113799977288e-07 f: -1.2092239962104246e-08 f2: -9.278245678574003e-09 f: -7.251859279925366e-09 f2: -3.739445379567644e-08 f: -1.4513937924802566e-08
So the alternating minimizations can find the minima with energy $0$, amidst many local minima!