Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Процесс решения некоторых задач оптимизации. В математике нелинейное программирование (НЛП) — это процесс решения задачи оптимизации, в которой некоторые ограничения не являются линейными равенствами или целевая функция не является линейной. Задача оптимизации — это вычисление экстремумов (максимумов, минимумов или стационарных точек) целевой функции на множестве неизвестных вещественных переменных при условии выполнения системы равенств и неравенств, которые в совокупности называются ограничениями. Это раздел математической оптимизации, занимающийся задачами, не являющимися линейными.
Solution process for some optimization problems
In mathematics, nonlinear programming (NLP) is the process of solving an optimization problem where some of the constraints are not linear equalities or the objective function is not a linear function. An optimization problem is one of calculation of the extrema (maxima, minima or stationary points) of an objective function over a set of unknown real variables and conditional to the satisfaction of a system of equalities and inequalities, collectively termed constraints. It is the sub field of mathematical optimization that deals with problems that are not linear.
Применимость
Типичная невыпуклая задача – это оптимизация транспортных расходов путем выбора из набора транспортных средств, один или несколько из которых демонстрируют эффект масштаба, с учетом различных связей и ограничений по пропускной способности. Примером может служить транспортировка нефтепродуктов с использованием трубопроводов, железнодорожных цистерн, автомобильных цистерн, речных барж или танкеров прибрежного плавания, либо их комбинации. Из-за экономической целесообразности размера партии функции затрат могут иметь разрывы в дополнение к плавным изменениям. В экспериментальной науке некоторые простые задачи анализа данных (например, аппроксимация спектра суммой пиков с известным положением и формой, но неизвестной амплитудой) можно решать линейными методами, но в общем случае эти задачи также нелинейны. Как правило, имеется теоретическая модель изучаемой системы с переменными параметрами и модель эксперимента или экспериментов, которые также могут содержать неизвестные параметры. Задача состоит в том, чтобы численно найти наилучшее соответствие. В этом случае часто требуется оценка точности полученного результата, наряду с самим наилучшим соответствием.
A typical non convex problem is that of optimizing transportation costs by selection from a set of transportation methods, one or more of which exhibit economies of scale, with various connectivities and capacity constraints. An example would be petroleum product transport given a selection or combination of pipeline, rail tanker, road tanker, river barge, or coastal tankship. Owing to economic batch size the cost functions may have discontinuities in addition to smooth changes. In experimental science, some simple data analysis (such as fitting a spectrum with a sum of peaks of known location and shape but unknown magnitude) can be done with linear methods, but in general these problems are also nonlinear. Typically, one has a theoretical model of the system under study with variable parameters in it and a model the experiment or experiments, which may also have unknown parameters. One tries to find a best fit numerically. In this case one often wants a measure of the precision of the result, as well as the best fit itself.
Аналитические методы
В условиях дифференцируемости и выполнения ограничений, условия Каруша — Куна — Таккера (KKT) предоставляют необходимые условия оптимальности решения. Если некоторые функции недифференцируемы, доступны субдифференциальные версии условий Каруша — Куна — Таккера (KKT). При выпуклости условия KKT являются достаточными для достижения глобального оптимума. Без выпуклости эти условия достаточны только для локального оптимума. В некоторых случаях число локальных оптимумов невелико, и их все можно найти аналитически, выбрав из них решение с наименьшим значением целевой функции.
Under differentiability and constraint qualifications, the Karush–Kuhn–Tucker (KKT) conditions provide necessary conditions for a solution to be optimal. If some of the functions are non differentiable, subdifferential versions of Karush–Kuhn–Tucker (KKT) conditions are available. Under convexity, the KKT conditions are sufficient for a global optimum. Without convexity, these conditions are sufficient only for a local optimum. In some cases, the number of local optima is small, and one can find all of them analytically and find the one for which the objective value is smallest.
Разделенный и связанный
Другой метод предполагает использование методов ветвей и границ, где программа разбивается на подзадачи, решаемые с помощью выпуклых (задача минимизации) или линейных аппроксимаций, формирующих нижнюю оценку общей стоимости в пределах данной подзадачи. При последующих разбиениях в какой-то момент будет получено фактическое решение, стоимость которого равна наилучшей нижней оценке, полученной для любого из приближенных решений. Это решение является оптимальным, хотя, возможно, и не единственным. Алгоритм также может быть остановлен преждевременно, с гарантией того, что наилучшее возможное решение находится в пределах допустимой погрешности от наилучшей найденной точки; такие точки называются ε-оптимальными. Завершение работы в ε-оптимальных точках обычно необходимо для обеспечения конечности алгоритма. Это особенно полезно для больших и сложных задач, а также для задач с неопределенными стоимостями или значениями, где неопределенность может быть оценена с использованием соответствующей оценки надежности.
Another method involves the use of branch and bound techniques, where the program is divided into subclasses to be solved with convex (minimization problem) or linear approximations that form a lower bound on the overall cost within the subdivision. With subsequent divisions, at some point an actual solution will be obtained whose cost is equal to the best lower bound obtained for any of the approximate solutions. This solution is optimal, although possibly not unique. The algorithm may also be stopped early, with the assurance that the best possible solution is within a tolerance from the best point found; such points are called ε optimal. Terminating to ε optimal points is typically necessary to ensure finite termination. This is especially useful for large, difficult problems and problems with uncertain costs or values where the uncertainty can be estimated with an appropriate reliability estimation.