Рубрика «метод ньютона»

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

Один из вариантов эффективного решения — умножать по модулю, вообще при этом не используя операции деления, с помощью алгоритма Монтгомери.

Про него я и хотел бы поговорить.

Постановка задачи

Для простоты изложения, я буду приводить алгоритм для 32-битных целых чисел. Про более широкие числа тоже будут определённые заметки, просто без кода.

Читать полностью »

О методах численной оптимизации написано много. Это и понятно, особенно на фоне тех успехов, которые в последнее время демонстрируют глубокие нейронные сети. И очень отрадно, что хотя бы часть энтузиастов интересуется не только тем, как забомбить свою нейросеточку на набравшей в этих ваших интернетах популярность фреймворках, но и тем, как и почему все это вообще работает. Однако мне в последнее время пришлось отметить, что при изложении вопросов, связанных с обучением нейросетей (и не только с обучением, и не только сетей), в том числе на Хабре, все чаще впроброс используется ряд “хорошо известных” утверждений, справедливость которых, мягко говоря, сомнительна. Среди таких сомнительных утверждений:

  1. Методы второго и более порядков плохо работают в задачах обучения нейросетей. Потомучто.
  2. Метод Ньютона требует положительной определенности матрицы Гессе (вторых производных) и поэтому плохо работает.
  3. Метод Левенберга-Марквардта — компромисс между градиентным спуском и методом Ньютона и вообще эвристичекий.

и т.д. Чем продолжать этот список, лучше перейдем к делу. В этом посте рассмотрим второе утверждение, поскольку его я только на Хабре встречал как минимум дважды. Первый вопрос затрону только в той части, что касается метода Ньютона, поскольку он куда более обширен. Третий и остальные оставим до лучших времен.
Читать полностью »

Julia и метод покоординатного спуска - 1

Метод покоординатного спуска является одним из простейших методов многомерной оптимизации и неплохо справляется с поиском локального минимума функций с относительно гладким рельефом, поэтому знакомство с методами оптимизации лучше начинать именно с него.

Поиск экстремума ведется в направлении осей координат, т.е. в процессе поиска изменяется только одна координата. Таким образом, многомерная задача сводится к одномерной.

Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js