We will be covering some lower bounds for first order methods, and matching them algorithms of convex minimization, – based on Nesterov, ch. 2.

Class notes (pretty incomplete, to be used just as a study guide), here and here.

**Homework**, due by Midnight May 1st:

- Consider the 4-dimensional space spanned by the polynomials

$$

p(x)=ax^6+bx^4+cx^2+d.

$$Find, using the Gram-Schmidt orthogonalization procedure,

the orthonormal basis, if the scalar product is given by

$$

(p_1,p_2)_Q=\int_{0}^\infty e^{-x}p_1(x)p_2(x) dx.

$$ - Consider quadratic form in $\Real^{100}$ given by

\[

Q=\left(

\begin{array}{ccccc}

2&1&1&\cdots&1\\

1&2&1&\cdots&1\\

1&1&2&\cdots&1\\

\vdots&\vdots&\vdots&&\vdots\\

1&1&1&\cdots&2\\

\end{array}

\right)

\]

(i.e. \(2\) on the diagonal,\(1\) elsewhere).- Find the spectrum of \(Q\).
- Solve

\[

Qx=b,

\]

where \(b=(1,0,\ldots,0)\). - Run two iterations of the conjugate gradient method for this system.

- Consider \(F(z)=z^3-9z+8\).
- Find roots of \(F\).
- Find (numerically) the for which starting points on the real line, the Newton method will converge to either of the roots.

For question 3 b), what are we finding?

All the starting points (on the real line) from which Newton algorithm converges to each of the roots. It will give you a partition of the line into several intervals; you need to find them.

For the project presentation, how long shall each group present? Approximately how many slides for each group? Thanks.

5 minutes

For Q2 is Q 100×100 or 10×10?

100×100

What does “numerically” mean in Question 3(b)?

I can’t seem to find the submission portal on Gradescope.

You should be able to find it by now.

I don’t understand what a “comprehensive exam” is. Will the final exam contain materials before midterm? Thanks!

Comprehensive means that the exam will contain material from all of the course.

Could you post the solutions to HW 5? And I think the class notes are not the ones for this week. Thanks!

Solutions come soon. Notes uploaded.