Primal-Dual

Definition 定义

primal-dual（原-对偶）指在优化与运筹学中同时处理“原问题（primal）”与“对偶问题（dual）”的一类思想、方法或算法框架。常见于线性规划、凸优化、网络流与组合优化中，用于利用对偶性来设计更高效或更易分析的算法。（也常写作 primal–dual 或 primal dual。）

Pronunciation 发音（IPA）

/ˈpraɪməl ˈdjuːəl/（也常见 /ˈpraɪməl ˈduːəl/）

Examples 例句

We solved the linear program using a primal-dual method.
我们用原-对偶方法求解了这个线性规划问题。

Primal-dual algorithms often update the primal variables and Lagrange multipliers together to enforce constraints while improving the objective.
原-对偶算法常常同时更新原变量与拉格朗日乘子，在改进目标值的同时逐步满足约束。

Etymology 词源

primal 源自拉丁语 primus（“第一、最初的”），在优化里引申为“原始形式的（原问题）”；dual 源自拉丁语 dualis（“双的、成对的”），在数学中指“对偶的”。二者组合成 primal-dual，强调“原问题—对偶问题”成对出现、相互约束与相互提供界（bound）的关系。

Related Words 相关词汇

• Duality
• Lagrangian
• KKT
• Saddle-Point
• Subgradient
• Interior-Point
• Linear-Programming
• Convex-Optimization
• Augmented-Lagrangian
• Min-Cost-Flow

Literary Works 文献与著作中的用例

• Convex Optimization（Boyd & Vandenberghe）：讨论对偶性与相关算法思想，常涉及原-对偶视角。
• Combinatorial Optimization: Polyhedra and Efficiency（Alexander Schrijver）：大量使用原问题/对偶问题与原-对偶技术。
• Network Flows: Theory, Algorithms, and Applications（Ahuja, Magnanti & Orlin）：网络流与费用流中常出现原-对偶方法框架。
• Primal-Dual Interior-Point Methods（Wright）：以内点法为核心系统介绍原-对偶算法。