ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 10 Apr 2017 21:45:01 -0500Black box numerical optimization of a convex functionhttp://ask.sagemath.org/question/23831/black-box-numerical-optimization-of-a-convex-function/I would like to numerically optimize a convex function without using any of its internals, that is, a python function. Is there an implementation of this in sage? I tried `sage.numerical.optimize.find_local_minimum` but it fails internally with a
TypeError: unable to find a common ring for all elements
My function to optimize is in fact the second largest eigenvalue of a matrix that is constructed from one parameter. Here it is in all gory detail:
def binaryStrings(k):
for i in range(2**k):
s = str(bin(i))[2:]
yield "0"^(k-len(s)) + s;
def hammingDistanceInt (a,b):
return bin(a^^b).count("1")
def cubeAdjacency (k):
# Note: We would like to use QQ instead of CDF, but this will
# result in inexact computations failing due to rounding later
# (Yes it does!)
# https://groups.google.com/forum/#!topic/sage-support/3IIbu0OBJX4
return matrix(CDF, 2^k, 2^k, lambda i, j: 1 if hammingDistanceInt(i,j)==1 else 0);
def hemmeckeFiberAdjacency (k, p1):
p2 = (1 - 4*k*p1)/2;
M = p1 * block_diagonal_matrix (cubeAdjacency(k),cubeAdjacency(k));
M[0,2^k] = p2
M[2^k,0] = p2
rowsums = M * vector ([1]*2^(k+1))
M += diagonal_matrix(vector([1]*2^(k+1))-rowsums);
return M
def slem(k,p):
e = map(abs, hemmeckeFiberAdjacency(k,p).eigenvalues())
e.sort();
return e[-2];
def slem4(p): return slem(4,p)
plot(slem4, [0,1/16]) # Works fine
sage.numerical.optimize.find_local_minimum(slem4, [0,1/16]) # Type errorTue, 19 Aug 2014 05:43:57 -0500http://ask.sagemath.org/question/23831/black-box-numerical-optimization-of-a-convex-function/Comment by tmonteil for <p>I would like to numerically optimize a convex function without using any of its internals, that is, a python function. Is there an implementation of this in sage? I tried <code>sage.numerical.optimize.find_local_minimum</code> but it fails internally with a </p>
<pre><code>TypeError: unable to find a common ring for all elements
</code></pre>
<p>My function to optimize is in fact the second largest eigenvalue of a matrix that is constructed from one parameter. Here it is in all gory detail:</p>
<pre><code>def binaryStrings(k):
for i in range(2**k):
s = str(bin(i))[2:]
yield "0"^(k-len(s)) + s;
def hammingDistanceInt (a,b):
return bin(a^^b).count("1")
def cubeAdjacency (k):
# Note: We would like to use QQ instead of CDF, but this will
# result in inexact computations failing due to rounding later
# (Yes it does!)
# https://groups.google.com/forum/#!topic/sage-support/3IIbu0OBJX4
return matrix(CDF, 2^k, 2^k, lambda i, j: 1 if hammingDistanceInt(i,j)==1 else 0);
def hemmeckeFiberAdjacency (k, p1):
p2 = (1 - 4*k*p1)/2;
M = p1 * block_diagonal_matrix (cubeAdjacency(k),cubeAdjacency(k));
M[0,2^k] = p2
M[2^k,0] = p2
rowsums = M * vector ([1]*2^(k+1))
M += diagonal_matrix(vector([1]*2^(k+1))-rowsums);
return M
def slem(k,p):
e = map(abs, hemmeckeFiberAdjacency(k,p).eigenvalues())
e.sort();
return e[-2];
def slem4(p): return slem(4,p)
plot(slem4, [0,1/16]) # Works fine
sage.numerical.optimize.find_local_minimum(slem4, [0,1/16]) # Type error
</code></pre>
http://ask.sagemath.org/question/23831/black-box-numerical-optimization-of-a-convex-function/?comment=23832#post-id-23832In order to understand where the error comes from, could you please provide the construction of the function to optimise ?Tue, 19 Aug 2014 07:48:58 -0500http://ask.sagemath.org/question/23831/black-box-numerical-optimization-of-a-convex-function/?comment=23832#post-id-23832Answer by tmonteil for <p>I would like to numerically optimize a convex function without using any of its internals, that is, a python function. Is there an implementation of this in sage? I tried <code>sage.numerical.optimize.find_local_minimum</code> but it fails internally with a </p>
<pre><code>TypeError: unable to find a common ring for all elements
</code></pre>
<p>My function to optimize is in fact the second largest eigenvalue of a matrix that is constructed from one parameter. Here it is in all gory detail:</p>
<pre><code>def binaryStrings(k):
for i in range(2**k):
s = str(bin(i))[2:]
yield "0"^(k-len(s)) + s;
def hammingDistanceInt (a,b):
return bin(a^^b).count("1")
def cubeAdjacency (k):
# Note: We would like to use QQ instead of CDF, but this will
# result in inexact computations failing due to rounding later
# (Yes it does!)
# https://groups.google.com/forum/#!topic/sage-support/3IIbu0OBJX4
return matrix(CDF, 2^k, 2^k, lambda i, j: 1 if hammingDistanceInt(i,j)==1 else 0);
def hemmeckeFiberAdjacency (k, p1):
p2 = (1 - 4*k*p1)/2;
M = p1 * block_diagonal_matrix (cubeAdjacency(k),cubeAdjacency(k));
M[0,2^k] = p2
M[2^k,0] = p2
rowsums = M * vector ([1]*2^(k+1))
M += diagonal_matrix(vector([1]*2^(k+1))-rowsums);
return M
def slem(k,p):
e = map(abs, hemmeckeFiberAdjacency(k,p).eigenvalues())
e.sort();
return e[-2];
def slem4(p): return slem(4,p)
plot(slem4, [0,1/16]) # Works fine
sage.numerical.optimize.find_local_minimum(slem4, [0,1/16]) # Type error
</code></pre>
http://ask.sagemath.org/question/23831/black-box-numerical-optimization-of-a-convex-function/?answer=23905#post-id-23905Here is the problem: if you look at the Traceback, you can see that the problem is in ``hemmeckeFiberAdjacency``, when you compute the ``diagonal_matrix``. You can also see that this function tries to find a common ring for the elements you give them.
So let us add some bugtracking in your code by replacing:
M += diagonal_matrix(vector([1]*2^(k+1))-rowsums);
by:
try:
M += diagonal_matrix(vector([1]*2^(k+1))-rowsums);
except Exception:
print "bug", p1, p1.parent()
so that when the error will appear, we will be able to see which ``p1`` caused the problem.
Indeed, we get another error : ``AttributeError: 'numpy.float64' object has no attribute 'parent'``. Here is the explanation : when you call ``sage.numerical.optimize.find_local_minimum``, Sage uses ``scipy.optimize`` which uses ``numpy.float64`` floating point numbers. Those numbers have no parent (a ring to live in) in Sage.
To fix your problem, you can just ensure that the ``p1`` that is given to ``hemmeckeFiberAdjacency`` can be correctly handled by Sage. It suffice to transform it into an element of the ``Real Double Field`` (which are Sage floating point numbers with the same precision as ``numpy.float64`` elements) by adding the following line at the beginning of your function ``hemmeckeFiberAdjacency``.
p1 = RDF(p1)
Now you will get:
sage: sage.numerical.optimize.find_local_minimum(slem4, 0,1/16)
(0.993614695234, 0.042890047690081409)
Which corresponds to what you saw on the picture.
Fri, 22 Aug 2014 19:34:41 -0500http://ask.sagemath.org/question/23831/black-box-numerical-optimization-of-a-convex-function/?answer=23905#post-id-23905Comment by tmonteil for <p>Here is the problem: if you look at the Traceback, you can see that the problem is in <code>hemmeckeFiberAdjacency</code>, when you compute the <code>diagonal_matrix</code>. You can also see that this function tries to find a common ring for the elements you give them.</p>
<p>So let us add some bugtracking in your code by replacing:</p>
<pre><code>M += diagonal_matrix(vector([1]*2^(k+1))-rowsums);
</code></pre>
<p>by:</p>
<pre><code>try:
M += diagonal_matrix(vector([1]*2^(k+1))-rowsums);
except Exception:
print "bug", p1, p1.parent()
</code></pre>
<p>so that when the error will appear, we will be able to see which <code>p1</code> caused the problem.</p>
<p>Indeed, we get another error : <code>AttributeError: 'numpy.float64' object has no attribute 'parent'</code>. Here is the explanation : when you call <code>sage.numerical.optimize.find_local_minimum</code>, Sage uses <code>scipy.optimize</code> which uses <code>numpy.float64</code> floating point numbers. Those numbers have no parent (a ring to live in) in Sage.</p>
<p>To fix your problem, you can just ensure that the <code>p1</code> that is given to <code>hemmeckeFiberAdjacency</code> can be correctly handled by Sage. It suffice to transform it into an element of the <code>Real Double Field</code> (which are Sage floating point numbers with the same precision as <code>numpy.float64</code> elements) by adding the following line at the beginning of your function <code>hemmeckeFiberAdjacency</code>.</p>
<pre><code>p1 = RDF(p1)
</code></pre>
<p>Now you will get:</p>
<pre><code>sage: sage.numerical.optimize.find_local_minimum(slem4, 0,1/16)
(0.993614695234, 0.042890047690081409)
</code></pre>
<p>Which corresponds to what you saw on the picture.</p>
http://ask.sagemath.org/question/23831/black-box-numerical-optimization-of-a-convex-function/?comment=37258#post-id-37258^_^ .Mon, 10 Apr 2017 21:45:01 -0500http://ask.sagemath.org/question/23831/black-box-numerical-optimization-of-a-convex-function/?comment=37258#post-id-37258Comment by Thomas for <p>Here is the problem: if you look at the Traceback, you can see that the problem is in <code>hemmeckeFiberAdjacency</code>, when you compute the <code>diagonal_matrix</code>. You can also see that this function tries to find a common ring for the elements you give them.</p>
<p>So let us add some bugtracking in your code by replacing:</p>
<pre><code>M += diagonal_matrix(vector([1]*2^(k+1))-rowsums);
</code></pre>
<p>by:</p>
<pre><code>try:
M += diagonal_matrix(vector([1]*2^(k+1))-rowsums);
except Exception:
print "bug", p1, p1.parent()
</code></pre>
<p>so that when the error will appear, we will be able to see which <code>p1</code> caused the problem.</p>
<p>Indeed, we get another error : <code>AttributeError: 'numpy.float64' object has no attribute 'parent'</code>. Here is the explanation : when you call <code>sage.numerical.optimize.find_local_minimum</code>, Sage uses <code>scipy.optimize</code> which uses <code>numpy.float64</code> floating point numbers. Those numbers have no parent (a ring to live in) in Sage.</p>
<p>To fix your problem, you can just ensure that the <code>p1</code> that is given to <code>hemmeckeFiberAdjacency</code> can be correctly handled by Sage. It suffice to transform it into an element of the <code>Real Double Field</code> (which are Sage floating point numbers with the same precision as <code>numpy.float64</code> elements) by adding the following line at the beginning of your function <code>hemmeckeFiberAdjacency</code>.</p>
<pre><code>p1 = RDF(p1)
</code></pre>
<p>Now you will get:</p>
<pre><code>sage: sage.numerical.optimize.find_local_minimum(slem4, 0,1/16)
(0.993614695234, 0.042890047690081409)
</code></pre>
<p>Which corresponds to what you saw on the picture.</p>
http://ask.sagemath.org/question/23831/black-box-numerical-optimization-of-a-convex-function/?comment=24015#post-id-24015Thanks a lot for the detailed explanation!Sun, 31 Aug 2014 10:47:03 -0500http://ask.sagemath.org/question/23831/black-box-numerical-optimization-of-a-convex-function/?comment=24015#post-id-24015