非线性规划中的序列内点仿射尺度法（Sequential Interior-Point Affine Scaling Method）基础题

字数 2482 2025-12-20 22:51:42

非线性规划中的序列内点仿射尺度法（Sequential Interior-Point Affine Scaling Method）基础题

1. 题目描述
考虑一个非线性规划问题：
minimize f(x)
subject to Ax = b, x ≥ 0
其中 f: ℝⁿ → ℝ 是连续可微函数，A ∈ ℝ^(m×n) 是行满秩矩阵，b ∈ ℝ^m，且假设严格内点存在（即存在 x⁰ > 0 满足 Ax⁰ = b）。
本题要求：设计一种“序列内点仿射尺度法”求解该问题，并详细解释其迭代步骤、仿射尺度变换的原理、步长选择策略，以及算法收敛的条件。

2. 解题过程

步骤1：理解问题结构
该问题具有线性等式约束与变量非负约束。内点法的核心思想是让迭代点始终保持在可行域内部（x > 0），并通过障碍函数或仿射尺度变换逐步逼近边界上的最优解。
序列内点法是指：在每一步求解一个近似子问题（例如线性化或二次化目标函数），并利用仿射尺度变换将非负约束转化为易于处理的形式。

步骤2：构造近似子问题
在当前迭代点 x^k > 0（且满足 Ax^k = b），将目标函数 f(x) 在 x^k 处作一阶泰勒展开：
f(x) ≈ f(x^k) + ∇f(x^k)ᵀ (x − x^k)
忽略常数项，得到线性近似子问题：
minimize ∇f(x^k)ᵀ d
subject to A(x^k + d) = b, x^k + d ≥ 0
令 d 为搜索方向，将约束改写为：
Ad = 0, d ≥ −x^k
注意 d ≥ −x^k 是 bounds 约束，不易直接求解。

步骤3：引入仿射尺度变换
定义对角矩阵 D_k = diag(x^k₁, x^k₂, …, x^kₙ)。作变量代换：
y = D_k⁻¹ d  ⇔ d = D_k y
则 d ≥ −x^k 等价于 D_k y ≥ −x^k，即 y ≥ −1（分量形式）。
同时，Ad = 0 变为 A D_k y = 0。
子问题转化为关于 y 的线性规划：
minimize [∇f(x^k)ᵀ D_k] y
subject to A D_k y = 0, y ≥ −1

步骤4：求解变换后的子问题
记 c_k = D_k ∇f(x^k)，Ā_k = A D_k。
子问题是：min c_kᵀ y, s.t. Ā_k y = 0, y ≥ −1。
这是一个带简单 bounds 的线性规划，其解可通过投影到零空间得到。
设 P_k = I − Ā_kᵀ (Ā_k Ā_kᵀ)⁻¹ Ā_k 为投影到 N(Ā_k) 的矩阵。
若 P_k c_k = 0，则当前点已是子问题的稳定点（一阶必要条件）；否则，可行下降方向为
y_k = −P_k c_k / ‖P_k c_k‖（单位范数方向，也可取其他缩放）。
注意需保证 y_k ≥ −1 以不违反 bounds。由于 y_k 来自零空间投影，通常不会全部分量为负，但若某个分量接近 −1，需进行截断或调整。

步骤5：回代得到原始空间的搜索方向
d_k = D_k y_k。
由于 y_k 满足 Ā_k y_k = 0，故 A d_k = 0，即等式约束自动保持。
又因 y_k ≥ −1，有 d_k ≥ −x^k，从而 x^k + d_k ≥ 0。

步骤6：步长选择与迭代更新
为使迭代点严格内点（x > 0），取步长 α_k ∈ (0,1]，使得
x^{k+1} = x^k + α_k d_k > 0。
可计算最大允许步长 α_max = min{ −x^k_i / d_k_i | d_k_i < 0 }（若 d_k ≥ 0 则 α_max = ∞），然后选 α_k = τα_max，其中 τ ∈ (0,1) 是安全系数（如 0.995）。
同时，可辅以目标函数下降条件（如 Armijo 线搜索）确定 α_k。

更新迭代点：x^{k+1} = x^k + α_k d_k，显然 Ax^{k+1} = b 且 x^{k+1} > 0。

步骤7：收敛判断
计算一阶最优性条件的度量。对原问题，KKT 条件为：
∇f(x) + Aᵀλ − ν = 0, Ax = b, x ≥ 0, ν ≥ 0, ν_i x_i = 0。
在每一步可估计 ν = −∇f(x) − Aᵀλ，其中 λ 由最小二乘解 λ = −(A Aᵀ)⁻¹ A ∇f(x) 给出。
定义残差：
η_k = max{ ‖∇f(x^k) + Aᵀλ‖_∞, ‖Ax^k − b‖, |min(x^k, ν)| }
当 η_k < ε（给定精度）时停止。

步骤8：算法总结

初始化：选严格可行点 x⁰ > 0，A x⁰ = b，设 k = 0。
计算梯度 ∇f(x^k) 和对角阵 D_k = diag(x^k)。
构造变换后的问题：c_k = D_k ∇f(x^k)，Ā_k = A D_k。
计算投影矩阵 P_k 及方向 y_k = −P_k c_k / ‖P_k c_k‖（需检查 y_k ≥ −1，否则截断）。
回代：d_k = D_k y_k。
计算最大步长 α_max 并选择 α_k（如 τ·α_max 或线搜索步长）。
更新：x^{k+1} = x^k + α_k d_k。
若满足收敛条件则停止，否则 k ← k+1 并返回步骤2。

3. 关键点说明

仿射尺度变换 D_k 将非负约束转化为 y ≥ −1，使得子问题容易求解。
该方法属于序列线性规划（SLP）与内点法的结合，每步求解一个线性规划子问题。
收敛性要求 f 梯度 Lipschitz 连续，且迭代点序列有界，通常需加入二阶校正或信赖域技术以增强稳定性。
本方法适合中等规模、目标函数非线性但约束为线性的问题，是经典内点法的一种简化变体。

非线性规划中的序列内点仿射尺度法（Sequential Interior-Point Affine Scaling Method）基础题 1. 题目描述考虑一个非线性规划问题： minimize f(x) subject to Ax = b, x ≥ 0 其中 f: ℝⁿ → ℝ 是连续可微函数，A ∈ ℝ^(m×n) 是行满秩矩阵，b ∈ ℝ^m，且假设严格内点存在（即存在 x⁰ > 0 满足 Ax⁰ = b）。本题要求：设计一种“序列内点仿射尺度法”求解该问题，并详细解释其迭代步骤、仿射尺度变换的原理、步长选择策略，以及算法收敛的条件。 2. 解题过程步骤1：理解问题结构该问题具有线性等式约束与变量非负约束。内点法的核心思想是让迭代点始终保持在可行域内部（x > 0），并通过障碍函数或仿射尺度变换逐步逼近边界上的最优解。序列内点法是指：在每一步求解一个近似子问题（例如线性化或二次化目标函数），并利用仿射尺度变换将非负约束转化为易于处理的形式。步骤2：构造近似子问题在当前迭代点 x^k > 0（且满足 Ax^k = b），将目标函数 f(x) 在 x^k 处作一阶泰勒展开： f(x) ≈ f(x^k) + ∇f(x^k)ᵀ (x − x^k) 忽略常数项，得到线性近似子问题： minimize ∇f(x^k)ᵀ d subject to A(x^k + d) = b, x^k + d ≥ 0 令 d 为搜索方向，将约束改写为： Ad = 0, d ≥ −x^k 注意 d ≥ −x^k 是 bounds 约束，不易直接求解。步骤3：引入仿射尺度变换定义对角矩阵 D_ k = diag(x^k₁, x^k₂, …, x^kₙ)。作变量代换： y = D_ k⁻¹ d  ⇔ d = D_ k y 则 d ≥ −x^k 等价于 D_ k y ≥ −x^k，即 y ≥ −1（分量形式）。同时，Ad = 0 变为 A D_ k y = 0。子问题转化为关于 y 的线性规划： minimize [ ∇f(x^k)ᵀ D_ k ] y subject to A D_ k y = 0, y ≥ −1 步骤4：求解变换后的子问题记 c_ k = D_ k ∇f(x^k)，Ā_ k = A D_ k。子问题是：min c_ kᵀ y, s.t. Ā_ k y = 0, y ≥ −1。这是一个带简单 bounds 的线性规划，其解可通过投影到零空间得到。设 P_ k = I − Ā_ kᵀ (Ā_ k Ā_ kᵀ)⁻¹ Ā_ k 为投影到 N(Ā_ k) 的矩阵。若 P_ k c_ k = 0，则当前点已是子问题的稳定点（一阶必要条件）；否则，可行下降方向为 y_ k = −P_ k c_ k / ‖P_ k c_ k‖（单位范数方向，也可取其他缩放）。注意需保证 y_ k ≥ −1 以不违反 bounds。由于 y_ k 来自零空间投影，通常不会全部分量为负，但若某个分量接近 −1，需进行截断或调整。步骤5：回代得到原始空间的搜索方向 d_ k = D_ k y_ k。由于 y_ k 满足 Ā_ k y_ k = 0，故 A d_ k = 0，即等式约束自动保持。又因 y_ k ≥ −1，有 d_ k ≥ −x^k，从而 x^k + d_ k ≥ 0。步骤6：步长选择与迭代更新为使迭代点严格内点（x > 0），取步长 α_ k ∈ (0,1 ]，使得 x^{k+1} = x^k + α_ k d_ k > 0。可计算最大允许步长 α_ max = min{ −x^k_ i / d_ k_ i | d_ k_ i < 0 }（若 d_ k ≥ 0 则 α_ max = ∞），然后选 α_ k = τα_ max，其中 τ ∈ (0,1) 是安全系数（如 0.995）。同时，可辅以目标函数下降条件（如 Armijo 线搜索）确定 α_ k。更新迭代点：x^{k+1} = x^k + α_ k d_ k，显然 Ax^{k+1} = b 且 x^{k+1} > 0。步骤7：收敛判断计算一阶最优性条件的度量。对原问题，KKT 条件为： ∇f(x) + Aᵀλ − ν = 0, Ax = b, x ≥ 0, ν ≥ 0, ν_ i x_ i = 0。在每一步可估计 ν = −∇f(x) − Aᵀλ，其中 λ 由最小二乘解 λ = −(A Aᵀ)⁻¹ A ∇f(x) 给出。定义残差： η_ k = max{ ‖∇f(x^k) + Aᵀλ‖_ ∞, ‖Ax^k − b‖, |min(x^k, ν)| } 当 η_ k  < ε（给定精度）时停止。步骤8：算法总结初始化：选严格可行点 x⁰ > 0，A x⁰ = b，设 k = 0。计算梯度 ∇f(x^k) 和对角阵 D_ k = diag(x^k)。构造变换后的问题：c_ k = D_ k ∇f(x^k)，Ā_ k = A D_ k。计算投影矩阵 P_ k 及方向 y_ k = −P_ k c_ k / ‖P_ k c_ k‖（需检查 y_ k ≥ −1，否则截断）。回代：d_ k = D_ k y_ k。计算最大步长 α_ max 并选择 α_ k（如 τ·α_ max 或线搜索步长）。更新：x^{k+1} = x^k + α_ k d_ k。若满足收敛条件则停止，否则 k ← k+1 并返回步骤2。 3. 关键点说明仿射尺度变换 D_ k 将非负约束转化为 y ≥ −1，使得子问题容易求解。该方法属于序列线性规划（SLP）与内点法的结合，每步求解一个线性规划子问题。收敛性要求 f 梯度 Lipschitz 连续，且迭代点序列有界，通常需加入二阶校正或信赖域技术以增强稳定性。本方法适合中等规模、目标函数非线性但约束为线性的问题，是经典内点法的一种简化变体。