Как найти максимум функции в матлабе

Вычмат лекции 2013 / Лекции Матлаб, программы и задачи к ним / 9 лекция Матлаб (Оптимизация, линейное программирование) / 9 лекция Матлаб (Оптимизация, линейное программирование)

Поиск экстремума функции одной переменной. Поиск локального (в пределах определенного интервала) минимума осуществляет функция [x,y]=fminbnd(имяФункции,границыИнтервала). Если же надо найти локальный минимум, то исследуемую функцию берут с другим знаком и ищут ее минимум, который фактически является ее максимумом. При этом значение функции в максимуме это найденное значение с другим знаком.

Поиск экстремума функции нескольких переменных. Если функция вычисляется от нескольких переменных, то для поиска ее минимума используется (после приблизительной оценки начальных приближений переменных в предполагаемом минимуме) команда [x,y]=fminsearch(имяФункции, векторНачальныхПриближенийПеременных).

Решение задач линейного программирования. В задачах линейного программирования требуется найти максимум или минимум линейной функции многих переменных при линейных ограничениях в виде равенств или неравенств. Рассмотрим для примера такую задачу.

Пусть функция L(x₁,x₂,x₃,x₄)=x₁+x₂+x₃+x₄ и надо найти ее максимум и соответствующие ее максимуму значения переменных.

Пусть даны ограничения в виде неравенств. x₁≥0, x₂≥0, x₃≥0, x₄≥0.

Пусть также даны еще ограничения в виде неравенств.

Для решения задачи линейного программирования (нахождения минимума) используется функция [x, L, f]=linprog(c, A, b, A1, b1,Lx, Rx) где

x вектор значений переменных, полученный в качестве ответа; L значение функции в минимуме;

f параметр, характеризующий вычислительный процесс (если он ноль то решение приостановлено после достижения максимального числа итераций, если положителен то все нормально решено, если отрицателен то решения не найдено);

c функция цели представленная в виде вектора коэффициентов (в нашем случае [1 1 1 -1] но так как нам нужен максимум, а функция [x, L, f]=linprog(c, A, b, A1, b1, Lx, Rx) ищет минимум, то в выражении для функции поменяем знак, поэтому вектор коэффициентов будет [-1 -1 -1 1]);

A, b система ограничений, заданная в матричном виде Ax≤b (это в нашей задаче ограничения 3x₁-x₂≤7, x₂-2x₃≤-1, 4x₃-x₄≤3, 5x₁+2x₄≥14, но так как 5x₁+2x₄≥14 не подходит, то надо поменять знак в этом неравенстве и тогда оно будет -5x₁-2x₄≤-14, в таком случае матрица А состоит из коэффициентов (при переменных) в этих неравенствах, а столбец b состоит из правых (не содержащих переменных) частей неравенств;

A1, b1 система равенств вида A1x=b (в нашей задаче такой системы ограничений нету, но могла бы быть);

Lx, Rx относятся к ограничениям в виде Lx≤x≤Rx, Lx≤x, x≤Rx (в нашей задаче есть ограничения вида Lx≤x, поэтому вектор Lx будет 0 0 0 0).

При использовании функции linprog в списке аргументов вместо тех, которые не указаны, ставятся пустые квадратные скобки.

Рассмотрим еще пример для тренировки. Пусть дана функция W=x₁+x₂+3x₃-x₄ и надо найти ее максимум. Пусть даны ограничения в виде неравенств.

Решим задачу с помощью функции [x, L, f]=linprog(c, A, b, A1, b1, Lx, Rx). Для ее применения нам надо подготовить аргументы функции. Вектор с коэффициентов функции равен (1 1 3 -1), но так как функция linprog ищет минимум, а нам нужен максимум, то поменяем знак у коэффициентов функции и тогда вектор с будет (-1 -1 -3 1). Матрица А состоит из коэффициентов при переменных в системе неравенств x₁-5x₂+4x₃≤5, x₁-2x₂-3x₃≤4, x₁+6x₂+5x₃≤4, x₂+x₃≤1. Так как все они со знаком ≤ то ничего менять не требуется. Вектор b состоит из правых частей этих же неравенств. Матрица A1 из системы A1х=b1 для нас не актуальна (нет таких условий). Lx, Rx относятся к ограничениям в виде Lx≤x≤Rx, Lx≤x, x≤Rx. У нас есть ограничения в виде неравенств. x₁≥0, x₂≥0, x₃≥0, x₄≥0. Тогда вектор Lx=[0; 0; 0; 0]. Что касается остальных типов ограничений, то так как у нас нет таких ограничений, то для нас они не важны.

Задачи нелинейного программирования. Нелинейная задача отличается от линейной. В ней есть система линейных неравенств Ax≤b, система линейных равенств A1x=b1, система ограничений вида lx≤x≤rx, lx≤x, x≤rx. Однако помимо этих уже знакомых (из линейного программирования) условий, есть еще система нелинейных ограничений вида g1(x)≤0, и система нелинейных равенств g2(x)=0. Для решения задачи нелинейного программирования (после выбора вектора начальных приближений х0) используется функция [x, y, f]=fmincon(F, x0, A, b, A1, b1, Lx, Rx, G), где G это М-функция, вычисляющая левые части нелинейных ограничений g1(x)≤0, g2(x)=0. Если какие-то аргументы не определены, то вместо них в вызове функции ставятся квадратные скобки.

Рассмотрим для примера следующую задачу. пусть дана функция x₁ 2 +x₂ 2 =1 при условии, что x₁x₂=4, x₁≥0, x₂≥0. Вектор начальных приближений примем равным х0=(0.1, 0.1).

Вычисление максимума функции с некоторыми критериями

Поиск значений интерполяционного многочлена в точках x1 и x2. Поиск максимума функции F(x) на отрезке [a;b]. Построение интерполяционного многочлена, нахождение максимума функции методом дихотомии. Создание и запуск программы в Matlab и Mathcab.

Рубрика	Программирование, компьютеры и кибернетика
Вид	курсовая работа
Язык	русский
Дата добавления	31.12.2012
Размер файла	598,3 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Курсовая работа по теме:

«Вычисление максимума функции с некоторыми критериями»

1. Постановка задачи

1.1 Поиск значений интерполяционного многочлена в точках x1 и x2

1.2 Поиск максимума функции F(x) на отрезке [a;b]

2. Детализированная схема алгоритма

2.1 Основная программа

2.2 Построение интерполяционного многочлена

2.3 Нахождение максимума функции методом дихотомии

2.4 Вычисление значения заданной функции

3. Создание и запуск программы

3.1 Создание и запуск программы в Matlab

3.2 Создание и запуск программы в Mathcab

4. Полученные результаты

Если функция, определенная и непрерывная в заданном промежутке, не является в нем монотонной, то найдутся такие части этого промежутка, в которых наибольшее и наименьшее значение достигается функцией во внутренней точке, т.е. между границами данного промежутка.

Говорят, что функция имеет в точке максимум, если эту точку можно окружить такой окрестностью (x0- ,x0+), содержащейся в промежутке, где задана функция, что для всех её точек выполняется неравенство:

Иными словами, точка x0 доставляет функции f(x) максимум, если значение f(x0) оказывается наибольшим из значений, принимаемых функцией в некоторой (хотя бы малой) окрестности этой точки.

Пусть величина y является функцией аргумента x. Это означает, что любому значению x из области определения поставлено в соответствии значение y. Вместе с тем на практике часто неизвестна явная связь между y и x, т.е. невозможно записать эту связь в виде y=f(x). В некоторых случаях даже при известной зависимости y=f(x) она настолько громоздка (например, содержит трудно вычисляемые выражения, сложные интегралы и т.п.), что ее использование в практических расчетах затруднительно.

Наиболее распространенным и практически важным случаем, когда вид связи между параметрами x и y неизвестен, является задание этой связи в виде некоторой таблицы . Это означает, что дискретному множеству значений аргумента поставлено в соответствие множество значений функции (i=0,1…n). Эти значения — либо результаты расчетов, либо экспериментальные данные. На практике нам могут понадобиться значение величины y и в других точках, отличных от узлов xi. Однако получить эти значения можно лишь путем очень сложных расчетов или проведением дорогостоящих экспериментов.

Таким образом, с точки зрения экономии времени и средств мы приходим к необходимости использования имеющихся табличных данных для приближенного вычисления искомого параметра y при любом значении (из некоторой области) определяющего параметра x, поскольку точная связь y=f(x) неизвестна.

Этой цели и служит задача о приближение (аппроксимации) функций: данную функцию f(x) требуется приближенно заменить (аппроксимировать) некоторой функцией g(x) так, чтобы отклонение (в некотором смысле) g(x) от f(x) в заданной области было минимальным. Функция g(x) при этом называется аппроксимирующей.

Для практики весьма важен случай аппроксимации функции многочленом:

При этом коэффициенты aj будут подбираться так, чтобы достичь наименьшего отклонения многочлена от данной функции.

Если приближение строится на заданном множестве точек , то аппроксимация называется точечной. К ней относятся интерполирование, среднеквадратичное приближение и др. При построении приближения на непрерывном множестве точек (например, на отрезке [a,b]) аппроксимация называется непрерывной или интегральной.

1. Постановка задачи.

Вычислить максимум функции F(x)=-L(x1)x2+3.1L(x2)x+5 на отрезке [a;b] с точностью е.

L(x1), L(x2) — значения интерполяционного многочлена, построенного для таблично заданной функции f(x) в точках x1, x2.

Name already in use

matlab-exam / 7 / optimization.md

• Go to file T
• Go to line L
• Copy path
• Copy permalink

• Open with Desktop
• View raw
• Copy raw contents Copy raw contents

Copy raw contents

Copy raw contents

Оптимизация — в математике, информатике и исследовании операций задача нахождения экстремума (минимума или максимума) целевой функции в некоторой области конечномерного векторного пространства, ограниченной набором линейных и/или нелинейных равенств и/или неравенств.

Теорию и методы решения задачи оптимизации изучает математическое программирование.

Одномерная оптимизация — целевая функция — это функция одной переменной. Многомерная оптимизация — целевая функция — функция нескольких переменных.

Безусловная оптимизация — область, в которой происходит поиск решения задачи оптимизации, ничем не ограничена. Условная оптимизация — область, в которой происходит поиск решения задачи оптимизации, ограничен набором линейных и/или нелинейных равенств и/или неравенств.

Безусловная оптимизация в MATLAB

Для решения задачи безусловной оптимизации в MATLAB встроены функции fminsearch и fminunc .

Функция fminsearch реализует симплексный алгоритм Нелдара-Мида. Его идея заключается в следующем: на предварительном шаге выбирается n + 1 точек, не расположенных в одной гиперплоскости. Эти точки являются вершинами симплекса, откуда название алгоритма. Точка, в которой значение функции максимально, удаляется и вместо неё по определённым правилам выбирается другая. Итерации продолжаются до тех пор, пока симплекс не станет достаточно малым. Алгоритм Нелдера-Мида можно использовать для оптимизации негладких и даже разрывных функций.

Функция fminunc реализует несколько методов гладкой безусловной оптимизации:

• метод наискорейшего спуска (Steepest Descent method)
• квази-Ньютоновский BFGS-метод (Broyden–Fletcher–Goldfarb–Shanno)
• квази-Ньютоновский DFP-метод (Davidon–Fletcher–Powell)
• методы, основанные на построении доверительных двумерных областей (trust region)

Первые три из них отнесены к «medium-scale»-методам и предназначены для решения задач оптимизации средней размерности (например, не больше 100 переменных), последний — к «large-scale»-методам. По умолчанию, если пользователь задает аналитическое выражение для градиента, запускается метод доверительного интервала. В противном случае используется BFGS-метод, но есть возможность переключиться и на другие. Метод наискорейшего спуска, как правило, очень медлителен и его не рекомен-дуется использовать для решения практических задач. В Matlab-е он присутствует только для иллюстративных целей.

Как найти максимум функции в матлабе

In the activities Contour Maps in Matlab and The Gradient in Matlab, we developed visualizations of level curves and the gradient field. In this activity, we will apply those visualizations to help determine extrema of multivariable functions of the form `f:R^2\to R`.

• local minima,
• local maxima, and
• saddles.

A local minimum is a point on a surface that is the lowest point in its immediate neighborhood. A local maximum is a point on the surface that is the highet point in its immediate neighborhood.

In Figure 1, we’ve marked a local minimum and a local maximum on the surface. In the case of the local minimum, note that it is not the absolute lowest point on the surface, because there are other points on the surface that are lower still. However, in its immediate locale or neighborhood, it is a lowest point. That is why this point is a local minimum, and not an absolute minimum. Similar comments are in order for the local maximum that is marked in Figure 1.

Defining local minima and maxima.

A third type of extrema that we will investigate in this activity is the saddle point. The surface has a saddle point when it is concave up in one direction but concave down in another direction.

In Figure 2, we’ve indicated a saddle point (at approximately `(0,0,0)`). Note that in one direction, the surface slopes upward on each side, but in a second direction, the surface slopes away and downward.

Defining a saddle point.

Time for an example.

The Problem

The goal of this activity is to find and classify all extrema of the function `f:R^2\to R` defined by:

We will investigate solutions in two styles:

1. visually, and
2. analytically.

We begin with visualiztion.

A Visual Approach

We will begin by drawing the surface represented by the equation `f(x,y)=x^3+y^3+3x^2-3y^2-8`. After some experimentation, we opted to draw the surface on the domain `<(x,y): -3 le x,y le 3>`.

After some further exploration, we settle on the following view.

Of course, we add appropriate annotation.

The resulting image is shown in Figure 3.

The surface `f(x,y)=x^3+y^3+3x^2-3y^2-8`.

Note that because of the relatively flat appearance of the surface, the extrema are not relatively apparent. There is some ready evidence of a saddle (note how near the the center of the figure, the surface slope both upward and away and downward and away), but the existence and location of local maxima and minima is almost impossible to determine. We need a better visualization.

Maybe a contour map will help.

The resulting contour map is shown in Figure 4.

The contour map for the function `f(x,y)=x^3+y^3+3x^2-3y^2-8`.

There is some evidence of a hill or depression near the point `(0,2)` in Figure 4, but there seems to be little evidence of other extrema. Perhaps forcing more contours will help.

The resulting contour map is shown in Figure 5.

Forcing more contours for the function `f(x,y)=x^3+y^3+3x^2-3y^2-8`.

Aha! Another depression or hilltop has become visible near the point `(-2,0)`.

There doesn’t seem to be much action in the lower right corner of the grid in Figure 5. Perhaps we should shift the domain to `<(x,y):-4 le x le 2, -2 le y le 4>`.

The resulting contour map is shown in Figure 6.

Shifting the domain for the contours for the function `f(x,y)=x^3+y^3+3x^2-3y^2-8`.

That’s much better! However, there are great many wasted contours on the boundary of our image in Figure 6. What is needed are more contours in the neighborhood of suspected extrema.

Let’s use manual labeling of the contours to get some sense of the `z`-values of the contours in Figure 6.

We use the mouse to click a few contours. When satisfied, with the cursor over the figure window, hit the return or enter button to terminate labeling. Our esulting contour map is shown in Figure 7.

The difficulty is seen when we examine the entries in the matrix z. Let’s get the maximum and minimum entries in the matrix z.

The first use of the max command finds the maximum entry in each column. A second application finds the maximum entry of the result, which is the maximum entry in the matrix z. Similar comments apply to the min command.

So, we see the difficulty. The command contour(x,y,z,20) examines the range of `z`-values, which fall between `-44` and 28, and provides 20 contours at linearly spaced increments. This gives us a lot of contours where they are not needed.

If we examine Figure 7, one of the minimal contours marked has a `z`-value of about `-14`. Let’s try producing contours at specific `z`-values, say at integer values between `-14` and 4.

We’ve decided to label the contours automatically (see the result in Figure 8), but it is a very good exercise to use clabel(c,h,’manual’) instead. It gives you a strong kinesthetic feel for the action near the extrema.

Forcing specific contours provides the best visualization.

We now have evidence of saddles at the points `(0,0)` and `(-2,2)`. Note how the numbers on the contours increase in one direction near these points and decrease in another direction.

We also have strong evidence of either local minima or maxima at the points `(0,2)` and `(-2,0)`, where the contours provide evidence of either «hilltops» or depressions. We could examine the number of the contours near the suspected maxima and minima, but superimposing a gradient field provides even better evidence.

First, calculate the gradient vector for the function `f(x,y)=x^3+y^3+3x^2-3y^2-8`.

$\begin \nabla f(x,y) &=&\langle \partial f/\partial x, \partial f/\partial y \rangle\\ &=&\langle 3x^2+6x,3y^2-6y \rangle \end$

Next, «hold» the last plot.

Create a grid where you want the tails of the gradient vectors to be positoned. We want enough vectors but not so many as our image becomes crowded.

Now, calculate the gradient vector at each point of the grid.

Use the quiver command to plot the gradient vectors.

The result is shown in Figure 9.

Superimposing the gradient field.

Wonderful! Here are some important observations regarding Figure 9.

1. Recall that the gradient vectors point in the direction of greatest increase of the function; i.e., they point «uphill.»
2. Note the action of the gradient field near the suspected saddle points at `(0,0)` and `(-2,2)`. The gradient vectors «flow» toward the saddle point in one direction, only to «flow» away in another direction. That’s because your are going uphill as you approach the saddle point, but fall away downhill in another direction.
3. Note that the gradient vectors all point inward near the point `(-2,0)`, regardless of approach. This means that we are constantly walking uphill as we approach the point `(-2,0)`, making `(-2,0)` a local maximum point.
4. Note that the gradient vectors all point outward near the point `(0,2)`, regardless of approach. This means that we are constantly walking downhill as we approach the point `(0,2)`, making `(0,2)` a local minimum point.

Analytical Approach

The first step of the anayltical approach is to find the critical values of the function `f(x,y)=x^3+y^3+3x^2-3y^2-8`. This requires that we find the partial derivative, a simple task using Matlab’s Symbolic Toolbox. First, declare symbolic variables `x` and `y`, then compute `f`.

Matlab will now access its Symbolic Toolbox using these symbolic variables. Compute the partial derivatives.

You should check these by hand. In mathematical notation, these derivatives are:

`frac(partial f)(partial x)=3x^2+6x\qquad\text\qquad frac(partial f)(partial y)=3y^2-6y.`

We’ll use the Symbolic Toolbox’s solve command to compute where the partial derivatives are simultaneously equal to zero.

A comment on syntax: When Matlab sees the command solve(fx,fy), it assumes you are asking to solve simultaneously the equations `partial f//partial x=0` and `partial f//partial y=0`.

Matlab returns the simultaneous solutions in a structure variable S, which has two fields, x and y. You can access each field with S.x and S.y. If we collect these results in a matrix, we can view the `x`- and `y`- coordinates of the simultaneous solutions side-by-side.

Aha! Note that these critical points are precisely the suspected extrema points found in our last visualization in Figure 9.

We’ll also need second partials.

In mathematical notation, these results are:

`frac(partial^2 f)(partial x^2)=6x+6,\qquad frac(partial^2 f)(partial y^2)=6y-6,\qquad\text\qquad frac(partial^2 f)(partial y partial x)=0.`

As instructed in class, use the second derivative test to determine the class of extrema, summarizing your results in a table similar to the following.

`(x,y)`	$f_(x,y)$	$f_(x,y)f_(x,y)-f_^2(x,y)$	Classification
`(0,0)`	`6`	`(6)(-6)-(0)^2=-36`	Saddle
`(-2,0)`	`-6`	`(-6)(-6)-(0)^2=36`	Local Max
`(-2,2)`	`-6`	`(-6)(6)-(0)^2=-36`	Saddle
`(0,2)`	`6`	`(6)(6)-(0)^2=36`	Local min

Note how the graphical visualization and analytical solution complement one another. The results in Table 1 are identical to the results found using Figure 9.

Matlab Files

Although the following file features advanced use of Matlab, we include it here for those interested in discovering how we generated the images for this activity. You can download the Matlab file at the following link. Download the file to a directory or folder on your system.