Archive | ece 490 sp19

ECE 490, final

Problems and solutions.…

ECE 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:

1. 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.$$
2. 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

$$\def\Real{\mathbb{R}}$$

Newton method, Conjugate gradients Guler, chapter 13.

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

ECE 490, Week of Apr. 8

$$\def\Real{\mathbb{R}}$$

Gradient descent; Newton method: Guler, chapter 13.

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

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.

1. Warehouses numbered $$0,1,\ldots,N$$ are located along the road. Initially, the warehouse $$k$$ holds $$N-k$$ units of goods. Management wants to redistribute the goods so that warehouse $$k$$ holds $$k$$ units. Moving one unit from $$k$$ to $$l$$ costs $$|k-l|$$. 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(1-x,2,1+x)$$;
• $$f(x)=\min((x-1)^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}}$$

1. 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 non-degenerate 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).

1. 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\}$$.
2. 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}.