Michael H. Veatch - Linear and Convex Optimization

Здесь есть возможность читать онлайн «Michael H. Veatch - Linear and Convex Optimization» — ознакомительный отрывок электронной книги совершенно бесплатно, а после прочтения отрывка купить полную версию. В некоторых случаях можно слушать аудио, скачать через торрент в формате fb2 и присутствует краткое содержание. Жанр: unrecognised, на английском языке. Описание произведения, (предисловие) а так же отзывы посетителей доступны на портале библиотеки ЛибКат.

Linear and Convex Optimization: краткое содержание, описание и аннотация

Предлагаем к чтению аннотацию, описание, краткое содержание или предисловие (зависит от того, что написал сам автор книги «Linear and Convex Optimization»). Если вы не нашли необходимую информацию о книге — напишите в комментариях, мы постараемся отыскать её.

Discover the practical impacts of current methods of optimization with this approachable, one-stop resource Linear and Convex Optimization: A Mathematical Approach Experienced researcher and undergraduate teacher Mike Veatch presents the main algorithms used in linear, integer, and convex optimization in a mathematical style with an emphasis on what makes a class of problems practically solvable and developing insight into algorithms geometrically. Principles of algorithm design and the speed of algorithms are discussed in detail, requiring no background in algorithms.
The book offers a breadth of recent applications to demonstrate the many areas in which optimization is successfully and frequently used, while the process of formulating optimization problems is addressed throughout. 
Linear and Convex Optimization Coverage of current methods in optimization in a style and level that remains appealing and accessible for mathematically trained undergraduates Enhanced insights into a few algorithms, instead of presenting many algorithms in cursory fashion An emphasis on the formulation of large, data-driven optimization problems Inclusion of linear, integer, and convex optimization, covering many practically solvable problems using algorithms that share many of the same concepts Presentation of a broad range of applications to fields like online marketing, disaster response, humanitarian development, public sector planning, health delivery, manufacturing, and supply chain management Ideal for upper level undergraduate mathematics majors with an interest in practical applications of mathematics, this book will also appeal to business, economics, computer science, and operations research majors with at least two years of mathematics training.

Linear and Convex Optimization — читать онлайн ознакомительный отрывок

Ниже представлен текст книги, разбитый по страницам. Система сохранения места последней прочитанной страницы, позволяет с удобством читать онлайн бесплатно книгу «Linear and Convex Optimization», без необходимости каждый раз заново искать на чём Вы остановились. Поставьте закладку, и сможете в любой момент перейти на страницу, на которой закончили чтение.

Тёмная тема
Сбросить

Интервал:

Закладка:

Сделать

Consider again the linear program ( 1.1) with the alternative objective function ( 1.2). The variables represent the number of pallets of tents and food. If we restrict the variables to be integers, i.e. we can only load whole pallets, then the problem becomes an integer program and can be stated

(1.5) Without the integer restriction it is a linear program with optimal solution - фото 126

Without the integer restriction, it is a linear program with optimal solution картинка 127and optimal value картинка 128. However, because this solution is not integer (i.e. not all of its variables have integer values), it is not feasible for the integer program. Only solutions that have integer values and satisfy the constraints are feasible, as shown in Figure 1.4. Once we have determined the feasible points, an optimal solution can be found graphically by sweeping the contour line Linear and Convex Optimization - изображение 129in the improving direction (upward). The last point touched by the line is optimal. In this case the last point is and the optimal value is Figure 14Feasible integer solutions for - фото 130and the optimal value is Figure 14Feasible integer solutions for 15 Although the graphical - фото 131.

Figure 14Feasible integer solutions for 15 Although the graphical method - фото 132

Figure 1.4Feasible integer solutions for ( 1.5).

Although the graphical method was fairly simple for this example, it is quite different than when solving linear programs. Note that:

There is not necessarily an optimal solution at the intersection of two constraints. In our example, lies only on the constraint line . In other examples, the optimal solution may not lie on any constraint.

The optimal solution is not necessarily obtained by rounding the linear program optimal solution. In fact, there is no limit to how far the optimal solution could be from the linear programming solution.

The integer program can be infeasible when the linear program is feasible.

These difficulties suggest that integer programs are harder to solve than linear programs, which we will see is true. Even solving a two‐variable integer program graphically can be tedious. However, we do not necessarily need to generate all integer feasible solutions. For example, if we start by generating the feasible point картинка 133, then we draw the contour line through it and check for integer points in the linear program's feasible region and above the contour. Checking points to the right of картинка 134(because this contour does not touch the feasible region for картинка 135), картинка 136is infeasible but картинка 137qualifies, so it is optimal. The idea of using a feasible integer solution to eliminate other integer points from consideration will be used in Chapter 13.

The general form of an integer program is the same as a linear program with the added constraint that the variables are integers. If only some of the variables are restricted to be integer, it is called a mixed integer program . When variables represent logical choices, they are usually defined so that картинка 138if true (decide to take the action) and картинка 139if false (decide not to take the action). A variable whose possible values are картинка 140is called a binary variable . An integer program with all binary variables is called a binary program .

General Form of an Integer Program

143 Nonlinear Programs An optimization problem where the objective function - фото 141

1.4.3 Nonlinear Programs

An optimization problem where the objective function and constraints may be nonlinear is called a nonlinear program . The variables are assumed to be continuous, as in a linear program. Thus, nonlinear programs are more general than linear programs, but do not include integer programs. While linear programs can be described in matrix notation, nonlinear programs are described in terms of functions.

General Form of a Nonlinear Program

We have not stated the nonnegativity constraints separately However a - фото 142

We have not stated the nonnegativity constraints separately. However, a nonnegativity constraint can be included in the functional constraints if needed.

The ability to solve a nonlinear program depends on the type of objective function картинка 143and constraints картинка 144. A class of more easily solved nonlinear programs called convex programs is discussed in Chapters 14and 15. Also, Chapter 3shows how certain piece‐wise linear convex programs can be converted into linear programs, which is useful because convex programs are somewhat harder to solve than linear programs.

Problems

For Exercises 1–6, solve the linear program graphically.

For Exercises 6–8, solve the integer program graphically.

1

2

3

4 a) Solve as stated. b) Change “min” to “max” and solve.

5

6

7

8

9 For the linear program (1.1)Suppose the objective is to minimize the cost of aid given in 1.2. What is the optimal solution? Explain why minimizing cost is not a reasonable objective for this problem.Find an objective function for which , is optimal. Show graphically that this point is optimal.

Конец ознакомительного фрагмента.

Текст предоставлен ООО «ЛитРес».

Прочитайте эту книгу целиком, купив полную легальную версию на ЛитРес.

Читать дальше
Тёмная тема
Сбросить

Интервал:

Закладка:

Сделать

Похожие книги на «Linear and Convex Optimization»

Представляем Вашему вниманию похожие книги на «Linear and Convex Optimization» списком для выбора. Мы отобрали схожую по названию и смыслу литературу в надежде предоставить читателям больше вариантов отыскать новые, интересные, ещё непрочитанные произведения.


Отзывы о книге «Linear and Convex Optimization»

Обсуждение, отзывы о книге «Linear and Convex Optimization» и просто собственные мнения читателей. Оставьте ваши комментарии, напишите, что Вы думаете о произведении, его смысле или главных героях. Укажите что конкретно понравилось, а что нет, и почему Вы так считаете.

x