Максимизация линейной функции на многограннике

[Nimza]

Подскажите, как показать, что если линейная функция $\langle c, x\rangle, c \in \mathbb{R}^n$ на множестве $\operatorname{conv} \left\{ p_{1}, \ldots, p_{m} \right\}$, где никакая из $p_{i}$ не представима как выпуклая комбинация других, достигает максимума в каких-то двух точках, то она достигнет максимум на некотором ребре $[p_{i},p_{j}]$?

[ИСН]

Если линейная функция одинакова в двух точках, то на отрезке между ними она что?
Если две точки принадлежат многограннику, то отрезок между ними что?

[Nimza]

С отрезком-то понятно. Но не факт, что если продолжить этот отрезок, мы наткнёмся на точки $p_{i}$

[ИСН]

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

[Nimza]

Вот я и хочу показать, что найдётся сколько-нибудь мерная грань, на которой достигается максимум. При $n = 3$ я могу ещё это показать, а вот дальше --- беда.

А что понимают под гранью многогранника в $n$-мерном пространстве? Если его представить как пересечение полупространств $\left\{ x:\langle c_{i}, x \rangle \leqslant d_{i} \right\}$, то по интуиции это будут те участки границы многогранника, на которых выполняется равенство в каком-либо из этих ограничений. Есть какое-то определение, может? Да и обоснование возможности такого представления меня собственно тоже интересует. Есть какая-нибудь литература, где обо всём этом можно почитать?

[ИСН]

Под гранью понимают... ну, грань, да. Можно и так. Равенство в каких-то этих.
Что она найдётся, явствует из того, что иначе отрезок между нашими точками проходил бы через нутрь, а там же не может быть максимума.

[Slava M]

Под гранью многогранника $K$, например, можно понимать пересечение $K$ с такой гиперплоскостью $h$, что $K \subset h^{+}$. ($h^{+}$ - одно из полупространств, ограниченных h).

Посмотрите книгу Лорана "Аппроксимация и оптимизация". Глава 1 (конусы допустимых направлений и характеризация точек минимума).

[мат-ламер]

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

-- Чт июн 09, 2011 21:07:15 --

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