Math | Terra Incognita

Math, News, Science

The bad good news for optimization

A new published paper called “NP-hardness of Deciding Convexity of Quartic Polynomials and Related Problems” brings light (or darkness) into a 20 years-old problem related to the whether or not does exist a polynomial time algorithm that can decide if a multivariate polynomial is globally convex. The answer is: NO.

Convex vs Non Convex Functions — Convex (top) vs Non Convex (bottom) Functions (Source: MIT News)

From the news article:

For complex functions, finding global minima can be very hard. But it’s a lot easier if you know in advance that the function is convex, meaning that the graph of the function slopes everywhere toward the minimum. Convexity is such a useful property that, in 1992, when a major conference on optimization selected the seven most important outstanding problems in the field, one of them was whether the convexity of an arbitrary polynomial function could be efficiently determined.

Almost 20 years later, researchers in MIT’s Laboratory for Information and Decision Systems have finally answered that question. Unfortunately, the answer, which they reported in May with one paper at the Society for Industrial and Applied Mathematics (SIAM) Conference on Optimization, is no. For an arbitrary polynomial function — that is, a function in which variables are raised to integral exponents, such as 13x⁴ + 7xy² + yz — determining whether it’s convex is what’s called NP-hard. That means that the most powerful computers in the world couldn’t provide an answer in a reasonable amount of time.

At the same conference, however, MIT Professor of Electrical Engineering and Computer Science Pablo Parrilo and his graduate student Amir Ali Ahmadi, two of the first paper’s four authors, showed that in many cases, a property that can be determined efficiently, known as sum-of-squares convexity, is a viable substitute for convexity. Moreover, they provide an algorithm for determining whether an arbitrary function has that property.

Read the full news article here, or the paper here.

16/07/2011 by Christian S. Perone

Math

Riemann Zeta function visualizations with Python

While playing with mpmpath and it’s Riemann Zeta function evaluator, I came upon those interesting animated plottings using Matplotlib (the source code is in the end of the post).

Riemann zeta function is an analytic function and is defined over the complex plane with one complex variable denoted as “ $s$ “. Riemann zeta is very important to mathematics due it’s deep relation with primes; the zeta function is given by:

$\zeta(s) = \sum_{n=1}^\infty \frac{1}{n^s} = \frac{1}{1^s} + \frac{1}{2^s} + \frac{1}{3^s} + \cdots$

for $Re(s) > 1$ .

So, let $\zeta(s)=v$ where $s = a + b\imath$ and $v = u + k\imath$ .

The first plot uses the triplet $(x,y,z)$ coordinates to plot a 3D space where each component is given by:

$x = Re(v)$ (or $x = u$ , previously defined);
$y = Im(v)$ (or $y = k$ , previously defined);
$z = Im(s)$ (or $z = b$ , previously defined);
The time component used in the animation is called $\theta$ and it’s given by $\theta = Re(s)$ or simply $\theta = a$ .

To plot the animation I’ve used the follow intervals:

For $Re(s)$ : from $\left[0.01, 10.0\right)$ , this were calculated at every 0.01 step – shown in the plot at top right;
For $Im(s)$ : from $\left[0.1, 200.0\right)$ , calculated at every 0.1 step – shown as the $z$ axis.

This plot were done using a fixed interval (no auto scale) for the $(x,y,z)$ coordinates. Where $Re(s) = 1/2$ ( $\theta = 1/2$ ) is when the non-trivial zeroes of Riemann Zeta function lies.

Now see the same plot but this time using auto scale (automatically resized $x,y$ coordinates):

Note the $(x,y)$ auto scaling.

See now from another plotting using a 2D space where each component is given by:

$x = Im(s)$ (or $x = b$ , previously defined);
$y = Im(v)$ (blue) and $Re(v)$ (green);
The time component used in the animation is called $\theta$ and it’s given by $\theta = Re(s)$ or simply $\theta = a$ .

To plot the animation I’ve used the follow intervals:

For $Re(s)$ : from $\left[0.01, 10.0\right)$ , this were calculated at every 0.01 step – shown in title of the plot at top;
For $Im(s)$ : from $\left[0.1, 50.0\right)$ , calculated at every 0.1 step – shown as the $x$ axis.

This plot were done using a fixed interval (no auto scale) for the $(x,y)$ coordinates. Where $Re(s) = 1/2$ ( $\theta = 1/2$ ) is when the non-trivial zeroes of Riemann Zeta function lies. The first 10 non-trivial zeroes from Riemann Zeta function is shown as a red dot, when the two series, the $Im(v)$ and $Re(v)$ cross each other on the red dot at the critical line ( $Re(s) = 1/2$ ) is where lies the zeroes of the Zeta Function, note how the real and imaginary part turns away from each other as the $Re(s)$ increases.

Now see the same plot but this time using auto scale (automatically resized $y$ coordinate):

If you are interested in more visualizations of Riemann Zeta function, you’ll like the well-done paper from J. Arias-de-Reyna called “X-Ray of Riemann zeta-function“.

I always liked the way visualization affects the understanding of math functions. Anscombe’s quartet is a clear example of how important visualization is.

The source-code used to create the plot are available here:

Source code for the 2D plots

Source code for the 3D plots

I hope you liked the post ! To make the plots and videos I’ve used matplotlib, mpmath and MEncoder.

– Christian S. Perone

20/02/2010 by Christian S. Perone