Главная  Методы условной оптимизации 

[0] [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]

- (1978b). On the validity of a nonlinear programming method for solving mini-

max problems, Report 1891, Mathematics Research Center, University of Wisconsin, Madison, Wisconsin.

Хан и Мангасарьян

Han S.-P- and Mangasarian O. L. (1979). Exact penalty function in nonlinear programming, Math. Prog. 17, pp. 251-269.

XappHC

Harris P. M. J. (1973). Pivot selection methods of the Devex LP code. Math. Prog. 5, pp. 1-28. [Reprinted in Math. Prog. Study 4 (f975), pp. 30-57.]

Хартли

Hartley H. O. (1961). Nonlinear programming by the simplex method, Econometrlca 29, pp. 223-237.

Хнчиян Л. Г, (1979). Полиномиальный алгоритм в линейном программнрива-нии.-До11Л. АН СССР, 1979, т. 244, с. 1093-1096.

Хебден

Hebden М. D. (1973). An algorithm for minimization using exact second derivatives. Report TP515, Atomic Energy Research Establishment, Harwell, England.

Хеллермап и Рарик

Hellerman E. and Rarick D. (1971). Reinversion with the preassigned pivot procedure. Math. Prog, i, pp. 195-216.

--(1972). <(The patitioned preassigned pivot procedure (/>*)», in Sparse Matrices

and their Applications (D. J. Rose and R. A. Willoughby, eds.), pp. 67-76, Plenum Press, New York.

Хестенс

Hestenes M- R. (1946). Sufficient conditions for the isoperimetric problem of Bolza in the calculus of variations. Trans. Amer. Math. Soc. 60, pp. 93-118.

- (1947). An alternative sufficiency proof for the normal problem of Bolza, Trans.

Amer. Math. Soc. 61, pp. 256-264.

- (1969). Multiplier and gradient methods, J. Opt. Th. Applies. 4, pp. 303-320.

- (1979). ((Historical overview of generalized Lagrangians and augmentability»,

presented at the IIASA Task Force Meeting on cGeneralized Lagrangians in Systems and Economic Theory, ilASA, Laxenburg, Austria (proceedinffs to be published in 1981).

- (1980a). Conjugate-Direction Methods in Optimization, Springer-Verlag, Beriin,

Heidefberg and New York-

- (1980b). Augmentability in optimization theory, J. Opt. Th. Applies. 32, pp.427-

440.

Хестенс и Штифель

Hestenes М. R. and Stiefel E. (1952). Methods of conjugate gradients for solving linear systems, J. Res. Nat. Bur, Standards 49, pp. 409-436.

Heath M. T. (1978). Numerical Algorithms for Nonlinearly Constrained Optimization, Ph. D. Thesis, Stanford University, California.

Хоув

Howe S. (1973). New conditions for exactness of a simple penalty function, SlAM J. Control 11, pp. 378-381.

Хэммииг

Hamming R. W. (1962). Numerical Methods for Scientists and Engineers, McGraw-Hill Book Co., New York.

- (1971). Introduction to Applied Numerical Analysis, McGraw-Hill Book Co., Ntu York.

- (1973). Numerical Methods for Scientists and Engineers (2nd Edition), McGraw-

Hill Book Co., New York.

Chanfi A. (1952). Optimality and degeneracy in linear programming. Economelrica

20, pp. 160-170. Чариес, Купер и Фергюсон

Charnes А., Cooper W. W. and Ferguson R. (1955). Optimal estimation of executive compensation by linear programming. Management Science 2, pp. 138-151.

Чемберлен

Chamberlain R.M. (1979). Some examples of cycling in variable metric methods for constrained minimization. Math. Prog. 16. pp. 378-383.

Чемберлен, Лемарешаль, Педерсон и Пауэлл

Chamberiain R. М., Lemarechal С, Pederson Н. С. and Powell M.J. D. (1980). The watchdog technique for forcing convergence in algorithms for constrained optimization. Report DAMTP 80/NA I. University of Cambridge.

Шанно

Shanno D- F. (1970). Conditioning of quasi-Newton methods tor function minimization. Mathematics ot Computation 24, pp. 647-657.

- (1978). Conjugate-gradient methods with inexact searches. Math. ofOper. Res. 3,

pp. 244-256.

- (1980). On variable metric methods for sparse Hessians, Mathematics ot Compu-

tation 34, pp. 499-514.

Шанно и Фуа

Shanno D- F. and Phua K- H. (1976). Algorithm 500-Minimization of unconstrained multivariate functions. ACM Trans. Math. Software 2, pp. 87-94.

Шиттковски

Schittkowski K. (1980). Nonlinear Programming Codes, Springer-Verlag Lecture Notes in Economics and Mathematical Systems, Volume 183. Berlin, Heidelberg and New York.

Шиттковски и Стоер

Schittkowski К. and Stoer J. (1979). A factorization method for the solution ot constrained linear feast-squares problems allowing data changes, Num. Math. 31. pp. 431-463.

Шор H. 3. (f970). О скорости сходимости метода обобщенного градиентного спуска с растяжением пространства.- Кибернетика. 1970, № 2. с. 80-85.

Шор Н. 3- (1977). Метод отсечения с растяжением пространства для решения задач выпуклого программирования.- Кибнетика. 1977, № I, с. 94-95

Шор Н. 3., Гершович В. И. (1979). Об одном семействе алгоритмов для решения задач выпуклого программирования.- Кибернетика, 1979, № 4. с. 62-67.

Штифель

Stiefel Е- (1960). Note on Jordan elimination, linear programming and Tscheby-schett approximation. Num.-Math. 2, pp. 1-17.

mvfiepT

Schubert L. K- (1970). Modification of a quasi-Newton method for nonlinear equations with a sparse Jacobian, Mathematics of Computation 24, pp. 27-30.

. An analog solution of programming problems.

Эблоу и Брай-хем Ablow С. М. and Brigham G. (I9f

Operation Research 3, pp. asa-

Эванс, Гулд и Толле

Evans J. p., Gould F. J. and Tolle J. W. (1973). Exact penalty functions in nonlinear programming. Math. Prog- 4, pp. 72-97.



Эккер

Ескег J. G. (1980). Geometric programming: methods, computations and appfica-tionb, sum Review 22, pp, 338-362.

Эль-Аттар, Впдьясагар и Дутта

El-Attar R. A., Vidyasagar M. and Dutta S. R. K. (1979). An algorithm for /i-norm minimization with application to nonlinear Z, approximation, SIAM J, Numer. Anal. 16, pp, 70-86.

Эскудеро

Escudero L. (1980). A projected Lagrangian method for nonlinear programming.

Report G320-3401, IBM Palo Alto Scientilic Center. Эспвол и Стоуи

Aspvalf В. and Stone R. E. (1980). Khachiyans linear programming algorithm. Journal o! Algorithms I, I-13.

Яррат и Наде

Jarratt p. and Nudds D. (1965). The use of rational functions in the iterative solution of equations on a computer, Computer Journal 9, pp. 62-G5,

ОГЛАВЛЕНИЕ

Предисловие редактора перевода . Предисловие.........

Глава 1- Введение .

1.1. Постановка задачи оптимизации . . . .

1.2. Классификация оптимизационных задач

1.3. Краткий обзор содержания......

12 14

Глава 2. Основы .

2.1. Введение в теорию ошибок вычислений .

2. L L Измерение ошибки...............

2.1-2. Представление числа в матине.......

2.1.3- Ошибки округления...............

2.1.4. Ошибки при вьтолненни арифметических операций

2.1.5. Ошибки компенсации...............

2.1.6. Точность при последовательных вычислениях . .

2.1.7. Анализ ошибок для алгоритмов.........

2.2. Введение в вычислительную линейную алгебру

2.2.1. Предварительные сведения.......

2.2.2. Векторные пространства......

2.2.3. Линейные преобразования...........

2.2.4. Линейные уравнения........i ..... .

2.2.5. Разложения матриц...............

2.2.6. Многомерная геометрия ... ..........

2.3. Элементы мнсгомериого анализа...........

2.3.1. Функщш многих переменных; линии уровня . . .

2.3.2. Непрерывные функции н их производные . . .

2.3.3. Порядок функции..............

2.3.4. Теорема Тейлора................

2.3.5. Конечно-разностиая аппроксимация производных ,

2.3.6. Скорости сходимости последовательностей . . , .

16 16 17 19

21 23 24 25 26 26 33 38 41 50 64 66 66 66 72 73 74 78

Глава 3. Условия оптимальности........ S1

3.1. Определение минимума................ 81

3.2. Безусловная оптимизация . . ........... 84

3.2.1. Одномерный случай............. 4

3.2.2. Много-мерный случаи............ - -

3.2.3. Свойства квадратичных функций............. 88



3.3. Оптимизация при линейных ограничениях......... 90

3.3.1. Задачи с; ограничениями типа линейных равенств . ... 91

3.3.2. Задачи с ограничениями типа линейных неравенств .... 95

3.4. Оптимизация при нелинейных ограничениях......... 104

3.4.1. Задачи с ограничениями типа нелинейных....... . 104

3.4.2. Задачи с ограничениями типа иелииейных неравенств . . , 109

Глава 4. Методы безусловной минимизации........... . . Ill

4.1. Методь! для функции одной переменной............ 111

4.1.1. Поиск нуля функции одной переменной.......... Ill

4.1.2. Метолы одномерной минимизации............ 118

4.2. Методы для негладких функций многих переменных..... 124

4.2.1. Применение методов с сопоставлением значений функции 124

4.2.2. Метод многогранника............... 125

4.2.3. Составные недифференцируемые функции .... 128

4.3. Методы для гладких функций многих переменных . 132

4.3.1. Модельная схема минимизации гладких функций .... 132

4.3.2. Сходимость модельной схемы............... 133

4.4. Методы второго порядка.................. 141

4.4.1. Метод Ньютона . . ................. 141

4.4.2. Стратегии для знаконеопределенной матрицы Гессе . . 144

4.5. Мегоды первого порядка................... 158

4.5.1. Ньютоновские методы с конечно-разностной аппроксимацией 158

4.5.2. Квазиныагоновские методы............... 160

4.6. Методы минимизации гладких функций без вычислений производных ............................... 174

4.6.1. Конечно-разностная аппроксимация первых производных . 175

4.6.2. Квазиньютоноаскне методы без вычисления производных . 180 4.7. Методы решения задач о наименьших квадратах....... 183

-4.7.1. Происхождение заДач о наименьших квадратах; основания

для использования специальных методов ..... 183

4.7.2. Метод Гаусса - Ньютона......... 184

4.7.3. Метод Левенберга - Л\аркардта .... 188

4.7.4. Квазиньютоновские методы............ 189

4.7.5. ("корректированный метод Гаусса - Ньютона . . . 190 -4.7.6- Не.1иней(ше уравнения................. 193

4.6. Методы решения задач большой размерности......... 195

4.8.1- Дискретные методы Ньютона для функций с разреженными

матрицами Гессе........................ 196

4.8.2. Квазиньютоновские методь! для функций с разреженными матрицами Гессе........................ 193

4.8.3. А\етоды сопряженных градиентов............ 200

4.8.4. Квазиньютоновские методы с ограниченной памятью .... 208

4.8.5. Методы сопряженных градиентов с улучшением обусловленности ............................. 209

4.8.6. Решение ньютоновских уравнений линейным методом сопряженных градиентов...................... 212

Глава б. Задачи с линейными ограничениями.......... 216

5.1. Методы поиска минимума при ограничениях-равенствах . 216

5.1.1. Принцип организации а..-1гори™оБ . . ........ 217

5.1.2. Расчет направления поиска............... 220

5.1.3. Представление нуль-пространства ограничетн"! , ... 225

5.1.4. Специальные формы целевой функции........... 228

5.1.5. Оценки множителей Лагранжа..............

5.2. Методы активного набора для задач с ограничениями типа линейных uepaBcHCTii.......................

5.2.1. Модельная схема................. .

5.2.2. Расчет направления поиска и длины шага ........

5.2.3. Интерпретация оценок множителей Лагранжа.......

5.2.4. Вычисления при изменении рабочего списка.......

5.3. Задачи специальных типов...............

5-3.1. Линейное программирование ... ........

5.3.2. Квадратичное программирование.............

5.3.3. Линейная задача о наименьших квадратах с ограничениями

5.4. Задачи с малым числом ограничений общего вида.......

5.4.1. Квадратичные задачи с положительно определенными матрицами Гессе ..........................

5.4.2. Методы вторых производных для решения задач общего вида 5-5. Задачи с ограничениями специального вида.........

5.5.1. Минимизация при простых ограничениях Eia переменные .

5.5.2. Задача со смесью простых ограничений и ограничений общего вида..............................

5.6. Большие задачи с линейными ограничениями........

5.6.1. Методы решения больших задач линейного программирования ..............................

5.6.2. Большие задачи с линейными ограничениями и нелинейными критериями............. .........

5.7. Поиск начальной допустимой точки ... ...

5.8. Реализация методов активного набора....... . .

5.8.1. Определение начального рабочего списка....... .

5.8.2. Линейно зависимые ограничения............,

5.8.3. Нулевые множители Лагранжа ..

Г.гава 6. Задачи с нелинейными ограничениями

6.1. Общие определения................... .

6.1.1. Функция выигрыша...................

6.1.2. Классификация подзадач.............

6.2. Методы штргфшх н барьерных функций..........

6.2.1. Методы гладких штрафньк и барьерных функций.....

6.2.2. Методы негладких штрафных функций..........

6.3. Методы приведенных ]-радиентов и проекций градиентов . . .

6.3.1. Общие с{Н)браження..................

6.3.2. Поиск при ограничениях-равенствах . . ......

6.3.3. Определение рабочего списка...........

6.4. Мето№1 моди4ииированных функций Лагранжа ....

6.4.1. Определение модифицированной функции Лагранжа ....

6.4.2. Схема алгоритмов с модифицированными функциями Лагранжа ..............................

6.4.3. Вариации стратегии поиска...............

6.5. Методы спроектированного лагранжиана...........

6.5.1. Предварительные соображения........<•»,>•

6.5.2. Подзадача с целевой функцией общего вида .«..,*«

6.5.3. Квадратичная [юдзадача............

6.5.4. Стратегии для дефектных подзадач ........., .

6.5.5. Постр)СИне активного набора .. .....

6.6. Оценки множителей Лагранжа..............

6.6.1. Оценки первого порядка................

6-6.2. Оценки второго порядка................

235 236 238 240 246 246 248 252 256

256 258 251 261

264 266

270 278 280 280 282 283

287 287

304 304 305 309 310 311

314 317

320 320 322 325 332 333 338 339 340



[0] [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]

0.001