半无限凸规划的割面算法 矩鲁棒优化的应用

这是一个相当便宜的步骤，它只需要求解一个线性规划，它的求解可以通过温启动进一步加快。由于没有第三和第四矩信息，分布的整体形状甚至不能近似地确定，我们期望未来成功的分布鲁棒优化算法也将具有在不确定集的识别中包含高阶矩信息的能力。确认本研究得到了NSF授予的CMMI-1100868的部分支持。本材料是由美国能源部科学研究中心、高级科学计算研究中心、应用数学项目资助的basedupon工作，奖号为DOE-SP0011568。我们也感谢裁判对技术细节和材料展示的投入。附录：定理1证明的证明。设Zidene为（DROi）对每i的最优目标函数值，设Zspdenote为（SP）的最优目标函数值；我们想证明limi→∞zi=zsp.序列(zi)i=0,1,...是收敛的，因为它是单调递减的（因为pp···TMmi=0pi)，并且它从下面有界为zsp:zi=minx∈xmaxq∈pizζ∈uh(x,ζ）Q(dζ）≥maxq∈piminx∈xzζ∈uh(x,ζ）Q(dζ）≥minx∈xzζ∈uh(x,ζ）P(dζ=zsp。（20）现在考虑随机规划问题(SP)。用它的一个最优解来表示，zidef=maxq∈piz∑∑h((x，ζ）Q(dζ）。显然，zi≤(zi)对于每一个i。鉴于（20）,本文证明了对每一个i,选择一个任意的qi∈arg maxq∈Pirζ∑H((x，ζ）Q(dζ）。由于qi和P的矩符合i阶，所以对于全次的多项式P至多为i，我们得到了zζ的πP(ζ）qi(dζ）=zζ的πP(ζ）P(dζ）（21）。假定函数h(x，·)在闭有界集态态上是连续的。设pjdenoteits最佳全次J的一致多项式逼近；通过Weierstrass近似定理，我们得到了对于每ε>0，存在一个次j(ε)，使得maxζ∈h((x，ζ）-pj(ε)(ζ）<ε，因此，zζ∈h(x，ζ）-pj(ε)(ζ）q(dζ<ε和zζ∈h(x，ζ）-pj(ε)(ζ）P(dζ<ε。（22）用这个j(ε),每个i≥j(ε)都有不等式zi-zsp=zζ∈h((x，ζ）qi(dζ）-zζ∈@pj(ε)(ζ）qi(dζ）-zζ∈@pj(ε)(ζ）qi(dζ）+zζ∈@pj(ε)(ζ）qi(dζ）-zζ∈h((x，ζ）P(dζ）=zζ∈h((x，ζ）P(dζ）=zζ∈h((x，ζ）P(dζ）=zàààh((x，ζ）-pj(ε)-pj(ε)=pj(ε)-pj(ε)Qi(dζ)+zζ∈@pj(ε)(ζ）P(dζ)-zζ∈H((x，ζ）P(dζ)≤≤zζ∈@h((x，ζ）-pj(ε)(ζ）qi(dζ）+zζ∈@h(x，ζ）-pj(ε)(ζ）P(dζ<2ε，用三角形不等式，(21)，(22)，再用三角形不等式。根据左右手之间的不均衡性，立即得出limi→∞_zi=zSP，正如所声称的那样。referencesd。Bertsimas,X.V.Doan,K.Natarajan和C.-P.提奥。具有风险厌恶的极大极小随机线性优化问题模型。运筹学数学，35(3):580-6022010.b。贝特奥。线性半线性规划的加速中心切割平面算法。数学规划，101:479-495,2004.DOI:10.1007/S10107-003-0492-5.E。德克勒克。单纯形、超立方体或球面优化的复杂性：简评。中欧运筹学杂志，16(2):111-125，2008。ISSN 1435-246x。DOI:10.1007/S10100-007-0052-9。网址http://dx.doi.org/10.1007/s10100-007-0052-9.e。德克勒克、M·洛朗和P·A·帕里洛。单形上整次多项式极小化的PTAS。理论计算机科学，361(2-3):210-225，2006。ISSN0304-3975。DOI:http://dx.doi.org/10.1016/j.tcs.2006.05.011.j。A.de Loera,R.Hemmecke,M.Kéoppe和R.Weismantel。FPTAS用于优化多项式的混合整数点。数学规划，115(2):273-290，2008。ISSN 0025-5610。DOI:10.1007/S10107-007-0175-8。网址http://dx.doi.org/10.1007/s10107-007-0175-8.e。Delage和Y.Ye。矩不确定下的分布鲁棒优化及其在数据驱动问题中的应用。

运筹学，58:595-612，2010。DOI:10.1287/OPRE.1090.0741.p.R.格里比克。半规划问题的中心割平面算法。INR.Hettich，编辑，半专业编程，在控制与信息系统课堂讲稿中排名第15位。斯普林格·弗拉格，纽约，纽约州，1979年。Henrion和J.-B.拉塞尔。Gloptipoly：用Matlaband Sedumi实现多项式的全局优化。数学软件学报，29(2):165-194，2003年6月。ISSN0098-3500。DOI:10.1145/779359.779363.K。Hoyland，M.Kaut和S.W.华莱士。一种启发式的矩匹配场景生成方法。计算优化与应用，24(2):169-185，2003年2月。DOI:10.1023/A:1021853807313.K.-L.黄和S.Mehrotra。混合整数线性规划遍历启发式的经验评估。计算优化与应用，2013。DOI:10.1007/S10589-013-9540-0.R。Kannan和H.Narayanan。多边形上的随机游动和线性规划的一个内点法。运筹学数学，37(1):2012年2月11-20日。DOI:10.1016/j.ejor.2006.08.045.c。Kleiber和J.Stoyanov。多元分布与矩问题。《多元分析学报》，113(1):7-18，2013。ISSN 0047-259X。DOI:10.1016/j.jmva.2011.06.001.URL http://dx.doi.org/10.1016/j.jmva.2011.06.001.k。O.Kortanek和H.No.一个求解凸半整数规划问题的中心割平面算法。暹罗优化学报，3(4):901-918，1993年11月。多项式优化问题-逼近算法及应用。香港中文大学博士论文，2011年。奥佩兹和G.仍然。半自动编程。欧洲运筹学杂志，180:491-518，2007。DOI:10.1016/j.ejor.2006.08.045.L。Lov\'asz和S.Vempala。从拐角处肇事逃逸。计算学报，35(4):985-1005，2006。DOI:10.1137/S009753970544727X.S。Mehrotra和D.Papp。使用优化技术生成矩匹配场景。《暹罗优化期刊》，23(2):963-999，2013。网址http://dx.doi.org/10.117/110858082.s。Mehrotra和H.Zhang。分布鲁棒最小二乘问题的模型和算法。2013年被数学规划录取。网址http://link.springer.com/article/10.1007/s10107-013-0681-9。技术报告网址:http://www.optimization-online.org/db_file/2011/02/2925.pdf.d。帕普和F.阿里扎德。代数中平方和锥的半有限刻划。《暹罗优化杂志》，2011年。A.帕里洛。半代数问题的编程松弛。数学编程，96(2):293-320，2003。ISSN 0025-5610。DOI:10.1007/S10107-003-0387-5.H。E.围巾。一个库存问题的最小最大解。技术报告P-910,RANDCorporation,1957年。Tichatschke和V.Nebeling。二次半规划问题的割面法。优化，19(6):803-817，1988.DOI:10.1080/02331938808843393.S。韦姆帕拉。几何随机游动：一个综述。组合几何与计算几何，52:573-612，2005.H.Waki、S.Kim、M.Kojima和M.Muramatsu。结构稀疏多项式优化问题的平方和与半剖分程序松弛。暹罗优化杂志，17:218-242，2006。ISSN 1052-6234。Doi：10.1137/050623802。