назад Оглавление вперед


[Старт] [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] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [ 248 ] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]


248

(1 I Л 3 3 3

111 2 4 4

111 ч5 5 5)

ЛИТЕРАТУРА

1. Derman С. Finite State Markovian Decision Process, Academic Press, New York, 1970.

2. Howard R. Dynamic Programming and Markov Processes, MIT Press, Cambridge, Mass., 1960. (Русский перевод: Ховард P. Динамическое программирование и марковские процессы. - М.: Сов. радио, 1964.)

Литература, добавленная при переводе

1. Дынкин Е. Б., Юшкевич А. А. Теоремы и задачи о процессах Маркова. - М.: Наука, 1967.

2. Кемени Дж., Снелл Дж. Конечные цепи Маркова. - М.: Наука, 1970.



ГЛАВА 20

КЛАССИЧЕСКАЯ ТЕОРИЯ ОПТИМИЗАЦИИ

В классической теории оптимизации для поиска точек максимума и минимума (экстремальных точек) функций в условиях как отсутствия, так и наличия ограничений на переменные широко используется аппарат дифференциального исчисления. Получаемые при этом методы не всегда оказываются удобными при их численной реализации. Однако соответствующие теоретические результаты лежат в основе большинства алгоритмов решения задач нелинейного программирования (см. главу 21).

В этой главе изложены необходимые и достаточные условия существования экстремумов функций при отсутствии ограничений на переменные задачи, методы Якоба и Лагранжа для решения задач с ограничениями на переменные в форме равенств, а также условия Куна-Таккера для задач с ограничениями в виде неравенств.

20.1. ЭКСТРЕМАЛЬНЫЕ ЗАДАЧИ БЕЗ ОГРАНИЧЕНИЙ

Экстремальная точка функции /(X) определяет либо ее максимальное, либо минимальное значение. С математической точки зрения точка Х.0 = (х1,xjyxj является точкой максимума функции /(X), если неравенство

/(X0 + h)</(X0)

выполняется для всех h = (А,, А;, Ап) таких, что Aj достаточно малы при всех j. Другими словами, точка Х0 является точкой максимума, если значения функции / в окрестности точки Х0 не превышают /(Х0). Аналогично точка Х0 является точкой минимума функции /(X), если для определенного выше вектора h имеет место неравенство

/(X0 + h)>/(X0).

На рис. 20.1 показаны точки максимума и минимума функции одной переменной f(x) на интервале [а, Ь]. Точки xv х2, х3, х4 и хв составляют множество экстремальных точек функции f(x). Здесь точки xv х3 и х6 являются точками максимума, а точки х2их4 - точками минимума функции f(x). Поскольку

f(x6) = max{/(t), f(x3), /(*„)}, значение f(x6) называется глобальным или абсолютным максимумом, а значения f{xx) и f(x3) - локальными или относительными максимумами. Подобным образом, значение f(x4) является локальным, a f(x2) - глобальным минимумом функции f(x).



а хх х2 хг х4 х5 х6 b х

Рас. 20.1. Экстремумы функции одной переменной

Заметим, что хотя точка х1 является точкой максимума функции f(x) (рис. 20.1), она отличается от остальных локальных максимумов f(x) тем, что по крайней мере в одной точке ее окрестности значение функции f(x) совпадает с f(x,). Точка х, по этой причине называется нестрогим (слабым) максимумом функции f(x), в отличие, например, от точки х3, которая является строгим максимумом f(x). Нестрогий максимум, следовательно, подразумевает наличие (бесконечного количества) различных точек, которым соответствует одно и то же максимальное значение функции. Аналогичные результаты имеют место в точке xt, где функция f(x) имеет нестрогий минимум. В общем случае Х0 является точкой нестрогого максимума функции f(x), если /(Х0 + h) < /(Х0), и точкой ее строгого максимума, если /(Х0 + h) < /(Х0), где h - вектор, определенный выше.

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

20.1.1. Необходимые и достаточные условия существования экстремума

В этом разделе излагаются необходимые и достаточные условия существования экстремумов функции п переменных /(X). При этом предполагается, что первые и вторые частные производные функции f(X) непрерывны в каждой точке X.

Теорема 20.1.1. Необходимым условием того, что точка Х0 является экстремальной точкой функции /(X), служит равенство

V/(X0) = 0.

Доказательство. Из теоремы Тейлора следует, что при 0 < в< 1 имеет место разложение функции f(X)

/(Х„ + h) -/(Х0) = V/(X0)h + ib/Hh Xi+0h,

[Старт] [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] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [ 248 ] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]