2014 dxdy logo

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

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




 
 Вопрос по нелинейному программированию (градиентный метод)
Сообщение20.08.2009, 13:20 
Здравствуйте!
Помогите, пожалуйста, разобраться. Очень нужно!

Имеется массив данных
$$\mathbf{C}=
\left( \begin{array}{cccc} 
c_{11}&c_{21}&\ldots&c_{n1}\\ 
c_{12}&c_{22}&\ldots &c_{n2}\\
\ldots&\ldots&\ldots&\ldots\\
c_{1m}&c_{2m}&\ldots &c_{nm}
\end{array} \right)$$

Имеется вектор $X=(X_1,X_2,...,X_n)$

Формируется вектор P:
$$\mathbf{P}=
\left( \begin{array}{P} 
P_{1}&P_{2}&\ldots&P_{m}\ 
\end{array}\right)$$

$P_1=c_{11}x_1+c_{21}x_2+...+c_{n1}x_n$

Требуется минимизировать целевую функцию и найти оптимальный вектор Х
$F(x) = \frac{P_1+P_2+...+Pl}{Pk+...+P_(m-1)+P_m}+\sqrt m \frac{\sum\limits_{j=1}^{m}(P_j-\overline{P})^3}{[\sum\limits_{j=1}^{m}(P_j-\overline{P})^2]^{(3/2)}}\to min$

где
$j=\overline{1,m}$
l,m - некоторые целые числа такие, что
$l<m $
$k=(m-l)$

при наличии ограничений:

$\sum\limits_{i=1}^{n}x_i=1$
$x_i\ge 0$ $i=\overline{1,n}$

Для оптимизации выбран градиентный метод (метод Франка-Вулфа) (книга И.Л. Акулич)

Алгоритм следующий:
1. задается начальный допустимый вектор $X^{(k)}$, $k=0$
2. рассчитывается градиент функции для текущего допустимого вектора
$gradF=(\frac{\delta&F(X^k)}{\delta&x_1};\frac{\delta&F(X^k)}{\delta&x_2};\ldots;\frac{\delta&F(X^k)}{\delta&x_n})$

3. минимизируется функция линейная функция
$F=\frac{\delta&F(X^k)}{\delta&x_1}x_1+\frac{\delta&F(X^k)}{\delta&x_2}x_2+\ldots+\frac{\delta&F(X^k)}{\delta&x_n}x_n$
при наличии ограничений:
$\sum\limits_{i=1}^{n}x_i=1$
$x_i\ge 0$ $i=\overline{1,n}$

с помощью симплекс-метода
получаем решение $Z=(Z_1,Z_2,...,Z_n)$

4. рассчитывается новое допустимое решение исходной задачи:
$X^{(k+1)}=X^{(k)}+\alpha_k(Z^{(k)}-X^{(k)})$
$0\le\alpha_k\le1 $

5. вычисляем $F^{(k)}(x)$ если $\left|F^{(k+1)}(x)-F^{(k)}(x)\right|<\varepsilon$, то решение найдено, иначе шаг 2 b $k=k+1$.

А теперь вопросы:
1. правильно ли подобран алгоритм для решения задачи (если нет, то почему и какой лучше использовать)
2. как на шаге (4) избежать нарушения исходных ограничений (т.е. в сумме х-ы =1 и все в отдельности больше или равны 0) ведь $X^{(k)}$ уже подходят под ограничения

Заранее спасибо за любую помощь!

 
 
 [ 1 сообщение ] 


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