精华内容
下载资源
问答
  • 锥,凸锥,二阶锥,二阶锥规划

    万次阅读 多人点赞 2017-12-17 22:46:40
    优化理论稍微深入些,就会涉及到这个概念,甚至还有专门的优化这个研究领域。我一直很奇怪到底是什么,准备查阅相关资料,将自己的理解写到博客里面。 1. (cone) 对于一个向量空间 VVV 与它...

    优化理论稍微深入些,就会涉及到锥这个概念,甚至还有专门的锥优化这个研究领域。我一直很奇怪锥到底是什么,准备查阅相关资料,将自己的理解写到博客里面。

    1. 锥(cone)

    • 对于一个向量空间 VVV 与它的一个子集 CCC,如果子集 CCC 中的任意一点 xxx 与 任意正数 aaa, 其乘积 axaxax 仍然属于子集 CCC, 则称 CCC 为一个锥。

    若向量空间为3维,满足定义的图像确实像一个锥,我猜这应该是它叫锥的原因。
    一个三维锥

    根据定义,一个锥总是无界的。

    2. 凸锥(convex cone)

    • 若一个锥 CCC 中任意两点 xxxyyy,以及任意两个正数 aaabbb, 都有 ax+byax+byax+by 属于 CCC, 则该锥为凸锥。

    显然上图也是一个凸锥。根据定义,凸锥也是一个凸集
    是否存在一个不是凸锥的锥?典型的例子:
    y=∣x∣y=|x|y=x
    一个点 (-2, 2), 另一个点 (1,1), 它们的和 (-1, 3)不在图形里。它的图形:
    不是凸锥的锥
    但是 y≥∣x∣y\geq |x|yx 就是一个凸锥

    3. 标准锥(norm cone)

    一个 n 维标准锥是满足下列条件的集合:
    C={(x,t)∣∥x∥≤t,x∈Rn−1,t∈R}C=\left\{(x, t)\mid \|x\|\leq t, x\in\mathbb{R^{n-1}}, t\in\mathbb{R}\right\}C={(x,t)xt,xRn1,tR}
    标准锥是一个凸锥。(标准锥里面的变量不仅包括 xxx,还包括 ttt.)

    4. 二阶锥(second order cone)

    二阶锥规划是一种非常特殊的非线性优化,有非常高效的求解算法,非常有必要了解一下什么是二阶锥。所谓二阶是指锥里面用到的是二范数,下面的表达式表示一个二阶锥。
    ∥Ax+b∥2≤cTx+d\|Ax+b\|_2\leq c^Tx+dAx+b2cTx+d

    二阶锥相当于对标准锥 C={(x,t)∣∥x∥2≤t,t≥0}C=\{(x,t)\mid \|x\|_2\leq t, t\geq 0\}C={(x,t)x2t,t0} 做了一个仿射变换:
    ∥Ax+b∥2≤cTx+d⟺(Ax+b,cTx+d)∈C\|Ax+b\|_2\leq c^Tx+d\Longleftrightarrow\Big(Ax+b, c^Tx+d\Big)\in CAx+b2cTx+d(Ax+b,cTx+d)C
    根据仿射变换的性质,变换后凹凸性不变,因此二阶锥仍然是一个凸锥。
    注:对向量 xxx 仿射变换(相当于将一个图形平移,或变大变小,或旋转,或倒影):y=Ax+by=Ax+by=Ax+b,其中 AxAxAx 表示对 xxx 变大或变小或旋转倒影,而 +b+b+b 表示平移。

    5. 二阶锥规划(second order cone programming,SOCP)

    很多问题都可以转化为二阶锥规划来求解,而二阶锥规划能够使用内点法很快求解。

    5.1 二次凸规划

    二次规划可以转化为二阶锥规划。一个二次凸规划表达式:
    XTAX+qTx+c≤0X^TAX+q^Tx+c\leq 0XTAX+qTx+c0
    转化成下面的二阶锥:
    ∥A1/2x+12A−1/2q∥2≤−14qTA−q−c\left\|A^{1/2}x+\frac{1}{2}A^{-1/2}q\right\|_2\leq \sqrt{-\frac{1}{4}q^{T}A^-q-c}A1/2x+21A1/2q241qTAqc
    就能使用二阶锥规划求解了。

    展开全文
  • 论文研究-一种求解二阶锥规划问题的新算法.pdf, 为了提高求解二阶锥规划问题的效率, 提出一种新的求解二阶锥规划问题的非单调信赖域算法. 基于Fischer-Burmeister光滑...
  • 基于二阶锥规划的宽带波束形成设计,白梅,李立萍,针对常规波束形成中普遍存在的波束主瓣宽度随频率发生变化,并导致输出信号失真的问题,提出了应用二阶锥规划方法实现恒定束宽波
  • 针对这一问题,提出一种采用二阶锥规划与压缩感知理论的改进自适应方向图综合算法。改进的算法将传统算法中的误差性能函数通过数学变换转换成标准二阶锥规划形式快速求解,同时应用压缩感知理论将大规模阵列权值稀疏...
  • 基于变压器高压侧电压、负荷、间歇性分布式电源(IDG)时序特性,通过配电网潮流方程及约束条件松弛,提出ADN中IDG消纳的二阶锥规划(SOCP)模型。该模型以IDG消纳量最大为目标函数,考虑分布式电源出力切除、有载...
  • 基于二阶锥规划的有源配电网SNOP电压无功时序控制方法,赵金利,李雨薇,分布式电源的广泛接入加剧了配电网的电压波动,与传统的负荷变化相比,由其引起的电压变化在时间尺度上更为迅速,但传统的电压无
  • 该方法基于最小均方误差(minimum mean square error,MMSE)准则,使均衡器的输出与训练码的均方误差最小,并且将信道均衡的最小均方误差目标函数转化为二阶锥形式,利用内点法求最优解。与传统基于最小均方误差(least ...
  • 二阶锥1.1 二阶锥定义1.2 二阶锥约束2. 优化问题建模3. 类似问题转化3.1 二次规划3.2 随机线性规划4. 问题求解 1. 二阶锥 1.1 二阶锥定义 在此之前,先给出二阶锥的定义。 在 kkk 维空间中二阶锥 (Second-order ...

    个人博客Glooow,欢迎各位老师来踩踩

    1. 二阶锥

    1.1 二阶锥定义

    在此之前,先给出二阶锥的定义。

    kk 维空间中二阶锥 (Second-order cone) 的定义为
    Ck={[ut]uRk1,tR,ut} \mathcal{C}_{k}=\left\{\left[\begin{array}{l} {u} \\ {t} \end{array}\right] | u \in \mathbb{R}^{k-1}, t \in \mathbb{R},\|u\| \leq t\right\}
    其也被称为 quadratic,ice-cream,Lorentz cone。

    1.2 二阶锥约束

    在此基础上,二阶锥约束即为
    Ax+bcTx+d[AcT]x+[bd]Ck \|A x+b\| \leq c^{T} x+d \Longleftrightarrow\left[\begin{array}{c} {A} \\ {c^{T}} \end{array}\right] x+\left[\begin{array}{l} {b} \\ {d} \end{array}\right] \in \mathcal{C}_{k}
    其中 xRn,AR(k1)×n,bRk1,cRn,Rx\in \mathbb{R}^{n}, A\in\mathbb{R}^{(k-1)\times n}, b\in\mathbb{R}^{k-1},c\in\mathbb{R}^{n},\mathbb{R}。实际上是对 xx 进行了仿射变换,由于仿射变换不改变凹凸性,因此二阶锥也是凸锥。

    2. 优化问题建模

    优化目标如下,其中 fRn,AiRni×n,biRni,ciRn,diR,FRp×n,f \in \mathbb{R}^{n}, A_{i} \in \mathbb{R}^{n_{i} \times n}, b_{i} \in \mathbb{R}^{n_{i}}, c_{i} \in \mathbb{R}^{n}, d_{i} \in \mathbb{R}, F \in \mathbb{R}^{p \times n}, and gRp,xRng \in \mathbb{R}^{p}, x \in \mathbb{R}^{n}
    minizefTxsubject toAix+bi2ciTx+di,i=1,,mFx=g \begin{aligned} \text{minize}\quad& f^{T} x\\ \text{subject to}\quad& {\left\|A_{i} x+b_{i}\right\|_{2} \leq c_{i}^{T} x+d_{i}, \quad i=1, \ldots, m}\\ &{F x=g} \end{aligned}
    上述问题被称为二次锥规划是因为其约束,要求仿射函数 (Ax+b,cTx+d)(Ax+b,c^T x+d)Rk+1\mathbb{R}^{k+1} 空间中的二阶锥。

    3. 类似问题转化

    一些其他优化问题也可以转化为 SOCP,例如

    3.1 二次规划

    考虑二次约束
    xTATAx+bTx+c0 x^{T} A^{T} A x+b^{T} x+c \leq 0
    可以等价转化为 SOC 约束
    (1+bTx+c)/2Ax2(1bTxc)/2 \left\|\begin{array}{c}\left(1+b^{T} x+c\right) / 2 \\ Ax\end{array}\right\|_{2} \leq\left(1-b^{T} x-c\right) / 2

    3.2 随机线性规划

    问题模型为
    minizecTxsubject toP(aiTxbi)p,i=1,,m \begin{aligned} \text{minize}\quad& c^{T} x\\ \text{subject to}\quad& \mathbb{P}\left(a_{i}^{T} x \leq b_{i}\right) \geq p, \quad i=1, \ldots, m \end{aligned}
    问题转化可参考维基百科

    4. 问题求解

    二阶锥规划可以应用内点法快速求解,且比半正定规划(semidefinite programming)更有效。

    Matlab 有专门的凸优化工具包,下载地址在这里,安装教程在官网上有。使用方法如下,只需要修改优化目标和约束条件即可

    m = 20; n = 10; p = 4;
    A = randn(m,n); b = randn(m,1);
    C = randn(p,n); d = randn(p,1); e = rand;
    cvx_begin
        variable x(n)
        minimize( norm( A * x - b, 2 ) )
        subject to
            C * x == d
            norm( x, Inf ) <= e
    cvx_end
    
    展开全文
  • Second-order cone program(二阶锥规划) 标准形式:-A second-order cone program (SOCP) is an optimization problem of the form: #SOCP import cvxpy as cp import numpy as np #problem datam m,n,p,n_i ...

    Second-order cone program(二阶锥规划

    标准形式:-A second-order cone program (SOCP) is an optimization problem of the form:

    #SOCP
    import cvxpy as cp
    import numpy as np
    
    #problem datam
    m,n,p,n_i = 3,10,5,5
    np.random.seed(1)
    F = np.random.randn(p,n)
    f = np.random.randn(n)
    
    x0 = np.random.randn(n)
    g = F@x0
    
    A = []
    b = []
    c = []
    d = []
    
    for i in range(0,m):
        A.append(np.random.randn(n_i,n))
        b.append(np.random.randn(n_i))
        c.append(np.random.randn(n))
        d.append(np.linalg.norm(A[i]@x0+b,2)-c[i].T@x0)
    
    #problem variable
    x = cp.Variable(n)
    
    #constraints
    soc_constraints = [cp.SOC(c[i].T@x + d[i], A[i]@x + b[i]) for i in range(m)]
    
    #objective
    objective = cp.Minimize(f.T@x)
    
    #construct the problem 
    prob = cp.Problem(objective,soc_constraints+[F@x == g])
    
    #solve
    prob.solve(solver = cp.,verbose = True)
    

     

    展开全文
  • 凸规划问题与二阶锥规划

    万次阅读 2018-10-12 11:39:38
    如果对于自变量x1、x2以及参数λ,有 则认为f是凸函数,进一步,如果 则认为f是严格凸函数。 ...R向量空间中,如果集合 S 中任两点...如果C∈R^n向量空间,对于任意x∈C,有ax∈C,则称C为集(类似于空间绝对可...

    如果对于自变量x1、x2以及参数λ,有

    f(\lambda x_{1} + (1- \lambda ) x{_2}) \leqslant \lambda f(x{_1}) + (1-\lambda)f(x{_2})

    则认为f是凸函数,进一步,如果

    f(\lambda x_{1} + (1- \lambda ) x{_2}) < \lambda f(x{_1}) + (1-\lambda)f(x{_2})

    则认为f是严格凸函数。

    R向量空间中,如果集合 S 中任两点的连线上的点都在 S 内,则称集合 S 为凸集。

     

    在凸集范围内,求凸函数在约束条件下的最小值成为凸规划,即:

    min( f(x))

    s.t     g{_i}(x)\le 0

             h{_i}(x) = 0

     

    如果C∈R^n向量空间,对于任意x∈C,有ax∈C,则称C为锥集(类似于空间绝对可积、有界的概念);进一步如果对于任意x∈C、y∈C,有ax + by ∈C ,则称C为凸锥集(类似于绝对可和+绝对可积、有界的概念);进一步的,如果向量 x∈R^n-1 以及数值 t∈R,总满足关系式 ||x|| ≤ t,则称所有(x,t)组成的集合为标准集;如果标准集成立条件中的x范数取为二阶,则称(x,t)为二阶锥集,但是在二阶锥的定义中限定了t≥0。

    在二阶锥范范围内求解约束条件下目标凸函数的最小值,就是二阶锥规划。

    关于凸优化问题的求解可以借助matlab工具包sedumi进行计算:

    sedumi帮助文档中的第一个例子

    首先看文档中对公式形式,以及变量的约定,对于原始标准形式:

    min(c^{T}x)

    s.t

    Ax = b

    x{_i}\geqslant 0

    或者上者的等价形式:

    max(b^{T} y)

    s.t c{_i} - a{_i}^{T}y \geqslant 0

     

    有了以上约定,假设我们现在面临这样一个线性规划问题:

    min( x{_1}-x{_2}  )

    s.t 

    10x{_1}-7x{_2}\ge5

    x{_1}+1/2x{_2}\le3

    x{_1}\ge0,x{_2}\ge0

    按照文档中的变量约定(约束条件1是≥号,需要在括号左边减去一个多个非负松弛变量,使≥转换成标准形式的=;同理约束条件2中,需要添加非负松弛变量,使其变成标准形式中的等号)

     c = [1;-1;0;0];
    A = [10,-7,-1,0;1,1/2,0,1];
    b = [5;3];
    sedumi(A,b,c)
    

    计算结果如下

    SeDuMi 1.3 by AdvOL, 2005-2008 and Jos F. Sturm, 1998-2003.
    Alg = 2: xz-corrector, Adaptive Step-Differentiation, theta = 0.250, beta = 0.500
    eqs m = 2, order n = 5, dim = 5, blocks = 1
    nnz(A) = 6 + 0, nnz(ADA) = 4, nnz(L) = 3
     it :     b*y       gap    delta  rate   t/tP*  t/tD*   feas cg cg  prec
      0 :            6.02E+00 0.000
      1 :  -1.20E+00 1.84E+00 0.000 0.3055 0.9000 0.9000   1.86  1  1  2.1E+00
      2 :  -6.94E-02 5.15E-01 0.000 0.2803 0.9000 0.9000   2.14  1  1  8.6E-01
      3 :  -1.21E-01 2.72E-02 0.000 0.0528 0.9900 0.9900   1.16  1  1  4.2E-02
      4 :  -1.25E-01 8.69E-06 0.000 0.0003 0.9999 0.9999   1.02  1  1  
    iter seconds digits       c*x               b*y
      4      0.3   Inf -1.2500000000e-01 -1.2500000000e-01
    |Ax-b| =   1.3e-15, [Ay-c]_+ =   0.0E+00, |x|=  2.9e+00, |y|=  2.8e-01
    
    Detailed timing (sec)
       Pre          IPM          Post
    9.600E-01    5.660E-01    5.899E-02    
    Max-norms: ||b||=5, ||c|| = 1,
    Cholesky |add|=0, |skip| = 0, ||L.L|| = 1.
    
    ans =
    
       (1,1)      1.958333333333333
       (2,1)      2.083333333333333

    通过以上结果我们可以发现,c*x的最大值 或者b*y的最小值是-1.2500000000e-01,以及对应的x1 = 1.958333333333333 ,x2 =2.083333333333333

    并且结果中给出了误差|Ax-b| =   1.3e-15

    展开全文
  • YALMIP系列 SOCP问题
  • 二阶锥求解器ECOS_C.zip

    2021-03-23 12:59:04
    最好用的二阶锥规划嵌入式求解器,用C语言编写,经试很好用。
  • 为了求解该非线性非凸模型,适当松弛原问题,将其转换为可直接求解的混合整数二阶锥规划(MISOCP)问题。仿真结果表明所提规划模型显著提升了系统的可靠性,降低了相关设备的配置容量,减少了能量传输损耗,降低了总体...
  • 提出了一种用于二阶锥规划(SOCP)问题的交替方向双重增广拉格朗日方法。 在算法中,在每次迭代中,它首先针对对偶变量最小化对偶增强拉格朗日函数,然后针对对偶松弛变量,同时保持其他两个变量不变,然后最后更新...
  • 二阶锥1.1 二阶锥定义1.2 二阶锥约束2. 优化问题建模3. 类似问题转化3.1 二次规划3.2 随机线性规划4. 问题求解 1. 二阶锥 1.1 二阶锥定义 在此之前,先给出二阶锥的定义。 在 kkk 维空间中二阶锥 (Second-order ...
  • 对于非线性规划,Cplex 与 Gurobi 只支持二次规划(包括凸规划,二阶锥规划,目标函数或约束条件中可以包含二次函数)。 若更高次数,或者非凸规划,非二阶锥规划,则需要用其他求解器了。 matlab 自带的 fmincon ...
  • 将聚焦变换的思想与二阶锥规划方法相结合,提出了一种稳健的宽带聚焦波束形成算法。该算法首先将宽带信号划为多个窄带信号,再通过最佳聚焦矩阵,聚焦到最佳聚焦频率上,将宽带问题转换为窄带问题,最后利用二阶锥...
  • 求解非线性二阶锥规划的Carroll函数方法的收敛性分析,顾剑,肖现涛,本文考虑了求解非线性二阶锥优化问题的基于Carroll函数的非线性拉格朗日方法的收敛速度。在严格互补条件、约束非退化条件和二阶充�
  • 最后,研究非合作静态博弈流程,为了求解复杂的混合整数非线性模型,采用二阶锥松弛方法将模型转化为混合整数二阶锥规划问题,提出基于数学优化的迭代搜索算法用以求解所提模型的Nash均衡解。以IEEE 33节点系统为例...
  • YALMIP.zip

    2021-02-01 12:21:13
    MATLAB软件包,能够通过统一的编程语言调用SDPT3、SEDUMI、SNOPT、IPOPT等主流优化求解器求解非线性规划、线性规划、二次规划、二阶锥规划、凸规划等优化问题。

空空如也

空空如也

1 2 3
收藏数 54
精华内容 21
关键字:

二阶锥规划