| dbo:abstract
|
- In optimization problems in applied mathematics, the duality gap is the difference between the primal and dual solutions. If is the optimal dual value and is the optimal primal value then the duality gap is equal to . This value is always greater than or equal to 0 (for minimization problems). The duality gap is zero if and only if strong duality holds. Otherwise the gap is strictly positive and weak duality holds. In general given two dual pairs separated locally convex spaces and . Then given the function , we can define the primal problem by If there are constraint conditions, these can be built into the function by letting where is the indicator function. Then let be a perturbation function such that . The duality gap is the difference given by where is the convex conjugate in both variables. In computational optimization, another "duality gap" is often reported, which is the difference in value between any dual solution and the value of a feasible but suboptimal iterate for the primal problem. This alternative "duality gap" quantifies the discrepancy between the value of a current feasible but suboptimal iterate for the primal problem and the value of the dual problem; the value of the dual problem is, under regularity conditions, equal to the value of the of the primal problem: The convex relaxation is the problem arising replacing a non-convex feasible set with its closed convex hull and with replacing a non-convex function with its convex closure, that is the function that has the epigraph that is the closed convex hull of the original primal objective function. (en)
- Розри́в двої́стості — це різниця між прямим і двоїстим розв'язками. Якщо — оптимальне значення двоїстої задачі, а — оптимальне значення прямої задачі, то розрив двоїстості дорівнює . Це значення завжди більше або дорівнює нулю (для задач мінімізації). Розрив двоїстості дорівнює нулю тоді й лише тоді, коли має місце сильна двоїстість. В іншому випадку розрив строго додатний, і має місце слабка двоїстість. (uk)
- 對偶間隙是應用數學中最佳化問題的詞語，是指原始解和對偶解之間的差距。若是對偶問題解對應的值，而是原始問題最佳解對應的值，則對偶間隙為。針對最小化的最佳化問題，對偶間隙恆大於等於零。對偶間隙為零若且唯若的條件成立，不然對偶間隙為嚴格正值，此時即為。 一般而言，給定二個的分隔 及。假定函數，可以定義原始問題為 若有限制條件，可以整合到函數中，方式是令，其中是示性函数。則令是使得。則對偶間隙即為以下的差值 其中為二個變數的凸共轭。 在計算最优化中，會提到另一種「對偶間隙」，是對偶解以及原始問題次最佳但是可行解之間的差距。這種對偶間隙反映了目前可行，但可能只是次最佳的迭代解，和對偶問題解之間的差距。對偶問題解是指規律性條件下，等於原始問題凸鬆弛（convex relaxation）下的解。凸鬆弛是指將問題中非凸可行集合改為閉凸包，將非凸函數改為凸的閉集（函數的是原始目標函數的閉凸包）。 (zh)
- Разрыв двойственности — это разница между прямым и двойственным решениями. Если является оптимальным значением двойственной задачи, а является оптимальным значением прямой задачи, то разрыв двойственности равен . Это значение всегда больше либо равно нулю (для задач минимизации). Разрыв двойственности равен нулю тогда и только тогда, когда имеет место сильная двойственность. В противном случае разрыв строго положителен, и имеет место слабая двойственность. (ru)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 7159 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dct:subject
| |
| rdfs:comment
|
- Розри́в двої́стості — це різниця між прямим і двоїстим розв'язками. Якщо — оптимальне значення двоїстої задачі, а — оптимальне значення прямої задачі, то розрив двоїстості дорівнює . Це значення завжди більше або дорівнює нулю (для задач мінімізації). Розрив двоїстості дорівнює нулю тоді й лише тоді, коли має місце сильна двоїстість. В іншому випадку розрив строго додатний, і має місце слабка двоїстість. (uk)
- 對偶間隙是應用數學中最佳化問題的詞語，是指原始解和對偶解之間的差距。若是對偶問題解對應的值，而是原始問題最佳解對應的值，則對偶間隙為。針對最小化的最佳化問題，對偶間隙恆大於等於零。對偶間隙為零若且唯若的條件成立，不然對偶間隙為嚴格正值，此時即為。 一般而言，給定二個的分隔 及。假定函數，可以定義原始問題為 若有限制條件，可以整合到函數中，方式是令，其中是示性函数。則令是使得。則對偶間隙即為以下的差值 其中為二個變數的凸共轭。 在計算最优化中，會提到另一種「對偶間隙」，是對偶解以及原始問題次最佳但是可行解之間的差距。這種對偶間隙反映了目前可行，但可能只是次最佳的迭代解，和對偶問題解之間的差距。對偶問題解是指規律性條件下，等於原始問題凸鬆弛（convex relaxation）下的解。凸鬆弛是指將問題中非凸可行集合改為閉凸包，將非凸函數改為凸的閉集（函數的是原始目標函數的閉凸包）。 (zh)
- Разрыв двойственности — это разница между прямым и двойственным решениями. Если является оптимальным значением двойственной задачи, а является оптимальным значением прямой задачи, то разрыв двойственности равен . Это значение всегда больше либо равно нулю (для задач минимизации). Разрыв двойственности равен нулю тогда и только тогда, когда имеет место сильная двойственность. В противном случае разрыв строго положителен, и имеет место слабая двойственность. (ru)
- In optimization problems in applied mathematics, the duality gap is the difference between the primal and dual solutions. If is the optimal dual value and is the optimal primal value then the duality gap is equal to . This value is always greater than or equal to 0 (for minimization problems). The duality gap is zero if and only if strong duality holds. Otherwise the gap is strictly positive and weak duality holds. In general given two dual pairs separated locally convex spaces and . Then given the function , we can define the primal problem by (en)
|
| rdfs:label
|
- Dualitätslücke (de)
- Duality gap (en)
- Разрыв двойственности (ru)
- Розрив двоїстості (uk)
- 對偶間隙 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
