Optimization

In this block we introduce a course on optimization. The optimization paradigm is a new model to solve many problems of real practice. The main ingredients are that they include constraints that must be imposed to the feasible solutions, so that it is guaranteed that they satisfy a minimum set of conditions, and also that they optimize the solutions using an objective function that permits to compare different solutions and decide which one is the best. We enumerate the topics to be studied in the course: linear programming, mon-linear pprogramming, mixed-integer programming, how to use of GAMS software, duality, sensitivity analysis and examples of applications. The course is practically oriented with many examples and its most original part is the sensitivity analysis, in which closed formulas for evaluating the sensitivity of the objective function and primal and dual variables with respect to the parameters are given.”

In this lesson we introduce the reader with linear programming problems by means of three examples: the transportation problem, the production scheduling problem and the diet problems. Since they involve linear objective functions and linear constraints, they are cases of linear programming problems. The GAMS code for solving these problems are given and discussed, so that the introduction of the Gams language becomes smooth.

In this lesson we present the different types of linear programming problems we can face. We refer to problems with unique solution, with multiple solutions, with unbounded solution and those with no feasible solution. We also introduce the standard form of a linear programming problem, which will reveal its important role when explaining the simplex method in a future lesson. Though it is defined for a particular problem, the definiton is valid for any problem.

In this lesson we describe how to use the GAMS software to solve some mathematical programming problems. One example with some typical errors has been generated to illustrate how the errors are detected by the GAMS software and how GAMS tells us about these eroors. Using the red lines procided by the software, we have immediate access to the lines where the eroors are made. This facilitates the identification of errors and the correction process. Once errors have been corrected, GAMS executes the code and gives the results. We show how the variable values can be accessed by means of the automatically file with the lst extension.

In this lesson we describe the simplex method which is the most common and well known method for solving linear programming problems. The method is described in great detail and several examples of applications are used to illustrate the different steps of the simplex algorithm. A given linear programming problem having a particular structure is presented that allows solving the problem immediately. The idea of the simplex is to obtain this very convenient structure by exchanging sequentially basic and non-basic variables. This means moving from an extreme point of the feasible region to another extreme point in each step until an optimum is obtained.

In this lesson we deal with nonlinear programming problems, denoted NLPP. We start with some illustrative and simple examples to motivate the reader and demonstrate that there are many problems that can be stated as NLPP. Thus, knowledge of the optimization methods is very relevant, because apart from incorporating constraints and obtain solutions that satisfy them, we optimize the solutions, that is, we obtain the best ones of all feasible. At the end of the lesson we review the main concepts of nonlinear programming, such as what a NLPP is, the concepts of local and global solution, differentiability, continuous differentiability, etc.

In this lesson we explain the GAMS commands in some detail. We have assumed that the reader has some practice with GAMS programs, because this lesson has been written under that assumption. In fact, this contains some material that must be consulted after some time has been dedicated to previous lessons, in which the students are assumed to be developed several examples of GAMS programs. All commands are explained in detail and some examples are given. We complete the lesson dealing with the conditional operator and the use of dynamic sets, including its capability to work with unions, intersections, differences and complements.

In this lesson is dedicated to the Karush-Kuhn-Tucker conditions. The reader probably will be familiar with the necessary conditions for unconstraint optimization problems and perhaps with the case of equality constraints. In this lesson we deal with the general case, that includes also inequality constraints. I invite the reader to follow this lesson because the general case is very powerful and arises very frequently in practice, much more than other cases. We use several examples, which are solved graphically and using the KKT conditions, to illustrate the methods.

In this lesson we present several examples of mixed-integer programming problems. The aim is to convince the reader about the power of these methods and invite him/her to think in optimization problem when faced with real life problems. The possibility of using binary variables is very attractive and useful. Here we describe The knapsack, the ship owner, the relevant symptoms, the academy selection, the school timetable and the discrete location problems. They are very simple problems, but will suggest the reader a wide variety of applications.

In this lesson we discuss how the algebraic structure of the set of all solutions of the systems of linear equations and inequalities is. We start by linear systems of equations homogeneous and complete, and continue with the case of inequalities, which is the most interesting. We show that the most general solution of a complete linear system of inequalities is the sum of a linear space plus a cone plus a polytope. To illustrate the different cases we give some examples. Finally, we use the knowledge of this general solution to obtain very easily all the solutions of LPP and use a truncated cube example for illustration purposes.";

In this lesson we introduce the important concept of duality in mathematical programming, which will be the basic material for the sensitivity analysis of a later lesson. First we define dual program and show that any optimization problem has a dual and that the dual of the dual is the primal. Next, we show how to obtain the dual of a given problem and provide rules to do it. This rules are summarized graphically using the graphical scheme shown above this paragraph. We end with some illustrative examples that include the table manufacturing problem and the support vector machines problem.

As a very interesting practical example of dual problems, in this lesson we deal with the case of an electric market. We state the problem as a primal problem first, and later as its dual problem. The primal is a dictatorial procedure, in which the market operator, ask the private information to the producers, and decides the optimal production for the system imposing the producers the quota of production. In the dual problem, the operator just control the prices and the producers decide the amount of production without the need of informing the operator about private information. An iterative process of change of prices leads to satisfaction of the demand. The surprising result is that both results are identical. An iterative method is used to solve the dual problem, which is based on adjusting the prices until convergence.

This lesson is dedicated to sensitivity analysis. After a brief motivation of sensitivity analysis in civil engineering, we introduce local sensitivity analysis, as determining how the objective function and the variables, primal or dual, change when the data change. We provide formulas for determining all these sensitivities. First an important theorem is given that says that the sensitivity of the objective function with respect to any parameter is the partial derivative of the Lagrangian function with respect to the parameter. Next, matrix formulas are given for determining all sensitivities in the regular case. Explicit formulas for the linear programming case are obtained. Finally, some examples of applications in civil engineering are given. The lesson ends with some conclusions and a discussion of some related bibliography.

In this lesson we apply the optimization methods to solve several problems of neural and functional networks. We propose workg with the inverse of the neural function instead of working with the neural function directly. We use five different models, some of which include learning the neural functions and using its inverse instead of the neural function, what has some important advantages. The corresponding GAMS code is given. Finally, the results obtained using the different methods are compared.

This example is dedicated to explain regression models and some duality concepts. First the three most common methods, least squares, minimax and least absolute values are described and the last two stated as linear programming problems. The dual of the minimax problem is obtained and its mathematical interpretation is given. Finally, an example of simulated data with three outliers is given and the three methods used to fit the data. The lesson ends with the interpretation of the results of the example.

In order to facilitate the use of the methods described in this course and students can work not only the exercises and problems raised, but other applications, we give the GAMS code used in the exmples. Finally, a list of bibliographic references is given.

Here are all the slideshow from Optimization