Archive | courses

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

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.

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.

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.

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.

…

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]$$?

ECE 490, week of Jan. 14

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

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

Here.…