11 | 12 | 2017

УПРАЖНЕНИЯ И ЗАДАНИЯ Выпуклое программирование

УПРАЖНЕНИЯ И ЗАДАНИЯ Выпуклое программирование

2.1. Рассмотрим задачу: , где — матрица, — вектор.

A). Привести геометрическую интерпретацию задачи.

B). Записать необходимые условия оптимальности. Являются ли они достаточными.

C). Является ли оптимальный план единственным? Почему?

D). Решить задачу при

2.2. Рассмотрим задачу: , . Пусть — локальный оптимальный план и , функция , , функции , , и вогнуты, а функции , . Доказать, что , где , .

2.3. Рассмотрим задачу одномерной минимизации: , — заданные векторы.

A). Записать необходимое условие минимума, если . Является ли оно достаточным?

B). Какие предположения о функции F нужно сделать, чтобы необходимое условие стало и достаточным?


2.4. Рассмотрим задачу: , . Пусть — некоторый план задачи, функция , функции , , и выпуклы, а при непрерывны. Пусть — оптимальный план задачи:

A). Показать, что .

B). Показать, что если , то план удовлетворяет условиям Куна-Таккера.

2.5. Рассмотрим задачу: , , где и выпукла. Показать, что — оптимальный план задачи тогда и только тогда, когда L=0, где

2.6. Рассмотрим задачу: , , , .

Пусть — оптимальный план задачи. Показать, что существует такое число K, что и при .

2.7. Рассмотрим задачу: , где .

A). Показать, что = удовлетворяет условиям Куна-Таккера и — единственный глобальный оптимальный план.

B). Показать (используя а).), что направлением наискорейшего подъема (возрастания) функции F в точке X является вектор .

2.8. Доказать неравенство

При , ,

Используя условие Куна-Таккера.

2.9. Установить связь между условиями Куна-Таккера для следующих задач

и

Где , , A — матрица размера , D — матрица размера , D¢=D, , , .

2.10. Установить связь между оптимальными планами и условиями Куна-Таккера двух следующих задач:

2.11. Рассмотрим задачу

Где , , A — матрица размера , D — матрица размера , D¢=D.

A). Выписать необходимые условия оптимальности второго порядка.

B). Обязательно ли каждый локальный оптимальный план будет глобальным? Доказать или привести контрпример.

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

2.12. Записать задачу двойственную к задаче

Где F, , , , , — выпуклые функции, Q — выпуклое множество.

2.13. Рассмотрим задачу

Записать условия Куна-Таккера и убедиться, что они выполняются в точке . Дать геометрическую интерпретацию, показать, что — глобальный оптимальный план.

2.14. Решить задачу

Геометрически; записать условия Куна-Таккера и найти оптимальный план; из точки построить направление спуска.

2.15. Рассмотрим задачу

Найти вектор , удовлетворяющий условиям Куна-Таккера.

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

а) целевые функции:

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

21.

22.

23.

24.

25.

26.

27.

28.

29.

30.

31.

32.

33.

34.

35.

36.

37.

38.

39.

40.

б) ограничения:

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

21.

22.

23.

24.

25.

26.

27.

28.

29.

30.

31.

32.

33.

34.

35.

36.

37.

38.

39.

40.

41.

42.

43.

44.

45.

46.

47.

48.

49.

50.

51.

52.

53.

54.

55.

56.

57.

58.

59.

60.