Методы оптимизации (нелинейные) - задачи

[l33roy]

Помогите разобраться в методах оптимизации.

Тест:

1)Какое из направлений является направлением убывания значения функции f(x) в точке x(0,1,2).

$$ f(x) = x_1^2 + 2x_2^2 + 5x_3^2 - 2x_1x_2 - 4x_1x_3 - 2x_3 $$

a)(1,1,1) b)(1,1,-1) c)(-1,1,1) d)(-1,-1,1)

Решаю так:

$$ \nabla f = ( 2x_1 - 2x_2 -4x_3; 4x_1 - 2x_1; 10x_3 - 4x_1 - 2) $$

$$ \nabla = (-6; 4; 18) $$

Что дальше?

2)Какая из точек удовлетворяет необходимым условиям экстремума для задачи:

$$ \sin {x_1} - x_2^2 $$

--> max
a)(0,0) b)(\pi, 0) c)(

$$ \frac {5 \pi} {2} $$

, 0) d)(

$$ \frac {\pi} {3} $$

,1)

Решаю так:
$\frac{\partial f}{\partial x_1} = \cos x_1 = 0 $
$x_k = \frac {\pi} {2} + \pi_k $
$\frac{\partial f}{\partial x_2} = -2x_2 = 0 $
$ x_2 = 0
Правильно?

3) Какая из точек является локальным минимумом функции
$ f(x) = x_1^4 + x_2^2 + 4x_1x_2 $
a)($\sqrt {2}, -2\sqrt {2}$) b)(0,$\sqrt {2}$) c)(0, 0) d)($-2\sqrt {2}, \sqrt {2}$)

Решаю так:
$\frac{\partial f}{\partial x_1} = 4x_1^3 + 4x_2 = 0 $
$\frac{\partial f}{\partial x_2} = 2x_2 + 4x_1 = 0 $
$ x_2 = -2x_1 $
$ x_1^3 - 2x_1 = 0 $
$ x_1(x_1^2 - 2) = 0 $
$ x_1 = 0 $
$ x_2 = 0 $
$ x_1 = \pm \sqrt {2} $
$ x_2 = \pm 2\sqrt {2} $
Как проверить какая именно из точек является решением?

4)Какая из точек является решение задачи:
$ x_1^2 + x_2^2 + x_3^2 $ --> min
$ x_1 + x_2 + x_3 = 3 $
$ 2x_1 - x_2 + x_3 \leqslant 5 $
a)(0,6,-3) b)(1,1,1) c)(3,0,0) d)(0,0,3)

Ясно, что ответ - (1,1,1) , но как это показать?

Все задачи аналитически решаются довольно просто, но нужно решить численно.
Предполагается использование: метод Ньютона(как для одномерных так и многомерных), Фибоначчи , сечение, метод наискорейшего спуска, метод Давидона - Флетчера - Пауэлла,штрафные функции
Конечно здесь все методы не используюся, только некоторые.

Помогите, пожалуйста!!!

[Brukvalub]

l33roy писал(а):

)Какое из направлений является направлением убывания значения функции f(x) в точке x(0,1,2).

Функция возрастает в направлениях, составляющих острый угол с градиентом.

l33roy писал(а):

Правильно?

Да.

l33roy писал(а):

Как проверить какая именно из точек является решением?

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

l33roy писал(а):

Ясно, что ответ - (1,1,1) , но как это показать?

Выразить одно из переменных через другие из 2-го уравнения и свести трехмерную задачу к более простой двумерной.

l33roy писал(а):

Все задачи аналитически решаются довольно просто, но нужно решить численно.
Предполагается использование: метод Ньютона(как для одномерных так и многомерных), Фибоначчи , сечение, метод наискорейшего спуска, метод Давидона - Флетчера - Пауэлла,штрафные функции
Конечно здесь все методы не используюся, только некоторые.

Помогите, пожалуйста!!!

Последнюю просьбу я совсем не понял. Означает ли она предложение составить за Вас алгоритмические схемы для задач, прогнать и отладить соответствующие программы??? Я бы за это не взялся

[M-A-E]

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

[l33roy]

Цитата:

Функция возрастает в направлениях, составляющих острый угол с градиентом.

Т.е. ответ в 1ом b)? Как это показать? Графически?

Цитата:

Во второй задаче выборку из стационарных точек осталось только сделать.

Во 2ой задаче ответ тоже с)? Я это, если честно, проверил графическим методом. Что за выборка?

Цитата:

В третьей задаче, осталось составить определитель из вторых производных и из полученного результата сделать вывод.

$$ \mathbf{X} = \left( \begin{array}{ccc} 12x_1^2 & 4 & \\ 4 & 2 & \\ \end{array} \right) $$

Что из этого следует?

Цитата:

Выразить одно из переменных через другие из 2-го уравнения и свести трехмерную задачу к более простой двумерной.

Поподробней можно?

[Brukvalub]

l33roy писал(а):

Т.е. ответ в 1ом b)? Как это показать? Графически?

Можно вспомнить выражение для производной по направлению в случае дифференцируемой функции.

l33roy писал(а):

Во 2ой задаче ответ тоже с)? Я это, если честно, проверил графическим методом. Что за выборка?

Вы нашли множество всех стационарных точек, осталось выяснить, какие из предложенных вам точек входят в это множество.

l33roy писал(а):

$$ \mathbf{X} = \left( \begin{array}{ccc} 12x_1^2 & 4 & \\ 4 & 2 & \\ \end{array} \right) $$

Что из этого следует?

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

l33roy писал(а):

Цитата:
Выразить одно из переменных через другие из 2-го уравнения и свести трехмерную задачу к более простой двумерной.


Поподробней можно?

Вы делать-то начните, тогда и пишите о своих затруднениях.

[M-A-E]

Цитата:

Во 2ой задаче ответ тоже с)? Я это, если честно, проверил графическим методом. Что за выборка?

Вы нашли решения уравнения cos(x)=0. Теперь из этих решений нужно выбрать, то которое подходит для ответа.

По поводу третьей задачи: то что вы записали выше является матрицей. Здесь определитель равен 24{x_1}^2-16. Нужно подставить вместо x_1, те числа, которые вы уже нашли. Если значение определителя будет меньше нуля, то экстремума нет, если равно 0, то требуется дополнительное исследование (в вашей задаче такого нет), если больше 0, то экстремум есть. Остается выяснить, что это максимум или минимум, для этого нужно найти значение второй частной производной по первой переменной в этой точке, если оно больше нуля, то в этой точке минимум...

[l33roy]

Цитата:

По поводу третьей задачи: то что вы записали выше является матрицей. Здесь определитель равен 24{x_1}^2-16. Нужно подставить вместо x_1, те числа, которые вы уже нашли. Если значение определителя будет меньше нуля, то экстремума нет, если равно 0, то требуется дополнительное исследование (в вашей задаче такого нет), если больше 0, то экстремум есть. Остается выяснить, что это максимум или минимум, для этого нужно найти значение второй частной производной по первой переменной в этой точке, если оно больше нуля, то в этой точке минимум...

т.е. ответ a)?

Цитата:

Вы нашли решения уравнения cos(x)=0. Теперь из этих решений нужно выбрать, то которое подходит для ответа.

Как выбор делать? Переборои или графически? Подругому никак?

Цитата:

Можно вспомнить выражение для производной по направлению в случае дифференцируемой функции.

Извините за тупой вопрос, но как тут будет выглядить производная по направлению и как ее посчитать?

Цитата:

Вы делать-то начните, тогда и пишите о своих затруднениях.

Можно ткнуть пальцем на подобный пример?

[Brukvalub]

l33roy писал(а):

Цитата:
Можно вспомнить выражение для производной по направлению в случае дифференцируемой функции.


Извините за тупой вопрос, но как тут будет выглядить производная по направлению и как ее посчитать?

Почитайте: http://elib.ispu.ru/library/math/sem2/k ... ode69.html
http://www.donnu.edu.ua/ekonom/UA/Kafed ... dBM/09.htm

l33roy писал(а):

Можно ткнуть пальцем на подобный пример?

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

[l33roy]

Производная по направлению получается равна:
$ -6\cos\alpha_1 + 4\cos\alpha_2 + 18\cos\alpha_3$

(1,1,1) : $ \frac {16\sqrt 2} {2}$

а другие чёто не соображу.

Что из этого следует?

Цитата:

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

Извините, у меня времени просто мало . Жду последний Ваш ответ.

[Brukvalub]

l33roy писал(а):

Производная по направлению получается равна:
$ -6\cos\alpha_1 + 4\cos\alpha_2 + 18\cos\alpha_3$

Что из этого следует?

Это скалярное произведение градиента и единичного вектора заданного направления. Скалярное произведение векторов равно произведению их длин, умноженному на косинус угла между ними.Отсюда все и выходит.

l33roy писал(а):

Жду последний Ваш ответ.

Ну почему сразу уж так и последний. Я ,таки, надеюсь еще трохи в Форум пописать

[l33roy]

Уважаемые форумяне.

Вопрос по 4ой задаче:
Если решать с помощью ф-и Лагранжа, то получается:
$ L = x_1^2 + x_2^2 + x_3^2 + u_1( x_1+x_2+x_3-3) + u_2(2x_1-x_2+x_3-5)$
Продолжив решение получаем, что ответ - (0,6,-3)

Но ведь, очевидно, что ответ - (1,1,1)

и, решая такую ф-ю:
$ L = x_1^2 + x_2^2 + x_3^2 + u_1( x_1+x_2+x_3-3) $
приходим к ответу - (1,1,1)

Поясните эту нелепость пожалуйста.

[Brukvalub]

l33roy писал(а):

Поясните эту нелепость пожалуйста.

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

[l33roy]

Цитата:

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

Почему не нужно учитывать ограничения типа неравенств в этом примере?

[Brukvalub]

l33roy писал(а):

Почему не нужно учитывать ограничения типа неравенств в этом примере?

Этого я не писал. Прочтите еще раз внимательно мое предыдущее сообщение.

[l33roy]

Цитата:

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

Почему?