凸优化－优化问题 – 我爱机器学习

25 September 2015

1. 凸优化问题

优化问题的定义为：

其中，

。

• f被称为目标函数（objective or criterion function）；
• g被称为约束函数（inequality constraint function）；
• 满足
  
  
  
  
  
  
  
  且
  
  
  
  
  
  
  
  的点称为可行解（feasible point）；
• 所有可行解中函数
  
  
  
  
  最小的点称为最优值（optimal value），记为
  
  
  ；
• 使得函数
  
  
  
  
  取得
  
  
  的点
  
  称为最优解（optimal point、solution或minimizer），当然，不是所有凸函数都存在最优解，即解为空，例如直线就不存在；
• 如果点
  
  满足
  
  
  
  
  
  
  
  
  
  ，则称点
  
  为
  
  
  
  
  
  
  
  
  
  
  
  
  解。

凸优化问题相对优化问题的定义而言，要求函数

和

是凸函数，

是仿射函数(

)。

对于仿射集和凸集的差别在凸优化－凸集一文也做了分析，二者的差别就在于凸集是线段而仿射集是直线（一维情况下）。很明显，求解凸函数的极小值（convex minimization）和凹函数的极大值（concave maximization）都是凸优化问题（convex optimization problem）。

2. 凸优化解的集合

我们定义凸优化解的集合（Convex solution sets）为

，记为：

1. 凸优化解的集合有一个关键性质就是凸优化解的集合必为凸集。因为，如果凸优化问题不存在最优解，那么解空间为空集，为凸集；如果凸优化问题仅存在一个解，那必定为多维上的一点，而空间上的一点属于凸集；如果存在两个解，那么必定存在一条线段或者一个平面的解的集合，而线段或者平面都是凸集。接下来，就证明为什么存在两个解，就必然会存在多个解：

证明：假设

都是优化问题的解，那么对于

，其中

，则：

• 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  ;
• 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  ;
• 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  。

因此，点

也是优化问题

的一个解，所以点

之间必然存在两点连线上的任意点都是优化问题的最优解。故，凸优化问题解的集合为凸集。也就意味着如果凸优化问题存在两个包含两个以上的解时，那么其必定包含无数个解。对于这一点，其实不是特别好想象。

1. 凸优化解的集合还有另外一个性质就是：如果优化函数为严格凸函数，那么它的最优解必是唯一的，即解空间
   
   
   
   
   只包含一个元素，如二次优化问题。

3. 凸优化问题实例：LASSO

熟悉机器学习算法里面的线性回归或者逻辑回归的同学因该明白LASSO问题，其定义为：

LASSO是Tibshirani（对就是Tibshirani）在1996年JRSSB上的一篇文章上《Regression shrinkage and selection via lasso》提出的。所谓lasso，其全称是least absolute shrinkage and selection operator，其含义是在限制了

的情况下，求使得残差平和达到最小的参数的估值。Tibshirani指出，对于回归算法，当

足够小的时候，会使得某些回归系数的估值是0，可以起到变量选择的作用，是逐步回归的一种表现。

因此，对于LASSO算法，其是否是凸优化问题？它的解集合是否是唯一的点？

答案是，LASSO问题是凸优化问题，因为

和

均是凸函数，因此该问题为凸优化问题；如果样本数目

大于特征数目

，且X满秩，那么

，关于

二阶微分恒为半正定p.s.d.，因此，解是唯一的；但是，如果样本数目

小于特征数目

，那么会造成高维特征空间上的维数灾难问题，此时，X为奇异矩阵，则解不唯一。

另一个实例是SVM算法，SVM算法的理论部分我就不多介绍了，会在机器学习算法篇章中对SVM做着重介绍，如果我们记SVM为：

其中，

为下图两个虚线边界的距离，

为引入分类错误的代价，代表下图错分样本点距正确分类边界的距离。具体如下图：

那么，该问题是否为凸优化问题呢？它的解是否是唯一？

答案是，SVM目标函数是凸优化问题，但是，它的解并不唯一，因为它不是严格凸函数。有兴趣的同学可以留言来解释为什么SVM是凸优化问题！

4. 局部最小值就是全局最小值

局部最优解的定义为：如果

，使得360docimg_501_360docimg_502_360docimg_503_360docimg_504_360docimg_505_360docimg_506_360docimg_507_360docimg_508_360docimg_509_，其中y满足360docimg_510_360docimg_511_360docimg_512_360docimg_513_360docimg_514_360docimg_515_360docimg_516_360docimg_517_，则点x为优化问题的局部最优解（locally optimal）。

对于凸优化问题，凸函数有一个特别的性质，即局部最优解是全剧最优解（local minima are global minima），即如果360docimg_518_360docimg_519_360docimg_520_，同时360docimg_521_满足所有约束，那么对于局部360docimg_522_360docimg_523_360docimg_524_360docimg_525_360docimg_526_360docimg_527_360docimg_528_360docimg_529_360docimg_530_360docimg_531_，当360docimg_532_360docimg_533_360docimg_534_360docimg_535_360docimg_536_360docimg_537_360docimg_538_360docimg_539_360docimg_540_时，对于所有可行解360docimg_541_360docimg_542_360docimg_543_360docimg_544_360docimg_545_360docimg_546_360docimg_547_360docimg_548_360docimg_549_360docimg_550_360docimg_551_。相反，非凸优化问题则不具有该性质，如下图所示。

360docimg_552_

那么我们需要证明的是为什么凸优化问题的局部最优值就是全局最优值？

证明：这里，我们采用反证法来证明该理论，假设x为凸优化问题的局部最优解，意味着函数在360docimg_553_范围内的点的值都小于360docimg_554_360docimg_555_360docimg_556_360docimg_557_。如果我们假设定理是错误的，那么必然存在一点360docimg_558_，使得，且360docimg_559_360docimg_560_360docimg_561_360docimg_562_360docimg_563_360docimg_564_360docimg_565_360docimg_566_。

此时，假设存在一点360docimg_567_，使得360docimg_568_360docimg_569_360docimg_570_360docimg_571_360docimg_572_360docimg_573_360docimg_574_360docimg_575_360docimg_576_360docimg_577_360docimg_578_，其中360docimg_579_360docimg_580_360docimg_581_360docimg_582_360docimg_583_360docimg_584_360docimg_585_，那么：

• 360docimg_586_360docimg_587_360docimg_588_，因为360docimg_589_360docimg_590_360docimg_591_，同时360docimg_592_360docimg_593_360docimg_594_，二者线性组合也必然存在于D；
• 360docimg_595_360docimg_596_360docimg_597_360docimg_598_360docimg_599_360docimg_600_360docimg_601_360docimg_602_360docimg_603_360docimg_604_360docimg_605_360docimg_606_360docimg_607_360docimg_608_360docimg_609_360docimg_610_360docimg_611_360docimg_612_360docimg_613_360docimg_614_360docimg_615_360docimg_616_360docimg_617_360docimg_618_360docimg_619_，因为360docimg_620_360docimg_621_360docimg_622_360docimg_623_360docimg_624_，360docimg_625_360docimg_626_360docimg_627_360docimg_628_360docimg_629_360docimg_630_360docimg_631_；
• 360docimg_632_360docimg_633_360docimg_634_360docimg_635_360docimg_636_360docimg_637_360docimg_638_360docimg_639_360docimg_640_360docimg_641_360docimg_642_360docimg_643_360docimg_644_360docimg_645_360docimg_646_360docimg_647_360docimg_648_360docimg_649_360docimg_650_360docimg_651_360docimg_652_360docimg_653_360docimg_654_360docimg_655_360docimg_656_360docimg_657_360docimg_658_360docimg_659_360docimg_660_360docimg_661_360docimg_662_360docimg_663_360docimg_664_360docimg_665_360docimg_666_360docimg_667_360docimg_668_360docimg_669_360docimg_670_360docimg_671_360docimg_672_360docimg_673_360docimg_674_360docimg_675_360docimg_676_360docimg_677_360docimg_678_360docimg_679_360docimg_680_360docimg_681_360docimg_682_360docimg_683_。

因此，意味着360docimg_684_同样也是是凸优化问题的可行解。

然后，因为点360docimg_685_在360docimg_686_360docimg_687_360docimg_688_360docimg_689_360docimg_690_360docimg_691_360docimg_692_内均成立，所以我们可以假设360docimg_693_足够小，但大于0，使得360docimg_694_可以落在点360docimg_695_以360docimg_696_为半径的圆内，这时，对于凸优化问题中可行解的两个点360docimg_697_360docimg_698_360docimg_699_之间的点360docimg_700_，我们可以得到如下公式：
360docimg_701_360docimg_702_360docimg_703_360docimg_704_360docimg_705_360docimg_706_360docimg_707_360docimg_708_360docimg_709_360docimg_710_360docimg_711_360docimg_712_360docimg_713_360docimg_714_360docimg_715_360docimg_716_360docimg_717_360docimg_718_360docimg_719_360docimg_720_
又因为360docimg_721_360docimg_722_360docimg_723_，且之前假设，所以，因此，这就与之前最开始假设x为局部最优解的定义相违背，因此，我们最终证明得到local minima are global minima。

5. 凸优化问题的一些性质和Trick

• First-order optimality condition：对于凸优化问题360docimg_724_360docimg_725_360docimg_726_360docimg_727_360docimg_728_360docimg_729_360docimg_730_360docimg_731_360docimg_732_360docimg_733_360docimg_734_360docimg_735_360docimg_736_360docimg_737_360docimg_738_360docimg_739_360docimg_740_360docimg_741_360docimg_742_360docimg_743_，如果函数360docimg_744_可微，那么当且仅当满足下式时，可行解（feasible point）360docimg_745_为最优解。

360docimg_746_360docimg_747_360docimg_748_360docimg_749_360docimg_750_360docimg_751_360docimg_752_360docimg_753_360docimg_754_360docimg_755_360docimg_756_360docimg_757_360docimg_758_360docimg_759_360docimg_760_360docimg_761_360docimg_762_

• Partial optimization：如果360docimg_763_360docimg_764_360docimg_765_360docimg_766_360docimg_767_360docimg_768_360docimg_769_360docimg_770_360docimg_771_360docimg_772_360docimg_773_360docimg_774_360docimg_775_360docimg_776_360docimg_777_360docimg_778_，那么优化问题

360docimg_779_360docimg_780_360docimg_781_360docimg_782_360docimg_783_360docimg_784_360docimg_785_360docimg_786_360docimg_787_360docimg_788_360docimg_789_360docimg_790_360docimg_791_360docimg_792_360docimg_793_360docimg_794_360docimg_795_360docimg_796_360docimg_797_360docimg_798_360docimg_799_360docimg_800_360docimg_801_360docimg_802_360docimg_803_360docimg_804_360docimg_805_360docimg_806_360docimg_807_360docimg_808_360docimg_809_360docimg_810_360docimg_811_360docimg_812_360docimg_813_360docimg_814_
等价于：
360docimg_815_360docimg_816_360docimg_817_360docimg_818_360docimg_819_360docimg_820_360docimg_821_360docimg_822_360docimg_823_360docimg_824_360docimg_825_360docimg_826_360docimg_827_360docimg_828_360docimg_829_360docimg_830_360docimg_831_360docimg_832_360docimg_833_360docimg_834_360docimg_835_360docimg_836_360docimg_837_
其中360docimg_838_360docimg_839_360docimg_840_360docimg_841_360docimg_842_360docimg_843_360docimg_844_360docimg_845_360docimg_846_360docimg_847_360docimg_848_360docimg_849_360docimg_850_360docimg_851_360docimg_852_360docimg_853_360docimg_854_360docimg_855_360docimg_856_360docimg_857_360docimg_858_360docimg_859_360docimg_860_360docimg_861_360docimg_862_360docimg_863_360docimg_864_360docimg_865_360docimg_866_；

SVM采用的hinge loss就是利用的partial optimization的思想。如果我们把SVM优化问题的目标函数记为：
360docimg_867_360docimg_868_360docimg_869_360docimg_870_360docimg_871_360docimg_872_360docimg_873_360docimg_874_360docimg_875_360docimg_876_360docimg_877_360docimg_878_360docimg_879_360docimg_880_360docimg_881_360docimg_882_360docimg_883_360docimg_884_360docimg_885_360docimg_886_360docimg_887_360docimg_888_360docimg_889_360docimg_890_360docimg_891_360docimg_892_360docimg_893_360docimg_894_360docimg_895_360docimg_896_360docimg_897_360docimg_898_360docimg_899_360docimg_900_360docimg_901_360docimg_902_360docimg_903_360docimg_904_360docimg_905_360docimg_906_360docimg_907_360docimg_908_360docimg_909_360docimg_910_360docimg_911_360docimg_912_360docimg_913_360docimg_914_360docimg_915_360docimg_916_360docimg_917_360docimg_918_360docimg_919_
那么我们可以将约束改写为360docimg_920_360docimg_921_360docimg_922_360docimg_923_360docimg_924_360docimg_925_360docimg_926_360docimg_927_360docimg_928_360docimg_929_360docimg_930_360docimg_931_360docimg_932_360docimg_933_360docimg_934_360docimg_935_360docimg_936_360docimg_937_360docimg_938_360docimg_939_360docimg_940_360docimg_941_360docimg_942_，SVM在优化过程中选用的hinge form就是将约束中的大于等于改写为等于，即:
360docimg_943_360docimg_944_360docimg_945_360docimg_946_360docimg_947_360docimg_948_360docimg_949_360docimg_950_360docimg_951_360docimg_952_360docimg_953_360docimg_954_360docimg_955_360docimg_956_360docimg_957_360docimg_958_360docimg_959_360docimg_960_360docimg_961_360docimg_962_360docimg_963_360docimg_964_360docimg_965_
因此，优化目标函数就变为：
360docimg_966_360docimg_967_360docimg_968_360docimg_969_360docimg_970_360docimg_971_360docimg_972_360docimg_973_360docimg_974_360docimg_975_360docimg_976_360docimg_977_360docimg_978_360docimg_979_360docimg_980_360docimg_981_360docimg_982_360docimg_983_360docimg_984_360docimg_985_360docimg_986_360docimg_987_360docimg_988_360docimg_989_360docimg_990_360docimg_991_360docimg_992_360docimg_993_360docimg_994_360docimg_995_360docimg_996_360docimg_997_360docimg_998_360docimg_999_360docimg_1000_360docimg_1001_360docimg_1002_
上式就是SVM求解目标函数的最终形式，可称为hinge form of SVMs。

• Transformations of variables：如果函数360docimg_1003_为单调递增函数，那么凸优化问题等价于：

360docimg_1004_360docimg_1005_360docimg_1006_360docimg_1007_360docimg_1008_360docimg_1009_360docimg_1010_360docimg_1011_360docimg_1012_360docimg_1013_360docimg_1014_360docimg_1015_360docimg_1016_360docimg_1017_360docimg_1018_360docimg_1019_360docimg_1020_360docimg_1021_360docimg_1022_360docimg_1023_360docimg_1024_360docimg_1025_360docimg_1026_360docimg_1027_360docimg_1028_360docimg_1029_360docimg_1030_360docimg_1031_360docimg_1032_360docimg_1033_360docimg_1034_360docimg_1035_360docimg_1036_360docimg_1037_360docimg_1038_360docimg_1039_360docimg_1040_360docimg_1041_360docimg_1042_360docimg_1043_360docimg_1044_360docimg_1045_360docimg_1046_360docimg_1047_
优化方法中的最大似然估计MLE就采用log函数对目标函数进行变换，就是采用的这个思想。

• Introducing slack variables：凸优化可以通过引入松弛因子（slack variables）来消除约束（constraints）中的不等式，我们可以把凸优化问题转换为：

360docimg_1048_360docimg_1049_360docimg_1050_360docimg_1051_360docimg_1052_360docimg_1053_360docimg_1054_360docimg_1055_360docimg_1056_360docimg_1057_360docimg_1058_360docimg_1059_360docimg_1060_360docimg_1061_360docimg_1062_360docimg_1063_360docimg_1064_360docimg_1065_360docimg_1066_360docimg_1067_360docimg_1068_360docimg_1069_360docimg_1070_360docimg_1071_360docimg_1072_360docimg_1073_360docimg_1074_360docimg_1075_360docimg_1076_360docimg_1077_360docimg_1078_360docimg_1079_360docimg_1080_360docimg_1081_360docimg_1082_360docimg_1083_360docimg_1084_360docimg_1085_360docimg_1086_360docimg_1087_360docimg_1088_360docimg_1089_360docimg_1090_360docimg_1091_360docimg_1092_360docimg_1093_360docimg_1094_360docimg_1095_360docimg_1096_360docimg_1097_
SVM算法都引入slack variables来允许训练误差的出现，防止模型过拟合。

5. 凸优化问题分类

凸优化问题根据目标函数和约束函数的形式分为：

• linear programs：线性规划；
• Quadratic programs：二次规划；
• Semidefinite programs：半正定规划；
• Cone programs：锥规划。

Ryan教授给了一个非常形象的例子来解释凸优化问题在优化问题领域的位置，以及以上几种优化问题间的关联关系，如下图：

360docimg_1098_

线性规划问题（LPs）定义是优化问题满足以下形式，线性规划的实例包括diet problem, transportation problem, basis pursuit和Dantzig selector等：
360docimg_1099_360docimg_1100_360docimg_1101_360docimg_1102_360docimg_1103_360docimg_1104_360docimg_1105_360docimg_1106_360docimg_1107_360docimg_1108_360docimg_1109_360docimg_1110_360docimg_1111_360docimg_1112_360docimg_1113_360docimg_1114_360docimg_1115_360docimg_1116_360docimg_1117_360docimg_1118_360docimg_1119_360docimg_1120_360docimg_1121_360docimg_1122_
二次规划问题（QPs）定义是优化问题满足以下形式，二次规划的实例包括portfolio optimization, lasso, SVM等：
360docimg_1123_360docimg_1124_360docimg_1125_360docimg_1126_360docimg_1127_360docimg_1128_360docimg_1129_360docimg_1130_360docimg_1131_360docimg_1132_360docimg_1133_360docimg_1134_360docimg_1135_360docimg_1136_360docimg_1137_360docimg_1138_360docimg_1139_360docimg_1140_360docimg_1141_360docimg_1142_360docimg_1143_360docimg_1144_360docimg_1145_360docimg_1146_360docimg_1147_360docimg_1148_360docimg_1149_360docimg_1150_360docimg_1151_360docimg_1152_360docimg_1153_
其中，360docimg_1154_360docimg_1155_360docimg_1156_是半正定。这里需要注意的是，当Q不是半正定的时候，上述问题则不属于凸优化问题。同样，当360docimg_1157_360docimg_1158_360docimg_1159_时，二次规划问题就变为线性规划问题。

半正定规划问题（SDPs）定义是优化问题满足以下形式：
360docimg_1160_360docimg_1161_360docimg_1162_360docimg_1163_360docimg_1164_360docimg_1165_360docimg_1166_360docimg_1167_360docimg_1168_360docimg_1169_360docimg_1170_360docimg_1171_360docimg_1172_360docimg_1173_360docimg_1174_360docimg_1175_360docimg_1176_360docimg_1177_360docimg_1178_360docimg_1179_360docimg_1180_360docimg_1181_360docimg_1182_360docimg_1183_360docimg_1184_360docimg_1185_360docimg_1186_360docimg_1187_360docimg_1188_360docimg_1189_360docimg_1190_360docimg_1191_360docimg_1192_360docimg_1193_
其中，360docimg_1194_360docimg_1195_360docimg_1196_360docimg_1197_360docimg_1198_，同时，360docimg_1199_360docimg_1200_360docimg_1201_360docimg_1202_360docimg_1203_360docimg_1204_。从上面的定义可以看出，和线性规划的定义基本一样，这里SDPs要求360docimg_1205_360docimg_1206_为矩阵，而LPs为向量，所以线性规划一定隶属于半正定规划的一个特例。