罚函数凸优化Python 最优化 凸函数

python非线性规划用什么模块

python非线性规划用什么模块本文使用SciPy的optimize模块来求解非线性规划问题，结合实际例子，引入非线性规划问题的求解算法及相应函数的调用。

创新互联是一家集成都做网站、网站制作、网站页面设计、网站优化SEO优化为一体的专业的建站公司，已为成都等多地近百家企业提供网站建设服务。追求良好的浏览体验,以探求精品塑造与理念升华,设计最适合用户的网站页面。 合作只是第一步，服务才是根本,我们始终坚持讲诚信，负责任的原则，为您进行细心、贴心、认真的服务,与众多客户在蓬勃发展的市场环境中,互促共生。

本文提纲一维搜索／单变量优化问题

无约束多元优化问题

非线性最小二乘问题

约束优化问题

非线性规划问题的目标函数或约束条件是非线性的。本文使用SciPy的optimize模块来求解非线性规划问题。

目标函数和约束条件是否连续光滑是非常重要的性质，这是因为如果光滑，则所有决策变量可微，多变量函数的偏导数组成的向量为梯度，梯度是指向目标函数增长最快的方向。将目标函数梯度作为搜索方向，对非线性规划问题的求解具有重要的意义。这些函数或其导数\梯度的不连续性给许多现有的非线性优化问题的求解带来了困难。在下文中，我们假设这些函数是连续且光滑的。

# Importing Modules

from scipy import optimize

import matplotlib.pyplot as plt

import numpy as np

import sympy

1、一维搜索／单变量优化问题(Univariate Optimization)

无约束非线性规划最简单的形式是一维搜索。一维搜索通常作为多维优化问题中的一部分出现，比如梯度下降法中每次最优迭代步长的估计。求解一维搜索常用的两类方法是函数逼近法和区间收缩法。其中函数逼近法是指用较简单的函数近似代替原来的函数，用近似函数的极小点来估计原函数的极小点，比如牛顿法；区间收缩法对于一个单谷函数通过迭代以不断缩小该区间的长度，当区间长度足够小时，可将该区间中的一点作为函数的极小点，比如黄金分割法。

e.g. 最小化一个单位体积的圆柱体的表面积。

r, h = sympy.symbols("r, h")

Area = 2 * sympy.pi * r**2 + 2 * sympy.pi * r * h

Volume = sympy.pi * r**2 * h

凸优化(四)——问题求解

凸优化主要学习《凸优化》(Stephen Boyd等著，王书宁等译)[1]这本书。学习过程中，对其内容的理解时有困惑，也参考一些其他书籍资料。笔者尽量将这部分知识整理地简洁明了，成此系列笔记。

凸优化之所以如此重要，是因为凸优化的重要特性： 凸优化的任意局部最优解也是全局最优解 。

对于少数一些简单的凸优化问题，可以利用最优性准则通过解析来求解。但对于大多数凸优化问题来讲，是没有办法通过解析来求解的。

下降方法中，有两个问题需要解决：确定搜索步长和确定搜索方向。确定搜索步长的方法和算法有： 固定步长搜索 、 精确直线搜索 和 回溯直线搜索 。确定搜索方向的方法和算法有： 梯度下降方法 、 最速下降方法 和 牛顿法。

步长值根据经验设定，为了防止算法震荡，值应当较小。优点：直观、简单；缺点：收敛速度慢。

比较常用的是回溯直线搜索，大概思路是，用迭代方法求得的步长只要能使目标函数有足够的减少即可。详见《 凸优化(五)——回溯直线搜索 》。

利用目标函数的一阶泰勒展开近似优化过程，进而确定学习方向。详见《 凸优化(六)——最速下降法 》。

利用目标函数的二阶泰勒展开近似表示目标函数，通过求解这个二次函数的极小值来确定搜索方向。详见《 凸优化(七)——牛顿法 》。

任何等式约束优化问题都可以通过消除等式约束转化为等价的无约束优化问题，然后利用无约束的方法求解。

利用无约束优化问题求解对偶问题，然后从对偶解中复原等式约束问题的解。详见《 凸优化(八)——Lagrange对偶问题 》。

详见《凸优化(七)——牛顿法》。

利用无约束优化问题求解对偶问题，然后从对偶解中复原不等式约束问题的解。《 凸优化(八)——Lagrange对偶问题 》。

主要思路：引进的惩罚函数的在可行域的边界上设置障碍，使求解的迭代过程始终在可行域内部进行。[2]

这里暂不详述，待有时间再学习整理。

[1]、《凸优化》，Stephen Boyd等著，王书宁等译

[2]、 《什么是内点法》

凸优化(一)——概述

凸优化(二)——凸集

凸优化(三)——凸函数

凸优化(四)——问题求解

凸优化(五)——回溯直线搜索

凸优化(六)——最速下降法

凸优化(七)——牛顿法

凸优化(八)——Lagrange对偶问题

2016-02-29 第一次发布

2016-08-07 修改文章名，重新整理完善

凸，凹函数在求解非线性优化问题中有什么特殊作用

有区别的。非线性规划grg又称罚函数法，是求解约束极小化问题的较好的算法，其基本原理是在原目标函数中加上一个罚函数，而得到一个增广目标函数；非线性规划内点法又称障碍函数法，是一种求解线性规划或非线性凸优化问题的算法；它们都是将原问题转化为一系列无约束问题来求解；这两种构造方法各有其优缺点；相对而言，非线性规划grg式结构较简单，但其导数（如果可导的话）复杂，更适用于不利用导数的无约束极小化算法；而非线性规划内点法式虽然较复杂，但是导函数却相对较简单，因而更适用于利用导数的无约束极小化算法。

如何利用 Python 实现 SVM 模型

我先直观地阐述我对SVM的理解，这其中不会涉及数学公式，然后给出Python代码。

SVM是一种二分类模型，处理的数据可以分为三类：

线性可分，通过硬间隔最大化，学习线性分类器

近似线性可分，通过软间隔最大化，学习线性分类器

线性不可分，通过核函数以及软间隔最大化，学习非线性分类器

线性分类器，在平面上对应直线；非线性分类器，在平面上对应曲线。

硬间隔对应于线性可分数据集，可以将所有样本正确分类，也正因为如此，受噪声样本影响很大，不推荐。

软间隔对应于通常情况下的数据集（近似线性可分或线性不可分），允许一些超平面附近的样本被错误分类，从而提升了泛化性能。

如下图：

实线是由硬间隔最大化得到的，预测能力显然不及由软间隔最大化得到的虚线。

对于线性不可分的数据集，如下图：

我们直观上觉得这时线性分类器，也就是直线，不能很好的分开红点和蓝点。

但是可以用一个介于红点与蓝点之间的类似圆的曲线将二者分开，如下图：

我们假设这个黄色的曲线就是圆，不妨设其方程为x^2+y^2=1，那么核函数是干什么的呢？

我们将x^2映射为X，y^2映射为Y，那么超平面变成了X+Y=1。

那么原空间的线性不可分问题，就变成了新空间的（近似）线性可分问题。

此时就可以运用处理（近似）线性可分问题的方法去解决线性不可分数据集的分类问题。

---------------------------------------------------------------------------------------------------------------------------

以上我用最简单的语言粗略地解释了SVM，没有用到任何数学知识。但是没有数学，就体会不到SVM的精髓。因此接下来我会用尽量简洁的语言叙述SVM的数学思想，如果没有看过SVM推导过程的朋友完全可以跳过下面这段。

对于求解（近似）线性可分问题：

由最大间隔法，得到凸二次规划问题，这类问题是有最优解的（理论上可以直接调用二次规划计算包，得出最优解）

我们得到以上凸优化问题的对偶问题，一是因为对偶问题更容易求解，二是引入核函数，推广到非线性问题。

求解对偶问题得到原始问题的解，进而确定分离超平面和分类决策函数。由于对偶问题里目标函数和分类决策函数只涉及实例与实例之间的内积，即xi,xj。我们引入核函数的概念。

拓展到求解线性不可分问题：

如之前的例子，对于线性不可分的数据集的任意两个实例：xi,xj。当我们取某个特定映射f之后，f(xi)与f(xj)在高维空间中线性可分，运用上述的求解（近似）线性可分问题的方法，我们看到目标函数和分类决策函数只涉及内积f(xi),f(xj)。由于高维空间中的内积计算非常复杂，我们可以引入核函数K(xi,xj)=f(xi),f(xj)，因此内积问题变成了求函数值问题。最有趣的是，我们根本不需要知道映射f。精彩！

我不准备在这里放推导过程，因为已经有很多非常好的学习资料，如果有兴趣，可以看：CS229 Lecture notes

最后就是SMO算法求解SVM问题，有兴趣的话直接看作者论文：Sequential Minimal Optimization:A Fast Algorithm for Training Support Vector Machines

我直接给出代码：SMO+SVM

在线性可分数据集上运行结果：

图中标出了支持向量这个非常完美，支持向量都在超平面附近。

在线性不可分数据集上运行结果（200个样本）：

核函数用了高斯核，取了不同的sigma

sigma=1，有189个支持向量，相当于用整个数据集进行分类。

sigma=10，有20个支持向量，边界曲线能较好的拟合数据集特点。

我们可以看到，当支持向量太少，可能会得到很差的决策边界。如果支持向量太多，就相当于每次都利用整个数据集进行分类，类似KNN。