2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: Максимизация линейной функции на многограннике
Сообщение09.06.2011, 19:01 
Аватара пользователя
Если линейная функция одинакова в двух точках, то на отрезке между ними она что?
Если две точки принадлежат многограннику, то отрезок между ними что?

 
 
 
 Re: Максимизация линейной функции на многограннике
Сообщение09.06.2011, 19:03 
С отрезком-то понятно. Но не факт, что если продолжить этот отрезок, мы наткнёмся на точки $p_{i}$

 
 
 
 Re: Максимизация линейной функции на многограннике
Сообщение09.06.2011, 19:14 
Аватара пользователя
Не факт, ох, не факт. Но сии точки неизбежно лежат в одной сколько-то-мерной грани (ибо если нет, то...), которая (ну, минимальная из которых) обязана вся находиться в той плоскости, где у целевой функции такое значение (ибо если она её пересекает, то...).
Ну а уж у этой грани есть рёбра, или она сама ребро.

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

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

 
 
 
 Re: Максимизация линейной функции на многограннике
Сообщение09.06.2011, 19:35 
Аватара пользователя
Под гранью понимают... :shock: :roll: ну, грань, да. Можно и так. Равенство в каких-то этих.
Что она найдётся, явствует из того, что иначе отрезок между нашими точками проходил бы через нутрь, а там же не может быть максимума.

 
 
 
 Re: Максимизация линейной функции на многограннике
Сообщение09.06.2011, 19:43 
Аватара пользователя
Под гранью многогранника $K$, например, можно понимать пересечение $K$ с такой гиперплоскостью $h$, что $K \subset h^{+}$. ($h^{+}$ - одно из полупространств, ограниченных h).

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

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

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

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

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group