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

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 { 0 }

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 }

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