On the principle of Lagrange in optimization theory and its application in transportation and location problems

Official URL: http://dx.doi.org/10.1007/978-3-030-91851-4_2

In mathematical optimzation, the Lagrangian approach is a general method to find an optimal solution of a finite( infinite) dimensional constrained continuous optimization problem. This method has beeen introduced by the Italian mathematician Joseph-Louıs Lagrange in 1775 in a series of letters to Euler.This approach became known under the name the principle of Lagrange and was also applied much later to integer programming problems The basic idea behind this method is to replace a constraianed optimization problem by a sequence of easier solvable optimzation probelems having fewer constraints and penalizing the deletıon of the original constraints by replacing the original objective function. To select the best penalization,the so-called Lagrangian dual function needs to be optimized and a possible algorithm to do so is called the subgradient algorithm. This method is discussed in detail at the end of this chapter.The Lagrangian approach led to the introduction of dual optimization problems in nonlinear programming and recently to the development of interior point methods and the identification of polynomially solvable casses of continuous optimiAlso it had its impact on how to construct algorithms to generate approximate solutions of integer programming problems.In this chapter, we discuss in the first part the main ideas behind this approach for any type of finite dimensional optimization problem. In the remaining parts of this chapter we focus in more detail how this approach is used in continuous optimization problems and show its full impact on the so-called K-convex continuous optimzation problems. Also we consider its application within linear integer programming problems and show how it is used to solve these type of problems. To illustrate its application to the well-known integer programming problems we consider in the final section its application to some vehicle routing and location models. As such this chapter shouldf be regarded as an introduction to duality theory for less mathematically oriented readers proving at the same time most of the results using the simplest possible proofs.