序列内点反射信赖域混合算法基础题

字数 10735 2025-12-09 16:08:33

序列内点反射信赖域混合算法基础题

题目描述

考虑一个非线性规划问题：

\[\begin{aligned} \min_{x \in \mathbb{R}^n} \quad & f(x) \\ \text{s.t.} \quad & c_i(x) = 0, \quad i \in \mathcal{E}, \\ & c_i(x) \geq 0, \quad i \in \mathcal{I}. \end{aligned} \]

其中，目标函数 \(f: \mathbb{R}^n \to \mathbb{R}\) 和约束函数 \(c_i: \mathbb{R}^n \to \mathbb{R}\) 是二次连续可微的。内点反射信赖域混合算法结合了内点法、信赖域法和反射技术，用于处理带不等式约束的非线性优化问题。本题目要求你阐述该算法的基本框架和关键步骤，并应用于以下具体例子：

\[\begin{aligned} \min_{x_1, x_2} \quad & f(x) = (x_1 - 1)^2 + (x_2 - 2)^2 \\ \text{s.t.} \quad & x_1 + x_2 - 2 \geq 0, \\ & x_1 \geq 0, \quad x_2 \geq 0. \end{aligned} \]

从初始点 \(x^{(0)} = (0.5, 0.5)\) 开始，执行一次算法迭代（包括构造子问题、求解信赖域子问题、进行反射步骤以及更新内点参数和信赖域半径）。要求展示详细计算过程，包括梯度、Hessian矩阵、障碍函数、子问题构造、信赖域求解、反射条件和参数更新规则。

解题过程循序渐进讲解

第一步：算法基本思想理解

内点反射信赖域混合算法的核心思想是：

内点法处理不等式约束：通过引入障碍函数（如对数障碍函数）将不等式约束融入目标函数，形成一个无约束或仅含等式约束的子问题，并确保迭代点始终位于可行域内部（即严格满足不等式约束）。
信赖域法控制步长：在每一步迭代，在当前点附近用一个简化模型（通常是二次模型）近似原问题，并限制步长在一个信赖域内，以保证模型的可靠性。
反射技术加速收敛：当试探步长导致点接近或违反边界时，不直接拒绝，而是尝试将其“反射”回可行域内部，可能获得更大的可行步长，从而提高收敛速度。

这个混合策略旨在结合内点法的可行性保持、信赖域法的全局收敛性以及反射技术的边界处理效率。

第二步：构造障碍函数和拉格朗日函数

对于不等式约束 \(c_i(x) \geq 0\)，引入对数障碍函数。原问题转化为一系列障碍子问题：

\[\min_{x} \quad \phi_\mu(x) = f(x) - \mu \sum_{i \in \mathcal{I}} \ln(c_i(x)), \]

其中 \(\mu > 0\) 是障碍参数，随着迭代逐渐减小趋于0。等式约束可以通过拉格朗日乘子处理。定义增广拉格朗日函数：

\[\mathcal{L}(x, \lambda) = \phi_\mu(x) + \sum_{i \in \mathcal{E}} \lambda_i c_i(x), \]

其中 \(\lambda_i\) 是对应等式约束的拉格朗日乘子。在我们的例子中，没有等式约束（\(\mathcal{E} = \emptyset\)），只有一个不等式约束 \(c_1(x) = x_1 + x_2 - 2 \geq 0\) 和两个边界约束 \(x_1 \geq 0, x_2 \geq 0\)。通常，边界约束可以直接纳入障碍项。因此，障碍函数为：

\[\phi_\mu(x) = (x_1 - 1)^2 + (x_2 - 2)^2 - \mu \left[ \ln(x_1 + x_2 - 2) + \ln(x_1) + \ln(x_2) \right]. \]

注意：初始点 \(x^{(0)} = (0.5, 0.5)\) 需严格满足 \(x_1>0, x_2>0, x_1+x_2-2>0\)（即 \(0.5+0.5-2=-1<0\)）。实际上，这个点不满足约束 \(x_1+x_2-2 \geq 0\)。内点法要求严格内点，所以我们需要调整初始点。为了使算法可行，我们调整初始点为 \(x^{(0)} = (1.5, 1.0)\)，此时 \(x_1=1.5>0, x_2=1.0>0, x_1+x_2-2=0.5>0\)，是严格内点。这是内点法的常见要求。

第三步：计算当前点的梯度和Hessian矩阵

在点 \(x^{(0)} = (1.5, 1.0)\)，设定初始障碍参数 \(\mu = 0.1\)。

首先计算目标函数梯度：

\[\nabla f(x) = \begin{bmatrix} 2(x_1 - 1) \\ 2(x_2 - 2) \end{bmatrix} = \begin{bmatrix} 2(1.5-1) \\ 2(1.0-2) \end{bmatrix} = \begin{bmatrix} 1 \\ -2 \end{bmatrix}. \]

障碍项部分：记 \(g_1(x) = x_1 + x_2 - 2\), \(g_2(x) = x_1\), \(g_3(x) = x_2\)。

\[\nabla (-\ln(g_1)) = -\frac{1}{g_1} \nabla g_1 = -\frac{1}{x_1+x_2-2} \begin{bmatrix} 1 \\ 1 \end{bmatrix} = -\frac{1}{0.5} \begin{bmatrix} 1 \\ 1 \end{bmatrix} = \begin{bmatrix} -2 \\ -2 \end{bmatrix}. \]

\[ \nabla (-\ln(g_2)) = -\frac{1}{x_1} \begin{bmatrix} 1 \\ 0 \end{bmatrix} = -\frac{1}{1.5} \begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{bmatrix} -2/3 \\ 0 \end{bmatrix} \approx \begin{bmatrix} -0.6667 \\ 0 \end{bmatrix}. \]

\[ \nabla (-\ln(g_3)) = -\frac{1}{x_2} \begin{bmatrix} 0 \\ 1 \end{bmatrix} = -\frac{1}{1.0} \begin{bmatrix} 0 \\ 1 \end{bmatrix} = \begin{bmatrix} 0 \\ -1 \end{bmatrix}. \]

因此，障碍函数梯度：

\[\nabla \phi_\mu = \nabla f - \mu \left( \sum_{i=1}^3 \nabla (-\ln(g_i)) \right) = \begin{bmatrix} 1 \\ -2 \end{bmatrix} - 0.1 \left( \begin{bmatrix} -2 \\ -2 \end{bmatrix} + \begin{bmatrix} -2/3 \\ 0 \end{bmatrix} + \begin{bmatrix} 0 \\ -1 \end{bmatrix} \right) = \begin{bmatrix} 1 \\ -2 \end{bmatrix} - 0.1 \begin{bmatrix} -8/3 \\ -3 \end{bmatrix}. \]

计算：

\[-0.1 \times (-8/3) = 0.8/3 \approx 0.2667, \quad -0.1 \times (-3) = 0.3. \]

所以，

\[\nabla \phi_\mu(x^{(0)}) \approx \begin{bmatrix} 1 + 0.2667 \\ -2 + 0.3 \end{bmatrix} = \begin{bmatrix} 1.2667 \\ -1.7 \end{bmatrix}. \]

现在计算Hessian矩阵。目标函数Hessian：

\[\nabla^2 f = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix}. \]

障碍项Hessian：对于 \(-\ln(g)\)，其Hessian为 \(\frac{1}{g^2} \nabla g (\nabla g)^T\)。

对于 \(g_1\)：

\[\nabla^2 (-\ln(g_1)) = \frac{1}{(x_1+x_2-2)^2} \begin{bmatrix} 1 \\ 1 \end{bmatrix} \begin{bmatrix} 1 & 1 \end{bmatrix} = \frac{1}{0.5^2} \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix} = 4 \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix} = \begin{bmatrix} 4 & 4 \\ 4 & 4 \end{bmatrix}. \]

对于 \(g_2\)：

\[\nabla^2 (-\ln(g_2)) = \frac{1}{x_1^2} \begin{bmatrix} 1 \\ 0 \end{bmatrix} \begin{bmatrix} 1 & 0 \end{bmatrix} = \frac{1}{1.5^2} \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix} \approx 0.4444 \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix} = \begin{bmatrix} 0.4444 & 0 \\ 0 & 0 \end{bmatrix}. \]

对于 \(g_3\)：

\[\nabla^2 (-\ln(g_3)) = \frac{1}{x_2^2} \begin{bmatrix} 0 \\ 1 \end{bmatrix} \begin{bmatrix} 0 & 1 \end{bmatrix} = \frac{1}{1.0^2} \begin{bmatrix} 0 & 0 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 0 & 0 \\ 0 & 1 \end{bmatrix}. \]

因此，

\[\nabla^2 \phi_\mu = \nabla^2 f - \mu \left( \nabla^2 (-\ln(g_1)) + \nabla^2 (-\ln(g_2)) + \nabla^2 (-\ln(g_3)) \right) = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} - 0.1 \left( \begin{bmatrix} 4 & 4 \\ 4 & 4 \end{bmatrix} + \begin{bmatrix} 0.4444 & 0 \\ 0 & 0 \end{bmatrix} + \begin{bmatrix} 0 & 0 \\ 0 & 1 \end{bmatrix} \right). \]

计算内部和：

\[\begin{bmatrix} 4 & 4 \\ 4 & 4 \end{bmatrix} + \begin{bmatrix} 0.4444 & 0 \\ 0 & 0 \end{bmatrix} + \begin{bmatrix} 0 & 0 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 4.4444 & 4 \\ 4 & 5 \end{bmatrix}. \]

乘以 \(\mu = 0.1\)：

\[0.1 \times \begin{bmatrix} 4.4444 & 4 \\ 4 & 5 \end{bmatrix} = \begin{bmatrix} 0.44444 & 0.4 \\ 0.4 & 0.5 \end{bmatrix}. \]

所以，

\[\nabla^2 \phi_\mu(x^{(0)}) \approx \begin{bmatrix} 2 - 0.44444 & 0 - 0.4 \\ 0 - 0.4 & 2 - 0.5 \end{bmatrix} = \begin{bmatrix} 1.55556 & -0.4 \\ -0.4 & 1.5 \end{bmatrix}. \]

第四步：构造信赖域子问题

在点 \(x^{(0)}\)，我们用二次模型近似障碍函数 \(\phi_\mu\)：

\[m(s) = \phi_\mu(x^{(0)}) + \nabla \phi_\mu(x^{(0)})^T s + \frac{1}{2} s^T \nabla^2 \phi_\mu(x^{(0)}) s, \]

其中 \(s = x - x^{(0)}\) 是步长。信赖域子问题为：

\[\min_{s \in \mathbb{R}^n} m(s) \quad \text{s.t.} \quad \| s \| \leq \Delta, \]

这里 \(\Delta > 0\) 是信赖域半径。我们初始设定 \(\Delta^{(0)} = 0.5\)。约束 \(\| s \|\) 通常取2-范数。

代入数值：

\[m(s) = \phi_\mu(x^{(0)}) + [1.2667, -1.7] \begin{bmatrix} s_1 \\ s_2 \end{bmatrix} + \frac{1}{2} [s_1, s_2] \begin{bmatrix} 1.55556 & -0.4 \\ -0.4 & 1.5 \end{bmatrix} \begin{bmatrix} s_1 \\ s_2 \end{bmatrix}. \]

常数项 \(\phi_\mu(x^{(0)})\) 在极小化中可忽略，所以模型简化为：

\[m(s) = 1.2667 s_1 - 1.7 s_2 + 0.5 (1.55556 s_1^2 - 0.8 s_1 s_2 + 1.5 s_2^2). \]

整理：

\[m(s) = 1.2667 s_1 - 1.7 s_2 + 0.77778 s_1^2 - 0.4 s_1 s_2 + 0.75 s_2^2. \]

第五步：求解信赖域子问题

这是一个带球形约束的二次优化问题。常用求解方法是计算无约束稳定点，然后投影到信赖域内。无约束稳定点满足 \(\nabla m(s) = 0\)：

\[\frac{\partial m}{\partial s_1} = 1.2667 + 1.55556 s_1 - 0.4 s_2 = 0, \\ \frac{\partial m}{\partial s_2} = -1.7 - 0.4 s_1 + 1.5 s_2 = 0. \]

写成矩阵形式：

\[\begin{bmatrix} 1.55556 & -0.4 \\ -0.4 & 1.5 \end{bmatrix} \begin{bmatrix} s_1 \\ s_2 \end{bmatrix} = \begin{bmatrix} -1.2667 \\ 1.7 \end{bmatrix}. \]

解这个线性方程组。计算行列式：

\[\text{det} = 1.55556 \times 1.5 - (-0.4) \times (-0.4) = 2.33334 - 0.16 = 2.17334. \]

逆矩阵：

\[\begin{bmatrix} 1.55556 & -0.4 \\ -0.4 & 1.5 \end{bmatrix}^{-1} = \frac{1}{2.17334} \begin{bmatrix} 1.5 & 0.4 \\ 0.4 & 1.55556 \end{bmatrix} \approx \begin{bmatrix} 0.6900 & 0.1840 \\ 0.1840 & 0.7156 \end{bmatrix}. \]

所以，

\[\begin{bmatrix} s_1 \\ s_2 \end{bmatrix} = \begin{bmatrix} 0.6900 & 0.1840 \\ 0.1840 & 0.7156 \end{bmatrix} \begin{bmatrix} -1.2667 \\ 1.7 \end{bmatrix}. \]

计算：

\[s_1 = 0.6900 \times (-1.2667) + 0.1840 \times 1.7 = -0.8740 + 0.3128 = -0.5612, \\ s_2 = 0.1840 \times (-1.2667) + 0.7156 \times 1.7 = -0.2331 + 1.2165 = 0.9834. \]

无约束步长 \(s^{\text{unc}} = (-0.5612, 0.9834)^T\)，其范数：

\[\| s^{\text{unc}} \| = \sqrt{(-0.5612)^2 + 0.9834^2} = \sqrt{0.3149 + 0.9671} = \sqrt{1.282} \approx 1.132. \]

因为 \(1.132 > \Delta = 0.5\)，所以无约束步长在信赖域外。我们需要找到约束边界 \(\| s \| = 0.5\) 上的解。这通常通过求解 \((\nabla^2 \phi_\mu + \lambda I) s = -\nabla \phi_\mu\) 并选择 \(\lambda \geq 0\) 使得 \(\| s \| = \Delta\)。由于计算复杂，这里我们采用简化：将无约束步长按比例缩放至信赖域边界：

\[s^{\text{tr}} = \frac{\Delta}{\| s^{\text{unc}} \|} s^{\text{unc}} = \frac{0.5}{1.132} \begin{bmatrix} -0.5612 \\ 0.9834 \end{bmatrix} \approx \begin{bmatrix} -0.2478 \\ 0.4342 \end{bmatrix}. \]

所以，信赖域步长为 \(s^{\text{tr}} \approx (-0.2478, 0.4342)^T\)。

第六步：反射步骤

计算试探点 \(x^{\text{trial}} = x^{(0)} + s^{\text{tr}} = (1.5 - 0.2478, 1.0 + 0.4342) = (1.2522, 1.4342)\)。检查约束违反情况：

\(g_1 = x_1 + x_2 - 2 = 1.2522 + 1.4342 - 2 = 0.6864 > 0\)，满足。
\(x_1 = 1.2522 > 0\)，满足。
\(x_2 = 1.4342 > 0\)，满足。
所以 \(x^{\text{trial}}\) 是严格内点，无需反射。如果 \(x^{\text{trial}}\) 接近或违反某个边界（比如 \(x_1\) 接近0），则可以进行反射操作：假设 \(x^{\text{trial}}\) 使得某个 \(g_i(x) \leq \epsilon\)（一个小正数），则将其沿边界法向反射回内部。这里我们不需要反射。

第七步：计算实际下降与预测下降，更新信赖域半径

计算实际下降：

\[\text{ared} = \phi_\mu(x^{(0)}) - \phi_\mu(x^{\text{trial}}). \]

首先计算 \(\phi_\mu(x^{(0)})\)：

\[\phi_\mu(x^{(0)}) = f(x^{(0)}) - \mu [\ln(g_1) + \ln(g_2) + \ln(g_3)] = (1.5-1)^2 + (1.0-2)^2 - 0.1 [\ln(0.5) + \ln(1.5) + \ln(1.0)]. \]

\(f = 0.25 + 1 = 1.25\)。\(\ln(0.5) = -0.6931, \ln(1.5)=0.4055, \ln(1)=0\)。和 = -0.2876。所以 \(\phi_\mu(x^{(0)}) = 1.25 - 0.1 \times (-0.2876) = 1.25 + 0.02876 = 1.27876\)。

现在计算 \(\phi_\mu(x^{\text{trial}})\)：

\[f(x^{\text{trial}}) = (1.2522-1)^2 + (1.4342-2)^2 = (0.2522)^2 + (-0.5658)^2 = 0.0636 + 0.3201 = 0.3837. \]

\(g_1 = 0.6864, g_2=1.2522, g_3=1.4342\)。
\(\ln(g_1) = \ln(0.6864) = -0.376, \ln(g_2)=0.225, \ln(g_3)=0.360\)。
和 = 0.209。所以 \(\phi_\mu(x^{\text{trial}}) = 0.3837 - 0.1 \times 0.209 = 0.3837 - 0.0209 = 0.3628\)。

因此，\(\text{ared} = 1.27876 - 0.3628 = 0.9160\)。

预测下降（模型下降）：

\[\text{pred} = m(0) - m(s^{\text{tr}}) = 0 - m(s^{\text{tr}}). \]

计算 \(m(s^{\text{tr}})\)：

\[m(s^{\text{tr}}) = 1.2667 \times (-0.2478) - 1.7 \times 0.4342 + 0.77778 \times (-0.2478)^2 - 0.4 \times (-0.2478) \times 0.4342 + 0.75 \times 0.4342^2. \]

逐项计算：

线性项：\(1.2667 \times (-0.2478) = -0.3139\), \(-1.7 \times 0.4342 = -0.7381\)，和为 -1.0520。
二次项：\(0.77778 \times 0.0614 = 0.0478\), \(-0.4 \times (-0.1076) = 0.0430\)（注意 \(-0.2478 \times 0.4342 = -0.1076\)），\(0.75 \times 0.1885 = 0.1414\)。
二次项和 = 0.0478 + 0.0430 + 0.1414 = 0.2322。
所以 \(m(s^{\text{tr}}) = -1.0520 + 0.2322 = -0.8198\)。
因此，\(\text{pred} = 0 - (-0.8198) = 0.8198\)。

比值 \(\rho = \frac{\text{ared}}{\text{pred}} = \frac{0.9160}{0.8198} \approx 1.117\)。

由于 \(\rho > 0.75\)（通常阈值），表明模型拟合良好，接受该步：\(x^{(1)} = x^{\text{trial}} = (1.2522, 1.4342)\)。同时，由于 \(\rho > 0.75\) 且 \(\| s^{\text{tr}} \| = \Delta = 0.5\)，可以扩大信赖域半径，比如 \(\Delta^{(1)} = 2 \Delta^{(0)} = 1.0\)。如果 \(\rho\) 很小（如<0.25），则缩小信赖域。

第八步：更新障碍参数

通常，障碍参数按照规则 \(\mu_{k+1} = \sigma \mu_k\) 更新，其中 \(\sigma \in (0,1)\)，比如 \(\sigma = 0.1\)。所以 \(\mu^{(1)} = 0.1 \times 0.1 = 0.01\)。

第九步：迭代与收敛

至此，我们完成了一次迭代。算法会重复步骤3-8，直到满足收敛条件（如梯度足够小、步长足够小、障碍参数足够小等）。最终点会趋近于原问题的最优解。对于本例，最优解在 \((1,2)\)，但需满足约束 \(x_1+x_2-2 \geq 0\)，实际最优点在边界 \(x_1+x_2=2\) 上，通过障碍法逼近。

总结：内点反射信赖域混合算法通过障碍函数处理不等式约束，信赖域控制步长可靠性，反射处理边界接近情况。本次迭代从严格内点出发，构建二次模型，求解信赖域子问题，得到可行点，更新参数，为后续迭代打下基础。

序列内点反射信赖域混合算法基础题题目描述考虑一个非线性规划问题： \[ \begin{aligned} \min_ {x \in \mathbb{R}^n} \quad & f(x) \\ \text{s.t.} \quad & c_ i(x) = 0, \quad i \in \mathcal{E}, \\ & c_ i(x) \geq 0, \quad i \in \mathcal{I}. \end{aligned} \] 其中，目标函数 \( f: \mathbb{R}^n \to \mathbb{R} \) 和约束函数 \( c_ i: \mathbb{R}^n \to \mathbb{R} \) 是二次连续可微的。内点反射信赖域混合算法结合了内点法、信赖域法和反射技术，用于处理带不等式约束的非线性优化问题。本题目要求你阐述该算法的基本框架和关键步骤，并应用于以下具体例子： \[ \begin{aligned} \min_ {x_ 1, x_ 2} \quad & f(x) = (x_ 1 - 1)^2 + (x_ 2 - 2)^2 \\ \text{s.t.} \quad & x_ 1 + x_ 2 - 2 \geq 0, \\ & x_ 1 \geq 0, \quad x_ 2 \geq 0. \end{aligned} \] 从初始点 \( x^{(0)} = (0.5, 0.5) \) 开始，执行一次算法迭代（包括构造子问题、求解信赖域子问题、进行反射步骤以及更新内点参数和信赖域半径）。要求展示详细计算过程，包括梯度、Hessian矩阵、障碍函数、子问题构造、信赖域求解、反射条件和参数更新规则。解题过程循序渐进讲解第一步：算法基本思想理解内点反射信赖域混合算法的核心思想是：内点法处理不等式约束：通过引入障碍函数（如对数障碍函数）将不等式约束融入目标函数，形成一个无约束或仅含等式约束的子问题，并确保迭代点始终位于可行域内部（即严格满足不等式约束）。信赖域法控制步长：在每一步迭代，在当前点附近用一个简化模型（通常是二次模型）近似原问题，并限制步长在一个信赖域内，以保证模型的可靠性。反射技术加速收敛：当试探步长导致点接近或违反边界时，不直接拒绝，而是尝试将其“反射”回可行域内部，可能获得更大的可行步长，从而提高收敛速度。这个混合策略旨在结合内点法的可行性保持、信赖域法的全局收敛性以及反射技术的边界处理效率。第二步：构造障碍函数和拉格朗日函数对于不等式约束 \( c_ i(x) \geq 0 \)，引入对数障碍函数。原问题转化为一系列障碍子问题： \[ \min_ {x} \quad \phi_ \mu(x) = f(x) - \mu \sum_ {i \in \mathcal{I}} \ln(c_ i(x)), \] 其中 \( \mu > 0 \) 是障碍参数，随着迭代逐渐减小趋于0。等式约束可以通过拉格朗日乘子处理。定义增广拉格朗日函数： \[ \mathcal{L}(x, \lambda) = \phi_ \mu(x) + \sum_ {i \in \mathcal{E}} \lambda_ i c_ i(x), \] 其中 \( \lambda_ i \) 是对应等式约束的拉格朗日乘子。在我们的例子中，没有等式约束（\( \mathcal{E} = \emptyset \)），只有一个不等式约束 \( c_ 1(x) = x_ 1 + x_ 2 - 2 \geq 0 \) 和两个边界约束 \( x_ 1 \geq 0, x_ 2 \geq 0 \)。通常，边界约束可以直接纳入障碍项。因此，障碍函数为： \[ \phi_ \mu(x) = (x_ 1 - 1)^2 + (x_ 2 - 2)^2 - \mu \left[ \ln(x_ 1 + x_ 2 - 2) + \ln(x_ 1) + \ln(x_ 2) \right ]. \] 注意：初始点 \( x^{(0)} = (0.5, 0.5) \) 需严格满足 \( x_ 1>0, x_ 2>0, x_ 1+x_ 2-2>0 \)（即 \( 0.5+0.5-2=-1<0 \)）。实际上，这个点不满足约束 \( x_ 1+x_ 2-2 \geq 0 \)。内点法要求严格内点，所以我们需要调整初始点。为了使算法可行，我们调整初始点为 \( x^{(0)} = (1.5, 1.0) \)，此时 \( x_ 1=1.5>0, x_ 2=1.0>0, x_ 1+x_ 2-2=0.5>0 \)，是严格内点。这是内点法的常见要求。第三步：计算当前点的梯度和Hessian矩阵在点 \( x^{(0)} = (1.5, 1.0) \)，设定初始障碍参数 \( \mu = 0.1 \)。首先计算目标函数梯度： \[ \nabla f(x) = \begin{bmatrix} 2(x_ 1 - 1) \\ 2(x_ 2 - 2) \end{bmatrix} = \begin{bmatrix} 2(1.5-1) \\ 2(1.0-2) \end{bmatrix} = \begin{bmatrix} 1 \\ -2 \end{bmatrix}. \] 障碍项部分：记 \( g_ 1(x) = x_ 1 + x_ 2 - 2 \), \( g_ 2(x) = x_ 1 \), \( g_ 3(x) = x_ 2 \)。 \[ \nabla (-\ln(g_ 1)) = -\frac{1}{g_ 1} \nabla g_ 1 = -\frac{1}{x_ 1+x_ 2-2} \begin{bmatrix} 1 \\ 1 \end{bmatrix} = -\frac{1}{0.5} \begin{bmatrix} 1 \\ 1 \end{bmatrix} = \begin{bmatrix} -2 \\ -2 \end{bmatrix}. \] \[ \nabla (-\ln(g_ 2)) = -\frac{1}{x_ 1} \begin{bmatrix} 1 \\ 0 \end{bmatrix} = -\frac{1}{1.5} \begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{bmatrix} -2/3 \\ 0 \end{bmatrix} \approx \begin{bmatrix} -0.6667 \\ 0 \end{bmatrix}. \] \[ \nabla (-\ln(g_ 3)) = -\frac{1}{x_ 2} \begin{bmatrix} 0 \\ 1 \end{bmatrix} = -\frac{1}{1.0} \begin{bmatrix} 0 \\ 1 \end{bmatrix} = \begin{bmatrix} 0 \\ -1 \end{bmatrix}. \] 因此，障碍函数梯度： \[ \nabla \phi_ \mu = \nabla f - \mu \left( \sum_ {i=1}^3 \nabla (-\ln(g_ i)) \right) = \begin{bmatrix} 1 \\ -2 \end{bmatrix} - 0.1 \left( \begin{bmatrix} -2 \\ -2 \end{bmatrix} + \begin{bmatrix} -2/3 \\ 0 \end{bmatrix} + \begin{bmatrix} 0 \\ -1 \end{bmatrix} \right) = \begin{bmatrix} 1 \\ -2 \end{bmatrix} - 0.1 \begin{bmatrix} -8/3 \\ -3 \end{bmatrix}. \] 计算： \[ -0.1 \times (-8/3) = 0.8/3 \approx 0.2667, \quad -0.1 \times (-3) = 0.3. \] 所以， \[ \nabla \phi_ \mu(x^{(0)}) \approx \begin{bmatrix} 1 + 0.2667 \\ -2 + 0.3 \end{bmatrix} = \begin{bmatrix} 1.2667 \\ -1.7 \end{bmatrix}. \] 现在计算Hessian矩阵。目标函数Hessian： \[ \nabla^2 f = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix}. \] 障碍项Hessian：对于 \( -\ln(g) \)，其Hessian为 \( \frac{1}{g^2} \nabla g (\nabla g)^T \)。对于 \( g_ 1 \)： \[ \nabla^2 (-\ln(g_ 1)) = \frac{1}{(x_ 1+x_ 2-2)^2} \begin{bmatrix} 1 \\ 1 \end{bmatrix} \begin{bmatrix} 1 & 1 \end{bmatrix} = \frac{1}{0.5^2} \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix} = 4 \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix} = \begin{bmatrix} 4 & 4 \\ 4 & 4 \end{bmatrix}. \] 对于 \( g_ 2 \)： \[ \nabla^2 (-\ln(g_ 2)) = \frac{1}{x_ 1^2} \begin{bmatrix} 1 \\ 0 \end{bmatrix} \begin{bmatrix} 1 & 0 \end{bmatrix} = \frac{1}{1.5^2} \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix} \approx 0.4444 \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix} = \begin{bmatrix} 0.4444 & 0 \\ 0 & 0 \end{bmatrix}. \] 对于 \( g_ 3 \)： \[ \nabla^2 (-\ln(g_ 3)) = \frac{1}{x_ 2^2} \begin{bmatrix} 0 \\ 1 \end{bmatrix} \begin{bmatrix} 0 & 1 \end{bmatrix} = \frac{1}{1.0^2} \begin{bmatrix} 0 & 0 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 0 & 0 \\ 0 & 1 \end{bmatrix}. \] 因此， \[ \nabla^2 \phi_ \mu = \nabla^2 f - \mu \left( \nabla^2 (-\ln(g_ 1)) + \nabla^2 (-\ln(g_ 2)) + \nabla^2 (-\ln(g_ 3)) \right) = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} - 0.1 \left( \begin{bmatrix} 4 & 4 \\ 4 & 4 \end{bmatrix} + \begin{bmatrix} 0.4444 & 0 \\ 0 & 0 \end{bmatrix} + \begin{bmatrix} 0 & 0 \\ 0 & 1 \end{bmatrix} \right). \] 计算内部和： \[ \begin{bmatrix} 4 & 4 \\ 4 & 4 \end{bmatrix} + \begin{bmatrix} 0.4444 & 0 \\ 0 & 0 \end{bmatrix} + \begin{bmatrix} 0 & 0 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 4.4444 & 4 \\ 4 & 5 \end{bmatrix}. \] 乘以 \( \mu = 0.1 \)： \[ 0.1 \times \begin{bmatrix} 4.4444 & 4 \\ 4 & 5 \end{bmatrix} = \begin{bmatrix} 0.44444 & 0.4 \\ 0.4 & 0.5 \end{bmatrix}. \] 所以， \[ \nabla^2 \phi_ \mu(x^{(0)}) \approx \begin{bmatrix} 2 - 0.44444 & 0 - 0.4 \\ 0 - 0.4 & 2 - 0.5 \end{bmatrix} = \begin{bmatrix} 1.55556 & -0.4 \\ -0.4 & 1.5 \end{bmatrix}. \] 第四步：构造信赖域子问题在点 \( x^{(0)} \)，我们用二次模型近似障碍函数 \( \phi_ \mu \)： \[ m(s) = \phi_ \mu(x^{(0)}) + \nabla \phi_ \mu(x^{(0)})^T s + \frac{1}{2} s^T \nabla^2 \phi_ \mu(x^{(0)}) s, \] 其中 \( s = x - x^{(0)} \) 是步长。信赖域子问题为： \[ \min_ {s \in \mathbb{R}^n} m(s) \quad \text{s.t.} \quad \| s \| \leq \Delta, \] 这里 \( \Delta > 0 \) 是信赖域半径。我们初始设定 \( \Delta^{(0)} = 0.5 \)。约束 \( \| s \| \) 通常取2-范数。代入数值： \[ m(s) = \phi_ \mu(x^{(0)}) + [ 1.2667, -1.7] \begin{bmatrix} s_ 1 \\ s_ 2 \end{bmatrix} + \frac{1}{2} [ s_ 1, s_ 2] \begin{bmatrix} 1.55556 & -0.4 \\ -0.4 & 1.5 \end{bmatrix} \begin{bmatrix} s_ 1 \\ s_ 2 \end{bmatrix}. \] 常数项 \( \phi_ \mu(x^{(0)}) \) 在极小化中可忽略，所以模型简化为： \[ m(s) = 1.2667 s_ 1 - 1.7 s_ 2 + 0.5 (1.55556 s_ 1^2 - 0.8 s_ 1 s_ 2 + 1.5 s_ 2^2). \] 整理： \[ m(s) = 1.2667 s_ 1 - 1.7 s_ 2 + 0.77778 s_ 1^2 - 0.4 s_ 1 s_ 2 + 0.75 s_ 2^2. \] 第五步：求解信赖域子问题这是一个带球形约束的二次优化问题。常用求解方法是计算无约束稳定点，然后投影到信赖域内。无约束稳定点满足 \( \nabla m(s) = 0 \)： \[ \frac{\partial m}{\partial s_ 1} = 1.2667 + 1.55556 s_ 1 - 0.4 s_ 2 = 0, \\ \frac{\partial m}{\partial s_ 2} = -1.7 - 0.4 s_ 1 + 1.5 s_ 2 = 0. \] 写成矩阵形式： \[ \begin{bmatrix} 1.55556 & -0.4 \\ -0.4 & 1.5 \end{bmatrix} \begin{bmatrix} s_ 1 \\ s_ 2 \end{bmatrix} = \begin{bmatrix} -1.2667 \\ 1.7 \end{bmatrix}. \] 解这个线性方程组。计算行列式： \[ \text{det} = 1.55556 \times 1.5 - (-0.4) \times (-0.4) = 2.33334 - 0.16 = 2.17334. \] 逆矩阵： \[ \begin{bmatrix} 1.55556 & -0.4 \\ -0.4 & 1.5 \end{bmatrix}^{-1} = \frac{1}{2.17334} \begin{bmatrix} 1.5 & 0.4 \\ 0.4 & 1.55556 \end{bmatrix} \approx \begin{bmatrix} 0.6900 & 0.1840 \\ 0.1840 & 0.7156 \end{bmatrix}. \] 所以， \[ \begin{bmatrix} s_ 1 \\ s_ 2 \end{bmatrix} = \begin{bmatrix} 0.6900 & 0.1840 \\ 0.1840 & 0.7156 \end{bmatrix} \begin{bmatrix} -1.2667 \\ 1.7 \end{bmatrix}. \] 计算： \[ s_ 1 = 0.6900 \times (-1.2667) + 0.1840 \times 1.7 = -0.8740 + 0.3128 = -0.5612, \\ s_ 2 = 0.1840 \times (-1.2667) + 0.7156 \times 1.7 = -0.2331 + 1.2165 = 0.9834. \] 无约束步长 \( s^{\text{unc}} = (-0.5612, 0.9834)^T \)，其范数： \[ \| s^{\text{unc}} \| = \sqrt{(-0.5612)^2 + 0.9834^2} = \sqrt{0.3149 + 0.9671} = \sqrt{1.282} \approx 1.132. \] 因为 \( 1.132 > \Delta = 0.5 \)，所以无约束步长在信赖域外。我们需要找到约束边界 \( \| s \| = 0.5 \) 上的解。这通常通过求解 \( (\nabla^2 \phi_ \mu + \lambda I) s = -\nabla \phi_ \mu \) 并选择 \( \lambda \geq 0 \) 使得 \( \| s \| = \Delta \)。由于计算复杂，这里我们采用简化：将无约束步长按比例缩放至信赖域边界： \[ s^{\text{tr}} = \frac{\Delta}{\| s^{\text{unc}} \|} s^{\text{unc}} = \frac{0.5}{1.132} \begin{bmatrix} -0.5612 \\ 0.9834 \end{bmatrix} \approx \begin{bmatrix} -0.2478 \\ 0.4342 \end{bmatrix}. \] 所以，信赖域步长为 \( s^{\text{tr}} \approx (-0.2478, 0.4342)^T \)。第六步：反射步骤计算试探点 \( x^{\text{trial}} = x^{(0)} + s^{\text{tr}} = (1.5 - 0.2478, 1.0 + 0.4342) = (1.2522, 1.4342) \)。检查约束违反情况： \( g_ 1 = x_ 1 + x_ 2 - 2 = 1.2522 + 1.4342 - 2 = 0.6864 > 0 \)，满足。 \( x_ 1 = 1.2522 > 0 \)，满足。 \( x_ 2 = 1.4342 > 0 \)，满足。所以 \( x^{\text{trial}} \) 是严格内点，无需反射。如果 \( x^{\text{trial}} \) 接近或违反某个边界（比如 \( x_ 1 \) 接近0），则可以进行反射操作：假设 \( x^{\text{trial}} \) 使得某个 \( g_ i(x) \leq \epsilon \)（一个小正数），则将其沿边界法向反射回内部。这里我们不需要反射。第七步：计算实际下降与预测下降，更新信赖域半径计算实际下降： \[ \text{ared} = \phi_ \mu(x^{(0)}) - \phi_ \mu(x^{\text{trial}}). \] 首先计算 \( \phi_ \mu(x^{(0)}) \)： \[ \phi_ \mu(x^{(0)}) = f(x^{(0)}) - \mu [ \ln(g_ 1) + \ln(g_ 2) + \ln(g_ 3)] = (1.5-1)^2 + (1.0-2)^2 - 0.1 [ \ln(0.5) + \ln(1.5) + \ln(1.0) ]. \] \( f = 0.25 + 1 = 1.25 \)。\( \ln(0.5) = -0.6931, \ln(1.5)=0.4055, \ln(1)=0 \)。和 = -0.2876。所以 \( \phi_ \mu(x^{(0)}) = 1.25 - 0.1 \times (-0.2876) = 1.25 + 0.02876 = 1.27876 \)。现在计算 \( \phi_ \mu(x^{\text{trial}}) \)： \[ f(x^{\text{trial}}) = (1.2522-1)^2 + (1.4342-2)^2 = (0.2522)^2 + (-0.5658)^2 = 0.0636 + 0.3201 = 0.3837. \] \( g_ 1 = 0.6864, g_ 2=1.2522, g_ 3=1.4342 \)。 \( \ln(g_ 1) = \ln(0.6864) = -0.376, \ln(g_ 2)=0.225, \ln(g_ 3)=0.360 \)。和 = 0.209。所以 \( \phi_ \mu(x^{\text{trial}}) = 0.3837 - 0.1 \times 0.209 = 0.3837 - 0.0209 = 0.3628 \)。因此，\( \text{ared} = 1.27876 - 0.3628 = 0.9160 \)。预测下降（模型下降）： \[ \text{pred} = m(0) - m(s^{\text{tr}}) = 0 - m(s^{\text{tr}}). \] 计算 \( m(s^{\text{tr}}) \)： \[ m(s^{\text{tr}}) = 1.2667 \times (-0.2478) - 1.7 \times 0.4342 + 0.77778 \times (-0.2478)^2 - 0.4 \times (-0.2478) \times 0.4342 + 0.75 \times 0.4342^2. \] 逐项计算：线性项：\( 1.2667 \times (-0.2478) = -0.3139 \), \( -1.7 \times 0.4342 = -0.7381 \)，和为 -1.0520。二次项：\( 0.77778 \times 0.0614 = 0.0478 \), \( -0.4 \times (-0.1076) = 0.0430 \)（注意 \(-0.2478 \times 0.4342 = -0.1076\)），\( 0.75 \times 0.1885 = 0.1414 \)。二次项和 = 0.0478 + 0.0430 + 0.1414 = 0.2322。所以 \( m(s^{\text{tr}}) = -1.0520 + 0.2322 = -0.8198 \)。因此，\( \text{pred} = 0 - (-0.8198) = 0.8198 \)。比值 \( \rho = \frac{\text{ared}}{\text{pred}} = \frac{0.9160}{0.8198} \approx 1.117 \)。由于 \( \rho > 0.75 \)（通常阈值），表明模型拟合良好，接受该步：\( x^{(1)} = x^{\text{trial}} = (1.2522, 1.4342) \)。同时，由于 \( \rho > 0.75 \) 且 \( \| s^{\text{tr}} \| = \Delta = 0.5 \)，可以扩大信赖域半径，比如 \( \Delta^{(1)} = 2 \Delta^{(0)} = 1.0 \)。如果 \( \rho \) 很小（如 <0.25），则缩小信赖域。第八步：更新障碍参数通常，障碍参数按照规则 \( \mu_ {k+1} = \sigma \mu_ k \) 更新，其中 \( \sigma \in (0,1) \)，比如 \( \sigma = 0.1 \)。所以 \( \mu^{(1)} = 0.1 \times 0.1 = 0.01 \)。第九步：迭代与收敛至此，我们完成了一次迭代。算法会重复步骤3-8，直到满足收敛条件（如梯度足够小、步长足够小、障碍参数足够小等）。最终点会趋近于原问题的最优解。对于本例，最优解在 \( (1,2) \)，但需满足约束 \( x_ 1+x_ 2-2 \geq 0 \)，实际最优点在边界 \( x_ 1+x_ 2=2 \) 上，通过障碍法逼近。总结：内点反射信赖域混合算法通过障碍函数处理不等式约束，信赖域控制步长可靠性，反射处理边界接近情况。本次迭代从严格内点出发，构建二次模型，求解信赖域子问题，得到可行点，更新参数，为后续迭代打下基础。