Linear and Convex Optimization. Michael H. Veatch

Linear and Convex Optimization - Michael H. Veatch


Скачать книгу
integer values. The function being optimized is the objective function. The domain over which the function is optimized is the set of points that satisfy the constraints, which can be equations or inequalities. We distinguish two kinds of constraints. Functional constraints can have any form, while variable bounds restrict the allowable values of one variable. Many problems have nonnegativity constraints as their variable bounds. In (1.1), the food constraint images is listed with the functional constraints, making three functional constraints plus two nonnegativity constraints (variable bounds), but it is also a bound, so the problem can also be said to have two functional constraints and three bounds.

      Let images be the decision variables and images images satisfies the constraintsimages be the solution set of the constraints. Departing somewhat from the usual meaning of a “solution” in mathematics, we make the following definitions

       A solution to a mathematical program is any value of the variables.

       A feasible solution is a solution that satisfies all constraints, i.e. .

       The feasible region is the set of feasible solutions, i.e. .

       The value of a solution is its objective function value.

       An optimal solution is a feasible solution that has a value at least as large (if maximizing) as any other feasible solution.

      To solve a mathematical program images is to find an optimal solution images and the optimal value images, or determine that none exists. We can classify each mathematical program into one of three categories.

      Existence of Optimal Solutions When solving a mathematical program:

       The problem has one or more optimal solutions (we include in this category having solutions whose value is arbitrarily close to optimal, but this distinction is rarely needed), or

       The problem is an unbounded problem, meaning that, for a maximization, there is a feasible solution with value for every , or

       The problem is infeasible: there are no feasible solutions, i.e. .

      An unbounded problem, then, is one whose objective function is unbounded on images (unbounded above for maximization and below for minimization). One can easily specify constraints for a decision problem that contradict each other and have no feasible solution, so infeasible problems are commonplace in applications. Any realistic problem could have bounds placed on the variables, leading to a bounded feasible region and a bounded problem. In practice, these bounds are often omitted, leaving the feasible region unbounded. A problem with an unbounded feasible region will still have an optimal solution for certain objective functions. Unbounded problems, on the other hand, indicate an error in the formulation. It should not be possible to make an infinite profit, for example.

Geometric representation of the problem which has optimal solution for dashed objective but is unbounded for dotted objective.

      Example 1.1 (Unbounded region) Consider the linear program

      (1.3)equation

      

equation

      However, we will always describe the feasible region using constraint equations or inequalities. The notation for the constraints is introduced in the following text.

      1.4.1 Linear Programs

      We have already seen two examples of linear programs.

      General Form of a Linear Program

equation

      There are images decision variables, images and images functional constraints. The constraints can use a mixture of “images”, “images”, and “images”. Each variable may have the bound images, images, or no bound, which we call unrestricted in sign (u.r.s.). The distinguishing characteristics of a linear program are (i) the objective function and all constraints are linear functions and (ii) the variables are continuous, i.e. fractional values are allowed. They are often useful


Скачать книгу