多目标优化算法

多目标优化定义

有两个 Optimization Toolbox™ 多目标求解器： fgoalattain 和 fminimax。

fgoalattain 求解了将一组非线性函数 F_i（x）简化为一组目标 F*_i 的问题。由于有多个函数 F_i(x)，求解这个问题的意义并不总是很清楚，尤其是当您无法同时实现所有目标时。因此，该问题被重新构造为一个始终定义明确的问题。
非缩放目标实现问题是为了最小化 F_i(x) – F*_i 的最大值。
对于非缩放问题有一个有用的概括。给定一组正权重 w_i，目标实现问题试图找到 x 来最小化
$\frac{F_{i} (x) - F_{i}^{*}}{w_{i}} .$ (1)
这种最小化应该在满足所有类型的约束的同时完成：c(x) ≤ 0, ceq(x) = 0, A·x ≤ b, Aeq·x = beq, and l ≤ x ≤ u。
如果将所有权重设置为 1（或任何其他正常数），则目标实现问题与未缩放的目标实现问题相同。如果 F*_i 为正，且将所有权重设置为 w_i = F*_i，则目标实现问题就变成最小函数 F_i(x) 和目标 F*_i 之间的相对差异。
换句话说，目标实现问题就是最小化一个松弛变量 γ，该变量定义为公式 1 中表达式的 i 上的最大值。这意味着目标实现问题的正式表述如下：
$\min_{x, γ} γ$
满足 F(x) – w·γ ≤ F*, c(x) ≤ 0, ceq(x) = 0, A·x ≤ b, Aeq·x = beq, and l ≤ x ≤ u。
fminimax 求解了最小化一组非线性函数的最大值的问题，受所有约束的制约：
$\min_{x} \max_{i} F_{i} (x)$
满足 c(x) ≤ 0, ceq(x) = 0, A·x ≤ b, Aeq·x = beq, and l ≤ x ≤ u。
显然，这个问题是无尺度目标实现问题的一个特例，有 F*_i = 0 和 w_i = 1。

算法

目标达成方法

本节介绍了 Gembicki [3] 的目标实现方法。该方法使用一组设计目标 $F^{*} = {F_{1}^{*}, F_{2}^{*}, ..., F_{m}^{*}}$ ，与一组目标 F(x) = {F₁(x),F₂(x),...,F_m(x)} 相关联。问题的表示允许目标未达到或超过目标，从而使得设计师对初始设计目标的把握相对不精确。目标未完成或超额完成的相对程度由加权系数向量 w = {w₁,w₂,...,w_m} 控制，并使用以下公式表示为标准优化问题

\underset{γ \in ℜ, x \in Ω}{minimize} γ

(2)

满足 $F_{i} (x) - w_{i} γ \leq F_{i}^{*}, i = 1, ..., m .$

术语 w_iγ 在问题中引入了松弛元素，否则就要求必须严格满足目标。加权向量 w 使设计师能够表达目标之间的相对权衡的测度。例如，将加权向量 w 设置为等于初始目标，表示实现了相同百分比的目标未完成或超额完成，F*。您可以通过将特定加权因子设置为零（即，w_i = 0）将硬约束纳入设计中。目标实现方法为设计问题提供了方便直观的解释，可以使用标准优化程序来求解。在弗莱明 ([10] 和 [11]) 中可以找到在控制系统设计中使用目标实现方法的说明性示例。

下图以二维几何形式表示了目标实现方法。

图 7-1: 目标达成方法的几何表示

Plot of the line [F_1*,F_2*] + [w_1,w_2]*gamma. Also a plot of the feasible region in [F_1,F_2] space for a given value of gamma as x varies. The optimal point is where the line intersects the feasible region associated with that value of gamma.

目标的规范 ${F_{1}^{*}, F_{2}^{*}}$ 定义了目标点 P。加权向量定义了从 P 到可行函数空间 Λ(γ) 的搜索方向。在优化过程中，γ 会发生变化，从而改变可行区域的大小。约束边界收敛到唯一的解点 F_1s, F_2s。

目标达成方法的算法改进

目标实现方法的优点在于它可以被呈现为非线性规划问题。非线性规划算法也可以利用该问题的特性。在序列二次规划 (SQP) 中，线搜索的评价函数的选择并不容易，因为在许多情况下很难“定义”改进目标函数和减少约束违反值之间的相对重要性。这导致了许多构建评价函数的不同方案（例如，请参阅 Schittkowski [36]）。在目标达成规划中，可能存在更合适的评价函数，您可以通过将公式 2 设置为极小极大问题来实现它

\underset{x \in ℜ^{n}}{minimize} \max_{i} {Λ_{i}},

(3)

其中

$Λ_{i} = \frac{F_{i} (x) - F_{i}^{*}}{w_{i}}, i = 1, ..., m .$

按照 Brayton 等人[1] 关于使用 SQP 进行极小极大优化的参量，使用公式 30 的优化函数来求解公式 3 的目标实现问题可得

ψ (x, γ) = γ + \sum_{i = 1}^{m} r_{i} \cdot \max {0, F_{i} (x) - w_{i} γ - F_{i}^{*}} .

(4)

当公式 4 的评价函数用作线搜索程序的基础时，尽管 ψ(x,γ) 在给定的搜索方向上一步步可能会减少，但函数 max Λ_i 可能会反常地增加。这就是接受最坏情况目标的下降。由于最坏情况目标决定了目标函数 γ 的值，因此接受最终增加目标函数以使其最小化的步骤。相反，当 max Λ_i 减少时，ψ(x,γ) 可能会增加，这意味着拒绝改善最坏情况目标的步骤。

按照 Brayton 等人的思路，[1] 的解是将 ψ(x) 设置为最坏情况目标，即

ψ (x) = \max_{i} Λ_{i} .

(5)

目标达成方法中的一个问题是，通常使用等于 0 的加权系数来纳入硬约束。然后，对于任意违反约束的情况，公式 5 的评价函数都会变为无限。

为了克服这个问题，同时仍然保留公式 5的特点，将评价函数与公式 31的评价函数相结合，得到以下内容：

ψ (x) = \sum_{i = 1}^{m} {\begin{array}{l} r_{i} \cdot \max {0, F_{i} (x) - w_{i} γ - F_{i}^{*}} & if w_{i} = 0 \\ \max_{i} Λ_{i}, i = 1, ..., m & otherwise . \end{array}

(6)

SQP 中可以利用的另一个特性是目标函数 γ。从 KKT 方程可以看出，拉格朗日函数的 Hessian 近似值 H 在与变量 γ 相关的行和列中应该有零。但是，如果将 H 初始化为单位矩阵，则此属性不会出现。因此，将 H 初始化并保持在与 γ 相关联的行和列中为零。

这些变化使得 Hessian H 变得不确定。因此，H 在与 γ 相关的行和列中被设置为零，但对角线元素除外，它被设置为一个较小的正数（例如，1e-10）。这允许使用二次规划解中描述的快速收敛正定 QP 方法。

前述修改已在 fgoalattain 中实现，并且被发现可以使该方法更加稳健。然而，由于 SQP 方法的快速收敛，要求评价函数严格减少有时需要比使用公式 30 的评价函数实现 SQP 更多的函数计算。

最小化最大目标

fminimax 使用目标实现方法。其目标为 0，权重为 1。根据这种表示，目标实现问题变成了

$\min_{i} \max_{x} (\frac{f_{i} (x) - g o a l_{i}}{w e i g h t_{i}}) = \min_{i} \max_{x} f_{i} (x),$

，即极小极大问题。

顺便说一下，您可能希望 fminimax 将多目标函数转变为单一目标。函数

f(x) = max(F₁(x),... F_j(x))

是一个需要最小化的单一目标函数。但是，它不可微，并且要求 Optimization Toolbox 目标必须是平滑的。因此，极小极大问题被构造为平滑的目标实现问题。

参考

[1] Brayton, R. K., S. W. Director, G. D. Hachtel, and L. Vidigal, “A New Algorithm for Statistical Circuit Design Based on Quasi-Newton Methods and Function Splitting,” IEEE Transactions on Circuits and Systems, Vol. CAS-26, pp 784-794, Sept. 1979.

[2] Fleming, P.J. and A.P. Pashkevich, Computer Aided Control System Design Using a Multi-Objective Optimisation Approach, Control 1985 Conference, Cambridge, UK, pp. 174-179.

[3] Gembicki, F.W., “Vector Optimization for Control with Performance and Parameter Sensitivity Indices,” Ph.D. Dissertation, Case Western Reserve Univ., Cleveland, OH, 1974.

[4] Grace, A.C.W., “Computer-Aided Control System Design Using Optimization Techniques,” Ph.D. Thesis, University of Wales, Bangor, Gwynedd, UK, 1989.

[5] Han, S.P., “A Globally Convergent Method For Nonlinear Programming,” Journal of Optimization Theory and Applications, Vol. 22, p. 297, 1977.

[6] Madsen, K. and H. Schjaer-Jacobsen, “Algorithms for Worst Case Tolerance Optimization,” IEEE Trans. of Circuits and Systems, Vol. CAS-26, Sept. 1979.

[7] Powell, M.J.D., “A Fast Algorithm for Nonlinear Constrained Optimization Calculations,” Numerical Analysis, ed. G.A. Watson, Lecture Notes in Mathematics, Vol. 630, Springer Verlag, 1978.

另请参阅

fgoalattain | fminimax