One more step closer to finish all the courses

I just submit my mid term take home exam for IP class. Now there are 2 final, 2 projects remaining before I finish all my desired courses to take. There are still some courses attracts to me. But I will only audit them and focus on doing research and make some progress.

Lattice Search

Suppose f(x,y) is a convex function. Now we want to find optimal integer x* and y* to minimize f(x,y) over integer set.
In continuou case, if we know x*(y), then we can just minimize f(x*(y),y) by taking derivative.
In discrete case, if we know x*(y), then can we say that -f(x*(y),y) is unimodular?

The problem of unit in the relationship between backorder and waiting time

The formula for the relationship between backorder and waiting time is
V[B]=lambda E[BW] + lambda^2 V[BW]

I think there is exact same formula in queueing theory about the number in the queue and waiting time. But the puzzle to me is the match of unit. Suppose the unit of B, lambda, BW are item, item/day, day. V[B]=item^2, lambda E[BW] = item and lambda^2 V[BW]=item^2.

If it was me to derive this formula, I would throw it into garbage after this check. But sometimes, we cannot trust common sense.

The difference and similarity between Poisson and BM

The more I learn about BM, the more I feel there are strong connection between Poisson and BM. Last week, I ask a question. If we discrete Poisson process to small time interval, it behaves exactly as random walk with probablity lamda*h up by one and 0 otherwise. And counterpart of BM in discrete world is also random work with probability 0.5 up by 1 and probability 0.5 down by 1. Then I ask a question, what if we change the measure just like that we can change the BM with drift to BM without drift. Answer is obvious no, there are several differences.

• discrete BM, up and down probability is fixed. the only scale factor is step size. But the scale factor of poisson process is probability up and step size is fixed
• when we change the measure, we require that two probability measuresare equivalent which means the null space is the same. The null space of discrete one step of randome walke is R/{-1,1}. But poisson is R/{0,1}.

But when I ask Professor what is discrete case of BM with drift. Is it with the symmetric step size but different probability or different step size but the same probability or both or does not matter. I have not get answer yet.

IP homework is way too hard

The second set of homework takes me two days with 16+ hours to finish and without leaving a logic hole.
The last two logic gaps I filled just now are
1. LP relaxation of TSP formulation with subtour elimination constrainted is strictly contained in TSP formulation with subtour elimination constrainted replaced by $u_i-u_j-nx_{ij} \leq n-1$. This invovle how to scale up the problem then scale down.
2. Find as many affine independent points as possible for $P={x \in R^+ | \sum^n_{i=1} x_{ij}=1 for i=1,...n and \sum^n_{j=1} x_{ij}=1 for j=1,...n}$. It would be easy to see the rules by beginning with n=3 and 4.

In homework 1 of IP class, the following question is challenging.
1. show that $max{x_1 − \sqrt(2) x_2 | 1 \leq x1 \leq \sqrt(2) x_2 and x_1, x_2 is integer}$ is feasible and bounded, but has no optimal solution. I use the contradiction to show that there is no optimal solution.

uniqueness of the fixed point

In section 2.4.3 (Univalent mapping arguement) from 'game theory in SC analysis' by Cachon and Netessine, they claim that if best response function is one-to-one, then there is at most one fixed point(uniqueness of equilibrium). But why? It is possible that we can have x and y where x not equal to y such that x=f(x) and y=f(y). For example, f(x_1,x_2)=(x_2,x_1) is univalent mapping. But when x_1 = x_2=a in R, f(a,a)=(a,a). We can construct a trival game, player x and y write down a number, if x=y, then they both get 10, if not then their payoff is 10-(x-y)^2. In this game, the best response is f(x_1,x_2)=(x_2,x_1) .

Pros and cons of staying in a small university

The most advantage is that the relationship between prof. and students are close. But sometimes you will be shocked. There is only one student registering real analysis class, so that the class is cancelled. It is hard to imagine that this could happen to the basic graduate math courses in those bigger universities.

Very limited courses are offered in Lehigh. After my three years in Lehigh, there is no open course about heuristics, the stochastic process class only using introductory level of book 'Introduction to Probability Models' by Ross. It takes me waiting for 2 years to have IP open again. And there are many other regrets about courses in Lehigh.

Crazy Tuesday and Thursday Next Semester

Finally I get my schedule for next semester. All the courses and meeting are concentrated in Tuesday and Thursday.
10:45-12:00 Advanced Stochastic Process II
12:10-1:00 IP Seminar (Th)
1:10:2:25 Real Analysis II
2:35-3:50 Financial Calculus II
4:00-5:00 Weekly Meeting with Larry(T)
7:00-8:15 Integer Programming
After crazy day, I will play tennis on Tuesday and Ping Pong on Thursday.

measurable or nonmeasurable

Now I am doing Real analysis homework, it is hard to imagine those strange sets. The course till now is all about trying to show that close properties about measurable set and functions. It is hard to come up your own counter example and deal with those 'strange' stuffs like Cantor, Borel, nonmeasure sets.

Luckly by keeping doing the homework even though the score is as normal as my other courses, I am still not lost in the class. It should be considered as the hardest course among all ones I take and audit. Maybe it is time to go office hour next time.

The benefit 'Dummy'

Today's nonlinear class, I learned a trick by creating dummy variables and constrains to decompose the problem.
The original problem is

min f_1(x) - f_2(x)
st. x \in X_1 \cap X_2

Then we can transform it to

min f_1(y) - f_2(z)
st. y = z
y \in X_1 and z \in X_2

Then we can write the dual of transformed problem and do the decomposition.

Suppose f_1 and f_2 is convex.
We imagine the geometric meaning, for each Lagrange vector for the constrain y = z. We can find the corresponding tangent lines of the f_1 and -f_2. If their x happens to be the same, then we done. Otherwise we update Lagrange vectors. The way to update Lagrange vector is based on sign of difference of two tangent points.

Global Optimization Quadratic Programming

When we discuss nonlinear optimization, usually we seek a local solution rather than global solution. This week, in the class, I got to know a way to get glocal solution for quadratic programming (any type matrix is ok). The main idea is to use branch and bound ( similar to IP problem ). In the IP, we relax integer variables. In the QP, for each inequality we can use a concave function bounded above and convex function bounded below. By doing that, we can get a convex set. Then we solve relaxed problem, if it happens to be in the boundry. We are done. Otherwise, branch and solve the problem. As IP, which variables you are going to branch is important decision. Here, how you branch the area is also a key question.

Also any IP problem can be reformed as binary problem. And any binary problem can be reformed as quadratic problem, like x(1-x)=0.

It is interesting that you can connect two distinct optimization areas togather.