Important submission instructions:

● All explanations and answers must be clearly and neatly written. Explain each step in your solution. Your solutions should make very clear to the instructor that you understand all of the steps and the logic behind the steps.

● You are allowed to discuss the homework problems with other students (in particular via Canvas discussion board). However, what you hand in should reflect your own understanding of the material. You are NOT allowed to copy solutions from other students or other sources. Also, please list at the end of the problem set the sources you consulted and people you worked with on this assignment.

● The final document should be saved and submitted as a single .pdf file, and please be sure all problem solutions are presented starting from the first to the last (that is, the first solution must correspond to problem 1 and the second to problem 2 and so on).

● Typed submissions  (for example in LaTeX) will be positively considered in the grade.   Overleaf is an easy avenue to start learning LaTeX. See the tutorials at https://www.overleaf.com/learn

● Be neat. There should not be text crossed out. Do not hand in your rough draft or first attempt, copy and re-copy your solution if needed.

● Very important: Honor code applies fully.  You must submit your own work only. In particular, it is prohibited to post the following problems on any website/forum or any other virtual means (for example Chegg).

Problem 1

Consider a discrete random variable X that takes the values z1 , z2 , ..., zn with probabilities p1 , p2 , ..., pn   such that pi   2 0 and     i pi   =  1.   Find the minimizer x*   of the function f (x) = e[(X - x)2].

Problem 2

Consider the problem

minimize  1 |Ax - b|2(2) ,

x×RE              2

where A e Rm_n  and b e Rm  are given in the text files A .txt and b .txt attached with this homework.

1. Write the optimality condition for this problem.  Express and compute the exact solution x* .

2.  Starting from x0  = (0, 0, ...0)* , use the steepest descent method to find an approx- imate solution.  Use the following stepsizes:  a) fixed step α = , b) exact line search, d) Armijo’s rule.

3. Try different stopping conditions: a) |vf (xk )| < f, b) |x*  - xk | < f0 , c) If (x* ) - f (xk )I < f1 . Use f = 10_4 .

4. Plot (use the appropriate log scale whenever suitable)

● the gradient |vf (xk )| vs iteration number k .

● the relative error |x* -xk |/|x* | vs. iteration number k .

● the error If (x* ) - f (xk )I vs iteration number k .

● the stepsize vs iteration number k .

● the error If (x* ) - f (xk )I vs the error If (x* ) - f (xk _1 )I to visualize the rate of convergence.

Problem 3

Consider the problem

minimize  f (x) = f (x1 , x2 ) = (x2 - x1(2))2 + δ(1 - x1 )2 ,

北 ×RE

where 0 < δ 《 1. Set δ = 0.01.

We know that the minimizer of this function is x*  = (1, 1)* .

a)

1.  Starting from different points: x0  = (-0.8, 0.8)* , x0  = (0, 0)* and x0  = (1.5, 1)* use the steepest descent method to find an approximate solution of the minimization problem.  Use the following stepsize methods:  Armijo rule, exact line search and decreasing c/^k, where k is the iteration number, and c is a constant that needs to be tuned. Use tolerance f = 10_5  for the stopping condition vf (xk ) < f.

2. Plot the error If (xk ) - f (x* )I vs. iteration number for each stepsize selection method used. Check the convergence rate is the one you expect for this method.

b)

Now apply Newton’s method.  Use same stepsize selection methods, the same tolerance and same initial points.

1. Plot the error If (xk ) - f (x* )I vs.  iteration number on a semilog scale.  Check the convergence rate is the one you expect for this method.

2.  Compare the convergence rates of this method vs. the steepest method.

Problem 4

Consider the following unconstrained problem with f : X → R, X S Rn  and aj   e Rn constant.

m                                            n                                       n

minimize  f (x) = -      log(1 - aj(*)x) -      log(1 + xi ) -      log(1 - xi ) ,

j=1                                        i=1                                   i=1

where X = {x e Rn  : aj(*)x < 1, j=1, 2, .., m,  Ixi I < 1, i=1, 2, .., n}.  Generate a random matrix A e Rm_n  whose rows serve as the vectors aj .  Always generate the same radom matrix by using a seed command. In MATLAB: the command rng(1) before generating the matrix (use a Normal randon variate generator). In this problem, the optimal solution is not known in advance, therefore to plot the error  If (xk ) - f (xx )I you need first to determine with high accuracy xx .

1. Derive expressions for the gradient and Hessian using the chain rule. For this func- tion it is harder to derive those expressions by computing partials directly.

2.  Starting from x0   =  (0, 0, ...0)* , use the steepest descent method to find an ap- proximate solution.  Find the number of iterations required for |vf | < 10_3 .  Use Armijo rule only.  Experiment with different size of the parameters, starting with σ = 1/10 and β = 1/2.  Also try different sizes of m and n starting from 20 and

10 respectively.  Hint: For this problem, the conditions aj(*)x < 1 and Ixi I < 1 must be satisfied at every step. Observe that, for small enough stepsize α, the conditions can be satisfied as long as the current x satisfies the conditions.

3. Plot the error If (xk ) - f (xx )I and the stepsize vs iteration number. Check conver- gence rate.

4. Repeat steps 2 and 3 using Newton’s method.  Compare convergence rates of both methods.

Problem 5

This is a continuation of the previous problem.  Evaluating the Hessian and solving the Newton system may be expensive.  For large problems, it is sometimes useful to replace the Hessian by a pd approximation.

1. Use m = 20, 000 and n = 10, 000 and run steepest descent and Newton’s method. It is possible that steepest method takes too many iterations to converge.

2. Apply a diagonal approximation, replacing the Hessian by its diagonal ∂2 f (x)/∂xi(2) . For the sake of ths experiment, you can just compute the Hessian and then take the diagonal since obtaining a formula for the second derivatives may be cumbersome (try it anyways).

3. Plot the error  If (xk ) - f (xx )I and the stepsize vs iteration number for steepest descent, Newton’s and its diagonal approximation. Compare convergence rates.