凸优化
总结
初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf
1基本概念
1.1） 凸集合：
是凸集，如果其满足：
几何解释：
，则线段[x,y]上的任何点都
1.2） 仿射集：
是仿射集，如果其满足：
几何解释：
，则穿过x, y的直线上的任何点都
1.3） 子空间：
是子空间，如果其满足：
几何解释：
，则穿过x, y，0的平面上的任何点都
1.4） 凸锥：
是凸锥，如果其满足：
几何解释：
，则x, y之间的扇形面的任何点都
集合C是凸锥的充分必要条件是集合C中的元素的非负线性组合仍在C中，作为一般化结果，其中非负线性组合的数目可以推广到无穷
1.5） 超平面：满足
的仿射集，如果b=0则变为子空间
1.6） 半空间：满足
的凸集，如果b=0则变为凸锥
1.7） 椭球体：
EMBED Equation.DSMT4 球心
1.8） 范数：f：Rn—R是一种范数，如果对所有的
满足
范数分类
· 1范数
· 2范数
· 3无穷范数
1.9） 有效域：集合
1.10） 水平集：
，其中
为一标量
1.11） 上镜图：函数
的上镜图由下面的集合给定
给出的
给出的子集。
1.12） 多面体：有限数目半空间集合的交集
1.13） 共轭函数：f：Rn—R上的共轭函数定义为：
，
是凸函数即使
不是
1.14） Jensen 不等式： f：Rn—R上的凸函数
· 两点
· 多点
· 连续
· 一般情况
1.15） 凸函数：设C是
上的凸子集，如果
则函数
称为凸函数
凸函数一阶可微定义
如果f一阶可微，则f是凸函数等价于对于所有的
，
凸函数二阶可微定义
如果f二阶可微，则f是凸函数等价于
，
常见的凸，凹函数
· 线性函数和仿射函数都是凸函数
· 二次函数
是凸函数等价于
· 任意求范数操作是凸函数
·
在
是凸的
; 凹的
·
在
是凹的,
在
是凸的
·
是凸的
· |x|, max(0, x), max(0,−x) 是凸的
·
是凹的
2规划问题分类
2.1） 线性规划linear program
目标函数和等式限制函数都是仿射函数的规划
Minimize
Subject to
目标函数中d可以消除，不会改变其凸性。线性规划的几何解释是仿射集形成的多面体上求解目标函数的最小值。应用中存在等效问题转化，不等式限制变等式限制，等式限制中的变量求出其反函数表达式来消除等式限制，以及找到一些松弛变量，例如如果存在最优解x，必然相应的-f(x)小于0。
例子：切比雪夫多面体求解中心
注：多项式max fi(x)
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
比较常用，实现凸优化问题的等效变化，可以使得问题得以简化，例如将目标函数设为新变量进行优化，求解新变量的反函数实现原优化问题解
2.3） 二次规划quadratic program (QP)
目标函数是二次函数，限制条件是仿射函数
Minimize
Subject to
其中P是半正定矩阵，上式中的不等式限制
也可以是二次函数限制
，此时优化问题转化为二次约束二次规划quadratically constrained quadratic program (QCQP)问题。此外，线性规划可以视为二次规划的特殊情况(P=0)。二次规划问题首先是解决约束P是半正定的，则问题马上可以得以解决。否则，问题的求解形式变得比较困难，即使任意一个
不是半征定的。QCQP问题当i=1时，不用考虑凸和非凸问题，可以求解。对于i=2的情况，如果有一个
不是半征定，可以通过SDP问题，进行求解（Luo on research）。i其他情况，如果有一个
不是半征定，NP-hard问题，难以解决。想办法求最有近似解。
几何解释
例子：带限制下的最小误差问题：
，还有两个多面体之间的距离问题，此外，可以考虑二次规划和信道估计误差相结合，限制条件是误码率小于限定值或者容量大于限定值，限制条件可以增加不断细化问题。
2.4） 二阶锥规划second-order cone program (SOCP)
二阶锥规划是特殊的二次规划形式
Minimize
Subject to
其中
，为二阶锥限制，如果c=0 则转化为二次限制二次规划问题QCQP问题，如果A=0，则转化为线性规划问题，LP。可见SOCP问题要比LP以及QCQP要更具有普遍性。
例子：鲁棒线性规划可视为二次锥规划
Minimize
Subject to
¸
转化为SOCP问题
Minimize
Subject to
大部分鲁棒线性规划问题可视为二次锥规划问题来处理，例如，误差的方差小于特定的概率，最小表面问题，连续积分离散化求和。
2.5） 几何规划geomet-ric program (GP).
单项式函数：
，在此情况下，
仿射函数，故凸
束函数：
几何规划的表示形式：
Minimize
subject to
其中
是束函数，
是单项式。一般多个单项式限制以及目标函数单项式并非凸函数，优化问题原来形式并非凸优化，但需要对目标函数以及限制条件进行转换，可以通过求对数运算将其转化为凸函数的形式
：
Minimize log
S.t. log
Log
GP问题：FDM系统功率分配问题（Luo- chapter5-
ppt
关于艾滋病ppt课件精益管理ppt下载地图下载ppt可编辑假如ppt教学课件下载triz基础知识ppt
）
2.6） 半正定规划semideinfite program (SDP)
Minimize
Subject to
其中
，
，如果
是对角矩阵，则该问题转化为线性规划问题
· 1
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
形式SDP：具有线性等式约束以及限制变量具有非负定性对于
Minimize
subject to
其中
· 2不等式SDP
Minimize
subject to
其中
，
例如：最小化最大特征值问题，对于
，
是SDP问题：
Minimize t
Subject to
2.7） 鲁棒优化Robust Optimization
一般的优化问题形式：
Minimize
subject to
实际中，由于误差或测试的影响：
subject to
2.8） SDP Relaxation对于非凸问题
模型一般性: LP < QP < QCQP < SOCP < SDP.
求解效率: LP > QP > QCQP > SOCP > SDP.
3规划问题的例子
3.1） 多面体中心设计问题
在多面体
内求解一最大的球，寻找球心称为切比雪夫中心设计问题。
球体
在多面体P内当且仅当
从而这也就等价于
因此，寻找切比雪夫中心可以归结为LP问题
3.2） 功率最优化问题
假定同一频率m发射机，mn接收机，发射机i同时给n个接收机
传输功率。Aijk代表发射机k到接收机(i; j)路径增益，Nij代表接收机的噪声功率。优化变量：发送功率pk, k = 1….m。
对于接收机(i; j)，期望信号功率：
干扰及其噪声功率：
信噪比：
优化目标：寻找pk使得最小
SINR最大化
线性分式规划问题
功率分配转化为几何规划问题
信噪比（dB）：
平均信噪比：
寻找pk使得平均 (dB)最大化
目前更多的SDP应用
· 结构优化(structural optimization): Ben-Tal, Nemirovsky, Kocvara, Bendsoe,
· 信号处理(signal Processing) Vandenberghe, Stoica, Lorenz, Davidson, Shaked, Nguyen, Luo, Sturm, Balakrishnan, Saadat, Fu, de Souza
· 电路设计(circuit design): El Gamal, Vandenberghe, Boyd, Yun,
· 代数几何学(algebraic geometry):Parrilo, Sturmfels, Lasserre, de Klerk, Pressman, Pasechnik
· 通信和信息理论(communications and information theory): Rasmussen, Rains, Abdi, Moulines,
· 量子论计算(quantum computing):Kitaev, Waltrous, Doherty, Parrilo, Spedalieri, Rains,
· 金融(finance): Iyengar, Goldfarb, . . .
· 机器学习(machine learning): Lanckriet, El Ghaoui,.
下一步研究
1， 问题的难点在于如何建模，建模非凸，如何凸优化松弛，怎么松弛才能得到较好近似解
2， 找出一些优化问题例子，比如波束形成中的加权因子，功率分配，预编码设计，多用户调度等问题，该问题需要涉及搜索最优变量，如何
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
3， 思考一些特定的场合中的优化问题，逼近问题，近似问题能否转化到凸优化上来
4， SeDuMi软件的应用
_1278694312.unknown
_1278694644.unknown
_1278772273.unknown
_1278772422.unknown
_1278772426.unknown
_1278772428.unknown
_1278772429.unknown
_1278772427.unknown
_1278772424.unknown
_1278772425.unknown
_1278772423.unknown
_1278772314.unknown
_1278772339.unknown
_1278772421.unknown
_1278772322.unknown
_1278772298.unknown
_1278772307.unknown
_1278772285.unknown
_1278694714.unknown
_1278694880.unknown
_1278772211.unknown
_1278772243.unknown
_1278772252.unknown
_1278772227.unknown
_1278772173.unknown
_1278772193.unknown
_1278772203.unknown
_1278772180.unknown
_1278772152.unknown
_1278772162.unknown
_1278694881.unknown
_1278772120.unknown
_1278694746.unknown
_1278694876.unknown
_1278694878.unknown
_1278694879.unknown
_1278694877.unknown
_1278694764.unknown
_1278694874.unknown
_1278694875.unknown
_1278694772.unknown
_1278694756.unknown
_1278694730.unknown
_1278694738.unknown
_1278694721.unknown
_1278694675.unknown
_1278694698.unknown
_1278694707.unknown
_1278694689.unknown
_1278694659.unknown
_1278694668.unknown
_1278694652.unknown
_1278694502.unknown
_1278694577.unknown
_1278694611.unknown
_1278694627.unknown
_1278694635.unknown
_1278694620.unknown
_1278694594.unknown
_1278694602.unknown
_1278694585.unknown
_1278694541.unknown
_1278694560.unknown
_1278694567.unknown
_1278694550.unknown
_1278694524.unknown
_1278694532.unknown
_1278694510.unknown
_1278694425.unknown
_1278694462.unknown
_1278694482.unknown
_1278694494.unknown
_1278694470.unknown
_1278694448.unknown
_1278694454.unknown
_1278694441.unknown
_1278694371.unknown
_1278694407.unknown
_1278694415.unknown
_1278694379.unknown
_1278694336.unknown
_1278694343.unknown
_1278694329.unknown
_1278083313.unknown
_1278100884.unknown
_1278101617.unknown
_1278694217.unknown
_1278694305.unknown
_1278694207.unknown
_1278678855.unknown
_1278101487.unknown
_1278101616.unknown
_1278101058.unknown
_1278101091.unknown
_1278101004.unknown
_1278099157.unknown
_1278099343.unknown
_1278100054.unknown
_1278100095.unknown
_1278099644.unknown
_1278099276.unknown
_1278083562.unknown
_1278083837.unknown
_1278083970.unknown
_1278083969.unknown
_1278083635.unknown
_1278083417.unknown
_1278083521.unknown
_1278083373.unknown
_1278081978.unknown
_1278082500.unknown
_1278082834.unknown
_1278082871.unknown
_1278082522.unknown
_1278082117.unknown
_1278082389.unknown
_1278082095.unknown
_1278081407.unknown
_1278081642.unknown
_1278081821.unknown
_1278081561.unknown
_1278081513.unknown
_1278081350.unknown
浙公网安备 33021202002483