| dbo:abstract
|
- Innere-Punkte-Verfahren sind in der Optimierung eine Klasse von Algorithmen zur Lösung von Optimierungsaufgaben.Ihr Hauptanwendungsgebiet sind lineare oder quadratische Programme. Sie werden aber auch zur Lösung (allgemeiner) nichtlinearer Programme, semidefinierter Programme oder Komplementaritätsproblemen eingesetzt. Im Vergleich zu den traditionelleren Active-Set-Methoden (z. B. Simplex-Verfahren) zeichnen sich Innere-Punkte-Verfahren durch bessere theoretische Eigenschaften (polynomiale Komplexität) und schnellere Konvergenz für sehr große dünnbesetzte Probleme aus. Ein Nachteil ist, dass sie vergleichbar ungeeignet zum Lösen einer Serie von Optimierungsaufgaben sind (was für viele Algorithmen der ganzzahligen Optimierung, wie z. B. Branch and Bound oder Schnittebenenverfahren, wichtig ist). (de)
- Interior-point methods (also referred to as barrier methods or IPMs) are a certain class of algorithms that solve linear and nonlinear convex optimization problems. An interior point method was discovered by Soviet mathematician I. I. Dikin in 1967 and reinvented in the U.S. in the mid-1980s.In 1984, Narendra Karmarkar developed a method for linear programming called Karmarkar's algorithm, which runs in provably polynomial time and is also very efficient in practice. It enabled solutions of linear programming problems that were beyond the capabilities of the simplex method. Contrary to the simplex method, it reaches a best solution by traversing the interior of the feasible region. The method can be generalized to convex programming based on a self-concordant barrier function used to encode the convex set. Any convex optimization problem can be transformed into minimizing (or maximizing) a linear function over a convex set by converting to the epigraph form. The idea of encoding the feasible set using a barrier and designing barrier methods was studied by Anthony V. Fiacco, Garth P. McCormick, and others in the early 1960s. These ideas were mainly developed for general nonlinear programming, but they were later abandoned due to the presence of more competitive methods for this class of problems (e.g. sequential quadratic programming). Yurii Nesterov, and Arkadi Nemirovski came up with a special class of such barriers that can be used to encode any convex set. They guarantee that the number of iterations of the algorithm is bounded by a polynomial in the dimension and accuracy of the solution. Karmarkar's breakthrough revitalized the study of interior-point methods and barrier problems, showing that it was possible to create an algorithm for linear programming characterized by polynomial complexity and, moreover, that was competitive with the simplex method.Already Khachiyan's ellipsoid method was a polynomial-time algorithm; however, it was too slow to be of practical interest. The class of primal-dual path-following interior-point methods is considered the most successful.Mehrotra's predictor–corrector algorithm provides the basis for most implementations of this class of methods. (en)
- Les méthodes de points intérieurs forment une classe d’algorithmes qui permettent de résoudre des problèmes d’optimisation mathématique. Elles ont l'intérêt d'être polynomiales lorsqu'on les applique aux problèmes d'optimisation linéaire, quadratique convexe, semi-définie positive ; et plus généralement aux problèmes d'optimisation convexe, pourvu que l'on dispose d'une représentant l'ensemble admissible, calculable en temps polynomial (ce n'est pas toujours le cas, car certains problèmes d'optimisation convexe sont NP-difficiles (voir Problème NP-complet)). Les méthodes de points intérieurs se répartissent en plusieurs familles :
* les méthodes « affine scaling » (optimisation sur des ellipsoïdes) ;
* les méthodes de réduction du potentiel (notion de barrière, chemin central, relaxation). (fr)
- 내부점법(Interior point method)은 볼록 최적화에서 최적해를 (영어: feasible region)의 내부에서 찾아가는 방법이다. 그러므로 볼록하다면 비선형 계획법에서도 적용할 수 있다. 선형 계획법에서 내부점법은 (마라티어: नरेंद्र करमरकर, 영어: Narendra Karmarkar)가 이라는 방법으로 1984년에 개발했다. (ko)
- 内点法（ないてんほう、英: internal point method）とは、連続最適化問題のアルゴリズムであり、カーマーカー法に触発されて生まれた多くの手法の総称である。実行可能領域の内部を経由して、最適解に収束するのが特徴である。また、大規模問題に対しては計算効率が良い点や非線型問題にも対応できる点で、シンプレックス法よりも優れているといえる。内点法は、点列を生成する方法によって、、、などに分類される。また、扱う問題によっては、与えられた問題を直接扱う方法(主内点法、英: primal interior point method)、その双対問題を扱う方法(双対内点法、英: dual interior point method)、主問題と双対問題を同時に解く方法(主双対内点法、英: primal-dual interior point method)に分けられる。 (ja)
- Метод внутренней точки — это метод позволяющий решать задачи выпуклой оптимизации с условиями, заданными в виде неравенств, сводя исходную задачу к задаче выпуклой оптимизации. Используется в решениях задач по сопромату, математическому моделированию и эконометрике. Метод внутренних точек был впервые упомянут в 1967 году.. Эти исследования были продолжены в том числе и отечественными учёными. В 1970-е годы В.Г. Жадану удалось получить основные результаты и разработать общий подход к построению методов внутренней точки для решения задач линейного и нелинейного программирования, основанный на преобразовании пространств; предложить барьерно-проективные и барьерно-ньютоновские численные методы. В западной литературе утверждается, что метод внутренней точки был впервые предложен Джоном фон Нейманом и в первоначальном виде не обладал полиномиальной сложностью, как и не был эффективным. На практике он даже уступал симплекс-методу, также не обладавшему полиномиальной сложностью. Однако в 1984 году предложенный индийским математиком Нарендра Кармаркаром алгоритм линейного программирования демонстрировал полиномиальное время даже превосходил симплекс-метод. Согласно методам внутренней точки (иначе называемым методами барьерных функции), исходную для поиска точку можно выбирать только внутри допустимой области. Выбор начальной точки поиска осуществляется в зависимости от формулировки задачи. При отсутствии ограничений или их преобразовании к функциям штрафа с внешней точкой начальная точка выбирается произвольно. При наличии ограничений или их преобразовании к функциям штрафа с внутренней точкой начальная точка выбирается внутри допустимой области При этом множество точек делится на допустимые и недопустимые в зависимости от ограничений . В свою очередь множество допустимых точек в зависимости от ограничений также делится на граничные и внутренние. (ru)
- Методи внутрішніх точок (їх також називають бар'єрними методами або ІРМ) — це певний клас алгоритмів, що вирішують задачі лінійної та нелінійної опуклої оптимізації. Джон фон Нейман запропонував внутрішній точковий метод лінійного програмування, який не був ні методом поліноміального часу, ні ефективним методом на практиці. Насправді він виявився повільнішим, ніж широко використовуваний симплекс-метод. У 1984 р. Нарендра Кармакар розробила метод лінійного програмування, який називається алгоритмом Кармаркара, який працює за поліноміальний час і також є дуже ефективним на практиці. Це дало змогу вирішити задачі лінійного програмування, що вийшли за межі можливостей симплексного методу. На відміну від симплексного методу, він досягає найкращого рішення шляхом обходу внутрішніх областей допустимих рішень. Метод може бути узагальнений до випуклого програмування на основі самокоректної бар'єрної функції, що використовується для кодування опуклого набору. Будь-яка проблема оптимізації опуклості може бути перетворена на мінімізацію (або максимізацію) лінійної функції над опуклою множиною шляхом перетворення її у форму епіграфа. Ідея кодування множини допустимих ріщень за допомогою бар'єру та проектування бар'єрних методів була вивчена Антонієм В. Юрієм Нестеровим та Аркадієм Немировським, вони придумали особливий клас таких бар'єрів, який можна використовувати для кодування будь-якої опуклої множини. Вони гарантують, що кількість ітерацій алгоритму обмежена поліномом у розмірності та точності рішення. Прорив Кармаркара активізував вивчення методів внутрішніх точок та бар'єрних проблем, показавши, що можна створити алгоритм лінійного програмування, який характеризується поліноміальною складністю і, крім того, конкурентоспроможним із симплексним методом. Вже еліпсоїдний метод Хачіяна був алгоритмом поліноміального часу; проте це було занадто повільно, щоб представляти практичний інтерес. Клас первинних-подвійних методів, що слідують за внутрішніми точками, вважається найбільш успішним. Алгоритм прогнозування-коректор Мехротри дає основу для більшості реалізацій цього класу методів. (uk)
|
| rdfs:comment
|
- 내부점법(Interior point method)은 볼록 최적화에서 최적해를 (영어: feasible region)의 내부에서 찾아가는 방법이다. 그러므로 볼록하다면 비선형 계획법에서도 적용할 수 있다. 선형 계획법에서 내부점법은 (마라티어: नरेंद्र करमरकर, 영어: Narendra Karmarkar)가 이라는 방법으로 1984년에 개발했다. (ko)
- 内点法（ないてんほう、英: internal point method）とは、連続最適化問題のアルゴリズムであり、カーマーカー法に触発されて生まれた多くの手法の総称である。実行可能領域の内部を経由して、最適解に収束するのが特徴である。また、大規模問題に対しては計算効率が良い点や非線型問題にも対応できる点で、シンプレックス法よりも優れているといえる。内点法は、点列を生成する方法によって、、、などに分類される。また、扱う問題によっては、与えられた問題を直接扱う方法(主内点法、英: primal interior point method)、その双対問題を扱う方法(双対内点法、英: dual interior point method)、主問題と双対問題を同時に解く方法(主双対内点法、英: primal-dual interior point method)に分けられる。 (ja)
- Innere-Punkte-Verfahren sind in der Optimierung eine Klasse von Algorithmen zur Lösung von Optimierungsaufgaben.Ihr Hauptanwendungsgebiet sind lineare oder quadratische Programme. Sie werden aber auch zur Lösung (allgemeiner) nichtlinearer Programme, semidefinierter Programme oder Komplementaritätsproblemen eingesetzt. (de)
- Interior-point methods (also referred to as barrier methods or IPMs) are a certain class of algorithms that solve linear and nonlinear convex optimization problems. An interior point method was discovered by Soviet mathematician I. I. Dikin in 1967 and reinvented in the U.S. in the mid-1980s.In 1984, Narendra Karmarkar developed a method for linear programming called Karmarkar's algorithm, which runs in provably polynomial time and is also very efficient in practice. It enabled solutions of linear programming problems that were beyond the capabilities of the simplex method. Contrary to the simplex method, it reaches a best solution by traversing the interior of the feasible region. The method can be generalized to convex programming based on a self-concordant barrier function used to encod (en)
- Les méthodes de points intérieurs forment une classe d’algorithmes qui permettent de résoudre des problèmes d’optimisation mathématique. Elles ont l'intérêt d'être polynomiales lorsqu'on les applique aux problèmes d'optimisation linéaire, quadratique convexe, semi-définie positive ; et plus généralement aux problèmes d'optimisation convexe, pourvu que l'on dispose d'une représentant l'ensemble admissible, calculable en temps polynomial (ce n'est pas toujours le cas, car certains problèmes d'optimisation convexe sont NP-difficiles (voir Problème NP-complet)). (fr)
- Методи внутрішніх точок (їх також називають бар'єрними методами або ІРМ) — це певний клас алгоритмів, що вирішують задачі лінійної та нелінійної опуклої оптимізації. Джон фон Нейман запропонував внутрішній точковий метод лінійного програмування, який не був ні методом поліноміального часу, ні ефективним методом на практиці. Насправді він виявився повільнішим, ніж широко використовуваний симплекс-метод. У 1984 р. Нарендра Кармакар розробила метод лінійного програмування, який називається алгоритмом Кармаркара, який працює за поліноміальний час і також є дуже ефективним на практиці. Це дало змогу вирішити задачі лінійного програмування, що вийшли за межі можливостей симплексного методу. На відміну від симплексного методу, він досягає найкращого рішення шляхом обходу внутрішніх областей допус (uk)
- Метод внутренней точки — это метод позволяющий решать задачи выпуклой оптимизации с условиями, заданными в виде неравенств, сводя исходную задачу к задаче выпуклой оптимизации. Используется в решениях задач по сопромату, математическому моделированию и эконометрике. Согласно методам внутренней точки (иначе называемым методами барьерных функции), исходную для поиска точку можно выбирать только внутри допустимой области. (ru)
|
