化成y-kx-b标准型：
2|y|＋|y-√3X|≤2√3
分区域讨论：
y≥0（x轴上部），y-√3≥0，y≥√3x（y=√3x上部）：
2y+y-√3x≤2√3
3y≤√3x+2√3
y≤x/√3+2/√3
y≥0（x轴上部），y-√30，y√3x（y=√3x下部）：
2y-y+√3x≤2√3
y≤-√3x+2√3
凸集和凸函数，都是为了解决凸优化问题做的铺垫。当然，在这之前，我们还应当对整个优化问题的概念体系有一个大致的了解。
一个标准的优化问题，通常都由：优化变量、目标函数、不等式约束、等式约束组成： 满足等式约束和不等式约束的值叫做优化问题的 可行域（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 ，来表达 ， 至少不比 差。
可行域无界是凸集。凸集的定义简单说来就是集合内任意两点连线上的点都在集合内，线性规划问题存在可行域，则其可行域是凸集，线性规划问题的每一个基解对应可行域的一个顶点，线性规划的最优解存在，则一定存在基本可行解是最优解。
满足某线性规划所有的约束条件（指全部前约束条件和后约束条件）的任意一组决策变量的取值，都称为该线性规划的一个可行解，
所有可行解构成的集合称为该线性规划的可行域（类似函数的定义域），记为 K 。
上一篇：为什么有的人喝茶会失眠有的人不会
下一篇：贵州医改新政策2023年最新
发表评论