钟根元p76页判断第4题求解，小弟感激不尽！

回复 华法林纳 的帖子感谢大侠的答复，，让我茅塞顿开。原来小弟的知识点概念掌握实在欠缺，这题预算线曲线是凹的，但是的确是凸集，一直思维定势，以为只有偏好的凸集就是凸集，没仔细想过，原来预算线的凸集和偏好的凸集不一样！

1凹函数是一个定义在某个向量空间的凸集C（区间）上的实值函数f。

2设f为定义在区间I上的函数，若对I上的任意两点X1&amp。

3lt。

4X2和任意的实数λ∈（0，1），总有f(λx1+。

5(1-λ)x2)≤λf(x1)+。

6(1-λ)f(x2),则f称为I上的凹函数。

7凸函数是数学函数的一类特征。

8凸函数就是一个定义在某个向量空间的凸子集C（区间）上的实值函数。

9凸函数是指一类定义在实线性空间上的函数。

10扩展资料每一个在内取值的线性变换都是凸函数，但不是严格凸函数，因为如果f是线性函数，那么f(a+。

11b)=f(a)+。

12f(b）。

13如果我们把“凸”换为“凹”，那么该命题也成立。

14每一个在内取值的仿射变换，也就是说，每一个形如f(x)=aTx+。

15b的函数，既是凸函数又是凹函数。

16每一个范数都是凸函数，这是由于三角不等式。

17如果f是凸函数，那么当t&amp。

18gt。

190时，g(x,t)=tf(x/t）是凸函数。

20单调递增但非凸的函数包括和g(x)=log(x）。

21非单调递增的凸函数包括h(x)=x2和k(x)=x。

22函数f(x)=1/xf(0)=+。

23∞，在区间（0,+。

24∞）内是凸函数，在区间（-∞，0）内也是凸函数，但是在区间（-∞，+。

25∞）内不是凸函数，这是由于x=0处的奇点。

凸集和凸函数，都是为了解决凸优化问题做的铺垫。当然，在这之前，我们还应当对整个优化问题的概念体系有一个大致的了解。

一个标准的优化问题，通常都由：优化变量、目标函数、不等式约束、等式约束组成： 满足等式约束和不等式约束的值叫做优化问题的 可行域（feasible set） 。可行域也要包含在所有函数的定义域内。

我们将可行域内 的 下确界 定义为问题的 optimal value 。 如果可行域是空集，我们取 。

如果 optimal value 在问题的可行域内可以取到，即 ，就称 是问题的 最优解（optimal point） ，注意不是所有问题都能取到最优解。所有的 optimal point 构成 最优集（optimal set） 。

如果该优化问题的最优集不为空，那么就算这个问题是 可解的（solvable） ，容易看到，并不是所有的可行域非空的优化问题都是可解的。

对于不等式约束条件，如果 ，我们就说约束条件 在 处是 inactive 的。不等式约束条件到底有没有起作用，在优化理论中被广泛研究。

优化问题的标准形式如本文式(1)。事实上，很多实际问题被提出的时候并不是标准形式，但是我们总能够将它们化为标准形式。

比如最大值问题添加一个负号就能变成最小值问题。因为凸函数具有全局的最小值点，所以习惯上我们还是考虑最小值问题。

通过一定的变换，我们可以把一个优化问题变成与它等价的另一个优化问题。有时候，这样的 *** 作可以帮助我们简化问题的求解。

通俗地说，凸优化问题，就是目标函数是凸函数，并且可行域是凸集的优化问题。 凸优化问题的标准形式，与一般优化问题的相比， 要求目标函数 和不等式约束函数 都是凸函数，并且等式约束都是线性的。

这样的约束条件，保证了 问题的可行域是凸集 。

如果目标函数不是凸的，是拟凸的，那么这个问题就是一个拟凸优化问题（ quasiconvex optimization problem ）

当目标函数和不等式约束都变成凹函数并且是求最大值，这个问题叫做凹优化问题。凹优化问题和凸优化问题本质是一样的。

凸优化，相比与一般的优化问题，有一个非常好的性质，那就是， 任何一个局部最优点（locally optimal）都是全局最优点（global optimal） 。

如果目标函数是可微的，那么还有一个判断最优点的准则：

设 是可行域， 最优 。

这个命题有着非常好的几何解释： 与 成钝角

同时 定义了一个过点 的对可行域的支撑超平面。

如果问题仅包含等式约束 ，那么 最优 。这个可以用之后介绍的KKT条件进行证明。

如果问题只是变量的非负约束，那么 最优

如果凸优化问题没有约束条件（Unconstrained problems），那么上面的命题，归结为一个广为人知的充分条件：

很多实际问题都可以归结于或者转化为几类经典的凸优化问题。包括 线性规划（LP）、二次规划（QP）、二次约束二次规划（QCQP）、二阶锥规划（SOCP）、几何规划（GP） ，接下来依次介绍它们。

线性规划应该是最简单、人们最熟悉的一种凸优化问题了。线性规划问题具有如下的典型形式： 通过一些变换，如添加松弛变量，引入正部、负部等方法，可以化为 标准形式 。 对于标准形式的线性规划问题，本科的运筹学课程应当会介绍 单纯形法 。这是根据线性规划可行域的特点提出的一种求解方法，因为线性规划的最优值如果存在那么必然取在可行域的极点上。

有几类问题可以转化为LP问题。

给定一个多面体 我们想知道这个多面体能包含的最大球的半径和球心。这个球心我们叫做该多面体的 chebyshev 中心。

我们假设这个球是 ，如果这个球在半平面 内，那么一定有： 最后我们得到相应的LP问题： 是LP问题的变量。

如果线性规划的目标函数不是线性函数，而是一个线性分式函数，这个问题就成了线性分式规划。它也可以转化成线性规划。

先做一个换元： 将上式代入约束条件，就顺利转化成线性规划了。

当LP中的目标函数是一个二次函数的时候，这个问题就成了 二次规划（quadratic program） 。注意这个时候，约束条件仍然要求是线性的。

如果不等式约束条件中的函数再变成二次函数，那么这就是 二次约束二次规划（quadratically constrained quadratic program ） 。

它们分别具有标准形式：

和： 需要注意，这样的二次规划问题，都需要矩阵 至少是半正定的。

有一些问题可以利用QP进行求解：

一定是半正定的。这是一个无约束的QP问题。

两个多面体 和 ，想要找到它们之间的最小距离。 这也是一个QP问题。

这也是一个经典的QP问题，在此从略。

二阶锥规划（second-order cone program） 具有典型形式： 乍一看，不等式约束两边同时平方一下，就能变成QCQP了。确实如此，SOCP可以看做是QCQP的推广。

椭球不确定集上的鲁棒线性优化，和高斯分布的线性机会约束，最后都转化成了一个SOCP。

几何规划（geometric program） 是一类 可以转化成凸优化问题 的非凸问题。在引入GP之前，我们还需要厘清一些概念。我们称 是一个单项式（monomial），几个单项式的和，叫做正项式（posynomial）。

一个标准的GP问题具有如下形式：

其中 都定义在 上。很显然，单项式并不一定是凸的，这并不是一个凸优化问题。作换元 ，对于新元 ，原问题具有如下形式：

如果GP的目标函数和不等式约束都是单项式的话，我们还可以通过换元将它变成LP。所以LP也可以看做是GP的一种特殊情况。

在前一章凸函数的末尾，我们通过广义不等式成功将凸函数推广到向量值函数。我们称： 为广义不等式约束下的凸优化问题的标准形式。正如一般凸优化问题的要求，这里还要求 在 上是 的。

数学的美，在于它能用精妙的理论，将许多看似没有关联的问题抽象地统一在一起。正如我们即将看到的，proper cone 的概念仿佛神来之笔，将整个优化理论的问题统一起来了。

锥形式的优化问题是一种很 general 的情况。在数学里面，我们认为一般性的结论是要好于特殊性的结论的。锥规划就是把很多经典的优化问题的形式抽象出来的一种表示方法。

锥规划一般都具有如下的典型形式： 线性规划显然是锥规划的一种特殊情况。

SOCP可以用锥规划的形式表示： 其中 是一个二阶锥： 。

半定规划（SDP）是一类非常非常重要的凸优化问题！在 Conic form problems 的基础上，令 为半正定矩阵锥，因为 ，可以将 看做 的线性函数。继而，我们有 这称为SDP的 标准形式 。SDP也有如下的形式： 关于矩阵的线性不等式我们叫做 linear matrix inequality ，在很多文献上简写为 LMI 。

广义不等式不仅可以作用在约束条件上，还能作用在目标函数上。令 是一个多元向量值函数，在 的一个凸集上 ，我们希望找到在一个广义不等式下的 的最小值/极小值。

这样的问题叫做向量优化问题。这样子的目的就在于，如果目标是多维的，可以通过定义一个 proper cone ，来表达 ， 至少不比 差。

　

　　其几何意义表示为：如果集合C中任意2个元素连线上的点也在集合C中，则C为凸集。其示意图如下所示：

　　

　　常见的凸集有：

　　n维实数空间；一些范数约束形式的集合；仿射子空间；凸集的交集；n维半正定矩阵集；这些都可以通过凸集的定义去证明。

　　凸函数的定义为：

　　

　　其几何意义表示为函数任意两点连线上的值大于对应自变量处的函数值，示意图如下：

　　

　　凸函数的一阶充要条件为：

　　

　　其中要求f一阶可微。

　　二阶充要条件为：

　　

　　其中要求f二阶可微，表示二阶导数需大于0才是凸函数。

按照上面的两个定义，如果f(x)=x^2肯定是凸函数，而g(x) = -x^2是非凸函数。也就是说开口向下的函数是非凸函数，但是对于这种情况可以通过添加负号变成凸函数，从而求解。

　　常见的凸函数有：指数函数族；非负对数函数；仿射函数；二次函数；常见的范数函数；凸函数非负加权的和等。这些可以采用上面2个充要条件或者定义去证明。

　　凸优化问题（OPT）的定义为：

　　

　　即要求目标函数是凸函数，变量所属集合是凸集合的优化问题。或者目标函数是凸函数，变量的约束函数是凸函数（不等式约束时），或者是仿射函数（等式约束时）。

　　对于凸优化问题来说，局部最优解就是全局最优解。

　　常见的凸优化问题包括：

　　线性规划（LP）：该问题是优化下面的式子：

　

　　其中那个不常见的奇怪符号表示按元素小于等于，后面出现类似符号可以类似理解。

　　二次规划（QP）：该问题是优化下面的式子：

　

　　二次约束的二次规划（QCQP）：该问题是优化下面的式子：

　

　　半正定规划（SDP）：该问题是优化下面的式子：

　　

　　按照文章说SDP在机器学习领域应用很广，最近很流行，不过我好像没太接触到过。