Archive | courses

RSS feed for this section

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

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 }

ECE 490, Week of Feb 11.

\(\def\Real{\mathbb{R}}\)

Finishing Guler, Chapter 4 and covering Chapter 6.

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

Exercises:

  • For each facet of the unit cube in \(\Real^3\) (eight vertices, twelve edges, six faces) find the set of \(x\in\Real^3\) such that closes to \(x\) point in the cube belongs to the given facet.
Read full story Comments { 0 }

ECE 490, Week of Feb 4

Finishing Guler, Chapter 3 and starting Chapter 4.

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

Using linear constraints compatibility in packing problems, see e.g. here.

Exercises:

  • Can a triangle on plane be a linear image of a cube (in a high-dimensional space)?
  • Is the set of positive polynomials (i.e. such that \(p(x)>0\) for any \(x\)) convex?
  • Represent \(n\times n\) matrix with all coefficient \(1/n\) as a convex combination of permutation matrices.
Read full story Comments { 17 }

ECE 490, Week of Jan 28

Finishing Chapter 2 of Guler (Sylvester criterion) and covering Chapter 3.

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

 …

Read full story Comments { 0 }

ECE 490, week of Jan 21

Following Chapter 2 of Guler.

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

Exercises:

  • Does there exist a differentiable function on unit interval with infinitely many global maxima and and global minima?
  • Does there exist a function (on real plane) with infinitely many global maxima but no local minima?
  • If a function on real line has a local minimum at \(x\); does it imply that for some \(\epsilon>0\) the function increases on \([x,x+\epsilon)\), decreases on \((x-\epsilon,x]\)?
Read full story Comments { 8 }

ECE 490, week of Jan. 14

\(\def\Real{\mathbb{R}}\)

Course outline is here.

Taylor formula

Spaces of differentiable functions on an interval \(I=[a,b]\subset\Real\):
\[
C(I,\Real), C^1(I,\Real),\ldots, C^n(I,\Real),\ldots
\]

For a function in \(C^1(I,\Real)\),
\[
f(y)=f(x)+\int_x^yf'(s)ds.
\]
Iterating (for functions in \(C^n(I,\Real)\), we obtain
\[
f(y)=f(x)+f'(x)(y-x)+\frac{f”(x)}{2!}(y-x)^2+\ldots+\frac{f^{(n-1)}(x)}{(n-1)!}(y-x)^{n-1}+
\int_{x<s_1<s_2<\ldots<s_n<y}f^{(n)}(s_1)\frac{(y-s_1)^{n-1}}{(n-1)!}ds.
\]

Implications:

  • Mean value theorem
  • If \(f”\geq 0\) on \(I\) and \(f'(x)=0\), then \(x\) is a global minimum of \(f\).

Several variables

Domain: \(U\subset\Real^n\), an open set.

Reminder: open, closed, bounded, compact sets.

Exercise: is the set \(\{|x|\leq 1, |y| \lt 1\}\) open?…

Read full story Comments { 0 }

ECE 515, mock final

Here.…

Read full story Comments { 2 }