Need to choose 1 from those 4
Optimization Projects At the beginning of the semester, I indicated that I wanted for each of you to do an optimization project. It is now time for us to begin to try to define the individual projects. I know that some of you have projects that you would like to pursue. If you have a project in mind, please write up a one page description of the project. I will then evaluate what you have given me and determine if the project has sufficient depth and complexity without being overly ambitious. We can then talk about the project and come up with a final description of what you are going to do. For those of you who do not have a project in mind, I will now define four potential projects. Two of these projects come from statistical problems that I am interested in or have worked on. But they are self contained as optimization problems and knowledge of statistics or the statistical background of the problems is not required. A third project is a continuous graph theory problem. The final project can be classified as an inverse problem and this type of problem is quite typical of a wide range of interesting examples. Problem I. Local polynomial smoother - Nonlinear Regression Suppose that we would like to estimate a function f(x) given measurements {(xi, yi)}Ni=1. From this data how to we estimate the unknown function y = f(x) given the assumption that our measurements of y contains measurement errors (or noise)? This is commonly called the regression problem. Clearly, simple interpolation of the noisy data will give a poor solution to the problem. There are many partial solutions to the regression problem including fitting a straight line (or plane in higher dimensions) or perhaps fitting a quadratic function. But these solutions do not solve the more general problem where the unknown function f can not be approximated by a plane or a quadratic surface. The solutions that I want you to implement are the local linear and local quadratic regression in dimensions one and two. A brief write up for this set of problems, and their solution from the book on Statistical Learning is attached. Please note that the solution to this portion of the problem is not iterative, but at each point x, the solution is given by solving a linear system. The implementation of an automatic scheme for choosing the scaling parameter (i.e. the width of the kernel function ) should be included as part of the solution package. This portion requires the optimization of the one dimensional function. The user should be given the choice of specifying the scaling parameter or to sue the automatic scheme. Please see me for more details if you are interested in this problem. Problem II. A variation on the Steiner tree problem - Graph theory Let G = (V,E) be a planar graph with vertices V and edges E. Let V = F ∪ M where F is a set of fixed vertices and M is a set of movable vertices with F and M having no common elements. If the edges are E = {e1, e2, . . . , em} and if W = {w1, w2, . . . , wm} are weights, the problem is to choose the location of the movable vertices that minimized m∑ i=1 wil(ei), where l(e) is the length of edge e. Note that in the case that two moveable vertices or a moveable vertex and a fixed vertex coincide, the moveable vertex is redundant and is to be removed. Design a system that, given an initial guess, finds a local minimum for the problem. Use this to build a system that generates multiple guesses for the location of the moveable vertices and then uses this to attempt to find a global solution. The system should generate images of both initial configurations and the final solution. Problem III. Maximum Likelihood Estimate for a Mixture Density. Let p(x, θ) be a probability density function with independent variable x and param- eter theta, which is either a scalar or vector. A good example of such a situation is the normal density which we normally written as p(x, µ, σ) = 1√ 2π 1 σ e −(x−µ)2 2σ2 . So in this example, θ = (µ, σ). In general, given data {x1, x2. . . . , xN}, we define the maximum likelihood estimate of the parameter θ as the choice of θ which maximizes the likelihood function. l(θ) = N∏ k=1 p(xk, θ). Equivalently, one might more easily maximum the log of this function which can be written as L(θ) = N∑ k=1 log p(xk, θ). Project I involves one particular instance of this situation which we refer to as the mixture of normal densities problem. To begin to define this problem, we first define the n dimensional multivariate normal density function as N(x, µ,Σ) == 1√ 2π n |Σ|−n/2e− 1 2 (x−µ)′Σ−1(x−µ) where µ is an arbitrary vector of length n and Σ is an n× n positive definite symmetric matrix. Formula for the maximum likelihood estimate of µ and Σ are well know and are µ̂ = 1 N N∑ k=1 xk and Σ̂ = 1 N N∑ k=1 (xk − µ̂)′(xk − µ̂). However, the problem that we are interested in is not so simple. We wish to maximum the mixture of multivariate normal densities. Letting pi(x, µi,Σi) = N(x, µi,Σi), this mixture density is p(x, θ) = m∑ i=1 αipi(x, µi,Σi), where m∑ i=1 αi = 1 with αi ≥ 0 for i = 1, 2, . . . ,m and where µi is a vector and Σi is a positive definite n× n matrix for i = 1, 2, . . . ,m. So the problem is to maximize L(α1, . . . , αm, µ1, . . . , µm,Σ1, . . . ,Σm) = N∑ k=1 log m∑ i=1 αipi(xk, µi,Σi) subject to m∑ i=1 αi = 1 with αi ≥ 0 for i = 1, 2, . . . ,m and with Σi a positive definite matrix for i = 1, 2, . . . ,m. This will be done in a two step process. The first step is to apply what is know as the EM algorithm to get good initial estimate of all of the parameters. For this problem the EM algorithm becomes α+i = 1 N N∑ k=1 αcipi(xk, µ c i ,Σ c i) p(xk, θc) µ+i = { N∑ k=1 xk αcipi(xk, µ c i ,Σ c i) p(xk, θc) }/{ N∑ k=1 αcipi(xk, µ c i ,Σ c i) p(xk, θc) } Σ+i = { N∑ k=1 (xk − µ+i )(xk − µ+i )′ αcipi(xk, µ c i ,Σ c i) p(xk, θc) }/{ N∑ k=1 αcipi(xk, µ c i ,Σ c i) p(xk, θc) } where θc = (αc1, . . . , α c m, µ c 1, . . . , µ c m,Σ c 1, . . . ,Σ c m). This algorithm has the property that the value of the log likelihood function is increased at every iteration. Once we have a good initial guess, you may use the optimization toolbox to refine the estimate. This is a constrained optimization problem, so you may want to discuss ways of handling these constraints within the unconstrained optimization routines. If you are interested in this problem, please see me and I will provide additional information. Project IV. Solving Boundary Value Problems A classical family of second order ordinary differential equation has the form y′′ + p(x)y′ + q(x)y = g(x), where p, q and g are specified. Of course such a differential equation willl generally have infinitely many solutions. A unique solution can be determined by specifying the initial conditions y(0) = y0 and y ′(0) = y′0 where y0 and y ′ 0 are specified values. Systems of n ordinary differential equations can be expressed as y′′ + P (x)y′ +Q(x)y = g(x), where y is a column vector of n unknown functions, P (x) and Q(x) are n× n matrices of known functions and g is a vector of n known functions. In this project, instead of initial conditions, we will be interested in boundary value problems of the following four types. I. y(0) = y0 and y(1) = y1 II. y′(0) = y0 and y ′(1) = y1 III. y′(0) = y0 and y(1) = y1 IV. y(0) = y0 and y ′(1) = y1 where y0 and y1 are known column vectors of length n Given a boundary value type (I, II, III or IV) and boundary values (y0 and y1) your code should solve for the missing initial condition. For example, if we have a boundary value of type II, then y′(0) is known, but y(0) is unknown and must be determined so that y(1) = y1. The idea is to determine the value of the missing initial condition so that when the ODE is solved, the boundary value at 1 is satisfied. For this project you should ODE45 to solve the forward problem and the Optimiza- tion Toolbox to estimate the missing initial condition. Do may not use the boundary value problem solver in Matlab. As indicated above, given the boundary type, the matrices of functions P (x) and Q(x) and the column vector of functions g(x), you code should solve for the unknown initial conditions. For systems of n second order systems of equations, there will be n unkown values to be determined using the Matlab Optimization Toolbox. You will be expected to make up your own examples to test the systems. I recommend that you first get ODE45 running on a set of examples where y(0) and y′(0) are specified. You can then use the Optimization Tool box to finish the problem. Testing the code in one demension is a good place to start. You might also note that in the special case that P (x) and Q(x) are diagonal, the equations become uncoupled. This can be useful in bulding simple test cases for your project. Ultimately the system should work for non-diagonal matrices P (x) and Q(x).