# Archive | ece 490 sp19

RSS feed for this section

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

Homework:

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 11

Midterm and solutions and

## 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}. ## ECE 490, Week of Feb 18 $$\def\Real{\mathbb{R}}$$ Linear Programming: Guler, Chapter 6 and Matousek/Gaertner, Understanding and using linear programming. Class notes (pretty incomplete, to be used just as a study guide), here and here. Exercises • Dualize the linear program: \[ \begin{array}{rl} x_1\to\max& \mathrm{subject\ to}\\ x_1\leq &0\\ x_2\leq &1\\ x_2\geq &0\\ \end{array}$
Solve both primal and dual programs.
• Give an example of LP such that neither primal nor dual problems are feasible.