Следствие. Если производная выпуклой функции обращается в некоторой точке в нуль, то функция в этой точке достигает своего аналитического минимума, являющегося при этом наименьшим ее значением. [c.120]
Следовательно, в точке у функция Н(Х у) имеет экстремум ввиду выпуклости функции этот экстремум должен быть минимумом. Таким образом, [c.125]
Остается в силе и аналог следствия п. 12.7 о том, что из обращения в нуль всех первых частных производных выпуклой функции в некоторой точке следует, что в этой точке достигается аналитический минимум, являющийся притом наименьшим значением функции. [c.135]
Из следствия п. 12.7 следует, что всякий локальный минимум выпуклой функции у является ее наименьшим значением. [c.136]
Она является выпуклой функцией С,-. Минимум суммы (11.96) на множестве (11.94) достигается при С, =G2 = G3 и равен 3(2X., + Х.2 - [ J) (l - с). Поэтому [c.423]
Множество допустимых планов, определяемое условиями 1—3, представляет собой выпуклый многогранник. Таким образом, требуется найти минимум выпуклой функции, задан- [c.74]
Доказано, что минимум выпуклой функции на выпуклом множестве точек может быть только один и, следовательно, локальный минимум совпадает с глобальным минимумом. В этом случае возможно сколь угодно точно аппроксимировать (заменять) задачу выпуклого программирования задачей линейного программирования. Для такой аппроксимации в данной задаче нужно заменить кривые / fa) вписанными в них ломаными линиями (рис. 12), а затем преобразовать целевую функцию в линейную, используя уравнения звеньев этих ломаных линий и вводя дополнительные ограничения. Полученная при этом задача линейного программирования имеет точное решение, которое одновременно является приближенным ответом для исходной нелинейной задачи. Разумеется, точность такого ответа будет тем выше, чем точнее кривая аппроксимирована ломаными прямыми линиями. [c.102]
Поскольку выпуклые функции обладают столь полезными оптимизационными качествами, они занимают исключительно важное место в теории исследования операций. Соответствующий раздел получил название выпуклого программирования, а общая задача выпуклого программирования формулируется как проблема поиска максимума вогнутой (минимума выпуклой) функции на выпуклом множестве. [c.93]
Целевая функция — в экстремальных задачах — функция, минимум или максимум которой требуется найти. Это ключевое понятие оптимального программирования. Найдя экстремум целевой функции и, следовательно, определив значения управляемых переменных, которые к нему приводят, мы тем самым находим оптимальное решение задачи. Таким образом, целевая функция выступает как критерий оптимальности решения задачи. Различается ряд видов целевых функций линейная, нелинейная, выпуклая, квадратичная и др. — в соответствии с формой математической зависимости, которую они отображают. Следует также выделить термин целевой функционал он применяется обычно, если целевая функция задачи является функцией от некоторых функций-ограничений. [c.226]
Любая стационарная точка дифференцируемой вогнутой (выпуклой) функции f(M) является точкой локального максимума (минимума) этой функции. [c.147]
Если хотя бы одна из этих функций — нелинейная или содержит произведения искомых переменных, то соответствующая задача — это задача нелинейного программирования. Среди них наиболее изучены задачи выпуклого программирования, в результате решения которых определяют минимум выпуклой (или максимум вогнутой) функции, заданной на выпуклом замкнутом множестве. [c.104]
Из задач выпуклого программирования подробно разработаны задачи квадратичного программирования, в которых требуется найти максимум (или минимум) квадратичной функции при условии, что ее переменные удовлетворяют некоторой системе линейных уравнений. [c.104]
Специфика задачи оптимизации транспортировки нефти проявилась также в выборе критерия оптимальности. В качестве последнего принят минимум расхода энергозатрат — важнейшей составляющей себестоимости, зависящей от объема перекачки. Поскольку эта зависимость нелинейна, то в модели задачи целевая функция нелинейна, в частности, кусочно-линейна, выпукла вниз. [c.72]
Из формулы для выражения средних издержек fT(y) через количество поставок п(Т) видно, что средние издержки являются выпуклой вниз функцией, т. е. достигают минимума в т. Q0, соответствующей оптимальному количеству поставок п(Т) так как ближайшими значениями к Q0 из допустимых целых являются Q и Q2, то минимум достигается в одной из этих точек, что треб, доказать. [c.14]
Требование минимума <т по w в силу выпуклости вниз этой функции [c.110]
До настоящего момента мы находили локальные экстремумы. Однако в оптимизационных задачах, с которыми встречаются в экономике (и в других дисциплинах), обычно ставится задача нахождения абсолютного экстремума. Важность выпуклых (и вогнутых) функций в оптимизационных задачах связана с тем, что локальные минимумы (максимумы) таких функций являются абсолютными. Прежде чем мы это докажем (теорема 8), обсудим более детально свойства выпуклости (вогнутости) функций. [c.170]
Выпуклость (вогнутость) функции позволяет нам легко найти ее абсолютный минимум (максимум), поскольку локальные минимумы (максимумы) таких функций являются одновременно и абсолютными. [c.175]
Так как функция (9) строго выпукла, найденное решение и будет искомым минимумом. П [c.374]
Таким образом, точка А(— 1, 2) — строгий локальный максимум функции, а точка В(1, —2) — ее строгий локальный минимум. 7. Исследуем направление выпуклости графика функции и найдем точки перегиба (см. также пример на с. 163). Найдем вторую производную функции и приравниваем ее нулю [c.176]
Но минимум выпуклой вниз функции и> ц- --2тт 1 гг 2 на выпуклом [c.145]
Но на основании леммы п. 12.10 функция ф(у) является строго выпуклой, а по следствию 3) из п. 12.4 ее минимум единствен (обо значим его через у ). Поэтому спектр всякой оптимальной стратегии игрока 2 исчерпывается точкой. у. Это значит, что кроме у игрок 2 никаких оптимальных стратегий не имеет. П [c.125]
Это значит, что на у достигается наименьшее значение функции Н(Х, ). Как было отмечено в пп. 12.9, 21.2, функция Н(Х, ) является выпуклой. Следовательно, если эта функция дифференцируема (в том смысле, что она имеет первые частные производные по всем компонентам стратегии у игрока 2), то, согласно сказанному в п. 21.2, наименьшее ее значение должно быть аналитическим минимумом в той опорной гиперплоскости, в которой лежит стратегия >> (см. п. 22,4). [c.139]
Целевая функция. Функция в экстремальных задачах, минимум или максимум которой необходимо найти, называется целевой. Экстремальному значению целевой функции обычно соответствует оптимальное решение. Различают линейные, нелинейные, выпуклые и другие целевые функции. В том случае, если допустимое множество экстремальной задачи есть пространство функций, тогда используют термин целевой функционал . [c.12]
Условие локального минимума. Функционал /( ( )) не является выпуклым функционалом, поскольку U — невыпуклая функция х а. С физической точки зрения это свойство совершенно естественно если бы функционал /( ( )) был выпуклым, то, согласно теореме единственности 1 гл. II, он имел бы единственный минимизирующий элемент, а это противоречит экспериментально наблюдаемому явлению неустойчивости упругих тел, связанному с существованием нескольких положений равновесия для одной и той же нагрузки. [c.167]
В случае периодических функций ак (у) стационарные точки вариационных задач (9.33) и (9.35) являются периодическими функциями . В самом деле, при строго выпуклой по и,,- функции Л (а, и, и,/) функционалы в (9.33) и (9.35) являются строго выпуклыми и имеют одну стационарную точку. Решения периодической задачи на ячейке принадлежит множеству допустимых функций и удовлетворяют уравнениям Эйлера вариационных задач (9.33) и (9.35) и, следовательно, доставляют минимум в (9.33) и максимуме (9.35). При этом минимуме (9.33) и максимум в (9.35) совпадают. [c.379]
Если функция y(x,,x,) выпукла вниз и имеет локальный минимум, то он является глобальным минимумом. Если функция f(xf,x2) выпукла вверх и имеет локальный максимум, то он является глобальным максимумом. [c.114]
В экономической теории функция У(х,, х2) обычно определена при х, > 0, х2 > 0 и она либо выпукла вверх, либо выпукла вниз, поэтому её локальный максимум (локальный минимум) является также и глобальным. [c.114]
Итак, задача состоит в отыскании минимума линейной функции при линейных ограничениях, иначе говоря, минимума этой функции на выпуклом многограннике допустимых планов. Выше указывалось, что этот минимум обязательно достигается в одной или нескольких вершинах многогранника. Уточним так дело обстоит, если многогранник ограничен. В противном случае решение задачи может и не существовать. Для решения задачи необходимо иметь возможность устанавливать, оптимален ли план без непосредственного сравнения с планами, соответствующими остальным вершинам многогранника. Эта возможность и дается признаком оптимальности плана, формулируемым в виде такой теоремы. [c.29]
Общая задача В.п. состоит в отыскании такого вектора х (т. е. такойточ-ки выпуклого допустимого множества), который доставляет минимум выпуклой функции J[x) или максимум вогнутой функции у(х) (рис. В.4). Для второго случая (выпуклая область допустимых значений и максимум вогнутой функции) ряд авторов предпочитают термин "вогнутое программирование". Выпуклость (вогнутость) важна тем, что гарантирует нахождение оптимального решения задачи, так как соответственно локальные и глобальный экстремумы здесь обязательно совпадают. Критериями оптимальности в первом случае могут быть, напр., издержки при различных сочетаниях факторов производства, во втором случае — величина прибыли при этих сочетаниях. Как видим, есть сходство между задачами выпуклого (вогнутого) и линейного программирования (последнее можно рассматривать как частный случай первого). Но нелинейность зависимостей делает задачу намного сложнее. [c.57]
Доказательство. Пусть сначала = 1. Тогда по лемме п. 14.2 найдется существенная стратегия х игрока 1, для которой выполняется (14.2). Следовательно, вблизи у = 1 функция Н(х, у) убывает. Но выпуклая функция не может переходить от возрастания к убыванию. Поэтому Н(х, у) убьюает на всем сегменте [О, 1], достигая при у = 1 своего минимума. Это значит, что [c.124]
Скорость сходимости метода случайного спуска в п раз ниже, чем у метода градиентного спуска, но в п раз выше, чем у метода случайного покоординатного спуска. Рассмотренные методы спуска применимы и к необязательно выпуклым функциям и гарантируют их сходимость при очень малых на них ограничениях (типа отсутствия локальных минимумов). [c.179]
Х< А справедливо неравенство d2f/dx2>0. Рассмотрим минимум строго выпуклой функции f(A i) + f(A 2) + f(A 3) при ограничении A i + А2 + + Аз - onst = с. Вводя множитель Лагранжа, убеждаемся, что минимум достигается npn li =A2 =А3. Следовательно, в точке минимума [c.248]
Доказано, что минимум выпуклой функции на выпуклом множестве точек может быть только один и, следовательно, локальный минимум совпадает с глобальным минимумом, В. этом случае, возможно сколь угодно точно аппроксимировать з.а-дачу выпуклого, программирования Рио- 15 задачей линейного программирова- [c.74]
Если f(M) — вогнутая (выпуклая) функция на множестве V, то в любой точке условного локального максимума (минимума) она достигает своего наибольшего (наименьшего) значения. [c.147]
Функция Лагранжа для этой задачи с условиями (5.19), как легко показать, выпукла вниз по д , 02 и достигает минимума в единственной точке. Это значит, что оптимальные значения потоков 0 и 02 постоянны и определяются выражениями (5.19). Однако законы перемещения поршней, естественно, отличаются от тех, которые соответствуют соотношениям Онзагера (5.27). [c.174]
ПРОГРАММИРОВАНИЕ ВЫПУКЛОЕ ( onvex programming) — раздел программирования математического, целевая функция и системы ограничений являются выпуклыми В П в локальный и глобальный экстремумы совпадают Задача П в сводится к отысканию минимума выпуклой вниз ф-ции Ею могут быть, напр, издержки производства [c.202]
Во-вторых, специфика зависимости величины минимума расхода электроэнергии на перекачку от ее объема (в соответствии с принципом 1 это и отображено в критерии оптимальности) такова, что эта зависимость выражается кусочно-линейной выпуклой (вниз) функцией. Это позволило построить точный, быстро сходящийся алгоритм решения задачи, являющейся обобщением метода потенциалов решения сетевой транспортной задачи линейного программирования (СТЗ ЛП) для случая кусочно-линейного выпуклого функционала [41, 47]. Для построения экономико-математической модели задачи введем обозначения г — номер вершины сети 3 (г, s) —дуга сети между вершинами г и s R(E) — множество вершин (дуг) сети Rir(R r< R) [R2t(R2r z zR) подмножество вершин сети, из которых выходят дуги, входящие в r-ю вершину (в которые входят дуги, выходящие из г-й вершины) ur(vr) — объем поступления (потребления) нефти в r-й вершине за плановый период . х — объем перекачки нефти по дуге (г, s) за плановый период ars(Prs) — нижний (верхний) предел значений xrs frs(xrs) — функция зависимости расхода электроэнергии от объема перекачки для дуги (г, s). [c.156]
В силу выпуклости существует точка и, -+ /, 6 U такая, что /<+i/l = = f[x(tf), Ui+vJ. Обычные оценки, используемые при обосновании методов численного интегрирования обыкновенных дифференциальных уравнений, позволяют утверждать, что решение разностной системы хм = х(- -ч/(х , ц мл/,) аппроксимирует траекторию x (t), х( — х (t СЧ, причем постоянная С зависит только от длины интервала Т и константы условия Липшица для функции / (х, и) f(x, и) — f(x, uJl x — х (это условие, разумеется, нужно оговорить). Теперь следует ослабить формулировку разностной задачи (7), потребовав выполнения условий х( G, XN — Х1 лишь с точностью до g. (или с точностью до /т), с тем, чтобы построенная выше разностная траектория могла считаться допустимым решением разностной задачи (7), а для решения этой задачи, существование которого следует из элементарных теорем о достижении минимума в конечномерных пространствах, получаем оценку минимизируемого функционала сверху [c.124]
Нижняя грань по всем неотрицательным фуикциям (4.25) легко находится. Ее определение сводится к вычислению минимума функции <р (а) = 2/ст2 + апри а > 0. Функция f (о) при а > 0 строго выпукла и имеет единственный МИНИМУМ. Решая [c.120]
Для решения этой задачи существует два пути. Во-первых, может быть осуществлена непосредственная минимизация функции F с помощью методов нелинейной оптимизации, позволяющих находить экстремумы выпуклых линий. Это, например, метод наискорейшего спуска, при использовании которого в некоторой исходной точке определяется антиградиент (направление наиболее быстрого убывания) функции F. Далее находится минимум /"при движении в данном направлении, и в точке этого минимума снова определяется градиент. Процедура повторяется до тех пор, пока разница значений F на двух последовательных шагах не окажется меньше заданной малой величины. Другой путь состоит в решении системы нелинейных уравнений, которая получается из необходимых условий экстремума функции F. Эти условия - равенство нулю частных производных функции Fno каждому из параметров а., т.е. [c.360]