精华内容
下载资源
问答
  • 二阶规划问题
    万次阅读 多人点赞
    2020-02-17 09:35:47

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

    1. 二阶锥

    1.1 二阶锥定义

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

    k k k 维空间中二阶锥 (Second-order cone) 的定义为
    C k = { [ u t ] ∣ u ∈ R k − 1 , t ∈ R , ∥ u ∥ ≤ t } \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\} Ck={[ut]uRk1,tR,ut}
    其也被称为 quadratic,ice-cream,Lorentz cone。

    1.2 二阶锥约束

    在此基础上,二阶锥约束即为
    ∥ A x + b ∥ ≤ c T x + d ⟺ [ A c T ] x + [ b d ] ∈ C k \|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} Ax+bcTx+d[AcT]x+[bd]Ck
    其中 x ∈ R n , A ∈ R ( k − 1 ) × n , b ∈ R k − 1 , c ∈ R n , R x\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} xRn,AR(k1)×n,bRk1,cRn,R。实际上是对 x x x 进行了仿射变换,由于仿射变换不改变凹凸性,因此二阶锥也是凸锥。

    2. 优化问题建模

    优化目标如下,其中 f ∈ R n , A i ∈ R n i × n , b i ∈ R n i , c i ∈ R n , d i ∈ R , F ∈ R p × 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}, fRn,AiRni×n,biRni,ciRn,diR,FRp×n, and g ∈ R p , x ∈ R n g \in \mathbb{R}^{p}, x \in \mathbb{R}^{n} gRp,xRn
    minize f T x subject to ∥ A i x + b i ∥ 2 ≤ c i T x + d i , i = 1 , … , m F x = 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} minizesubject tofTxAix+bi2ciTx+di,i=1,,mFx=g
    上述问题被称为二次锥规划是因为其约束,要求仿射函数 ( A x + b , c T x + d ) (Ax+b,c^T x+d) (Ax+b,cTx+d) R k + 1 \mathbb{R}^{k+1} Rk+1 空间中的二阶锥。

    3. 类似问题转化

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

    3.1 二次规划

    考虑二次约束
    x T A T A x + b T x + c ≤ 0 x^{T} A^{T} A x+b^{T} x+c \leq 0 xTATAx+bTx+c0
    可以等价转化为 SOC 约束
    ∥ ( 1 + b T x + c ) / 2 A x ∥ 2 ≤ ( 1 − b T x − c ) / 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 (1+bTx+c)/2Ax2(1bTxc)/2

    3.2 随机线性规划

    问题模型为
    minize c T x subject to P ( a i T x ≤ b i ) ≥ 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} minizesubject tocTxP(aiTxbi)p,i=1,,m
    问题转化可参考维基百科

    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
    
    更多相关内容
  • 给出解决二阶规划(SOCP)问题的VU-分解方法.问题首先被转化为非线性规划,并给出相应的精确罚函数的Clarke次微分结构及VU-空间分解.在某种条件下,可以计算出一个二阶连续可微的轨道,进而得到目标函数f在其上的二阶...
  • 论文研究-一种求解二阶规划问题的新算法.pdf, 为了提高求解二阶规划问题的效率, 提出一种新的求解二阶规划问题的非单调信赖域算法. 基于Fischer-Burmeister光滑...
  • 规划问题二阶锥规划

    万次阅读 2018-10-12 11:39:38
    如果对于自变量x1、x2以及参数λ,有 ...在凸集范围内,求凸函数在约束条件下的最小值成为凸规划,即: s.t 如果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

    展开全文
  • 应用ECOS求解器,求解二阶问题,程序中有备注,上传的是整个方案,可以直接使用VS2010打开
  • 为了求解该非线性非凸模型,适当松弛原问题,将其转换为可直接求解的混合整数二阶规划(MISOCP)问题。仿真结果表明所提规划模型显著提升了系统的可靠性,降低了相关设备的配置容量,减少了能量传输损耗,降低了总体...
  • 大数据-算法-非凸二阶规划问题的非线性重新尺度.pdf
  • 请注意!!!!本资料自2021.10.15更新了OLTC、DG的问题,解决了同学们提出的一些问题错 ... 有主动配电网二阶锥最优潮流的所有学习资料,看完我这个,绝对不会有这方面的问题。运行问题可以帮忙解决!!!可答疑
  • 针对一致方程唯一解的求解问题,通过以综合滤波器组阻带能量最小化为目标函数、HFB准确重构作为约束条件,提出一种基于二阶规划法的PR-HFB设计算法,该算法能有效解得方程组全局最优解,并可以推广到方程最小范数解的...
  • 基于二阶规划的宽带波束形成设计,白梅,李立萍,针对常规波束形成中普遍存在的波束主瓣宽度随频率发生变化,并导致输出信号失真的问题,提出了应用二阶规划方法实现恒定束宽波
  • 在此假设条件下,原始问题(P)及其对偶问题(D)都有最优解且最优值相等,并且求解二阶规划问题等价于求解其最优性条件: (1) 3. 算法描述 光滑函数在二阶锥规划光滑算法的设计和收敛性分析中起着非常重要的作用。...

    Advances in Applied Mathematics

    Vol.04 No.03(2015), Article ID:15898,6

    pages

    10.12677/AAM.2015.43033

    Smoothing Inexact

    Newton Method for the Second Order Cone Programming

    Li Dong1, Siqi Xu2, Jingen Yang1

    1College of Mathematics and Information Science, Xinyang Normal University, Xinyang Henan

    2Department of Civil Engineering, Xinyang Normal University, Xinyang Henan

    Received: Jul. 30th, 2015; accepted: Aug. 12th, 2015; published: Aug. 18th, 2015

    Copyright © 2015 by authors and Hans Publishers Inc.

    This work is licensed under the Creative Commons Attribution International License (CC BY).

    http://creativecommons.org/licenses/by/4.0/

    htmlimages%5C1-2890033x%5Ce70a10f1-7c93-45ea-9603-062237856e4b.png

    htmlimages%5C1-2890033x%5Ce898c85e-ffc4-45c9-b817-14224a4d6960.png

    htmlimages%5C1-2890033x%5Cf4daa762-ba39-44c9-b439-8965414d84df.png

    ABSTRACT

    A new smoothing inexact

    Newton method is presented for solving the second-order cone programming. At each iteration, the method uses an inexact

    Newton method to solve the system of equations, which saves computation work of smoothing

    Newton methods. Under weak assumptions, our method is proved to have global and local quadratic convergence. Numerical experiments indicate that the proposed method is quite effective.

    Keywords:Second-Order Cone Programming, Smoothing Inexact Newton Method, Convergence

    二阶锥规划的光滑非精确牛顿法

    董丽1,徐思齐2,杨金根1

    1信阳师范学院数学与信息科学学院,河南 信阳

    2信阳师范学院土木工程学院,河南 信阳

    收稿日期:2015年7月30日;录用日期:2015年8月12日;发布日期:2015年8月18日

    84a701b35442b7995c0f4d54cc16e4d8.png

    摘 要

    本文给出了一个新的求解二阶锥规划的光滑非精确牛顿法。在每次迭代时,新方法采用非精确牛顿法去求解一个方程组的解,降低了光滑牛顿法的计算量。在较弱条件下,证明了算法具有全局和局部二阶收敛性质。数值试验表明算法是有效的。

    关键词 :二阶锥规划,光滑非精确牛顿法,收敛性

    5b735f6f51858d20af08b3f41c7a9980.png

    1. 引言

    本文考虑如下二阶锥规划:

    (P)

    f2c3f3db12caa3d76b4608be111b7fd3.png

    其中

    08732ec6975bc1077a01bd81a1f89cb8.png是变量,

    bd9dd708d5550c497ce565348ae59d0c.png

    8f5844d0de5091e9da01d38151b353c3.png是已知的量。

    b1d696dedc14790e33ce6cf7fb0dc36b.png

    975a4499d2a5300d1d44ad149eaf7381.png维的二阶锥,其定义为

    f3e71418098b26e6e8f0478622ed6426.png

    其中

    e77e0720f45fcf6cd0256de24958b15e.png为向量的欧几里得范数。(P)的对偶规划为

    (D)

    3a24a318a8dbaf7b27cce1e5ff56310c.png

    二阶锥规划作为数学规划领域的一个重要分支,有着非常重要而又广泛的应用背景和实际意义, 其研究问题涉及控制、金融、组合优化、工程技术、神经网络、机器学习等诸多领域[1] 。许多数学规划问题, 如凸二次规划、二次约束的凸二次规划、矩阵分式优化、范数极小化问题、鲁棒最小二乘问题、天线阵列的设计、带损失风险的金融优化问题等均可以转化为二阶锥规划[1] 。因此近年来二阶锥规划成为数学规划领域一个值得关注的方向。

    光滑算法是近年来求解二阶锥规划的一种新方法[2] -[6] 。该方法的基本思想是利用一个光滑函数将二阶锥规划等价转化成一个非线性方程组,然后利用牛顿法求解该方程组,从而得到原问题的最优解。由于光滑算法不但在理论上具有好的收敛性质,而且在具体实施中有很好的实际计算效果,因而近年来得到了迅速的发展。注意到,文献[2] -[6] 所研究的光滑算法在每次迭代时,都需要精确求出一个非线性方程组的解。如果要求解的问题规模较大,精确求解此方程组的解往往效率不高,而非精确牛顿法是解决这类问题的一种很好的途径。

    本文给出了一个求解二阶锥规划的光滑非精确牛顿法,证明了算法的全局和局部收敛性质。该方法采用非精确牛顿法求解方程组的解,大大提高了光滑算法的效率。数值试验表明算法对求解大规模二阶锥规划是有效的。

    2. 预备知识

    对任意的

    3ca8ede86798bfed0226fd55a804efba.png

    8d95bc1a600981fb489d485a7e2b1d36.png,与二阶锥

    182053810003eb876f62148803e5dec2.png相伴的约当代数定义为

    956399b11f68f3e36f7974a1738105f9.png

    c519e63ac2b97b973459aa679abb602d.png是一个欧几里得约当代数,其单位元为

    6c5b84ea00a2e1a556f89a052c1e0082.png

    对任意的

    128333992da6e6a68d113a0d82be4498.png,定义

    a88ba546a759d94a203c517d44937a66.png,其中I为

    70f69f7ef0c88aa6bdf99cd301d9e45a.png维单位矩阵。

    易知

    dcb92397d25d6a3c27774a28cdb2261f.png

    下面给出与二阶锥

    3ed2db2e133460a0b2c3681f4cc49e33.png相伴的

    4f167c5b7da3fff48e6e33138fc886ed.png中向量的谱分解。对任意的

    abd74fd89b013b86e9b10429233a3c25.png,它的谱分解为

    3c526946ea62cd93f66db66cc9fb904b.png,其中谱值

    79c5723a2798e86a085c1d3819b78212.png和谱向量

    24c54580edc09100984275f2d2e4df65.png分别为

    25263003954599aba59f282cb955cef0.png

    这里

    29057d78389a80e44b362c3405dcd204.png是满足

    581b191f4ce17ea85444ae4d66c80f07.png的任意向量。利用谱分解,我们可以定义

    32c43821ebf1282aed04adc0a7b8daef.png

    本文假设原始问题(P)及其对偶问题(D)都严格可行。在此假设条件下,原始问题(P)及其对偶问题(D)都有最优解且最优值相等,并且求解二阶锥规划问题等价于求解其最优性条件:

    92d137da16da62b97ea1771f6c1b18f5.png(1)

    3. 算法描述

    光滑函数在二阶锥规划光滑算法的设计和收敛性分析中起着非常重要的作用。本文采用著名的Fischer–Burmeister光滑函数,其定义如下:

    5ee3137cc4626642bcf1078098820148.png(2)

    由文献[7] 中的命题4.2可知

    23717d6aaf0e7a0953de771bc4b8b18a.png(3)

    3d908fb16f758f01a6e6b43e6e8a98db.png。利用

    c7c55cf9829f01a2aea82eef6c8b02a3.png定义函数

    ae4199e89377fc33e22d4b8e06e35da2.png如下:

    dcdb34106d93df55140607a5fb6d5310.png(4)

    由(1)和(3)可知

    1056e528f3f1bf2dee2f23555e8c17c6.png

    efbb4cbb9981da4a3fb6962f35eb5cfb.png的解当且仅当

    1ca996435fff55574306d02bc178ed72.png是(P)和(D)的解。

    下面给出我们的算法。

    算法3.1. (光滑非精确牛顿法)

    步骤0: 选取常数

    f586e5086b3e0eeab8b1d9ad6689c85f.png。选取初始点

    e98ed9f3355aa141711dcc01701640cc.png。令

    9ed30e65d1005a238cf92fce6d9b8e1a.png。选取常数

    fde2233796f6174c207874356fde5fac.png,使得

    3b317ef75b051cbfa191a8ae18ac2d06.png。选取常数

    98e671cc73ef500f79cbe7bee3872f56.png,使得

    1ff63d47ffcfb6b8cb268014cf5732b5.png。令

    38f956d5b569e9733bc8aad5ee1e47b2.png

    步骤1:如果

    e2b7810c82d08509934bd8f7cb9e55ca.png,则停止迭代。否则,计算

    700d2eb53c066057936e28ecde70ccc4.png(5)

    步骤2:求解如下方程组得搜索方向

    0123bd5142d52ce2053782536a853b68.png,

    c212b6cc7fa153f088d47beb8826d3dc.png(6)

    这里

    6ceb8cc134f65a48a0841ad9724e2b47.png,其中

    ecaafdd758e9f023a5e248b83d65daa6.png并且满足

    1db827fd9082efa372f7687afff3ab96.png(7)

    步骤3:令

    93c93f3cafc7c415f876b7de34a6c17a.png是使得下式成立的最小非负整数

    35695f5739c7df34e0002cf2fdf1f8a1.png(8)

    edd5fa3333e34863e9bd9bd1b14a521a.png

    步骤4:令

    589f49899829fc103589e6f3b77b772c.png。令

    4106d19d781db1d6f02e771d7d0f3ddc.png。转步骤1。

    注:令

    46effd8875f05161efcc93c1f7841891.png,则由算法3.1的步骤2可知

    20f843688b01ac36a5a19300c3fbdc96.png

    即方程组(6)由非精确牛顿法求解。

    下面定理给出了

    32ee91dc1ef65269371bdf5697b91a9d.png的雅可比矩阵及其可逆性,具体证明可参见文献[6] 中的定理3.2。

    定理3.1:设

    c408c88e0f3b0ca30541d328a6be8fb6.png由(4)定义,则有下面结论。

    (i)

    032e502883903647bdf3db90a6cc7419.png

    6ed5b12de26f303992118fc11fe223f3.png上全局Lipschitz连续且处处强半光滑,并且在任意的

    36aa6b53a60ccdfcbe7fa86bd68d988b.png处连续可微,其雅可比矩阵为

    bc4a0e52491a0d41e58dab4def2fb199.png

    其中

    90d7fa09ad579f6074530b67ec7a3dc5.png

    (ii) 如果矩阵

    c5c6b7be899482b19f36b6da93695c69.png行满秩,则对任意的

    1b1c7ff48bc6cf281c011bc19a2be89c.png

    cce1392ea7691dac287f6dd9bd3e50c6.png可逆。

    定理3.2:设矩阵

    50c86b5e7f612b246bbda9c1f5086f99.png行满秩,则算法3.1有好的定义。

    证明:假设对于某个

    1f7de23537a37e196d7789808304dbcc.png

    1dffc22008b91dfcd64c347f187b45e0.png。因为矩阵

    129c3a493edd3fc732e6d8d8a0fd2a6a.png行满秩,故由定理3.1知

    2aae4af9f7cd8ab73ea32cf4f034c295.png可逆,所以在第

    72a29e64ad10b9f402b6d7c987925eef.png步迭代步骤2有好的定义。令

    c34ca4b8772d51254644bb20d3e2efcc.png为方程组(6)的解,则对任意的

    a208697d6785916b2f09c84a4b632a07.png,有

    5ba6487bf4d3fbf59e93dc3f805ad604.png(9)

    由(9)及定理3.1可知

    f30666a121b8ad70d945fb4b56fab7b3.png

    67e8f781131cb7c5668f6331badff15c.png附近连续可微。对任意的

    45872e54486e2387b5e59f91e76c457c.png,定义

    3331acda5b25bd13377501e6a2e9abb8.png(10)

    89fdad40b792b5316cc934bc863129c5.png。由(5)和(7)知

    992399038ae3c9bfba66733208c8e75d.png

    3c5280b67b931fc02a3c5c6530a403fc.png,故知

    d1031c3df02e077326871efe0246e873.png

    因此,由(6)和(10)可知对任意的

    ff32ba256a2bf1bfcc031fc633d2ea7e.png,有

    5515a5c53eb5e41a8409b5fe23f1f5aa.png

    因为

    914b8e2c11356b1367ac27d96ab9ab93.png,所以存在一个常数

    dfde748dcebfd6539ab13951cea24627.png使得对于任意的

    e4a8629e1f09ac04d549e2ffd424101f.png,有

    148ab944cdb911573582be98e3d82877.png

    从而可知步骤3在第

    3eb16f83bc59b8eeb551aa2aec4d8397.png步迭代有好的定义,即算法步骤3可以产生一个步长

    c0320a22ddabf8575610b4097f980cb9.png。由(9)可知

    9617923a0364bb9c70078accafb80863.png,因此由数学归纳法可知算法3.1有好的定义。证毕。

    引理3.1 设

    45aeba82a8001369bb9cfa86da2dd36c.png为算法3.1产生的迭代点列,则对任意的

    6a011145e11745eb5a7383cc7c4f38de.png

    faffd21e07f91aadeeb797fb59869537.png

    证明:由算法3.1的步骤3和步骤4可知点列

    4ec372ce49580dc8e9e3050f71cd9b26.png单调下降,从而由

    1c1a2805c6da0136dd54a9c107cc279c.png的定义可知点列

    ebd090622b00702bba9b7608228a8e84.png也是单调下降的。由算法3.1的步骤0可知

    c425df0119d9fcfe441639b75b37e2cd.png。假设对于某个

    80655b2f38676b76c35308e6761280a8.png

    c58111717748324aa6df595a9560bea1.png,则由(9)可得

    b8c96b99384eaea7c040133b3554b28c.png,

    进而由数学归纳法可知结论成立。证毕。

    4. 算法的收敛性质

    定理4.1:如果矩阵

    5d4ab9eef590fcef1adffe2885e675e6.png行满秩并且

    540ff33910561ee7b45701f7d8552cc2.png是由算法3.1产生的迭代点列,那么

    cab406fcf52d1dbf72afeaa8c85117c2.png的任意聚点

    23204d82c28aae45dcef7b642fa469c6.png都是

    e9ff488edc0b3ae05314dd627ed4b6c6.png的解。

    证明:不失一般性,我们假设当

    0cc7b2b080932784272e8ab779cef127.png时,

    2f99d6df62ab9a11b40f00286e9f0e2a.png收敛到

    827d8c694d27334b2c5c5a1c94499d73.png。因为

    51f45833e80b99be817a1f30c3e1aace.png单调下降并且有下界,所以由

    fcaf6efdb75869937c17fe3c2181626e.png的连续性可知

    5f6dfbdc7852da4776cf35381e5c045c.png收敛到一个非负数

    7a1316993fe8ac8d3136d4987e694753.png。若

    142f9fe7a057af401d96633de4f6c186.png,则结论成立。假设

    66e7ed7a57e1236ec5c42e6f1ab27e6d.png。因为

    cf4beb322100bf31600aa0fdc7e7dfc6.png并且

    99cd32b58e0f74e1235fae9fba594586.png单调下降,故

    0835ca196495d6bb41aa6d73cb72991d.png,

    从而由定理3.1可知

    3a0d7a247833fb3e3b1f5e21643a538a.png存在并可逆。因此,存在

    bab1f2e64479b9163621102c3ebbde96.png的一个闭邻域

    0c5d60e9e91e310dcc596603bcd945e9.png,使得对任意的

    ed76012723fa2bff40b9bd4b64858af1.png

    f63c3671f0485e83c5f4c8da7782508a.png并且

    e674fc53bd0c4fef50dedff02c3464f3.png可逆。因为

    42e48fdff12eece1cecf9e5e3340442f.png,故对于充分大的

    49b5824ce51760f7fc3985938eeacf2e.png

    483d96a7baa456b157f7ec2f359c1827.png,进而可知

    490b610aaaaccb7d4bd8d185d96b64d3.png并且

    4d5175a48f42a677721964dbe050e0c0.png可逆。对于充分大的

    fd799e223a906d8436e1dc9458e68b7a.png,设

    d614972bb70c18692a9f0aec7366d6c5.png是方程组

    9ad5faa2bddc7082a86fe2e544599ce2.png唯一的解。类似于定理3.2的证明,对于充分大的

    ae5a53d17267185e31bca4b5739e0592.png,存在一个非负整数

    a75bbd4c42846ac2d7742ac56da301c3.png满足

    f66400141131f36484acbca40e6ef6ed.png,这里

    85fd8045dbf65e0ffdb1a998188b55e8.png,使得

    dc4aa6bd5df69d7b28d586278fe1c63e.png

    对任意的

    80d5203c439b5d016361ad0f971fdbb2.png

    0e3a28e25489c72b54260498704e58bb.png都成立。对于充分大的

    5d1f7debed849863dc850fb992b6a41d.png,因为

    f86a47c9c3b29900ec998f04fd8e211f.png,所以由算法3.1的步骤3和步骤4可得

    4c957d511e87d388f4ad48e2ed1ed6dc.png

    04b7d70d1a5830e702a73844d0d074fa.png并在上式两边取极限,利用

    b79e665ad81dac535c714a0e6b462155.png,可得

    f4030d04362f64aec4b8f0546b1de2a0.png。这与

    77965d2bbd7f6108e80cf2ead79f7e24.png矛盾。因此可知

    3ab432d6fccd8327261d536ba1348c84.png。证毕。

    定理4.2:假设矩阵

    2638fe1e5ab7c28801598c14db8d4c0e.png行满秩并且

    a97922bf46ec896f02d08221e6db83f3.png是算法3.1产生的迭代点列

    68e827e611529de61757f18a7e40471d.png的任意聚点。如果所有的

    46b6f99db01e56b44ca8d3bec7351f57.png都是非奇异的,则

    c880db804bf4787c45c616009effcfd3.png二次收敛到

    86689bc4441d08039ec5c25efa2bd13c.png,即

    3d2700f616478f9e86c9ee2d2c126613.png

    证明:由定理4.1可知

    ae89a05585d55f14f280718c53ca412c.png,故对于充分大的

    4feffc6382cf9f68283ca989e8349bf1.png,有

    ce5a4ba82ff339a3ea49fcf3c42a39bd.png并且

    01f39bd03c23e48a3fe03db52cdba5ac.png,进而可知

    652e9a3c669c85930e0eef43f575e30e.png

    因此,类似于文献[2] 中的定理4.3可证得结论成立。在此省略。证毕。

    表1. 算法3.1的数值结果

    5. 数值试验

    为检验算法3.1的实算效果,我们用Matlab7.0.1编程在Windows XP操作系统的电脑上做数值试验。

    在所有的试验中,参数选择为

    b5847fe7025d5b37f9c15fa107644c46.png

    8185fb2b6d60c48c5210da15ae92ebfe.png

    aad1a99fc4c30bca189f872261b7985d.png

    4a4ad779acdb68759d478034881ba4b2.png

    386077e68d8ee9ad9e4486e56e9cd8d8.png。我们选择

    df51ba4754ef8b5ba953a014fd1d4163.png

    bc0bd7b08c8081ba77023b540fc123e1.png作为初始点。终止准则为

    69647257d5e9cae827bb9b705669961e.png

    测试问题是随机生成的二阶锥规划问题。具体步骤为:首先生成随机的行满秩矩阵

    2b660c712bbebe75fa155fbb56004661.png和随机向量

    ba76df765466d3b106b097499a4cd249.png

    b9e0e993b08b23e6f06311e0303b155d.png

    bef335af7d9d8dd5488d214078b03465.png,这里

    c32a23720a5422b0a5a0b0c331b3165d.png,然后令

    c9f71fab5dffeb059d32a08a0916be97.png

    94b14625e87803281059c48fa4f8e646.png,则得到的二阶锥规划的原问题和对偶问题都存在最优解且最优值相等。每个算例测试10次,计算结果列于表1,其中

    5d4904d455f42d4d1ecb7950d030d93a.png表示

    50c40f5c52767247aadf5851a91e8039.png,AIT表示算法所需的迭代次数的平均值,ACPU表示算法所需的CPU时间(单位:秒)的平均值,MHK表示算法终止时10个算例中

    6b8dde8dc174748300ae18b6395a280e.png的最大值。

    由表1可以看出,算法3.1是有效的并且能够求解大规模二阶锥规划问题,它只需要很少的迭代次数和CPU时间就可以得到满足终止条件的解。

    基金项目

    河南省自然科学基金(142300410437),河南省高等学校重点科研项目(15A110039)。

    文章引用

    董丽,徐思齐,杨金根. 二阶锥规划的光滑非精确牛顿法

    Smoothing Inexact Newton Method for the Second Order Cone Programming[J]. 应用数学进展, 2015, 04(03): 271-276. http://dx.doi.org/10.12677/AAM.2015.43033

    参考文献 (References)

    1. Alizadeh, F. and Goldfarb, D. (2003) Second-order cone optimization. Mathematical Programming, 95, 3-51.

    http://dx.doi.org/10.1007/s10107-002-0339-5

    2. Chi, X.N. and Liu, S.Y. (2009) A non-interior continuation method for second-order cone optimization. Optimization, 58, 965-979. http://dx.doi.org/10.1080/02331930701763421

    3. Chi, X.N. and Liu, S.Y. (2009) A one-step smoothing Newton method for second-order cone programming. Journal of Computational and Applied Mathematics, 223, 114-123. http://dx.doi.org/10.1016/j.cam.2007.12.023

    4. Fang, L., He, G.P. and Hu, Y.H. (2009) A new smoothing Newton-type method for second-order cone programming problems. Applied Mathematics and Computation, 215, 1020-1029. http://dx.doi.org/10.1016/j.amc.2009.06.029

    5. Tang, J.Y., He, G.P., Dong, L. and Fang, L. (2011) A smoothing Newton method for second-order cone optimizationbased on a new smoothing function. Applied Mathe-matics and Computation, 218, 1317-1329.

    http://dx.doi.org/10.1016/j.amc.2011.06.015

    6. 汤京永, 贺国平 (2012) 一个新的求解二阶锥规划的非内部连续化算法. 应用数学, 1, 26-31.

    7. Fukushima, M., Luo, Z.Q. and Tseng, P. (2002) Smoothing functions for second-order-cone complementarity problems. SIAM Journal on Optimization, 12, 436-460. http://dx.doi.org/10.1137/S1052623400380365

    展开全文
  • 二阶锥求解器ECOS_C.zip

    2021-03-23 12:59:04
    最好用的二阶规划嵌入式求解器,用C语言编写,经试很好用。
  • 二阶规划在工程、控制、金融等领域具有广泛的应用.本文研究一种求解二阶规划的非精确不可行内点法.该算法的基本思想是首先定义不可行中心路径及其邻域,然后通过求解一个非线性方程组得到非精确的搜索方向,再...
  • 锥,凸锥,二阶锥,二阶规划

    万次阅读 多人点赞 2017-12-17 22:46:40
    二阶规划(second order cone programming,SOCP) 很多问题都可以转化为二阶规划来求解,而二阶规划能够使用内点法很快求解。 5.1 二次凸规划 二次规划可以转化为二阶规划。一个二次凸规划表达式: X T A ...

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

    1. 锥(cone)

    • 对于一个向量空间 V V V 与它的一个子集 C C C,如果子集 C C C 中的任意一点 x x x 与 任意正数 a a a, 其乘积 a x ax ax 仍然属于子集 C C C, 则称 C C C 为一个锥。

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

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

    2. 凸锥(convex cone)

    • 若一个锥 C C C 中任意两点 x x x y y y,以及任意两个正数 a a a b b b, 都有 a x + b y ax+by ax+by 属于 C C C, 则该锥为凸锥。

    显然上图也是一个凸锥。根据定义,凸锥也是一个凸集
    是否存在一个不是凸锥的锥?典型的例子:
    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 ∈ R n − 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}
    标准锥是一个凸锥。(标准锥里面的变量不仅包括 x x x,还包括 t t t.)

    4. 二阶锥(second order cone)

    二阶锥规划是一种非常特殊的非线性优化,有非常高效的求解算法,非常有必要了解一下什么是二阶锥。所谓二阶是指锥里面用到的是二范数,下面的表达式表示一个二阶锥。
    ∥ A x + b ∥ 2 ≤ c T x + d \|Ax+b\|_2\leq c^Tx+d Ax+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} 做了一个仿射变换:
    ∥ A x + b ∥ 2 ≤ c T x + d ⟺ ( A x + b , c T x + d ) ∈ C \|Ax+b\|_2\leq c^Tx+d\Longleftrightarrow\Big(Ax+b, c^Tx+d\Big)\in C Ax+b2cTx+d(Ax+b,cTx+d)C
    根据仿射变换的性质,变换后凹凸性不变,因此二阶锥仍然是一个凸锥。
    注:对向量 x x x 仿射变换(相当于将一个图形平移,或变大变小,或旋转,或倒影): y = A x + b y=Ax+b y=Ax+b,其中 A x Ax Ax 表示对 x x x 变大或变小或旋转倒影,而 + b +b +b 表示平移。

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

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

    5.1 二次凸规划

    二次规划可以转化为二阶锥规划。一个二次凸规划表达式:
    X T A X + q T x + c ≤ 0 X^TAX+q^Tx+c\leq 0 XTAX+qTx+c0
    转化成下面的二阶锥:
    ∥ A 1 / 2 x + 1 2 A − 1 / 2 q ∥ 2 ≤ 1 4 q T A − 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
    就能使用二阶锥规划求解了。

    展开全文
  • 该存储库提供与论文“通过二阶规划快速重建稀疏相对冲激响应”相关的Matlab代码(作者Rajmic,Koldovský,Daňková,在WASPAA研讨会2017年出版) 在文件夹SYNTHETIC中,您可以找到Matlab代码,其中显示了有关...
  • 利用凸泛函定义了广义二阶C- 凸函数及广义二阶C-拟凸函数,在这些新函数的约束下,针对一类多目标分式规划二阶对偶问题,给出弱对偶、强对偶和逆对偶问题的相关结论.
  • 本文研究了非线性二阶规划问题.利用投影映射将非线性二阶规划问题的KKT最优性条件转化成非光滑方程组,获得了一个修正的中心路径非光滑牛顿法.在适当的条件下保证方程组的B-次微分在任意点都可逆,并且证明...
  • 代码主要主要研究的配电网优化,具体为配电网中的动态重构问题,...2)主动配电网多时段动态重构问题,重构的目标函数为重构后的网络损耗最低,同时潮流的求解方法采用二阶锥方法,构建了SOCP模型,求解效率大大增加
  • 针对这一问题,提出一种采用二阶规划与压缩感知理论的改进自适应方向图综合算法。改进的算法将传统算法中的误差性能函数通过数学变换转换成标准二阶规划形式快速求解,同时应用压缩感知理论将大规模阵列权值稀疏...
  • 开始在PyCharm安装cvxopt包时很快就好了,后面需要用CVX求解二阶规划SOCP时,发现安装cvxpy包总是出现错误,scs包也是不能直接安装 Could not build wheels for scs which use PEP 517 and cannot be installed ...
  • 问题遇到的现象和发生背景 优化问题的约束中存在一个变量平方和开方的二次约束,可转化为二阶锥约束。导师建议不要用sqrt语言和2范数语言,使用二阶锥程序语言。但是在matlab中用二阶锥语言表示该约束运行后,又报...
  • 该方法在已有高分辨聚焦算法的基础之上,通过对矢量阵近场权向量的模强加不等式约束,进而利用二阶规划求解最优权及空间谱,明显改善了矢量阵MVDR聚焦处理器的稳健性。优化后的高稳健性聚焦处理器在失配条件下可以...
  • 【OR】YALMIP 二阶规划

    千次阅读 2020-09-30 19:58:46
    YALMIP系列 SOCP问题
  • 针对二阶规划问题,给出了一种新的原始-对偶不可行内点法,利用该算法只需迭代次就可找到问题的边似解。该算法不要求初始点及其迭代点的可行性,只要求所有迭代点位于不可行中心路径的某个邻域内。初步的数值实验...
  • 基于经典弹塑性理论中多数屈服准则具有凸锥数学结构的事实,将在大规模计算中更具潜力的锥规划法引入弹塑性分析。考虑到弹塑性流动理论有关联与非关联之分,本文提出利用锥型互补法求解弹塑性问题。具体以Drucker-...
  • 半正定问题二阶凸锥问题(SDP&SOCP)

    千次阅读 2020-03-15 13:00:15
  • 基于二阶规划的主动配电网动态最优潮流求解 关键词:配电网优化 二阶锥优化 动态优化 最优潮流 参考文档:《主动配电网最优潮流研究及其应用实例》仅参考部分模型,非完全复现 仿真平台:MATLAB YALMIP+CPLEX 主要...
  • 1 二阶线性微分方程边值问题的 MATLAB 求解* 云 文 在 ( 包头师范学院 数学科学学院,内蒙古 包头 014030) 摘 要: 本文给出二阶线性微分方程边值问题数值算法的 MATLAB 实现,并举例进行了求解仿真及与解 析解的...
  • 基于Mehrotra型预估一矫正算法在锥规划问题中的应用,利用一种新的自适应更新方法,在没有引进任何”保障措施”的情况下,提出了一个宽邻域上线性规划问题的不可行内点算法,并且证明了算法具有O(n1.5log(1/ε))...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,609
精华内容 1,843
关键字:

二阶规划问题