| dbo:abstract
|
- في الإستمثال الرياضي، تعتبر شروط كاروش كوهن تاكر (KKT)، المعروفة أيضا باسم شروط كوهن تاكر، هي اختبارات مشتقة أولى (تسمى أحيانا الشروط الضرورية من الدرجة الأولى) لإيجاد حل في البرمجة غير الخطية يكون هو الأمثل، شريطة استيفاء بعض شروط الانتظام والسماح بقيود عدم المساواة المفروضة على دالة الهدف، فإن نهج KKT في البرمجة غير الخطية يعمم طريقة مضاعفات لاجرانج التي لا تسمح في الأصل إلا بقيود المساواة. على غرار نهج لاجرانج، تتم إعادة صياغة مشكلة إيجاد القيمة العظمى المقيدة (التصغير) كدالة لاجرانج التي تكون نقطتها المثلى هي نقطة السرج تلعب هذه الظروف دورا مهما جدا في نظرية الإستمثال المقيدة وتطوير الخوارزمية. للحصول على مشكلة إستمثال: min f(x) تخضع إلى gi(x) - bi ≥ 0 , i=1,…,k gi(x) - bi = 0 , i=k+1,…,m هناك أربعة شروط KKT لبداية مثلى : 1. القيود المجدية:gi(x*) - bi 2. لا يوجد هبوط ممكن:f(x*) - Σi=1,m λi* ∇gi(x*) = 0∇ 3. الركود التكميلي:λi*(gi(x*) - bi) = 0 4. مضاعفات لاجرانج إيجابية:λi* ≥ 0 يشير رمز النجمة (*) إلى القيم المثلى. ينطبق شرط الجدوى (1) على كل من قيود المساواة وعدم المساواة، بمجرد إثبلت نه يجب عدم انتهاك القيود في الظروف المثلى.شرط التدرج (2) يضمن عدم وجود اتجاه ممكن يمكن أن يحسن الدالة الهدف.الشرطين الأخيرين (3 و 4) مطلوبين في حالة وجود قيود عدم المساواة وأن مضاعفات لاجرانج تكون موجبة في حالة القيد النشط (=0) وتساوي صفر في حالة القيد الغير نشط (>0). تشكل شروط KKT (Karush-Kuhn-Tucker) العمود الفقري للبرمجة الخطية وغير الخطية فتمثل الأسس النظرية للعديد من الخوارزميات، نذكر منها على وجه الخصوص خوارزمية كارماركر وطريقة السيمبلكس. كما هي:
* ضرورية وكافية لتحقيق الإستمثال في البرمجة الخطية.
* ضرورية وكافية لتحقيق الأمثلية المحدبة، مثل تصغير المربع الأقل في الانحدار الخطي.
* ضرورية لتحقيق الأمثل في مشكلة الإستمثال غير المحدبة، مثل تدريب نموذج التعلم العميق. (ar)
- En programació no lineal les condicions de Karush-Kuhn-Tucker (també anomenades condicions de KKT, o condicions Kuhn-Tucker) són condicions que ha de complir un punt que sigui solució d'un problema de la forma: on on On, si definim i : Es tracta d'una generalització del Mètode dels multiplicadors de Lagrange. (ca)
- Die Karush-Kuhn-Tucker-Bedingungen sind ein notwendiges Optimalitätskriterium erster Ordnung in der nichtlinearen Optimierung. Sie sind die Verallgemeinerung der notwendigen Bedingung von Optimierungsproblemen ohne Nebenbedingungen und der Lagrange-Multiplikatoren von Optimierungsproblemen unter Gleichungsnebenbedingungen. Sie wurden zum ersten Mal 1939 in der allerdings unveröffentlichten Master-Arbeit von William Karush aufgeführt. Bekannter wurden diese jedoch erst 1951 nach einem Konferenz-Paper von Harold W. Kuhn und Albert W. Tucker. (de)
- Las condiciones de Karush-Kuhn-Tucker (también conocidas como las condiciones KKT o Kuhn-Tucker) son requerimientos necesarios y suficientes para que la solución de un problema de programación matemática sea óptima. Es una generalización del método de los multiplicadores de Lagrange. (es)
- In mathematical optimization, the Karush–Kuhn–Tucker (KKT) conditions, also known as the Kuhn–Tucker conditions, are first derivative tests (sometimes called first-order necessary conditions) for a solution in nonlinear programming to be optimal, provided that some are satisfied. Allowing inequality constraints, the KKT approach to nonlinear programming generalizes the method of Lagrange multipliers, which allows only equality constraints. Similar to the Lagrange approach, the constrained maximization (minimization) problem is rewritten as a Lagrange function whose optimal point is a saddle point, i.e. a global maximum (minimum) over the domain of the choice variables and a global minimum (maximum) over the multipliers, which is why the Karush–Kuhn–Tucker theorem is sometimes referred to as the saddle-point theorem. The KKT conditions were originally named after Harold W. Kuhn and Albert W. Tucker, who first published the conditions in 1951. Later scholars discovered that the necessary conditions for this problem had been stated by William Karush in his master's thesis in 1939. (en)
- En mathématiques, les conditions de Karush-Kuhn-Tucker ou anciennement conditions de Kuhn-Tucker sont une généralisation des multiplicateurs de Lagrange qui permettent de résoudre des problèmes d'optimisation sous contraintes non linéaires d'inégalités. Soit , une fonction appelée fonction objectif, et des fonctions , , appelées contraintes. On suppose que et les sont de classe C1. Le problème à résoudre est le suivant : Trouver qui maximise sous les contraintes pour tout . (fr)
- カルーシュ・クーン・タッカー条件（英: Karush-Kuhn-Tucker condition）あるいはKKT条件とは、非線形計画において一階導関数が満たすべき最適条件を指す。ラグランジュの未定乗数法が等式制約のみを扱うのに対して、KKT条件を用いた解法は不等式制約も扱うことができる。KKT条件に対応する連立方程式は、解析的に閉形式解法が導かれる特殊な場合を除いては直接的には解かない。すでにKKT条件の連立方程式を数値的に解く方法は数多く確立されており、それらを用いて解くのが一般的である。KKT条件は線形計画法における主双対内点法などの解法において、重要な役割を持つ。 (ja)
- 카루시-쿤-터커 조건(Karush–Kuhn–Tucker conditions) 또는 KKT 조건은 (William Karush), (Harold W. Kuhn), (Albert W. Tucker)가 만든 최적화의 조건으로 라그랑주 승수법을 부등식을 가진 경우로 일반화한 것이다. (ko)
- In matematica, le condizioni di Karush–Kuhn–Tucker (anche conosciute come condizioni di Kuhn-Tucker o condizioni KKT) sono condizioni necessarie per la soluzione di un problema di programmazione non lineare in cui i vincoli soddisfino una delle condizioni di regolarità dette . Si tratta di una generalizzazione del metodo dei moltiplicatori di Lagrange, applicato a problemi in cui siano presenti anche vincoli di disuguaglianza. Tali considerazioni prendono il proprio nome da , , e e sono derivate, come caso particolare in cui siano soddisfatte le condizioni di qualificazione dei vincoli, dalle . Considerato il seguente problema di ottimizzazione non lineare: in cui è la funzione da minimizzare (detta anche funzione obiettivo), sono i vincoli monolateri e sono i vincoli bilateri. Le condizioni necessarie per questo generico problema di ottimizzazione vincolata furono inizialmente pubblicate, nella sua tesi di laurea magistrale, da , anche se furono conosciute solamente dopo l'articolo di e .. (it)
- Em otimização, as Condições de Karush-Kuhn-Tucker (também conhecidas como Condições de Kuhn-Tucker ou condições KKT) são condições de primeira ordem para que uma solução de um problema de programação não linear seja ótima, desde que valham condições chamadas de condições de qualificação ou, em inglês, constraint qualifications. Permitindo restrições de desigualdade, as condições KKT generalizam, na programação não linear, o método de multiplicadores de Lagrange, que permite somente restrições de igualdade. O sistema de equações e inequações correspondente às condições KKT em geral não é resolvido diretamente, exceto em alguns casos especiais onde uma solução pode ser obtida analiticamente. Nos demais casos, diversos algoritmos de otimização podem ser usados para resolver numericamente o sistema. As condições KKT foram originalmente nomeadas após Harold W. Kuhn e Albert W. Tucker, que primeiro publicaram essas condições em 1951. Porém, estudiosos posteriores descobriram que as condições necessárias para esse problema já haviam sido ditadas por em sua tese de mestrado em 1939. (pt)
- Karush–Kuhn–Tucker-villkor (eller KKT-villkor) är ett villkor som måste vara uppfyllt för att en punkt ska vara en till ett optimeringsproblem. Villkoret är nödvändigt men inte tillräckligt, det vill säga om villkoret är uppfyllt så behöver det inte betyda att punkten är optimum. Dock är det säkert att optimum uppfyller villkoret så en punkt som inte uppfyller villkoret kan inte vara optimum. (sv)
- В теории оптимизации условия Каруша — Куна — Таккера (англ. Karush — Kuhn — Tucker conditions, KKT) — необходимые условия решения задачи нелинейного программирования. Чтобы решение было оптимальным, должны быть выполнены некоторые условия регулярности. Метод является обобщением метода множителей Лагранжа. В отличие от него, ограничения, накладываемые на переменные, представляют собой не уравнения, а неравенства. (ru)
- Умови Каруша — Куна — Такера — необхідні умови оптимальності розв'язку математичної задачі нелінійного програмування при виконанні деяких умов регулярності. Названі на честь авторів: Вільяма Каруша, і . Нехай маємо наступну задачу оптимізації: при виконанні умовде — функція, що мінімізується, — функції обмежень-нерівностей і — функції обмежень-рівностей. (uk)
- 在數學中，卡鲁什-库恩-塔克条件（英文原名：Karush-Kuhn-Tucker Conditions，常見別名：Kuhn-Tucker，KKT條件，Karush-Kuhn-Tucker最優化條件，Karush-Kuhn-Tucker條件，Kuhn-Tucker最優化條件，Kuhn-Tucker條件）是在满足一些有规则的条件下，一個非線性規劃（Nonlinear Programming）問題能有最優化解法的一個必要條件。這是一個使用广义拉格朗日函数的结果。 考慮以下非線式最優化問題： 是需要最小化的函數，是不等式約束，是等式約束，和分別為不等式約束和等式約束的數量。 不等式約束問題的必要和充分條件初見於的硕士論文，之後在一份由W.库恩（Harold W. Kuhn）及塔克（Albert W. Tucker）撰寫的研究生論文出現後受到重視。 (zh)
|
| rdfs:comment
|
- En programació no lineal les condicions de Karush-Kuhn-Tucker (també anomenades condicions de KKT, o condicions Kuhn-Tucker) són condicions que ha de complir un punt que sigui solució d'un problema de la forma: on on On, si definim i : Es tracta d'una generalització del Mètode dels multiplicadors de Lagrange. (ca)
- Die Karush-Kuhn-Tucker-Bedingungen sind ein notwendiges Optimalitätskriterium erster Ordnung in der nichtlinearen Optimierung. Sie sind die Verallgemeinerung der notwendigen Bedingung von Optimierungsproblemen ohne Nebenbedingungen und der Lagrange-Multiplikatoren von Optimierungsproblemen unter Gleichungsnebenbedingungen. Sie wurden zum ersten Mal 1939 in der allerdings unveröffentlichten Master-Arbeit von William Karush aufgeführt. Bekannter wurden diese jedoch erst 1951 nach einem Konferenz-Paper von Harold W. Kuhn und Albert W. Tucker. (de)
- Las condiciones de Karush-Kuhn-Tucker (también conocidas como las condiciones KKT o Kuhn-Tucker) son requerimientos necesarios y suficientes para que la solución de un problema de programación matemática sea óptima. Es una generalización del método de los multiplicadores de Lagrange. (es)
- En mathématiques, les conditions de Karush-Kuhn-Tucker ou anciennement conditions de Kuhn-Tucker sont une généralisation des multiplicateurs de Lagrange qui permettent de résoudre des problèmes d'optimisation sous contraintes non linéaires d'inégalités. Soit , une fonction appelée fonction objectif, et des fonctions , , appelées contraintes. On suppose que et les sont de classe C1. Le problème à résoudre est le suivant : Trouver qui maximise sous les contraintes pour tout . (fr)
- カルーシュ・クーン・タッカー条件（英: Karush-Kuhn-Tucker condition）あるいはKKT条件とは、非線形計画において一階導関数が満たすべき最適条件を指す。ラグランジュの未定乗数法が等式制約のみを扱うのに対して、KKT条件を用いた解法は不等式制約も扱うことができる。KKT条件に対応する連立方程式は、解析的に閉形式解法が導かれる特殊な場合を除いては直接的には解かない。すでにKKT条件の連立方程式を数値的に解く方法は数多く確立されており、それらを用いて解くのが一般的である。KKT条件は線形計画法における主双対内点法などの解法において、重要な役割を持つ。 (ja)
- 카루시-쿤-터커 조건(Karush–Kuhn–Tucker conditions) 또는 KKT 조건은 (William Karush), (Harold W. Kuhn), (Albert W. Tucker)가 만든 최적화의 조건으로 라그랑주 승수법을 부등식을 가진 경우로 일반화한 것이다. (ko)
- Karush–Kuhn–Tucker-villkor (eller KKT-villkor) är ett villkor som måste vara uppfyllt för att en punkt ska vara en till ett optimeringsproblem. Villkoret är nödvändigt men inte tillräckligt, det vill säga om villkoret är uppfyllt så behöver det inte betyda att punkten är optimum. Dock är det säkert att optimum uppfyller villkoret så en punkt som inte uppfyller villkoret kan inte vara optimum. (sv)
- В теории оптимизации условия Каруша — Куна — Таккера (англ. Karush — Kuhn — Tucker conditions, KKT) — необходимые условия решения задачи нелинейного программирования. Чтобы решение было оптимальным, должны быть выполнены некоторые условия регулярности. Метод является обобщением метода множителей Лагранжа. В отличие от него, ограничения, накладываемые на переменные, представляют собой не уравнения, а неравенства. (ru)
- Умови Каруша — Куна — Такера — необхідні умови оптимальності розв'язку математичної задачі нелінійного програмування при виконанні деяких умов регулярності. Названі на честь авторів: Вільяма Каруша, і . Нехай маємо наступну задачу оптимізації: при виконанні умовде — функція, що мінімізується, — функції обмежень-нерівностей і — функції обмежень-рівностей. (uk)
- 在數學中，卡鲁什-库恩-塔克条件（英文原名：Karush-Kuhn-Tucker Conditions，常見別名：Kuhn-Tucker，KKT條件，Karush-Kuhn-Tucker最優化條件，Karush-Kuhn-Tucker條件，Kuhn-Tucker最優化條件，Kuhn-Tucker條件）是在满足一些有规则的条件下，一個非線性規劃（Nonlinear Programming）問題能有最優化解法的一個必要條件。這是一個使用广义拉格朗日函数的结果。 考慮以下非線式最優化問題： 是需要最小化的函數，是不等式約束，是等式約束，和分別為不等式約束和等式約束的數量。 不等式約束問題的必要和充分條件初見於的硕士論文，之後在一份由W.库恩（Harold W. Kuhn）及塔克（Albert W. Tucker）撰寫的研究生論文出現後受到重視。 (zh)
- في الإستمثال الرياضي، تعتبر شروط كاروش كوهن تاكر (KKT)، المعروفة أيضا باسم شروط كوهن تاكر، هي اختبارات مشتقة أولى (تسمى أحيانا الشروط الضرورية من الدرجة الأولى) لإيجاد حل في البرمجة غير الخطية يكون هو الأمثل، شريطة استيفاء بعض شروط الانتظام والسماح بقيود عدم المساواة المفروضة على دالة الهدف، فإن نهج KKT في البرمجة غير الخطية يعمم طريقة مضاعفات لاجرانج التي لا تسمح في الأصل إلا بقيود المساواة. على غرار نهج لاجرانج، تتم إعادة صياغة مشكلة إيجاد القيمة العظمى المقيدة (التصغير) كدالة لاجرانج التي تكون نقطتها المثلى هي نقطة السرج تلعب هذه الظروف دورا مهما جدا في نظرية الإستمثال المقيدة وتطوير الخوارزمية. للحصول على مشكلة إستمثال: (ar)
- In mathematical optimization, the Karush–Kuhn–Tucker (KKT) conditions, also known as the Kuhn–Tucker conditions, are first derivative tests (sometimes called first-order necessary conditions) for a solution in nonlinear programming to be optimal, provided that some are satisfied. The KKT conditions were originally named after Harold W. Kuhn and Albert W. Tucker, who first published the conditions in 1951. Later scholars discovered that the necessary conditions for this problem had been stated by William Karush in his master's thesis in 1939. (en)
- In matematica, le condizioni di Karush–Kuhn–Tucker (anche conosciute come condizioni di Kuhn-Tucker o condizioni KKT) sono condizioni necessarie per la soluzione di un problema di programmazione non lineare in cui i vincoli soddisfino una delle condizioni di regolarità dette . Si tratta di una generalizzazione del metodo dei moltiplicatori di Lagrange, applicato a problemi in cui siano presenti anche vincoli di disuguaglianza. Tali considerazioni prendono il proprio nome da , , e e sono derivate, come caso particolare in cui siano soddisfatte le condizioni di qualificazione dei vincoli, dalle . (it)
- Em otimização, as Condições de Karush-Kuhn-Tucker (também conhecidas como Condições de Kuhn-Tucker ou condições KKT) são condições de primeira ordem para que uma solução de um problema de programação não linear seja ótima, desde que valham condições chamadas de condições de qualificação ou, em inglês, constraint qualifications. Permitindo restrições de desigualdade, as condições KKT generalizam, na programação não linear, o método de multiplicadores de Lagrange, que permite somente restrições de igualdade. O sistema de equações e inequações correspondente às condições KKT em geral não é resolvido diretamente, exceto em alguns casos especiais onde uma solução pode ser obtida analiticamente. Nos demais casos, diversos algoritmos de otimização podem ser usados para resolver numericamente o si (pt)
|
