What is the optimal exercise regime for improving cognitive functioning? It seems that researchers agree that physical exercise increases cognitive abilities. This seems to work universally for all ages: children, adults and old people. 

It is suggested that everyone should exercise for half an hour at least 3 times a week. I'm wondering if there are any studies which try to find dependencies between the amount of training and the effect of it on cognitive abilities?
Yes, there are several  studies which found links between the amount of training and the effect of it on cognitive abilities. See the below for references and summaries of some of these:

Jaeggi, Susanne M., et al. "Improving fluid intelligence with training on working memory." Proceedings of the National Academy of Sciences 105.19 (2008): 6829-6833.

Jaeggi et al. found that dual n-back could improve fluid intelligence. This approach has been developed into a game, and this game which can be freely played online. 

However, more recent research has failed to support its effectiveness for normal individuals, although I have read anecdotal evidence for effectiveness in increasing mental ability in older adults or individuals with ADHD. 

Overall, it appears that the literature suggests that brain training does not work, that "the scientific literature does not support claims that the use of software-based “brain games” alters neural functioning in ways that improve general cognitive performance in everyday life, or prevent cognitive slowing and brain disease."

http://www.scientificamerican.com/article/brain-training-doesn-t-make-you-smarter/

However, working your brain hard through education has been linked to increases in IQ so maybe that is the best approach.

Winship, Christopher, and Sanders Korenman. "Does staying in school make you smarter? The effect of education on IQ in The Bell Curve." Intelligence, Genes, and Success. Springer New York, 1997. 215-234.