## Project Euler 607

If you like solving Project Euler problems you should try Problem number 607. It’s not very hard, as it can be reduced to a small optimization problem. The idea is to find a path which minimizes time, knowing that certain regions correspond to different speeds. A precise statement of the result can be found on the official page. Here’s an image of the path which realizes the shortest time:

## SIAM 100 digit challenge no 4 – Matlab solution

In 2002 the SIAM News magazine published a list of problems in numerical analysis. The answer to each of the problems should be given with an accuracy of at least digits. And so there came the *Hundred-Dollar, Hundred-Digit Challenge*. I present below my attempt to solving the th problem in this series, as it deals to finding the global minimum of a highly oscillating function. I confess that my approach is rather simplistic, but solves the problem. First let’s state the problem below:

**Problem 4.** What is the global minimum of the function

## Optimal triangles with vertices on fixed circles

Let and suppose is a triangle such that there exists a point which satisfies , , . What is the relative position of with respect to the triangle such that

a) The area is maximized;

b) The perimeter is maximized.

This was inspired by this answer on Math Overflow.

## Two more mind games solved using Matlab

After doing this, solving the Sudoku puzzle with Matlab, I wondered what else can we do using integer programming? Many of the mind games you can find on the Internet can be modelled as matrix problems with linear constraints. I will present two of them, as well as their solutions, below. The game ideas are taken from www.brainbashers.com. Note that in order to use the pieces of code I wrote you need to install the YALMIP toolbox.

You have a table and on each row and column you need to have squares coloured with color and squares coloured with color such that no three squares taken vertically or horizontally have the same color. In the begining you are given the colors of some of the square such that it leads to a unique solution satisfying the given properties. The goal is to find the colors corresponding to each small square starting from the ones given such that the end configuration satisfies the given properties.

## Simple optimization problem regarding distances

Given points in the plane we can study the problem

For the solution is known and for a triangle which has an angle less than is the Toricelli (or Fermat) point, which lies at the intersection of the circumcircles of the equilateral triangles built outside the triangle having the sides of the triangle as support.

For , if we have a convex quadrilateral, then a simple triangle inequality argument proves that the optimal position for is the intersection of the diagonals.

In general, we cannot precisely say what is the position of the solution. Providing a numerical algorithm which computes the optimal position of is not a hard task, and I will do that in the end of this post.

## Numerical method – minimizing eigenvalues on polygons

I will present here an algorithm to find numerically the polygon with sides which minimizes the -th eigenvalue of the Dirichlet Laplacian with a volume constraint.

The first question is: how do we calculate the eigenvalues of a polygon? I adapted a variant of the method of fundamental solutions (see the general 2D case here) for the polygonal case. The method of fundamental solutions consists in finding a function which already satisfies the equation on the whole plane, and see that it is zero on the boundary of the desired shape. We choose the fundamental solutions as being the radial functions where are some well chosen source points and . We search our solution as a linear combination of the functions , so we will have to solve a system of the form

in order to find the desired eigenfunction. Since we cannot solve numerically this system for every we choose a discretization on the boundary of and we arrive at a system of equations like:

and this system has a nontrivial solution if and only if the matrix is singular. The values for which is singular are exactly the square roots of the eigenvalues of our domain .

## Distance from a point to an ellipsoid

Here I will discuss the problem of finding the point which realizes the minimal distance from a given to an ellipsoid. First I will look at the theoretical properties which will lead us to and then I will present a numerical algorithm to find the nearest point.

This problem is interesting in itself, but has some other applications. Sometimes in optimization problems we need to impose a quadratic constraint, so after a gradient descent we always project the result on the constraint which is an ellipsoid.

Let’s begin with the problem, which can be formulated in a general way like this: we are given , and a matrix , positive semidefinite, which gives an ellipsoid . Without loss of generality assume that is diagonal (if not, we diagonalize it using an orthogonal matrix and work in a new coordinate system). The problem becomes

(note that the square is not important here, but simplifies the computations later)