KKT背景
KKT条件得名于三位数学家：Karush（1939）、Kuhn（1951）和Tucker（1952），他们分别提出了类似的优化条件，并在后续研究中被统一和扩展。KKT条件是一种用于判断约束优化问题全局最优解的必要条件（在某些情况下也是充分条件），它通过引入拉格朗日乘子法和对偶性，将原问题转化为更易求解的形式。
KKT优点
- 广泛适用性：KKT条件可以处理包括线性、非线性、等式和不等式约束在内的各种类型的优化问题，具有广泛的应用范围。
- 理论严谨性：KKT条件为判断优化问题的全局最优解提供了坚实的理论基础，是优化领域中的核心概念之一。
- 对偶性应用：KKT条件与对偶性紧密相连，通过对偶问题可以求得原问题的近似解或下界，为求解大规模优化问题提供了一种有效的途径。
- 求解方法多样：基于KKT条件的求解方法多样，包括梯度下降法、牛顿法、内点法等，可以根据具体问题的特点选择合适的求解方法。
KKT缺点
- 条件充分性限制：虽然KKT条件是判断全局最优解的必要条件，但在某些情况下（如非凸优化问题）并不能保证充分性。即，满足KKT条件的点不一定是全局最优解。
- 计算复杂性：对于复杂的优化问题，求解KKT条件可能涉及高维矩阵运算和复杂的迭代过程，计算量较大，对计算资源要求较高。
- 对初值敏感：某些基于KKT条件的求解算法对初值的选择较为敏感，不同的初值可能导致算法收敛到不同的局部最优解。
- 约束条件限制：KKT条件要求优化问题具有明确的约束条件，对于无约束或约束条件不明确的优化问题，KKT条件可能无法直接应用或需要额外的处理。
function Karush_Kuhn_Tucker(f_expr, A, b)
% 项目名称：KKT解线性约束
% 更新时间：2024/09/28
% 背景：KKT条件是用来解决带有约束的非线性规划最优解问题的重要工具，它最初由Kuhn和Tucker在1951年独立发表，Karush在1939年的文章中已经有过这个定理的表述。本方法处理的是只含有线性约束的一般优化问题。
% 作者：月白风清江有声 % 假设 A 是一个矩阵，b 是一个向量，f_expr 是一个关于 x 的符号表达式 numRows = size(A, 1); numCols = size(A, 2); syms x [numCols, 1] real; % 假设 x 是一个列向量，与 A 的列数相同，变量默认就是实数（real） syms lambda [numRows, 1] real; % lambda 是一个与 A 的行数相同的列向量 % 构建拉格朗日函数 diff_f_lgr_lambda = A * x - b; f_lgr = f_expr + sum(lambda .* diff_f_lgr_lambda); % 对 x 和 lambda 求导 diff_f_lgr_x = gradient(f_lgr, x); % 对于 lambda，由于是线性约束，其导数已经是约束本身，但在此处不需要显式求导 % 构建方程组 eqns = [diff_f_lgr_x; diff_f_lgr_lambda]; eqns = eqns == 0; %生成一个逻辑数组（或逻辑表达式数组），其中每个元素表示原始eqns中对应元素是否等于0。% 求解方程组 sol = solve(eqns, [x; lambda]); disp(sol);%solve 函数返回一个结构体（struct）,包含变量名，所以不能依次.引用
end %{
syms x1 x2 x3;
f_expr = x1^2 + 2*x2^2 + x3^2 + x3 - 2*x1*x2;
A = [1, 1, 1; 2, -1, 1];
b = [4; 2];
Karush_Kuhn_Tucker(f_expr, A, b);
%}