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.

**Homework**:

- 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.