凸优化第四章凸优化问题 4.2 凸优化 |
您所在的位置:网站首页 › 什么是最优解,最优解唯一吗 › 凸优化第四章凸优化问题 4.2 凸优化 |
4.2 凸优化
标准形式的凸优化问题局部最优解与全局最优解可微函数
也可以写成: 重要性质:凸优化问题的可行集也是凸集(凸函数定义域——凸集的交集)。 证明:可行集是满足不等式约束和等式约束的点的集合,首先不等式约束函数 稍微改变符号,我们也称: 为凸优化问题,如果目标函数 考虑 首先判断可行集,由两个约束函数可推出
但可以得到其等价的凸优化问题: 凸优化问题的基础性质:其任意局部最优解也是全局最优解。 证明:假设x是局部最优解,且存在一个可行点y, 因为x是局部最优解,故存在一些R, 因为凸优化问题的可行集是凸集,故取 因为 此时令 而根据凸函数性质: 与上式矛盾。故凸优化问题中局部最优解就是全局最优解。 4.2.3 可微函数当 如果x是最优解,对任意的y属于可行集,首先满足
可行集就是 证明:因为
可行解的最优性条件:对任意的y属于可行集,即 将x、y代入最优条件:
又因为 上述最优性条件也可以拉格朗日乘子法得到,令
当x为最优解时,最优性条件: 而 将最优条件写成: 所以要使上式恒成立要求 即 保持问题凸性的转换有:消除等式约束、引入等式约束、引入松弛变量、上境图问题形式、极小化部分变量 消除等式约束等价于:
等价于:
那么问题变为: 凸优化问题的上境图形式: 极小化部分变量 极小化凸函数的部分变量将保持凸性不变, 等价于 其中:
凸优化与拟凸优化问题最重要的不同在于拟凸优化问题的局部最优解不一定是全局最优解。 如上图 如果 要注意的是,此条件仅仅是最优性的充分条件,而凸问题的可行性准则是充要条件。 通过可行性问题求解拟凸优化问题在3.4.5节中我们知道可以用一族凸函数不等式表示拟凸函数的下水平集,这是解决拟凸优化问题的一般方法。 选择一族凸函数 注意:t固定时,每个 用p*表示拟凸优化问题的最优值。如果可行性问题: 是可行的,我们有 因此,我们可以通过求解凸可行性问题来判断拟凸优化问题的最优值p*大于或小于给定值t。如果凸可行性问题是可行的,则有 上面的想法可以用来构造解决拟凸优化问题的一个简单算法:使用二分法并在每步中求解凸可行性问题。 算法思想:有一个区间,包含最优解,取区间的中点,判断最优解在上半区间还是下半区间,然后更新区间,不断将区间缩小为原来的一般直到找到足够小的区间。 算法: 给定 重复以下步骤: 求解凸可行性问题 如果问题可行,u=t,否则l=t 直至
参考:https://blog.csdn.net/wangchy29/article/details/86577267 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |