2.7. СРАВНЕНИЕ ДОСТАТОЧНЫХ УСЛОВИЙ

Очень интересно сравнить два типа условий, гарантирующих достаточность условий Куна — Таккера. Первое, выведенное в § 2.5, требует, чтобы функция была псевдовогнутой и допустимое множество было выпуклым.

В § 2—6 приведено второе условие: из следует, что

Эти два условия различны. В качестве упражнения (2.25) предлагается показать, что задача для найти при удовлетворяет бторому условию, но не удовлетворяет первому.

С другой стороны, задача: найти при удовлетворяет первому условию, хотя не удовлетворяет второму (см. упр. 2.26).

Выводы. Эта глава была посвящена выводу условий для проверки данной точки на оптимальность. По существу условия Куна — Таккера были необходимыми и в комбинации либо с предположениями о характере функций, либо с определенными условиями на функцию Лагранжа превращались в достаточные. К сожалению, имеются оптимальные точки, которые удовлетворяют условиям Куна — Таккера, но все же не удовлетворяют этим дополнительным условиям.

Упражнения

(см. скан)

(кликните для просмотра скана)

(кликните для просмотра скана)

(кликните для просмотра скана)

(см. скан)

Примечания и ссылки

§ 2.1 и 2.2. Дальнейшее обсуждение вопросов, связанных с градиентом, разложением в ряд Тейлора и другими понятиями этого раздела, могут быть найдены в работах по математическому анализу, например: Апостол, Флеминг. Краткий обзор этих вопросов содержится также в приложении к этой книге.

§ 2.3. Для детального изучения вогнутости и выпуклости см. работы Эгльстона; Фенчела. Квазивогнутые функции были предложены Никаидо, хотя в НЛП они были введены Эрроу и Энтховеном. Значение псевдовогнутых функций в НЛП было подчеркнуто Мангасаряном (1965). Новые обобщения вогнутости,

такие, как дугообразные вогнутые функции, можно найти у Зангвилла (1967в).

§ 2.4. Материал этого раздела в основном изложен так, как у Эрроу и Удзава, за исключением того, что мы пользуемся более простым, хотя и менее общим условием регулярности.

Первоначальный подход Куна и Таккера представлен в упр. 15. Рассмотрение условия регулярности, приведенное в упр. 12, может быть найдено у Эрроу и Энтховена. Некоторый анализ условия регулярности мы приводим в упр. 13 и 14. Эти упражнения очень важны, так как они содержат простые условия, гарантирующие наличие условия регулярности. Дальнейшее обсуждение упр. 13 может быть найдено ,у Эрроу, Гурвиц и Удеава (1961); (у Эрроу и Удзава, а упр. 14 основано на работе Слейтера, хотя намеченное доказательство является новым.

Лемма Фаркаша обсуждена в приложении (см. также Фаркаш).

Несколько отличный подход к необходимым условиям, который фактически предшествовал условиям Куна — Таккера, принадлежит Ф. Джону (см. Джон; Коттл (1963а); Мангасарян и Фромовиц; Абади).

Для изучения этих вопросов см. Бургер; Форсайт.

§ 2.5. Теорему 2.15 можно найти у Мангасаряна (1956). Однако упр. 2.18 представляет собой новое обобщение. Это обобщение является улучшением доказательств достаточности, имеющихся у Зангвилла (1967в).

§ 2.6 и 2.7.. Представленное здесь изложение двойственности интересно потому, что в отличие от предыдущих подходов оно не использует выпуклость. В основе своей изложение является упрощением некоторых вводных утверждений Зангвилла (1967в). Эта ссылка содержит также теоремы, основанные на минимаксных условиях существования седловой точки: Подход этого раздела связан с подходом Стоэра, хотя мы упоминали, что он не использует выпуклость, как это делает Стоэр (см. Стоэр; Мангасарян и Понстейн; Карамардян). Ранние статьи, где также требуется выпуклость, принадлежат Дорну (1960а); (1960b), (1960с) и (1961); Хансону; Хьюарду; Мангасаряну; Вольфу. Для рассмотрения, использующего выпуклость, представляет интерес понятие сопряженных функций (см. Карлин; Рокафелар). Другой подход, использующий выпуклость, представлен у Чарнса, Купера и Кортанека. Симметричная выпуклая двойственность была предложена Данцигом, Эйзенбергом и Коттлом; Коттлом (19бЗв).

Интересный подход, не использующий выпуклость, был предложен Риссаненом, но, кажется, в теоремах и доказательствах этой работы имеется несколько математических изъянов.

Дополнительные замечания. Важным вопросом, рассмотрение которого выходит за рамки настоящей книги, является минимизация вогнутой функции на множестве. Эта задача принципиально отлична от максимизации этих функций и весьма трудна. Имеется большое количество ее применений к задачам производства и управления запасами. См. напр. Хедли (1964); Зангвилл (1966b, с, d, е, f). Более общий подход см. в работе Зангвилла (1967с).