In this paper, we propose a primal-dual interior point method for solving general constrained nonlinear programming problems. To avoid the situation that the algorithm we use may converge to a saddle point or a local ...In this paper, we propose a primal-dual interior point method for solving general constrained nonlinear programming problems. To avoid the situation that the algorithm we use may converge to a saddle point or a local maximum, we utilize a merit function to guide the iterates toward a local minimum. Especially, we add the parameter ε to the Newton system when calculating the decrease directions. The global convergence is achieved by the decrease of a merit function. Furthermore, the numerical results confirm that the algorithm can solve this kind of problems in an efficient way.展开更多
In the present paper we present a class of polynomial primal-dual interior-point algorithms for semidefmite optimization based on a kernel function. This kernel function is not a so-called self-regular function due to...In the present paper we present a class of polynomial primal-dual interior-point algorithms for semidefmite optimization based on a kernel function. This kernel function is not a so-called self-regular function due to its growth term increasing linearly. Some new analysis tools were developed which can be used to deal with complexity ＂analysis of the algorithms which use analogous strategy in [5] to design the search directions for the Newton system. The complexity bounds for the algorithms with large- and small-update methodswere obtained, namely,O（qn^（p＋q/q（P＋1）log n/ε and O（q^2√n）log n/ε,respectlvely.展开更多
A primal-dual infeasible interior point algorithm for multiple objective linear programming (MOLP) problems was presented. In contrast to the current MOLP algorithm. moving through the interior of polytope but not con...A primal-dual infeasible interior point algorithm for multiple objective linear programming (MOLP) problems was presented. In contrast to the current MOLP algorithm. moving through the interior of polytope but not confining the iterates within the feasible region in our proposed algorithm result in a solution approach that is quite different and less sensitive to problem size, so providing the potential to dramatically improve the practical computation effectiveness.展开更多
Interior-point methods （IPMs） for linear optimization （LO） and semidefinite optimization （SDO） have become a hot area in mathematical programming in the last decades. In this paper, a new kernel function with si...Interior-point methods （IPMs） for linear optimization （LO） and semidefinite optimization （SDO） have become a hot area in mathematical programming in the last decades. In this paper, a new kernel function with simple algebraic expression is proposed. Based on this kernel function, a primal-dual interior-point methods （IPMs） for semidefinite optimization （SDO） is designed. And the iteration complexity of the algorithm as O（n^3/4 log n/ε） with large-updates is established. The resulting bound is better than the classical kernel function, with its iteration complexity O（n log n/ε） in large-updates case.展开更多
It is well established that Nash equilibrium exists within the framework of mixed strategies in strategic-form non-cooperative games. However, finding the Nash equilibrium generally belongs to the class of problems kn...It is well established that Nash equilibrium exists within the framework of mixed strategies in strategic-form non-cooperative games. However, finding the Nash equilibrium generally belongs to the class of problems known as PPAD (Polynomial Parity Argument on Directed graphs), for which no polynomial-time solution methods are known, even for two-player games. This paper demonstrates that in fixed-sum two-player games (including zero-sum games), the Nash equilibrium forms a convex set, and has a unique expected payoff. Furthermore, these equilibria are Pareto optimal. Additionally, it is shown that the Nash equilibrium of fixed-sum two-player games can theoretically be found in polynomial time using the principal-dual interior point method, a solution method of linear programming.展开更多
Kernel functions play an important role in defining new search directions for primal-dual interior-point algorithm for solving linear optimization problems. In this paper we present a new kernel function which yields ...Kernel functions play an important role in defining new search directions for primal-dual interior-point algorithm for solving linear optimization problems. In this paper we present a new kernel function which yields an algorithm with the best known complexity bound for both large- and small-update methods.展开更多
进化类算法和内点法交替迭代的混合算法在求解含电压源换流器的高压直流输电(voltage source converter basedhigh voltage direct current,VSC-HVDC)的交直流系统最优潮流(optimal power flow,OPF)问题时由于截断误差的影响和VSC-HVDC...进化类算法和内点法交替迭代的混合算法在求解含电压源换流器的高压直流输电(voltage source converter basedhigh voltage direct current,VSC-HVDC)的交直流系统最优潮流(optimal power flow,OPF)问题时由于截断误差的影响和VSC-HVDC控制方式的限制,容易发生振荡,因此提出一种基于差分进化(differential evolution,DE)和原—对偶内点法(primal-dual interior point method,PDIPM)的统一混合迭代算法。算法的主要思想是以DE算法为框架,对离散变量进行优化,在DE算法的每一次迭代过程中,采用PDIPM对每个DE个体进行连续变量的优化和适应度评估。由于采用PDIPM进行DE种群适应度评估,无需设定VSC-HVDC的控制方式,因此提高了算法的全局寻优能力。多个算例结果表明,该混合算法数值稳定性高,寻优能力强,能很好地解决含两端、多端、多馈入VSC-HVDC的交直流系统最优潮流问题。展开更多
电压源换流器(voltage source converter,VSC)在稳态模型和工作原理上与传统高压直流输电(high voltage directcurrent,HVDC)的换流器有本质区别,因此传统的交直流系统最优潮流计算方法不适用于含基于电压源换流器高压直流输电(VSC base...电压源换流器(voltage source converter,VSC)在稳态模型和工作原理上与传统高压直流输电(high voltage directcurrent,HVDC)的换流器有本质区别,因此传统的交直流系统最优潮流计算方法不适用于含基于电压源换流器高压直流输电(VSC based HVDC,VSC-HVDC)的交直流系统。讨论一种适用于原对偶内点法(primal-dual interior-pointmethod,PDIPM)和预测校正内点法(predictor-corrector PDIPM,PCPDIPM)解最优潮流的VSC-HVDC稳态模型。基于该稳态模型,将VSC-HVDC直流网络与交流系统结合起来,对交直流系统进行联立求解,并对多组算例进行仿真和分析,算例结果表明原对偶内点法在解决含VSC-HVDC的最优潮流问题的能力上,保持了传统内点法最优潮流的高效性,而在同样的条件下,预测–校正内点法迭代次数大大少于原对偶内点法。展开更多
根据电压源换流器–高压直流输电(voltage sourceconverter-high voltage direct current,VSC-HVDC)的稳态潮流模型,结合自动微分(automatic differentiation,AD)技术,提出一种基于原对偶内点法的交直流系统最优潮流算法。该算法利用高...根据电压源换流器–高压直流输电(voltage sourceconverter-high voltage direct current,VSC-HVDC)的稳态潮流模型,结合自动微分(automatic differentiation,AD)技术,提出一种基于原对偶内点法的交直流系统最优潮流算法。该算法利用高效的基于操作符重载的AD工具生成雅可比(Jacobian)矩阵和海森(Hessian)矩阵,减少了微分表达式推导和代码编写的工作量,提高了程序的开发效率。多个算例的仿真结果表明,该算法保持了传统原对偶内点法在解决含VSC-HVDC的交直流最优潮流问题上的高效性,且对VSC的不同控制方式组合均具有良好的适应性。展开更多
文摘In this paper, we propose a primal-dual interior point method for solving general constrained nonlinear programming problems. To avoid the situation that the algorithm we use may converge to a saddle point or a local maximum, we utilize a merit function to guide the iterates toward a local minimum. Especially, we add the parameter ε to the Newton system when calculating the decrease directions. The global convergence is achieved by the decrease of a merit function. Furthermore, the numerical results confirm that the algorithm can solve this kind of problems in an efficient way.
文摘In the present paper we present a class of polynomial primal-dual interior-point algorithms for semidefmite optimization based on a kernel function. This kernel function is not a so-called self-regular function due to its growth term increasing linearly. Some new analysis tools were developed which can be used to deal with complexity ＂analysis of the algorithms which use analogous strategy in [5] to design the search directions for the Newton system. The complexity bounds for the algorithms with large- and small-update methodswere obtained, namely,O（qn^（p＋q/q（P＋1）log n/ε and O（q^2√n）log n/ε,respectlvely.
基金Supported by the Doctoral Educational Foundation of China of the Ministry of Education(20020486035)
文摘A primal-dual infeasible interior point algorithm for multiple objective linear programming (MOLP) problems was presented. In contrast to the current MOLP algorithm. moving through the interior of polytope but not confining the iterates within the feasible region in our proposed algorithm result in a solution approach that is quite different and less sensitive to problem size, so providing the potential to dramatically improve the practical computation effectiveness.
基金Project supported by the National Natural Science Foundation of China （Grant No. 10117733）, the Shanghai Leading Academic Discipline Project （Grant No.J50101）, and the Foundation of Scientific Research for Selecting and Cultivating Young Excellent University Teachers in Shanghai （Grant No.06XPYQ52）
文摘Interior-point methods （IPMs） for linear optimization （LO） and semidefinite optimization （SDO） have become a hot area in mathematical programming in the last decades. In this paper, a new kernel function with simple algebraic expression is proposed. Based on this kernel function, a primal-dual interior-point methods （IPMs） for semidefinite optimization （SDO） is designed. And the iteration complexity of the algorithm as O（n^3/4 log n/ε） with large-updates is established. The resulting bound is better than the classical kernel function, with its iteration complexity O（n log n/ε） in large-updates case.
文摘It is well established that Nash equilibrium exists within the framework of mixed strategies in strategic-form non-cooperative games. However, finding the Nash equilibrium generally belongs to the class of problems known as PPAD (Polynomial Parity Argument on Directed graphs), for which no polynomial-time solution methods are known, even for two-player games. This paper demonstrates that in fixed-sum two-player games (including zero-sum games), the Nash equilibrium forms a convex set, and has a unique expected payoff. Furthermore, these equilibria are Pareto optimal. Additionally, it is shown that the Nash equilibrium of fixed-sum two-player games can theoretically be found in polynomial time using the principal-dual interior point method, a solution method of linear programming.
基金Supported by National Natural Science Foundation of China (Grant Nos.10771133 and 70871082)Shanghai Leading Academic Discipline Project (Grant No.S30104)
文摘Kernel functions play an important role in defining new search directions for primal-dual interior-point algorithm for solving linear optimization problems. In this paper we present a new kernel function which yields an algorithm with the best known complexity bound for both large- and small-update methods.
文摘进化类算法和内点法交替迭代的混合算法在求解含电压源换流器的高压直流输电(voltage source converter basedhigh voltage direct current,VSC-HVDC)的交直流系统最优潮流(optimal power flow,OPF)问题时由于截断误差的影响和VSC-HVDC控制方式的限制,容易发生振荡,因此提出一种基于差分进化(differential evolution,DE)和原—对偶内点法(primal-dual interior point method,PDIPM)的统一混合迭代算法。算法的主要思想是以DE算法为框架,对离散变量进行优化,在DE算法的每一次迭代过程中,采用PDIPM对每个DE个体进行连续变量的优化和适应度评估。由于采用PDIPM进行DE种群适应度评估,无需设定VSC-HVDC的控制方式,因此提高了算法的全局寻优能力。多个算例结果表明,该混合算法数值稳定性高,寻优能力强,能很好地解决含两端、多端、多馈入VSC-HVDC的交直流系统最优潮流问题。
文摘电压源换流器(voltage source converter,VSC)在稳态模型和工作原理上与传统高压直流输电(high voltage directcurrent,HVDC)的换流器有本质区别,因此传统的交直流系统最优潮流计算方法不适用于含基于电压源换流器高压直流输电(VSC based HVDC,VSC-HVDC)的交直流系统。讨论一种适用于原对偶内点法(primal-dual interior-pointmethod,PDIPM)和预测校正内点法(predictor-corrector PDIPM,PCPDIPM)解最优潮流的VSC-HVDC稳态模型。基于该稳态模型,将VSC-HVDC直流网络与交流系统结合起来,对交直流系统进行联立求解,并对多组算例进行仿真和分析,算例结果表明原对偶内点法在解决含VSC-HVDC的最优潮流问题的能力上,保持了传统内点法最优潮流的高效性,而在同样的条件下,预测–校正内点法迭代次数大大少于原对偶内点法。
文摘根据电压源换流器–高压直流输电(voltage sourceconverter-high voltage direct current,VSC-HVDC)的稳态潮流模型,结合自动微分(automatic differentiation,AD)技术,提出一种基于原对偶内点法的交直流系统最优潮流算法。该算法利用高效的基于操作符重载的AD工具生成雅可比(Jacobian)矩阵和海森(Hessian)矩阵,减少了微分表达式推导和代码编写的工作量,提高了程序的开发效率。多个算例的仿真结果表明,该算法保持了传统原对偶内点法在解决含VSC-HVDC的交直流最优潮流问题上的高效性,且对VSC的不同控制方式组合均具有良好的适应性。
