欢迎光临 x-algo
关注算法在工业界应用
Hi, 这是一个关注大数据算法在工业界应用的网站

集合约束和无约束优化问题

一般来说优化问题可以表示为:

\(\begin{matrix}minimize \ &f(x)\\subject \ to \ &x \in \Omega\end{matrix}\)

其中 \(\Omega =\{x:h(x) =0,g(x)\le0\}\) ,由于极大值和极小值可以通过改变目标函数的符号等价变换,所以只需要考虑求解函数极小值的问题即可。

接下来让我们讨论一下局部极小点的条件。

一阶导和二阶导

函数 \(f\) 的一阶导数 \(Df\) 为:

\(Df=\left[ \frac{\partial{f}}{\partial{x_1}}, \frac{\partial{f}}{\partial{x_2}},...,\frac{\partial{f}}{\partial{x_n}}\right ]\)

二阶导,也称为汉森矩阵:

\(D^2f=\begin{bmatrix}\frac{\partial^2{f}}{\partial{x_1^2}} &... &\frac{\partial^2{f}}{\partial{x_n}\partial{x_1}} \\ \vdots & &\vdots \\\frac{\partial^2{f}}{\partial{x_1}\partial{x_n}} &... &\frac{\partial^2{f}}{\partial{x_n^2}} \end{bmatrix}\)

可行方向

有约束的问题中,最值可能位于可行域内部,也可能是位于边界处,这里仅仅给出来一个定义,就是当前点 \(x\) 按照某个方向向量d平移之后依然在约束集之内,就称d为x处的可行方向。

方向导数

初识方向导数的时候让人有点摸不着头脑,因为我们可能会考虑一个问题,就是点 \(x\) 的导数 \(f'(x)\) 是有方向的吗?如果有,方向是什么?

函数f沿着d方向的导数可以表示为:

\(\frac{\partial{f}}{\partial{d}}(x)=\lim_{\alpha\rightarrow 0}\frac{f(x+\alpha d)-f(x)}{\alpha}\)

如果x和d都是常量,上式就变为关于 \(\alpha\) 的函数,有

\(\left.\begin{matrix}\frac{\partial{f}}{\partial{d}}(x)=\frac{\partial{f(x+\alpha d)}}{\partial{\alpha}} \end{matrix}\right|_{\alpha=0}\)

应用链式法则可以得到:

\(\frac{\partial{f}}{\partial{d}}(x)=\left.\begin{matrix}\frac{\partial{f(x+\alpha d)}}{\partial{\alpha}} \end{matrix}\right|_{\alpha=0}=\bigtriangledown f(x)^T\mathbf{d} = <\bigtriangledown f(x),\mathbf{d}>=\mathbf{d}^T \bigtriangledown f(x)\)

由此可见,当d是一个单位向量时,函数f的值在x处沿着d方向的增长率可以用内积 \(\) 表示。

局部极小点一阶必要条件

  1. 如果 \(x^*\) 是函数f在 \(\Omega\) 上的局部极小值点,则对于 \(x^*\) 处的任意可行方向d,都有: \(\mathbf{d}^Tf'(x^*) \ge 0\)
  2. 局部极小点位于约束集内部时的一阶必要条件是: \(f'(x^*)=0\)

上面两个条件的区别的关键是「边界」。

局部极小点二阶必要条件

多元实值函数f在约束 \(\Omega\) 上二阶连续可导,如果 \(x^*\) 是局部极小点,d是x的一个可行方向,且 \(d^Tf'(x^*)=0\) ,则有:

\(\mathbf{d}^TF(x^*) \mathbf{d} \ge 0\)

上面公式不难理解,其中等于0主要考虑的是边界的情况,典型的例子就是x三次方的例子,在0点一阶导数为0,二阶导数大于等于0,如果x=0想要成为极小值,那么必须可行域是x>=0。

局部极小点二阶充分条件

终于来了一个充分条件了,不容易啊。充分条件是:

  1. \(f'(x^*)=0\)
  2. \(F(x^*)>0\)

容易理解的例子还是x三次方的例子。

参考资料

《最优化导论》Edwin K.P.Chong Stanislaw H. Zak

未经允许不得转载:大数据算法 » 集合约束和无约束优化问题

评论 抢沙发

*

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注大数据算法在工业界应用

本站的GitHub关于本站