线性规划中,若原始可行解 x 与对偶可行解 y 满足互补松弛条件,凭什么断言两者同时达到各自的最优值?这一条件又是怎样被算法用作可快速核验的最优性证书的?
In linear programming, when primal-feasible x and dual-feasible y satisfy complementary slackness, what licenses the claim that both attain their optima simultaneously, and how do algorithms exploit the condition as a quickly verifiable optimality certificate?
弱对偶性给出单向夹逼:对一切原始可行的 x 与对偶可行的 y 都有 c^T x ≤ b^T y,因此只要找出一组使等号成立的解,上下界便同时被锁死。互补松弛要求每个不起作用的约束所对应的对偶变量为零,这使差值 Σ y_i (b_i − a_i x) 逐项归零,对偶间隙被强制闭合。既然任何一方都无法在不破坏可行性的前提下越过这条界,该解对即为最优;原始单纯形法的停机判据、内点法的中心路径极限以及整数规划中对偶间隙的分析,全都依赖这一可即时核验的证书。
Weak duality supplies a one-way squeeze: c^T x ≤ b^T y holds for every primal-feasible x and dual-feasible y, so exhibiting any pair that attains equality pins both bounds down at once. Complementary slackness demands that the dual variable attached to every non-binding constraint vanish, which kills the gap term Σ y_i (b_i − a_i x) summand by summand and forces the duality gap closed. Since neither side can cross this bound without forfeiting feasibility, the pair is optimal; the simplex stopping rule, the central-path limit of interior-point methods, and duality-gap analyses in integer programming all lean on this instantly checkable certificate.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 来源待核验 · Source pending review
来源 · Source
出处备注：此条未指向带版次的可引用著作（通识性内容、机构文件或未展开的英文书名），本库不提供独立书目出处；如需精确引用，需由编辑补全具体篇目与版次。
D. Gale, H. W. Kuhn, A. W. Tucker, Linear Programming and the Theory of Games, Econometrica, vol. 19, no. 1, pp. 54-65, 1951
D. Gale, H. W. Kuhn, A. W. Tucker, Linear Programming and the Theory of Games, Econometrica 19 (1951) 54-65
#线性规划 #对偶理论
在约束优化问题中,为什么最优点处目标函数的梯度必须与约束曲面的法线方向平行?
In a constrained optimization problem, why must the gradient of the objective be parallel to the normal direction of the constraint surface at an optimum?
因为可行点只能沿约束曲面移动。若目标函数的梯度在该点还带有沿曲面切向的分量,沿这个切向挪一小步,目标值就会继续下降(或上升),说明它并不是极值点;只有当切向分量消失,即梯度 ∇f 与约束的法向 ∇g 平行时,才可能是驻点。拉格朗日乘子法正是把这个平行条件写成 ∇f=λ∇g,其中乘子 λ 还表示约束每放松一单位时最优值的变化量,经济学里称为影子价格。
Feasible points can move only along the constraint surface. If the objective gradient keeps a component tangent to that surface at the candidate point, a small slide in the tangential direction still lowers (or raises) the objective, so the point cannot be an extremum. An extremum requires the tangential component to vanish, i.e., the gradient grad f parallel to the constraint normal grad g — precisely the Lagrange condition grad f = lambda * grad g. The multiplier lambda also measures how much the optimal value changes per unit of relaxed constraint, the economist's shadow price.
难度 专业 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-10-04 · 2 条独立证据
来源 · Source
J. Nocedal 与 S. J. Wright《Numerical Optimization》第2版,Springer,2006
J. Nocedal & S. J. Wright, Numerical Optimization, 2nd ed., Springer, 2006
独立核验依据 · Independent verification: 核验依据 1 ISBN 9780387987934 (1999) · 核验依据 2 ISBN 9780387400655 (2006)
#最优化 #拉格朗日乘子 #影子价格
为什么‘局部最优’不一定是‘全局最优’？
Why is a 'local optimum' not necessarily the 'global optimum'?
在起伏的山地里，你站上最近的小山顶（局部最优）却未必是整座山脉的最高峰（全局最优）。很多优化算法容易被困在局部，需要随机重启或全局搜索。
In hilly terrain you may stand on the nearest small peak (local optimum) yet not the highest of the whole range (global). Many optimizers get stuck locally, needing random restarts or global search.
难度 进阶 · 适合 大众
CC BY 4.0 · 已核验 · Verified 2026-10-04 · 2 条独立证据
来源 · Source
J. Nocedal 与 S. J. Wright《Numerical Optimization》第2版,Springer,2006
J. Nocedal & S. J. Wright, Numerical Optimization, 2nd ed., Springer, 2006
独立核验依据 · Independent verification: 核验依据 1 ISBN 9780387987934 (1999) · 核验依据 2 ISBN 9780387400655 (2006)
#优化 #全局
拉格朗日对偶是什么？
What is Lagrange duality?
拉格朗日对偶为每个原问题构造一个“对偶问题”，其对偶目标给出原问题最优值的下界，且常可轻易求得。强对偶成立时两者相等，是 SVM 的理论核心。
Lagrange duality forms a dual problem whose value bounds the primal optimum from below; under strong duality they coincide—the theory behind SVMs.
难度 进阶 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-10-04
来源 · Source
《凸优化》Boyd 与 Vandenberghe
Convex Optimization by Boyd and Vandenberghe
独立核验依据 · Independent verification: 核验依据 1 ISBN 9780521833783 (2006)
#优化 #对偶
内点法是什么？
What is an interior-point method?
内点法从可行域内部出发，沿中心路径逼近最优解，能在多项式时间内求解线性与凸规划。相比单纯形法，它对超大规模问题更稳定高效。
Interior-point methods move inside the feasible region toward optimality in polynomial time; more stable than the simplex method for huge problems.
难度 进阶 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-10-04
来源 · Source
《凸优化》Boyd 与 Vandenberghe
Convex Optimization by Boyd and Vandenberghe
独立核验依据 · Independent verification: 核验依据 1 ISBN 9780521833783 (2006)
#优化 #内点法
凸优化是什么？
What is convex optimization?
凸优化在凸集上最小化凸函数；它的任何局部最优都是全局最优，因而高效可解。机器学习的大量训练问题都可写成凸优化（或近似凸）形式。
Convex optimization minimizes a convex function over a convex set; every local minimum is global, making it efficiently solvable and central to ML.
难度 进阶 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-10-04
来源 · Source
《凸优化》Boyd 与 Vandenberghe
Convex Optimization by Boyd and Vandenberghe
独立核验依据 · Independent verification: 核验依据 1 ISBN 9780521833783 (2006)
#优化 #凸优化
最优传输是什么？
What is optimal transport?
最优传输研究把一堆质量（如概率分布）以最小“搬运成本”移到另一堆的最优方式，对应蒙日-安培方程。它在图像对齐、生成模型（Wasserstein GAN）中很热。
Optimal transport finds the cheapest way to move one probability mass to another (Monge–Ampère); used in image alignment and Wasserstein GANs.
难度 进阶 · 适合 高中(15-18)
CC BY 4.0 · 来源待核验 · Source pending review
来源 · Source
出处备注：本题原挂出处与答案内容不符，已撤回；具体书目待补，暂不展示来源。
本题原挂出处与答案内容不符，已撤回；具体书目待补。
Previous citation withdrawn as unsupported for this answer; a specific source is pending.
#优化 #最优传输
单纯形法求解线性规划时,为什么只需要考察可行域的顶点?它在最坏情况下的效率如何?
Why does the simplex method for linear programming only need to inspect vertices of the feasible region, and how efficient is it in the worst case?
线性目标函数若在多面体可行域上取到最优,必有某个极点(顶点)同样最优:目标的等值面是超平面,只要当前点不是顶点,就能沿改善目标的方向继续滑行,直到撞上边界顶点。于是单纯形法从一个顶点出发,反复转移到使目标值不减的相邻顶点,直到无邻点可改进即宣告最优。Klee 与 Minty 构造的实例迫使它遍历指数多个顶点,但实际运行通常很快;椭球法与内点法补上了多项式时间的理论保证。
Whenever a linear objective attains an optimum over a polytope, some extreme point (vertex) is also optimal: level sets are hyperplanes, so from any non-vertex point you can keep sliding in an improving direction until you hit a boundary vertex. The simplex method exploits this by hopping from vertex to adjacent vertex, never letting the objective drop, and stops once no neighboring vertex improves it. Klee and Minty exhibited instances that force exponentially many vertices to be visited, yet the method runs fast in practice; the ellipsoid and interior-point methods supply the polynomial-time guarantees.
难度 进阶 · 适合 大众
CC BY 4.0 · 来源待核验 · Source pending review
来源 · Source
出处备注：此条未指向带版次的可引用著作（通识性内容、机构文件或未展开的英文书名），本库不提供独立书目出处；如需精确引用，需由编辑补全具体篇目与版次。
Dantzig, G. B.(1951). Maximization of a linear function of variables subject to linear inequalities, 载于 Koopmans (ed.), Activity Analysis of Production and Allocation, Wiley, pp.339-347;Klee & Minty (1972)
Dantzig, G. B. (1951). Maximization of a linear function of variables subject to linear inequalities, in Koopmans (ed.), Activity Analysis of Production and Allocation, Wiley, pp. 339-347; Klee, V. and Minty, G. J. (1972). How good is the simplex algorithm?, Inequalities III, Academic Press, pp. 159-175
独立核验依据 · Independent verification: 核验依据 1 OPENLIBRARY 标识 /works/OL9189205W：Activity Analysis of Pr · 核验依据 3 CROSSREF 标识 10.2307/1907816：Activity Analysis of Product
#运筹优化 #线性规划
机器学习训练时为什么总说「梯度下降」?沿着坡往下走就能找到最优吗?
Why does machine learning keep saying gradient descent — and does walking downhill always find the best spot?
梯度是函数上升最快的方向,取负号便是下降最陡的方向;参数沿负梯度小步移动并反复迭代,损失函数像滚下山坡的球逐渐落到谷底。学习率是步长:太大来回震荡甚至发散,太小磨蹭到天荒地老;动量法给球加惯性冲过小坑,Adam 算法则为每个参数自适应调步长。深层网络的损失面并非碗状而是高维崎岖地形,幸运的是实践发现大量鞍点与平坦极小值反而带来更好的泛化——所以「找不到全局最优」常常无伤大雅,这也是深度学习能work的隐秘原因之一。
The gradient points uphill fastest; step against it repeatedly and the loss rolls downhill like a ball seeking valleys. The learning rate is stride length: too large oscillates or diverges, too small crawls forever. Momentum adds inertia to roll past small dips; Adam tunes per-parameter strides adaptively. Deep-network loss surfaces are not bowls but rugged high-dimensional terrain — luckily practice finds abundant saddle points and flat minima that generalize well, so missing the global optimum usually costs little, one quiet reason deep learning works.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-10-04
来源 · Source
Goodfellow, I., Bengio, Y. & Courville, A.，《Deep Learning》，MIT Press，2016
Goodfellow, I., Bengio, Y. & Courville, A., Deep Learning, MIT Press, 2016
独立核验依据 · Independent verification: 核验依据 1 ISBN 978-0-262-03561-3 (MIT Press)
#梯度下降 #学习率 #优化器
旅行商问题（TSP）是什么？
What is the traveling salesman problem (TSP)?
TSP 要在访问每个城市一次后回到起点，使总路程最短。它是经典的 NP 难组合优化问题，近似算法与启发式（如分支定界）广泛用于物流调度。
TSP seeks the shortest tour visiting every city once; a classic NP-hard problem with algorithms widely used in logistics.
难度 入门 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-10-04
来源 · Source
Applegate、Bixby、Chvatal 与 Cook,《The Traveling Salesman Problem》,Princeton University Press,2006
D. L. Applegate et al., The Traveling Salesman Problem, Princeton University Press, 2006
独立核验依据 · Independent verification: 核验依据 1 ISBN 9780691129938 (2006)
#优化 #旅行商
当目标函数是凸函数时,为什么算法求得的局部最小值一定就是全局最小值?
When the objective function is convex, why is any local minimum found by an algorithm guaranteed to be a global minimum?
因为凸函数的图像处处向上弯,任意两点之间的弦都落在函数图形上方。假如某点只是局部最小而别处另有更低点,那么连结这两点的弦在中段必然低于局部点的取值,而弦的中段又可以无限接近该局部点,这与它是局部最小矛盾。所以局部最优就是全局最优,梯度下降等迭代法不会被困在伪最优解上,这正是线性回归、支持向量机等凸模型可靠好解的原因。
A convex function curves upward everywhere, so the chord joining any two of its points never dips below the function. If a point were merely a local minimum while a strictly lower value existed elsewhere, the chord to that better point would sit below the local value over its middle stretch, and those middle points lie arbitrarily close to the supposed minimum — contradiction. Hence local optimality implies global optimality, which is why descent methods solve convex models like linear regression and support vector machines reliably.
难度 入门 · 适合 大众
CC BY 4.0 · 已核验 · Verified 2026-10-04
来源 · Source
S. Boyd 与 L. Vandenberghe《Convex Optimization》,Cambridge University Press,2004
S. Boyd & L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004
独立核验依据 · Independent verification: 核验依据 1 ISBN 9780521833783 (2006)
#凸优化 #全局最优 #梯度下降
快递员一天要送一百个包裹,路线怎么排才不绕路?旅行商问题难在哪?
A courier delivers a hundred parcels daily — how to order stops without backtracking? Where does the traveling salesman difficulty hide?
难点在组合爆炸:10个城市的可能路线约18万条,100个城市的选择数超过可观测宇宙的原子总数。暴力枚举注定失败,于是运筹学兵分三路:精确算法(分支定界、动态规划)在小规模下保证最优;启发式(最近邻、2-opt局部改进)秒级给出可用解;现代求解器融合两者,已能对数万城市规模找到与最优解差距不到百分之一的路线。TSP 的价值远超快递——电路板钻孔、基因测序排序、天车调度都是它的变体,它也是 P 与 NP 问题的标志性成员。
Combinatorial explosion is the enemy: ten cities offer about 180,000 tours, while a hundred cities exceed the atom count of the observable universe. Brute force dies fast, so operations research splits forces — exact algorithms (branch-and-bound, dynamic programming) guarantee optimality at small scale; heuristics (nearest-neighbor, 2-opt local search) return usable routes in seconds; modern solvers blend both, closing within one percent of optimal for tens of thousands of stops. TSP matters far beyond couriers — PCB drilling, genome ordering, crane scheduling are variants, and it stars in the P versus NP question.
难度 入门 · 适合 大众
CC BY 4.0 · 已核验 · Verified 2026-10-04
来源 · Source
Applegate、Bixby、Chvatal 与 Cook,《The Traveling Salesman Problem》,Princeton University Press,2006
D. L. Applegate et al., The Traveling Salesman Problem, Princeton University Press, 2006
独立核验依据 · Independent verification: 核验依据 1 ISBN 9780691129938 (2006)
#旅行商问题 #组合优化 #启发式算法