求解最优潮流问题(optimal power flow, OPF)的凸松弛技术可将非凸的OPF问题转化为凸优化问题,并在精确松弛的前提下获得原问题的全局最优解。近10年来,该项技术已成为国内外电力系统优化领域的一个研究热点。首先,回顾电力系统优化领...求解最优潮流问题(optimal power flow, OPF)的凸松弛技术可将非凸的OPF问题转化为凸优化问题,并在精确松弛的前提下获得原问题的全局最优解。近10年来,该项技术已成为国内外电力系统优化领域的一个研究热点。首先,回顾电力系统优化领域凸松弛技术的发展过程,介绍半正定规划松弛、二阶锥规划松弛、二次凸包络松弛的基本概念与数学形式。接着,对于凸松弛技术的精确性,总结并梳理保证精确松弛的充分条件和构造更紧凸松弛的方法。最后,从技术手段与应用场景两个方面对OPF凸松弛技术未来的研究方向做出展望。展开更多
基于内点半定规划(semi-definite programming,SDP),提出一种求解最优潮流(optimal power flow,OPF)的新方法——SDP-OPF法。该方法将非凸OPF问题等价转换为半定规划问题,然后应用原始–对偶内点法求解。根据OPF半定规划模型的特点,采...基于内点半定规划(semi-definite programming,SDP),提出一种求解最优潮流(optimal power flow,OPF)的新方法——SDP-OPF法。该方法将非凸OPF问题等价转换为半定规划问题,然后应用原始–对偶内点法求解。根据OPF半定规划模型的特点,采用基于半定规划的稀疏技术,使存储效率和计算性能得以大幅度提高。以4节点的简单电力系统为例,展示模型等价转换的过程及如何获取原OPF问题的解。IEEE-300节点等6个标准系统的仿真计算表明:所提算法具有超线性收敛性,其计算结果与内点非线性规划的结果一致,且能保证解的全局最优性,可在多项式时间内完成,是一种应用前景广阔的方法。展开更多
In this paper we present a filter-successive linearization method with trust region for solutions of nonlinear semidefinite programming. Such a method is based on the concept of filter for nonlinear programming introd...In this paper we present a filter-successive linearization method with trust region for solutions of nonlinear semidefinite programming. Such a method is based on the concept of filter for nonlinear programming introduced by Fletcher and Leyffer in 2002. We describe the new algorithm and prove its global convergence under weaker assumptions. Some numerical results are reported and show that the new method is potentially efficient.展开更多
以内点法求解最优潮流(optimal power flow,OPF)的经典非线性规划模型已得到广泛应用,但无法保证解的全局最优性。而求解OPF的半正定规划模型,在一定条件下能获得全局最优解,但存在计算时间长和可能无法获得可行解的缺点。因此,文中提...以内点法求解最优潮流(optimal power flow,OPF)的经典非线性规划模型已得到广泛应用,但无法保证解的全局最优性。而求解OPF的半正定规划模型,在一定条件下能获得全局最优解,但存在计算时间长和可能无法获得可行解的缺点。因此,文中提出一种结合非线性规划和半正定规划模型两者优势求解OPF问题的混合优化方法,以实现在更短的时间内获得全局最优解。首先,提出验证由内点法求解OPF非线性规划模型(nonlinear programming,NLP)所得解是否为全局最优的充分条件。若非全局最优,则基于OPF的半正定规划模型给出由该局部最优解出发的下降方向,并通过步长控制得到新的初值,交由内点法重新求解OPF的非线性规划模型。算例测试结果表明,该算法在避免求解完整半正定模型需耗费大量时间的同时,能够有效跳出非线性规划模型的局部最优解,收敛到全局最优解或更优的解。展开更多
This paper presents a hybrid symbolic-numeric algorithm to compute ranking functions for establishing the termination of loop programs with polynomial guards and polynomial assignments.The authors first transform the ...This paper presents a hybrid symbolic-numeric algorithm to compute ranking functions for establishing the termination of loop programs with polynomial guards and polynomial assignments.The authors first transform the problem into a parameterized polynomial optimization problem,and obtain a numerical ranking function using polynomial sum-of-squares relaxation via semidefinite programming(SDP).A rational vector recovery algorithm is deployed to recover a rational polynomial from the numerical ranking function,and some symbolic computation techniques are used to certify that this polynomial is an exact ranking function of the loop programs.At last,the authors demonstrate on some polynomial loop programs from the literature that our algorithm successfully yields nonlinear ranking functions with rational coefficients.展开更多
Many problems in mathematical programming can be modelled as semidefinite programming. The success of interior point algorithms for large-scale linear programming has prompted researchers to develop these algorithms t...Many problems in mathematical programming can be modelled as semidefinite programming. The success of interior point algorithms for large-scale linear programming has prompted researchers to develop these algorithms to the semidefinite programming (SDP) case. In this paper, we extend Roos’s projective method for linear programming to SDP. The method is path-following and based on the useof a multiplicative barrier function. The iteration bound depends on the choice ofthe exponent μ in the numerator of the barrier function. The analysis in this paper resembles the one of the approximate center method for linear programming, as proposed by Rocs and Vial [14].展开更多
We study two instances of polynomial optimization problem over a single sphere. The first problem is to compute the best rank-1 tensor approximation. We show the equivalence between two recent semidefinite relaxations...We study two instances of polynomial optimization problem over a single sphere. The first problem is to compute the best rank-1 tensor approximation. We show the equivalence between two recent semidefinite relaxations methods. The other one arises from Bose-Einstein condensates(BEC), whose objective function is a summation of a probably nonconvex quadratic function and a quartic term. These two polynomial optimization problems are closely connected since the BEC problem can be viewed as a structured fourth-order best rank-1 tensor approximation. We show that the BEC problem is NP-hard and propose a semidefinite relaxation with both deterministic and randomized rounding procedures. Explicit approximation ratios for these rounding procedures are presented. The performance of these semidefinite relaxations are illustrated on a few preliminary numerical experiments.展开更多
文摘求解最优潮流问题(optimal power flow, OPF)的凸松弛技术可将非凸的OPF问题转化为凸优化问题,并在精确松弛的前提下获得原问题的全局最优解。近10年来,该项技术已成为国内外电力系统优化领域的一个研究热点。首先,回顾电力系统优化领域凸松弛技术的发展过程,介绍半正定规划松弛、二阶锥规划松弛、二次凸包络松弛的基本概念与数学形式。接着,对于凸松弛技术的精确性,总结并梳理保证精确松弛的充分条件和构造更紧凸松弛的方法。最后,从技术手段与应用场景两个方面对OPF凸松弛技术未来的研究方向做出展望。
文摘基于内点半定规划(semi-definite programming,SDP),提出一种求解最优潮流(optimal power flow,OPF)的新方法——SDP-OPF法。该方法将非凸OPF问题等价转换为半定规划问题,然后应用原始–对偶内点法求解。根据OPF半定规划模型的特点,采用基于半定规划的稀疏技术,使存储效率和计算性能得以大幅度提高。以4节点的简单电力系统为例,展示模型等价转换的过程及如何获取原OPF问题的解。IEEE-300节点等6个标准系统的仿真计算表明:所提算法具有超线性收敛性,其计算结果与内点非线性规划的结果一致,且能保证解的全局最优性,可在多项式时间内完成,是一种应用前景广阔的方法。
基金supported by National Natural Science Foundation of China (Grant No. 10871098)Science Foundation of Jiangsu Province (Grant No. BK2006214)
文摘In this paper we present a filter-successive linearization method with trust region for solutions of nonlinear semidefinite programming. Such a method is based on the concept of filter for nonlinear programming introduced by Fletcher and Leyffer in 2002. We describe the new algorithm and prove its global convergence under weaker assumptions. Some numerical results are reported and show that the new method is potentially efficient.
文摘以内点法求解最优潮流(optimal power flow,OPF)的经典非线性规划模型已得到广泛应用,但无法保证解的全局最优性。而求解OPF的半正定规划模型,在一定条件下能获得全局最优解,但存在计算时间长和可能无法获得可行解的缺点。因此,文中提出一种结合非线性规划和半正定规划模型两者优势求解OPF问题的混合优化方法,以实现在更短的时间内获得全局最优解。首先,提出验证由内点法求解OPF非线性规划模型(nonlinear programming,NLP)所得解是否为全局最优的充分条件。若非全局最优,则基于OPF的半正定规划模型给出由该局部最优解出发的下降方向,并通过步长控制得到新的初值,交由内点法重新求解OPF的非线性规划模型。算例测试结果表明,该算法在避免求解完整半正定模型需耗费大量时间的同时,能够有效跳出非线性规划模型的局部最优解,收敛到全局最优解或更优的解。
基金supported in part by the National Natural Science Foundation of China under Grant Nos.10901055,61021004,91118007by NKBRPC 2011CB302802,2011CB70690by the Fundamental Research Funds for the Central Universities under Grant No.78210043
文摘This paper presents a hybrid symbolic-numeric algorithm to compute ranking functions for establishing the termination of loop programs with polynomial guards and polynomial assignments.The authors first transform the problem into a parameterized polynomial optimization problem,and obtain a numerical ranking function using polynomial sum-of-squares relaxation via semidefinite programming(SDP).A rational vector recovery algorithm is deployed to recover a rational polynomial from the numerical ranking function,and some symbolic computation techniques are used to certify that this polynomial is an exact ranking function of the loop programs.At last,the authors demonstrate on some polynomial loop programs from the literature that our algorithm successfully yields nonlinear ranking functions with rational coefficients.
文摘Many problems in mathematical programming can be modelled as semidefinite programming. The success of interior point algorithms for large-scale linear programming has prompted researchers to develop these algorithms to the semidefinite programming (SDP) case. In this paper, we extend Roos’s projective method for linear programming to SDP. The method is path-following and based on the useof a multiplicative barrier function. The iteration bound depends on the choice ofthe exponent μ in the numerator of the barrier function. The analysis in this paper resembles the one of the approximate center method for linear programming, as proposed by Rocs and Vial [14].
基金supported by National Natural Science Foundation of China (Grant Nos. 11401364, 11322109, 11331012, 11471325 and 11461161005)the National High Technology Research and Development Program of China (863 Program) (Grant No. 2013AA122902)+1 种基金the National Center for Mathematics and Interdisciplinary Sciences, Chinese Academy of SciencesNational Basic Research Program of China (973 Program) (Grant No. 2015CB856002)
文摘We study two instances of polynomial optimization problem over a single sphere. The first problem is to compute the best rank-1 tensor approximation. We show the equivalence between two recent semidefinite relaxations methods. The other one arises from Bose-Einstein condensates(BEC), whose objective function is a summation of a probably nonconvex quadratic function and a quartic term. These two polynomial optimization problems are closely connected since the BEC problem can be viewed as a structured fourth-order best rank-1 tensor approximation. We show that the BEC problem is NP-hard and propose a semidefinite relaxation with both deterministic and randomized rounding procedures. Explicit approximation ratios for these rounding procedures are presented. The performance of these semidefinite relaxations are illustrated on a few preliminary numerical experiments.
