Archive | ece 490 sp19

RSS feed for this section

ECE 490, final

Problems and solutions.…

Read full story Comments { 0 }

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.
Read full story Comments { 13 }

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

Read full story Comments { 0 }

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

Read full story Comments { 2 }

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?
Read full story Comments { 12 }

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}\).

 …

Read full story Comments { 0 }

ECE 490, Week of Mar 11

Midterm and solutions and

midterm scores.…

Read full story Comments { 11 }

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

Read full story Comments { 0 }

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?
Read full story Comments { 0 }

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}.
Read full story Comments { 20 }