Standard

Оценка трудоёмкости алгоритма по поиску нуля одной выпуклой кусочно-линейной функции. / Тамасян, Григорий Шаликович; Просолупов, Евгений Викторович.

In: ДИСКРЕТНЫЙ АНАЛИЗ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ, Vol. 25, No. 2, 2018, p. 82-100.

Research output: Contribution to journal › Article › peer-review

Harvard

Тамасян, ГШ & Просолупов, ЕВ 2018, 'Оценка трудоёмкости алгоритма по поиску нуля одной выпуклой кусочно-линейной функции', ДИСКРЕТНЫЙ АНАЛИЗ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ, vol. 25, no. 2, pp. 82-100. https://doi.org/10.17377/daio.2018.25.571

APA

Тамасян, Г. Ш., & Просолупов, Е. В. (2018). Оценка трудоёмкости алгоритма по поиску нуля одной выпуклой кусочно-линейной функции. ДИСКРЕТНЫЙ АНАЛИЗ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ, 25(2), 82-100. https://doi.org/10.17377/daio.2018.25.571

Vancouver

Тамасян ГШ, Просолупов ЕВ. Оценка трудоёмкости алгоритма по поиску нуля одной выпуклой кусочно-линейной функции. ДИСКРЕТНЫЙ АНАЛИЗ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ. 2018;25(2):82-100. https://doi.org/10.17377/daio.2018.25.571

Author

Тамасян, Григорий Шаликович ; Просолупов, Евгений Викторович. / Оценка трудоёмкости алгоритма по поиску нуля одной выпуклой кусочно-линейной функции. In: ДИСКРЕТНЫЙ АНАЛИЗ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ. 2018 ; Vol. 25, No. 2. pp. 82-100.

BibTeX

@article{37751f6d8a4e4e64b753535a50f1a212,
title = "Оценка трудоёмкости алгоритма по поиску нуля одной выпуклой кусочно-линейной функции",
abstract = "Известно, что задача ортогонального проецирования точки на стандартный симплекс сводится к решению скалярного уравнения. В работе анализируется трудоёмкость алгоритма поиска нуля выпуклой кусочно-линейной функции, предложенного в [30]. Проведён анализ лучших и худших случаев входных данных для алгоритма. Для этого изучены наибольшее и наименьшее числа итераций алгоритма как функции от размера входных данных. Показано, что в случае равенства элементов входного множества алгоритм совершает наименьшее число итераций. В случае же различающихся элементов входного множества количество итераций максимально и очень слабо зависит от конкретных значений элементов множества. Приведены результаты вычислительных экспериментов со случайными входными данными высокой размерности.",
keywords = "стандартный симплекс, ортогональное проецирование точки, нули функции",
author = "Тамасян, {Григорий Шаликович} and Просолупов, {Евгений Викторович}",
year = "2018",
doi = "10.17377/daio.2018.25.571",
language = "русский",
volume = "25",
pages = "82--100",
journal = "ДИСКРЕТНЫЙ АНАЛИЗ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ",
issn = "1560-7542",
publisher = "Институт математики им. С.Л. Соболева СО РАН",
number = "2",

}

RIS

TY - JOUR

T1 - Оценка трудоёмкости алгоритма по поиску нуля одной выпуклой кусочно-линейной функции

AU - Тамасян, Григорий Шаликович

AU - Просолупов, Евгений Викторович

PY - 2018

Y1 - 2018

N2 - Известно, что задача ортогонального проецирования точки на стандартный симплекс сводится к решению скалярного уравнения. В работе анализируется трудоёмкость алгоритма поиска нуля выпуклой кусочно-линейной функции, предложенного в [30]. Проведён анализ лучших и худших случаев входных данных для алгоритма. Для этого изучены наибольшее и наименьшее числа итераций алгоритма как функции от размера входных данных. Показано, что в случае равенства элементов входного множества алгоритм совершает наименьшее число итераций. В случае же различающихся элементов входного множества количество итераций максимально и очень слабо зависит от конкретных значений элементов множества. Приведены результаты вычислительных экспериментов со случайными входными данными высокой размерности.

AB - Известно, что задача ортогонального проецирования точки на стандартный симплекс сводится к решению скалярного уравнения. В работе анализируется трудоёмкость алгоритма поиска нуля выпуклой кусочно-линейной функции, предложенного в [30]. Проведён анализ лучших и худших случаев входных данных для алгоритма. Для этого изучены наибольшее и наименьшее числа итераций алгоритма как функции от размера входных данных. Показано, что в случае равенства элементов входного множества алгоритм совершает наименьшее число итераций. В случае же различающихся элементов входного множества количество итераций максимально и очень слабо зависит от конкретных значений элементов множества. Приведены результаты вычислительных экспериментов со случайными входными данными высокой размерности.

KW - стандартный симплекс

KW - ортогональное проецирование точки

KW - нули функции

U2 - 10.17377/daio.2018.25.571

DO - 10.17377/daio.2018.25.571

M3 - статья

VL - 25

SP - 82

EP - 100

JO - ДИСКРЕТНЫЙ АНАЛИЗ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ

JF - ДИСКРЕТНЫЙ АНАЛИЗ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ

SN - 1560-7542

IS - 2

ER -

ID: 27203746