Hi everyone. Ling Chieh Kung again, and welcome back to operations research. Very quickly, this is the end of this course and this is the last week. Lets do some course summary and give you some future directions. First I will talk about a summary of this whole course and then in the next video that's preview for the future. The first topic we mentioned formally is linear programming duality. This is a very interesting thing because well, it's beautiful but it's also hard because it's abstract. It's not very easy to understand but at least we know for any primal linear program, there is a dual program. The dual of a dual goes back to primer, are very interesting. Then we gave you some duality theorems saying that you have weak duality, some upper bound whatever, you have strong duality, your primal and the dual, their optimal solutions gives you the same objective value. We tell you that from your primal optimal solution, how to get your dual optimal solution directly. We tell you about complimentary slackness, primal variable times dual slack must be zero, something like that, and then we stamp, we have shadow prices. We are able to say when a constraint right hand size increased by one or increased somewhat, what's the impact on the whole linear program and what's the impact on the optimal solution. Linear programming duality provides a set of optimality conditions. Many of them have been mentioned in the lecture. But here I just want to give you one example to remind you. For example, a solution is primal feasible if and only if the following thing holds. First, it is primal feasible, of course. Second, you may find a solution that is dual feasible. Finally, between these primal and these dual feasible solutions, you will have complimentary slackness. The way to prove that one solution is optimal to a linear program is to find another solution that is optimal for another linear program, something like that. I feel sorry that in this particular course, this somewhat undergraduate level course, I cannot give you a bunch of advanced theories showing you that this optimality condition is really so important. But still in the lecture you still see in some cases that you may utilize these optimality conditions to help you solve some problems. There are also many algorithms that are designed by utilizing this particular idea. It at least help us to do sensitivity analysis and illustrate how beautiful mathematics maybe. How too beautiful the theory is. We then have sensitivity analysis and dual simplex. You may consider it as an extension from the duality part. We talked about if you have a new variable in your linear program, what should we do? We talked about if you have a new constraint, what do we do? In particular in this thing, we use, we introduced dual simplex algorithm. For this particular one, we want to illustrate a very important idea. Is always the case that when we want to solve a problem, when we want to solve an instance, we should try to utilize whatever we have. For example, the optimal solution for the previous instance. Because the instance we want to solve is very similar to an instance that we already solved. The existing optimal solution should be used. We mentioned in that lecture about how to use this, and in particular how to run several dual simplex iterations to get you an optimal solution. The idea really depends on duality. Duality shows how to do sensitivity analysis and this thing in particular, help us to speed up our branch and bound algorithm. That's somewhat a principle. Somewhat some philosophy. If you want to solve something, try to utilize whatever you have on hand. Do not try to do everything from scratch. We then got into integer programming or the connection between linear programming and integer programming. That's network flow models. We talked about minimum cost, network flow problem, and linear programming formulation. Is interesting that here we mentioned the thing about total unimodularity. If you have an integer program and if it's constraint coefficient is totally unimodular, then what we may say is that it's linear programming relaxation guarantees to give you an integer solution. What does that mean? That means it doesn't really matter whether you formulate it as an integer program or a linear program. This probability is very special because you don't see it everywhere. Network flow models fall into this category and somehow that's why they may be solved easily. This also in particular helps us to show you why that bipartite matching problem may be solved in polynomial time. That's something we mentioned in that lecture. Network flow models are very important because first, they have a lot of applications, logistics, production, and so on and so on and so on. They are just so many problems that may be expressed as graphs, as networks. They have a lot of applications, plus they have good underlying theory. That's why efficient mathematical models exist and the efficient exact algorithms exist. We then jump into nonlinear programming. We first look at unconstrained problems. To really deal with unconstrained problems, we need to know most things about convex sets and convex functions. Once we have those things, we are able to solve nonlinear programs. We first focused on single-dimensional or single variate problems, and then we also talked about gradient, Hessian or even some positive semi-definiteness of Hessian matrix. With all of these, we are able to show whether a set is convex, whether a function is convex, and so on and so on. We mentioned about convexity because the first-order necessary condition would become sufficient if you are trying to minimize a convex function or maximize a concave function. The best thing is that it does not just work for single variate problems. It also works for multivariate problems. After this lecture, now we really know why gradient descent and in the Newton's method sometimes may fail. If your function is not convex, if your program is not convex, your searching algorithms may be drafted into a local minima. Now we have a very concrete idea about all of this. We then move to constrained optimization. Now you have constraints. Once you have constraints, the first thing we want to do is to get rid of those constraints. We mentioned about Lagrangian relaxation to move those constraints into the objective function. With some, you may call it reward terms or penalty terms, we add those lagran, whatever things those lagrangian multiplier to reward feasibility or penalize infeasibility. Lagrangian relaxation help us to do that and eventually gives us the KKT condition, which is the constrained version of the first-order necessary condition. There you may see that a solution is optimal to a nonlinear program if the following things happen. Only if. First, it should be primal feasible. Second, it should be dual feasible, which means you may find a set of Lagrangian multiplier such that the sign makes sense and you have the first-order condition for the Lagrangian. Finally, you need complementary slackness. Hopefully, you may see that the KKT condition really has some connection with linear programming even though the KKT condition is used to solve nonlinear problems but many things, or roughly all the things are connected. In particular, we spend some time to show you LP duality is actually a special case of Lagrangian duality. If I give you a linear program and ask you to use Lagrangian duality to reformulate the problem, it gives you your linear programming dual program. This again shows you how beautiful the theory is. At least, when I first learned this, I feel, oh, it's just amazing. We have some case studies. Probably I shouldn't call them case studies because they are obviously models, theoretical models, maybe I should call them applications. But anyway, we show you that statistics and machine learning, and many other fields, they really rely on optimization. Because those model parameters that you need to estimate really need to be optimized so that they are chosen to minimize the square of the arrows or the gaps, whatever. Whenever you have some parameter estimation problem in statistics or machine learning, in many cases you are solving optimization problems and in many cases they are non-linear problems. We have linear regression, we have support vector machine. Hopefully, you still have some ideas about them and then you'll see the flavor of optimization inside. We really need to solve some optimization problems, some optimization models, so that these statistics or machine learning models can be used. Today, optimization is still very important and because of the rise of data science, I would say it becomes even more important than in the past. That's pretty much what we have done in this particular course.
