ECE 490: projects for 4th credit

\(\def\Real{\mathbb{R}}\)

  1. For a smooth function \(f\) on \(\Real^n\), consider the gradient descent algorithm
    \[
    x_{n+1}=x_n-\eta\nabla f(x_n)
    \]
    (here \(\eta>0\) is a step size.It is known that for almost all starting positions, the iterations of the gradient descent converge to a local minimizer of \(f\). To ensure convergence for all initial data, it was suggested to perturb the trajectory once in a while, to escape potential trap in saddles, and shown that the procedure works, at least for non-degenerate critical points.What happens at the degenerate critical points? This project would investigate dependence on the parameters of the algorithm of the time till escape from a vicinity of the origin for
    \[
    f(x,y)=x^3+y^3.
    \]
  2. Assume that the results of a tournament are given: a table \(T=(t_{kl}), 1\leq k,l\leq N\), where \(t_{kl}=-t_{lk}\) is the result of the game(s) of the team \(k\) against the team \(l\).
    This project will ask, given a predictor function
    \[
    \phi(x,y)\to\Real,
    \]
    interpreted as the predicted outcome of a match between two teams of strength \(x\) and \(y\), respectively, to find the implicit strengths \(x_k, k=1,\ldots,N\) best fitting observed results \(T\). In other words, we are looking at minimizing
    \[
    \sum_{k,l} L(\phi(x_k,x_l)-t_{k,l})\to\min
    \]
    (here \(L\) is some loss function). One easy example would be to take
    \[\phi(x,y)=x-y, L(s)=s^2.\]
    The project is to develop corresponding optimization algorithm and to test it on a real life example (taking as inputs, say, NBA scoreboard).
  3. For a polynomial of degree 3 or 4, to determine, the domains where the Newton method for finding its root converges. Namely, we are looking into finding, experimentally, the points \(z_0\) for which iterations
    \[
    z_{n+1}=z_n-\frac{P(z_n)}{P'(z_n)}
    \]
    converge (to a root of \(P\). Write the code and present results for, say, \(P=z^4-5z+1
    \).
  4. For a closed planar curve \(C\) bounding a domain, we say that a trajectory \(z_0,z_2,\ldots,z_{p-1}\in C\) is a \(p\)-periodic billiard trajectory, if for any impact point \(z_k\), the angle of incidence – the angle of the link \([z_{k-1},z_k]\) with the tangent line to \(C\) at \(z_k\), – equals the angle of reflection, i.e. the angle of the link \([z_{k+1},z_k]\) with the tangent line to \(C\) at \(z_k\).It is known that billiard trajectories are the critical points of the length function:

    \[
    L(z_0,\ldots,z_{p-1})\mapsto \sum_{k=0}^{p-1}|z_k-z_{k+1}|.
    \]
    The project will be to search for local maxima of \(L\) and thus for periodic trajectories for some curves, e.g.
    \[
    C=\{(10\cos(t)-\cos(4t),10\sin(t)+\sin(5t-1)), t\in[0,2\pi]\}, p=2,3,7.
    \]
  5. Given a function \(f:\Real^d\to\Real\) and a couple of local minima, \(x_-,x_+\), how to locate the saddle separating them? One approach is to consider an \(n\)-chain of points, connecting \(x_-\) and \(x_+\)
    \[
    x_-=x_0-x_1-\cdots -x_n=x_+.
    \]
    If one minimizes the functional
    \[
    \sum_{l=0}^{n-1} f(x_l)+|x_l-x_{l+1}|^2,
    \]
    for large \(n\) the point \(x_l\) in the chain with the highest \(f(x_l)\) will be close to the saddle.The project is to develop the code and experiment with it.
  6. Consider some collection of lattice vectors, say
    \[
    e_1=(1,2), e_2=(-2,1), e_3=(3,2), e_4=(0,2).
    \]
    For large \(N\), there are very many closed trajectories of length \(N\) with each step being one of the vectors \(e_j\). These trajectories will contain approximately the same fractions of the vectors of each kind. The project will be to write a code determining these fractions.
4-credit students project signup
No comments yet.

Leave a Reply