About yuliy

Author Archive | yuliy

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 }

Fact of the day: Functions with given merge tree

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

Consider a Morse function on \(f:\Real^n\to \Real\) with controlled behavior at infinity, – say, \(f=|x|^2\) near infinity. Assume further that all critical values \(a_1<a_2<\ldots<a_k\) are distinct and that all indices of critical points are \(0\) or \(1\). (Condition obviously holds in one variable.)

Clearly, there are many function that satisfy these conditions. In the (again, most transparent) univariate case, the enumeration of topological types of functions with given critical values is the subject of a nice thread of papers by Arnold on “snakes” (see, e.g., here), relating them to enumeration of ramified coverings of Riemannian spheres, up-down sequences and other cute objects.…

Read full story Comments { 0 }

Mapping department strength

What is your math department strength? One of those rather polarizing questions, or an opportunity to gossip without guilt.

Still, important to understand where your department is on the map, if one wants to steer it in some particular direction, or to keep it where it is.

I wrote a short python script, using BeautifulSoup (thank you!) and campus-wide subscription to MathSciNet (thank you too!) – and downloaded the raw numbers: how many items (whichever MathSciNet is indexing: articles, books, theses,…) are authored by folks from ‘1-IL’ (our code) vs.…

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 }