Archive  ece 490 sp19
RSS feed for this sectionECE 490, week of Apr 22
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 4dimensional space spanned by the polynomials
$$
p(x)=ax^6+bx^4+cx^2+d.
$$Find, using the GramSchmidt 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.
ECE 490, Week of Apr 15
ECE 490, Week of Apr. 8
ECE 490, Week of Apr 1
\(\def\Real{\mathbb{R}}\)
Conic duality: Guler, Chapters 11, 13 and Barvinok’s “A Course in Convexity“, Chapter 4.
Class notes (pretty incomplete, to be used just as a study guide), here.
Homework, due Apr. 16.
 Warehouses numbered \(0,1,\ldots,N\) are located along the road. Initially, the warehouse \(k\) holds \(Nk\) units of goods. Management wants to redistribute the goods so that warehouse \(k\) holds \(k\) units. Moving one unit from \(k\) to \(l\) costs \(kl\). What is the optimal movement plan?
ECE 490, Week of Mar 25
\(\def\Real{\mathbb{R}}\)
Convex programming and duality: Guler, Chapter 11.
Class notes (pretty incomplete, to be used just as a study guide), here and here.
Exercises:
Find Legendre duals for the following functions:
 \(f(x)=\min(1x,2,1+x)\);
 \(f(x)=\min((x1)^2,(x+1)^2)\);
 \(f(x,y)= 0 \mathrm{\ if\ } x^2+y^2\leq 2; +\infty \mathrm{\ otherwise}\).
…
ECE 490, week of Mar 4
\(\def\Real{\mathbb{R}}\)
Finishing Noninear Programming: Guler, Chapter 9.
Class notes (pretty incomplete, to be used just as a study guide), here and here.
Elad’s Jupiter notebook with some computations for computing spectra of quadratic forms restricted to subspaces.…
ECE 490: projects for 4th credit
\(\def\Real{\mathbb{R}}\)
 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 nondegenerate critical points.What happens at the degenerate critical points?
ECE 490, Week of Feb 25
\(\def\Real{\mathbb{R}}\)
Simplex method (see Matousek/Gaertner, Understanding and using linear programming.
Starting Noninear Programming: Guler, Chapter 9.
Class notes (pretty incomplete, to be used just as a study guide), here and here.
Homework (due by midnight of Sunday, Mar. 10).

Sketch the contour plot for the function
\[
f(a,b)=\min_{(x,y)\in P} ax+by.
\]
for \(P\) being convex hull of the points
\[
(0,1),(0,1),(1,0),(2,1);
\]  ellipse \(\{x^2+3y^2\leq1\}\);
 negative \(x\)ray, \(\{(x,0), x\leq 0\}\).
 convex hull of the points

Dualize the following LP:
\[
\begin{array}{rrc}
x_1&2x_2&\to\max\\
\mathrm{subject\ to}&&\\
x_1&x_2&\leq 1\\
x_1&+x_2&\leq 1\\
x_1&+x_2&\geq 1\\
x_1&&\leq 1\\
&x_2&\leq 1\\
\end{array}.