13

Considérons 30 matrices Toeplitz 30 par 30 dont toutes les entrées sont 0 ou 1. Ce défi est un défi d'optimisation simple pour trouver la matrice avec le plus grand déterminant possible.

Entrée Aucune

Sortie d' une matrice Toeplitz 30 x 30 dont toutes les entrées sont 0 ou 1 avec son déterminant.

Score Le déterminant de la matrice que vous produisez. Si deux personnes obtiennent le même score, la première réponse l'emporte.

Principales entrées à ce jour

65.455.857.159.975 en Matlab par Nick Alger (environ (10 ^ 13.8)
65,455,857,159,975 en Python par isaacg (environ 10 ^ 13,8)
39 994 961 721 988 dans Mathematica d' ici 2012 camp (environ 10 ^ 13,6)
39,788,537,400,052 dans R par Flounderer (environ 10 ^ 13,6)
8,363,855,075,832 en Python par Vioz- (environ 10 ^ 12,9)
6,984,314,690,903 dans Julia par Alex A. (environ 10 ^ 12,8)

Contraintes supplémentaires ennuyeuses 16 juillet 2015

Si cela est possible, veuillez utiliser une arithmétique arbitraire ou de haute précision pour calculer le déterminant de sortie final afin que nous puissions être sûrs de ce qu'il est réellement (il devrait toujours être un entier). En python, cela devrait être utile.

code-challenge math optimization Communauté
la source

Je suis surpris que ce problème ne soit pas déjà résolu. La réponse est-elle connue pour les matrices circulantes?

xnor

1

@NickAlger Si la bibliothèque est accessible au public pour tout le monde, vous pouvez l'utiliser.

orlp

2

@immibis Malheureusement, il y en a 2 ^ 59.

1

Il est intéressant de noter que deux méthodes indépendantes ont permis d'obtenir une matrice de Toeplitz avec exactement le déterminant de matrice circulante maximum. Je n'ai aucune intuition mathématique pour savoir pourquoi - ce déterminant est-il juste commun pour les matrices binaires de Toeplitz?

lirtosiast

1

@ Min_25 Je devrais avoir le maximum jusqu'à 19 d'ici demain. Vous obtiendra le code / valeurs dans la question connexe, Lembik. Avec des algorithmes heuristiques, j'ai atteint au maximum exactement les mêmes valeurs pour n = 30 que les deux autres affiches jusqu'à présent. Plusieurs fois, avec randomisation impliquée. Aussi avec des matrices circulantes comme résultat chaque fois que j'atteins ce maximum, même si ma recherche ne se limite pas aux matrices circulantes. BTW, un autre fait déroutant (pour moi): le maximum pour n = 15 est exactement 2 ^ 17.

Reto Koradi

11

Matlab, 65,455,857,159,975 (10 ^ 13.8159)

La méthode est une ascension en gradient à l'intérieur du cube [0,1] ^ 59, avec de nombreuses suppositions initiales aléatoires, et un arrondi à la fin pour tout faire des zéros et des uns.

Matrice:

0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0
0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1
1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1
1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1
1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0
0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1
1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1
1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1
1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0
0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1
1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0
0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0
0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0
0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1
1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0
0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0
0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1
1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0
0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1
1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1
1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0
0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1
1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0
0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0
0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0
0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0
0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1
1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1
1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1
1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0

Code:

% Toeplitz 0-1 determinant optimization

n = 30;
m = n + n-1;

toeplitz_map = @(w) toeplitz(w(n:-1:1), w(n:end));

objective = @(w) det(toeplitz_map(w));

detgrad = @(A) det(A)*inv(A)';

toeplitz_map_matrix = zeros(n^2,m);
for k=1:m
    ek = zeros(m,1);
    ek(k) = 1;
    M = toeplitz_map(ek);
    toeplitz_map_matrix(:,k) = M(:);
end

gradient = @(w) (reshape(detgrad(toeplitz_map(w)),1,n^2)*...
                 toeplitz_map_matrix)';

%check gradient with finite differences
w = randn(m,1);
dw = randn(m,1);
s = 1e-6;
g_diff = (objective(w+s*dw) - objective(w))/s;
g = gradient(w)'*dw;
grad_err = (g - g_diff)/g_diff

warning('off')
disp('multiple gradient ascent:')
w_best = zeros(m,1);
f_best = 0;
for trial=1:100000
    w0 = rand(m,1);
    w = w0;
    alpha0 = 1e-5; %step size
    for k=1:20
        f = objective(w);
        g = gradient(w);
        alpha = alpha0;
        for hh=1:100
            w2 = w + alpha*g;
            f2 = objective(w2);
            if f2 > f
                w = w2;
                break;
            else
                alpha = alpha/2;
            end
        end

        buffer = 1e-4;
        for jj=1:m
            if (w(jj) > 1)
                w(jj) = 1 - buffer;
            elseif (w(jj) < 0)
                w(jj) = 0 + buffer;
            end
        end
    end

    w = round(w);
    f = objective(w);
    if f > f_best
        w_best = w;
        f_best = f;
    end
    disp(trial)
    disp(f_best)
    disp(f)
end

M = toeplitz_map(w_best);

Les mathématiques derrière le calcul du gradient:

Dans le produit intérieur élément par élément (c'est-à-dire le produit intérieur de Hilbert-Schmidt), le gradient du déterminant a Riesz représentatif G donné par

G = det (A) A ^ (- *).

La carte, J, des variables d'optimisation (valeurs diagonales) aux matrices toeplitz est linéaire, donc le gradient global g est la composition de ces deux cartes linéaires,

g = (vec (G) * J) »,

où vec () est l' opérateur de vectorisation qui prend une matrice et la déplie en un vecteur.

Montée en dégradé intérieur:

Après cela, tout ce que vous avez à faire est de choisir un vecteur initial de valeurs diagonales w_0, et pour certaines petites étapes, itérer alpha:

w_proposé = w_k + alpha * g_k
pour obtenir w_ (k + 1), prendre w_proposed et tronquer les valeurs en dehors de [0,1] à 0 ou 1
répétez jusqu'à ce que vous soyez satisfait, puis arrondissez le tout à 0 ou 1.

Mon résultat a atteint ce déterminant après avoir fait environ 80 000 essais avec des hypothèses initiales aléatoires uniformes.

Nick Alger
la source

Le lien OEIS que vous avez donné concernait les matrices circulantes, qui sont un cas particulier des matrices Topelitz. Donc, c'est encore mieux.

isaacg

@isaacg Et aussi extrêmement probable!

Oui bien sûr, je me trompais. J'ai modifié mon message pour le corriger.

Nick Alger

1

Oui, il a atteint cette valeur à l'itération 250 et y est resté pendant 100 000 itérations. Le vecteur définissant la matrice toeplitz 18x18 avec le déterminant 2994003 était [0,0,0,1,0,1,1,1,1,0,1,1,0,0,0,1,0,1,0, 0,0,1,0,1,1,1,1,0,1,1,0,0,0,1,0], où l'ordre va du bas à gauche au haut à droite.

Nick Alger

2

Je vous ai décerné la victoire alors que vous aviez une nouvelle idée et que vous aviez le premier numéro IIRC. Oh, et cela montre pourquoi votre réponse fonctionne math.stackexchange.com/questions/1364471/… .

11

Python 2 avec Numpy, 65 455 857 159 975 ~ = 10 ^ 13,8

C'est de l'escalade, aussi simple que possible. Calcul du déterminant final effectué à l'aide de SymPy pour obtenir un résultat exact. Toutes les matrices trouvées avec ce déterminant sont circulantes.

Matrices trouvées avec ce déterminant, données comme valeur de diagonale du bas à gauche au coin supérieur droit:

01000100101101000011100111011101000100101101000011100111011
01011101110011100001011010010001011101110011100001011010010
01100001000111011101001110100101100001000111011101001110100
01110100111010010110000100011101110100111010010110000100011
01011101110001000011010010111001011101110001000011010010111
01000101100010110100111101110001000101100010110100111101110
01000100101101000011100111011101000100101101000011100111011

Le premier, sous forme de matrice:

[[1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1]
 [1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1]
 [1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0]
 [0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1]
 [1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1]
 [1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1]
 [1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0]
 [0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0]
 [0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1]
 [1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1]
 [1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1]
 [1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0]
 [0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0]
 [0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0]
 [0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0]
 [0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1]
 [1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0]
 [0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1]
 [1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1]
 [1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0]
 [0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1]
 [1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0]
 [0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0]
 [0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1]
 [1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0]
 [0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0]
 [0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0]
 [0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1]
 [1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0]
 [0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1]]

Code:

import numpy as np
import sympy as sp
import random
import time
SIZE = 30

random.seed(0)

def gen_diag():
    return [random.randint(0, 1) for i in range(SIZE*2 - 1)]

def diag_to_mat(diag):
    return [diag[a:a+SIZE] for a in range(SIZE-1, -1, -1)]

def diag_to_det(diag):
    matrix = diag_to_mat(diag)
    return np.linalg.det(matrix)

def improve(diag):
    old_diag = diag
    really_old_diag = []
    while really_old_diag != old_diag:
        really_old_diag = old_diag
        for flip_at in range(SIZE * 2 - 1):
            new_diag = old_diag[:]
            new_diag[flip_at] ^= 1
            old_diag = max(old_diag, new_diag, key=diag_to_det)
    return old_diag

overall_best_score = 0
time.clock()
while time.clock() < 500:
    best = improve(gen_diag())
    best_score = diag_to_det(best)
    if best_score > overall_best_score:
        overall_best_score = best_score
        overall_best = best
        print(time.clock(), sp.Matrix(diag_to_mat(overall_best)).det(), ''.join(map(str,overall_best)))


mat = diag_to_mat(overall_best)

sym_mat = sp.Matrix(mat)

print(overall_best)
print(sym_mat.det())

isaacg
la source

1

C'est fou. Bon travail.

Alex A.

Le .227 est un peu inquiétant. Pensez-vous qu'il existe un moyen d'être sûr de ce qu'est réellement le déterminant?

Il semble que stackoverflow.com/questions/6876377/… pourrait aider à évaluer le déterminant final?

@Lembik Merci - SymPy a fait l'affaire.

isaacg

C'est vraiment très bien!

10

R, 39 788 537 400 052

Voici ma tentative de faire un algorithme génétique mais uniquement avec une reproduction asexuée. J'espère avoir bien compris le défi. Edit: accéléré un peu, essayé une graine aléatoire différente et limitée à 100 générations.

    options(scipen=999)

toeplitz <- function(x){
# make toeplitz matrix with first row
# x[1:a] and first col x[(a+1):n]
# where n is the length of x and a= n/2
# Requires x to have even length
#
# [1,1] entry is x[a+1]

N <- length(x)/2
out <- matrix(0, N, N)
out[1,] <- x[1:N]
out[,1] <- x[(N+1):length(x)]
for (i in 2:N){
  for (j in 2:N){
    out[i,j] <- out[i-1, j-1]
  }
} 

out
}

set.seed(1002)

generations <- 100
popsize <- 25
cols <- 60
population <- matrix(sample(0:1, cols*popsize, replace=T), nc=cols)
numfresh <- 5 # number of totally random choices added to population

for (i in 1:generations){

fitness <- apply(population, 1, function(x) det(toeplitz(x)) )
mother <- which(fitness==max(fitness))[1]

population <- matrix(rep(population[mother,], popsize), nc=cols, byrow=T)
for (i in 2:(popsize-numfresh)){
  x <- sample(cols, 1)
  population[i,x] <- 1-population[i,x]
}
for (i in (popsize-numfresh +1):popsize){
  population[i,] <- sample(0:1, cols, replace=T)
}


print(population[1,])
print(fitness[mother])
print(det(toeplitz(population[1,]))) # to check correct

}

Production:

print(population[1, 1:(cols/2)]) # first row
print(population[1, (cols/2+1):(cols)]) # first column (overwrites 1st row)

to <- toeplitz(population[1,])

for (i in 1:(cols/2)) cat(to[i,], "\n")

1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 
0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 
1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 
0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 
0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 
0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 
1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 
1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 
1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 
1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 
0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 
1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 
1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 
1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 
0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 
0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 
0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 
0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 
1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 
0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 
0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 
1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 
0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 
0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 
0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 
0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 
1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 
0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 
1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 
1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1

Flet
la source

C'est très gentil. Vous gagnez de loin actuellement.

Plus

3

Julia, 6,984,314,690,902,998

Cela construit juste 1 000 000 de matrices Toeplitz aléatoires et vérifie leurs déterminants, enregistrant le maximum rencontré. J'espère que quelqu'un trouvera une solution analytique élégante, mais en attendant ...

function toeplitz(a, b)
    n = length(a)
    T = Array(Int, n, n)
    T[1,:] = b
    T[:,1] = a
    for i = 2:n
        T[i,2:n] = T[i-1,1:n-1]
    end
    T
end

d = 0
A = Any[]

for i = 1:1000000
    # Construct two random 0,1 arrays
    r1 = rand(0:1, 30)
    r2 = rand(0:1, 30)

    # Compute the determinant of a toeplitz matrix constructed
    # from the two random arrays
    D = det(toeplitz(r1, r2))

    # If the computed determinant is larger than anything we've
    # encountered so far, add it to A so we can access it later
    D > d && begin
        push!(A, (D, r1, r2))
        d = D
    end
end

M,N = findmax([i[1] for i in A])

println("Maximum determinant: ", M, "\n")
println(toeplitz(A[N][2], A[N][3]))

Vous pouvez voir la sortie ici .

Alex A.
la source

Je me demande à quel point le calcul déterminant est précis. Je suppose que le calcul sous-jacent se fait en double précision? Étant donné que les chiffres après la virgule décimale sont .998, il y a probablement de bonnes chances que l'entier le plus proche soit toujours le déterminant correct. Généralement, vous commencerez à obtenir des problèmes de précision en virgule flottante lors de l'application d'un calcul de déterminant à usage général, par exemple basé sur une décomposition LR standard, à ces matrices une fois qu'elles seront assez grandes.

Reto Koradi

@RetoKoradi On dirait qu'il utilise une décomposition LU pour obtenir le déterminant.

Alex A.

3

Mathematica, 39 994 961 721 988 (10 ^ 13,60)

Une méthode d'optimisation de recuit simulé simple; pas encore d'optimisation ou de réglage.

n = 30;
current = -\[Infinity];
best = -\[Infinity];
saved = ConstantArray[0, {2 n - 1}];
m := Array[a[[n + #1 - #2]] &, {n, n}];
improved = True;
iters = 1000;
pmax = 0.1;
AbsoluteTiming[
 While[improved || RandomReal[] < pmax,
   improved = False;
   a = saved;
   Do[
    Do[
      a[[i]] = 1 - a[[i]];
      With[{d = Det[m]},
       If[d > best,
          best = d;
          current = d;
          saved = a;
          improved = True;
          Break[];,
          If[d > current || RandomReal[] < pmax (1 - p/iters),
           current = d;
           Break[];,
           a[[i]] = 1 - a[[i]];
           ]
          ];
        ;
       ],
      {i, 2 n - 1}];,
    {p, iters}];
   ];
 ]
best
Log10[best // N]
a = saved;
m // MatrixForm

Exemple de sortie:

{20.714876,Null}
39994961721988
13.602
(1  1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0
0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0
0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0
0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0
0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1
1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0
0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0
0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0
0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0
0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1
1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1
1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0
0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1
1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1
1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0
0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1
1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1
1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1
1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0
0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1
1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1
1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0
0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0
0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0
0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0
0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1
1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0
0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1
1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1
1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1

)

2012rcampion
la source

1

Python 2, 8 363 855 075 832

Cela implique une stratégie très basique, presque inexistante.

from scipy import linalg

start = 2**28
mdet  = 0
mmat  = []
count = 0
powr  = 1
while 1:
 count += 1
 v = map(int,bin(start)[2:].zfill(59))
 m = [v[29:]]
 for i in xrange(1,30):
     m += [v[29-i:59-i]]
 d = 0
 try: d = linalg.det(m, check_finite=False)
 except: print start
 if d > mdet:
     print d
     print m
     mdet = d
     mmat = m
     start += 1
     powr = 1
 else:
     start += 2**powr
     powr += 1
     if start>(2**59-1):
         start-=2**59-1
         powr = 1
 if count%10000==0: print 'Tried',count

Voici la meilleure matrice trouvée après environ 5 580 000 essais:

1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1 1 0 1 0
1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1 1 0 1
1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1 1 0
0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1 1
1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1
0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0
1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1
0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0
0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0
1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1
1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0
0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0
0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0
0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0
0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0
0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0
1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1
0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1
1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1
1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0
1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1
1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1
1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1
1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0
1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1
1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1
0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0
0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0
1 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1
0 1 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1

Cours toujours...

Kade
la source

Un défi d'optimisation déterminant

Réponses: