or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Do you want to remove this version name and description?
Syncing
xxxxxxxxxx
Зачет по оптимизации
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →Материалы:
Оглавление:
- Зачет по оптимизации
- 9. Матрица Гессе и ее применение для решения задач оптимизации.
- 10. Методы оптимизации нулевого порядка.
- 11. Условная оптимизация.
- 12. Градиент и его применение для решения задач оптимизации.
- 13. Генетические алгоритмы
- 14. Аппроксимация как задача оптимизации.
- 15. Золотое соотношение и его применение для решения задач оптимизации.
- 16. Условия Каруша-Куна-Таккера.
9. Матрица Гессе и ее применение для решения задач оптимизации.
Матрица Гессе — симметрическая квадратичная формы, описывающая поведение функции во втором порядке. Матрица этой квадратичной формы образована вторыми частными производными функции. Если все производные существуют, то она определяется следующим образом:
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →Определитель этой матрицы называется определителем Гессе, или просто гессианом. Матрицы Гессе используются в задачах оптимизации методом Ньютона. Полное вычисление матрицы Гессе может быть затруднительно, поэтому были разработаны квазиньютоновские алгоритмы, основанные на приближённых выражениях для матрицы Гессе. Наиболее известный из них — алгоритм Бройдена — Флетчера — Гольдфарба — Шанно. В методичке он называется BFGS (страница 64).
Если градиент \(f\) (её векторная производная) равен нулю в некоторой точке \(x_{0}\), то эта точка называется критической. Достаточным условием существования экстремума в этой точке является знакоопределённость гессиана \(f\) (понимаемого в данном случае как квадратичная форма), а именно:
10. Методы оптимизации нулевого порядка.
11. Условная оптимизация.
Условная оптимизация — метод поиска максимума или минимума функции при заданных ограничениях на ресурсы системы и выбранных критериях оптимизации. Если ограничения отсутствуют, то метод оптимизации называется безусловным.
Методы условной оптимизации:
2. Метод штрафных функций
3. Метод барьерных функций
12. Градиент и его применение для решения задач оптимизации.
Градиент (от лат. gradiens, род. п. gradientis «шагающий, растущий») — вектор, своим направлением указывающий направление наибольшего возрастания некоторой величины \(\varphi\), значение которой меняется от одной точки пространства к другой (скалярного поля), а по величине (модулю) равный скорости роста этой величины в этом направлении.
Имеет два варианта обозначения: \(grad \varphi\) ,\(\nabla \varphi\).
Допустим есть некоторая функция:
\[ \varphi = \varphi (x, y, z) \]
Градиент данной функции будет равен:
\[ \nabla \varphi = \frac{d\varphi}{dx}i + \frac{d\varphi}{dy}j + \frac{d\varphi}{dz}k \]
Главное свойство градиента – градиент указывает направление наибольшего локального увеличения функции.
Применяется в некоторых алгоритмах оптимизации:
Подробное описание всех перечисленных методов можно найти тут.
13. Генетические алгоритмы
Методичка страница, 64.
Генетические алгоритмы (ГА), так же как другие численные алгоритмы
оптимизации являются итерационными.
Основным объектом, над которым производятся операции в ГА являются особи
(или иначе хромосомы). Каждая хромосома представляет собой набор
значений некоторых параметров, которые можно менять для того, чтобы получить
идеальную особь.
Каждая итерация генетического алгоритма включают в себя три этапа:
Работа алгоритма завершается, когда все хромосомы станут «похожи», или когда будет выполнено достаточное число итераций, или когда будет достигнуто нужное значение функции пригодности.
Генетические алгоритмы часто применяют при решении комбинаторных задач. При этом практически для каждой задачи приходится проектировать отдельный алгоритм, правила скрещивания, мутации и вычисления функции пригодности. Однако многие практические задачи легко сводятся к задаче поиска минимума функции \(n\) вещественных переменных и могут быть решены с помощью единого
алгоритма.
14. Аппроксимация как задача оптимизации.
В информатике сложность аппроксимации — это область изучения вычислительной сложности поиска решений задач оптимизации, близких к оптимальным.
(серег мб это)
1.Задать целевую ф-ию и началльное положение х0
2.Построить апроксимрующую ф-ию f*(x) примерно равную f(x)
3.Найти экстремум x1, для f*
4.Проверить точности, если больше, то шаг 2
15. Золотое соотношение и его применение для решения задач оптимизации.
Метод золотого сечения — метод поиска экстремума действительной функции одной переменной на заданном отрезке. В основе метода лежит принцип деления отрезка в пропорциях золотого сечения. Является одним из простейших вычислительных методов решения задач оптимизации. Впервые представлен Джеком Кифером в 1953 году.
Алгоритм:
На первой итерации заданный отрезок делится двумя симметричными относительно его центра точками и рассчитываются значения в этих точках.
После чего тот из концов отрезка, к которому среди двух вновь поставленных точек ближе оказалась та, значение в которой максимально (для случая поиска минимума), отбрасывают.
На следующей итерации в силу показанного выше свойства золотого сечения уже надо искать всего одну новую точку.
Процедура продолжается до тех пор, пока не будет достигнута заданная точность.
Золотое сечение (золотая пропорция, деление в крайнем и среднем отношении, гармоническое деление) — соотношение двух величин a и b, при котором бо́льшая величина относится к меньшей, так же, как сумма величин к бо́льшей, то есть:
\[ \frac{a}{b} = \frac{a+b}{a} \]
Золотое сечение имеет множество представлений, например непрерывной дробью:
ЗОЛОТОЕ СООТНОШЕНИЕ - содерижтся в методе золотого сечения, когда мы делим отрезок в отношении U(типо фи). ПРи этом свойства золотого сечения гарантируют, что на следующем шаге новая точка в центре отрезка также будет делить его в том же соотношении (это из конспекта)
16. Условия Каруша-Куна-Таккера.