优化书总结 第1篇

除了上面介绍的线性加权法，主要目标法（也称\epsilon-约束方法）， 是一个应用广泛的算法

\begin{array}{c} \min_{x} f_p(x) \tag{9} \\ \text{. } f_k(x) \le \epsilon_k ,k=1,...,K,且k\not ={p} \\ \text{ } g_i(x) \ge 0 ,i \in [1,M ] \\ \text{ } h_j(x) = 0 ,j \in [1,L ] \end{array}

\epsilon-约束方法从K个目标中选择最重要的子目标作为优化目标，其余的子目标作为约束条件。 每个子目标，通过上界\epsilon_k来约束。设上述约束条件得到的可行域为\hat{D}。

一般情况下，界限值可以取子目标函数的上界值：

\min \{ f_k| f_k(x) ,k=1,...,K,且k\not ={p} \} \le \epsilon_k \tag{10} \\

这种取法可以使得某些f_k(x)留在可行域\hat{D}内，并且 \hat{D}内有较多的点靠近f_k(x)的最优解。

主要目标法的优缺点对比

优化书总结 第2篇

下面给出一个严格条件下多目标优化的充分必要条件。

约束规格

下文给出的充要条件前，我们先引入了约束规格条件：

\begin{array}{c} \min_{x\in \hat{D} } F(x) = \sum_{k=1}^{K} f_i(x) \\ \hat{D} ={x \in D | f(x) \leq f(\hat{x})} \tag{6} \end{array}

定理：设f(x)，g(x)为凸函数，且在x\in D处可微，h(x)为线性函数，且\hat{D} ={x \in D | f(x) \leq f(\hat{x})}满足KKT约束规格[4]，则x^*是MOO的有效解的充分必要条件是存在\lambda \in R^K,u\in R^M, v\in R^L,使得

\begin{cases} \nabla_x L(x^*,\lambda^*,u^*,v^*) = \nabla f(x^*) \lambda^* + \nabla g(x^*) u^* + \nabla h(x^*) v^* = 0 , \\ u^{*T} g(x^*) = 0, \\ \lambda^* > 0 ,u^* \geq 0. \tag{7} \end{cases}

定理的证明参考[1].

优化书总结 第3篇

带约束的多目标问题MOO(mulit object optimization )

\begin{array}{c} \min_{x} \enspace F(x) = [f_1(x),f_2(x),...,f_K(x)] \tag{4} \\ \text{. } g_i(x) \ge 0 ,i \in [1,M ] \\ \text{ } \enspace h_j(x) = 0 ,j \in [1,L ] \end{array}

令D为上述多目标优化问题的可行域，即

D= \{x |g_i(x) \ge 0 ,i \in [1,M ] , h_j(x) = 0 ,j \in [1,L ] \} \\

优化书总结 第4篇

求解问题(35)，需要找到一个满足约束的基本可行解。对于随机产生的可行解\theta_r ,一种最直接的方法找到初始可行解\theta_0

\begin{array}{c} \min_{\theta_0} || \theta_0 - \theta_r||^2 \\ \text{.} L(\theta_0) \in \Omega_k \tag{38} \end{array}

定义活跃限制集合（activated constraints ):

I(\theta_r) = \{j| G_j(\theta_r) \geq 0 ,j = 1,...,K \} \tag{39}

我们找到能令I(\theta_r)中所有的活跃限制函数值下降的方向：

(d_r,\alpha_r ) = \text{argmin}_{d\in R^n,\alpha in R } \alpha + \frac{1}{2}||d||^2 \\ \text{.} \nabla G_j(\theta_r)^T d \leq \alpha , j \in I(\theta_r) \tag{40}

求解上述问题后，可以得到对应的更新公式：

\theta_{r_{t+1}} = \theta_{r_{t}} + \eta_r d_{r_t} \\

上述问题(36)能将活跃集内的约束目标值减少，使得越来越多的约束目标小于0 。 I(\theta_r)最后变成空集，则\theta_r是可行解。

受限帕累托最优 : \theta^*是多任务L(\theta)在子区域\Omega_k的最优解，如果\theta^* \in \Omega_k且不存在\hat{\theta} \in \Omega_k使得\hat{\theta} < \theta^*

考虑如下的多目标优化问题：

(d_t,\alpha_t ) = \text{argmin}_{d\in R^n,\alpha \in R } \alpha + \frac{1}{2}||d||^2 \\ \text{.} \nabla L_i(\theta_t)^T d \leq \alpha , i=1,...,m\\ \nabla G_j(\theta_t)^T d \leq \alpha , j \in I_{\epsilon} (\theta_t) \\ \tag{41}

其中I_{\epsilon} (\theta_t)定义：

I_{\epsilon} (\theta_t) = \{j\in I | G_j(\theta)\geq -\epsilon \} \\

参考《多目标优化（四）：梯度下降算法》这一节

我们有：

令(d^k,\alpha^{k})是多任务学习问题(41)的解，则

\alpha_t \leq -\frac{1}{2} ||d_t||^2 < 0 ,\\ \nabla L_i(\theta_t)^T d \leq \alpha, i=1,...,m\\ \nabla G_j(\theta_t)^T d \leq \alpha , j \in I_{\epsilon} (\theta_t) \\ \tag{42}

迭代公式：

\theta_{t+1} = \theta_{t} + \eta d_{t} \\

通过求解上述问题，能够获得一个有效的搜索方向。

上述方法能够获得一个有效的搜索方向，对于大规模的问题，求解起来会比较困难。这里将问题(41)重写，将其表示为对偶形式：

d_t= -（\sum_{i=1}^{m} \lambda_i \nabla L_i(\theta_t) + \sum_{j\in I_\epsilon (\theta)} \beta_i \nabla G_j(\theta_t)) \\ \sum_{i=1}^{m} \lambda_i + \sum_{j\in I_\epsilon (\theta)} \beta_j = 1 \tag{43}

\max_{\lambda_i,\beta_j} -\frac{1}{2} || \sum_{i=1}^{m} \lambda_i \nabla L_i(\theta_t) + \sum_{j\in I_\epsilon (\theta)} \beta_i \nabla G_j(\theta_t)||^2 \\ \text{. } \sum_{i=1}^{m} \lambda_i + \sum_{j\in I_\epsilon (\theta)} \beta_j = 1 ,\lambda_i \geq 0,\beta_j \geq ,\forall i =1,...,m ,\forall j \in I_{\epsilon} (\theta) \tag{44}

将多任务学习转化为其对偶问题后，求解空间不再是参数空间，而是变成了任务个数和受限条件数，使得求解问题极大的减少了。

Pareto MTL 算法如下图：