Modified Exact Jacobian Semidefinite Programming Relaxation for Celis-Dennis-Tapia Problem

A modified exact Jacobian semidefinite programming(SDP)relaxation method is proposed in this paper to solve the Celis-Dennis-Tapia(CDT)problem using the Jacobian matrix of objective and constraining polynomials.In the modified relaxation problem,the number of introduced constraints and the lowest relaxation order decreases significantly.At the same time,the finite convergence property is guaranteed.In addition,the proposed method can be applied to the quadratically constrained problem with two quadratic constraints.Moreover,the efficiency of the proposed method is verified by numerical experiments.

Semidefinite programming approach for TDOA/GROA based source localization

Time-differences-of-arrival （TDOA） and gain-ratios-of- arrival （GROA） measurements are used to determine the passive source location. Based on the measurement models, the con- strained weighted least squares （CWLS） estimator is presented. Due to the nonconvex nature of the CWLS problem, it is difficult to obtain its globally optimal solution. However, according to the semidefinite relaxation, the CWLS problem can be relaxed as a convex semidefinite programming problem （SDP）, which can be solved by using modern convex optimization algorithms. Moreover, this relaxation can be proved to be tight, i.e., the SDP solves the relaxed CWLS problem, and this hence guarantees the good per- formance of the proposed method. Furthermore, this method is extended to solve the localization problem with sensor position errors. Simulation results corroborate the theoretical results and the good performance of the proposed method.

ON SOME PROPERTIES OF SOLUTIONS TO SEMIDEFINITE PROGRAMMING

It is well known that for symmetric linear programming there exists a strictly complementary solution if the primal and the dual problems are both feasible. However, this is not necessary true for symmetric or general semide finite programming even if both the primal problem and its dual problem are strictly feasible. Some other properties are also concerned.

Safe Bounds in Semidefinite Programming by Using Interval Arithmetic

Efficient solvers for optimization problems are based on linear and semidefinite relaxations that use floating point arithmetic. However, due to the rounding errors, relaxation thus may overestimate, or worst, underestimate the very global optima. The purpose of this article is to introduce an efficient and safe procedure to rigorously bound the global optima of semidefinite program. This work shows how, using interval arithmetic, rigorous error bounds for the optimal value can be computed by carefully post processing the output of a semidefinite programming solver. A lower bound is computed on a semidefinite relaxation of the constraint system and the objective function. Numerical results are presented using the SDPA (SemiDefinite Programming Algorithm), solver to compute the solution of semidefinite programs. This rigorous bound is injected in a branch and bound algorithm to solve the optimisation problem.

A SUCCESSIVE QUADRATIC PROGRAMMING ALGORITHM FOR SDP RELAXATION OF MAX-BISECTION

A successive quadratic programming algorithm for solving SDP relaxation of Max- Bisection is provided and its convergence result is given. The step-size in the algorithm is obtained by solving n easy quadratic equations without using the linear search technique. The numerical experiments show that this algorithm is rather faster than the interior-point method.

Successive quadratic programming multiuser detector

Based on the semidefinite programming relaxation of the CDMA maximum likelihood multiuser detection problem, a detection strategy by the successive quadratic programming algorithm is presented. Coupled with the randomized cut generation scheme, the suboptimal solution of the multiuser detection problem in obtained. Compared to the interior point methods previously reported based on semidefmite programming, simulations demonstrate that the successive quadratic programming algorithm often yields the similar BER performances of the multiuser detection problem. But the average CPU time of this approach is significantly reduced.

On Decompositions of Real Polynomials Using Mathematical Programming Methods

We present a procedure that gives us an SOS (sum of squares) decomposition of a given real polynomial in variables, if there exists such decomposition. For the case of real polynomials in non-commutative variables we extend this procedure to obtain a sum of hermitian squares SOHS) decomposition whenever there exists any. This extended procedure is the main scientific contribution of the paper.

Higher-Order Duality for Minimax Fractional Type Programming Involving Symmetric Matrices

Convexity and generalized convexity play important roles in optimization theory. With the development of programming problem, there has been a growing interest in the higher-order dual problem and a lot of related generalized convexities are given. In this paper, we give the convexity of (F, α ,p ,d ,b , φ )β vector-pseudo- quasi-Type I and formulate a higher-order duality for minimax fractional type programming involving symmetric matrices, and give the weak, strong and strict converse duality theorems under the condition of higher-order (F, α ,p ,d ,b , φ )β vector-pseudoquasi-Type I.

Weighted semidefinite programming scheme for wireless positioning with lognormal shadowing

Received signal strength(RSS)based positioning schemes ignore the actual environmental feature that the volatility of RSS increases as signal propagation distance grows.Therefore,RSS over long distance generally has relatively large measurement error and degrades the positioning performance.To reduce the negative impact of these RSSs over long distances,a weighted semidefinite programming(WSDP)positioning scheme was proposed.The WSDP positioning scheme first assesses the signal propagation quality using the average variance of all RSS sets.Then appropriate weighting factors are set based on the variance of each RSS set,and a weighted semidefinite programming optimizer is formulated to estimate the positions of target nodes.Simulation results show that the WSDP positioning scheme can effectively improve the positioning performance.

Optimal Micro-PMU Placement for Improving State Estimation Accuracy via Mixed-integer Semidefinite Programming

Micro-phasor measurement units(μPMUs)with a micro-second resolution and milli-degree accuracy capability are expected to play an important role in improving the state estimation accuracy in the distribution network with increasing penetration of distributed generations.Therefore,this paper investigates the problem of how to place a limited number ofμPMUs to improve the state estimation accuracy.Combined with pseudo-measurements and supervisory control and data acquisition(SCADA)measurements,an optimalμPMU placement model is proposed based on a two-step state estimation method.The E-optimal experimental criterion is utilized to measure the state estimation accuracy.The nonlinear optimization problem is transformed into a mixed-integer semidefinite programming(MISDP)problem,whose optimal solution can be obtained by using the improved Benders decomposition method.Simulations on several systems are carried out to evaluate the effective performance of the proposed model.

无需先验测量误差的定位节点选择方法

针对现有定位节点选择算法依赖先验测量误差的问题,研究了一种不依赖先验测量误差的时差与频差无源定位节点选择方法,该方法将两步加权最小二乘定位算法中目标估计误差协方差作为目标函数。在给定可用定位节点数目的情况下,通过引入一组布尔量构建关于目标函数为带约束的最小估计误差寻优问题,通过半定松弛技术将非凸问题转为半定规划问题进行求解,依据最小化问题特性,使得所提算法不依赖先验测量误差。仿真结果表明,不依赖测量误差的方法与穷举搜索法相比在定位性能上无太大差别;相比于穷尽搜索算法,所提方法复杂度低、实时性好。同时,仿真结果进一步表明在对运动目标定位过程中,及时调整定位节点组合的必要性。

基于SDP松弛的干扰资源优化分配技术研究

提出一种基于semidefinite programming(简称SDP)松弛的干扰资源优化分配算法。在问题优化过程中首先对模型中非凸的约束条件进行松弛,变为凸约束,将原来的数学模型转化成SDP求解形式,利用内点算法对松弛后的模型求解。该算法利用解析的手段使得干扰资源优化分配问题中的NP难问题在多项式时间内得以解决,并且有较高的可靠性。仿真结果验证了算法的有效性。

分布式卫星系统中的物理层安全波束成形算法

针对分布式卫星系统中的安全传输问题,提出两种协作波束成形算法。首先,针对分布式卫星系统采用放大转发协议将来自静止轨道的卫星信号转发至合法用户的场景,构建以最小化分布式卫星系统的总发射功率为目标、合法用户安全速率和非目标用户受到的干扰满足要求为约束条件的优化问题。其次,为求解该非凸优化问题,提出一种基于拉格朗日对偶和半正定规划相结合的协作波束成形算法,并得出最优波束成形权矢量。此外,提出一种基于部分迫零的次优协作波束成形算法,可在不折损系统性能要求的条件下有效降低实现复杂度。相较于传统迫零算法,所提最优和次优算法能够分别节省20 dB和15 dB左右的功率。

基于半正定规划的交直流主动配电网三相有功无功联合优化

交直流主动配电网作为未来配电网的主要发展形态,实现其有功无功资源的协同优化控制具有重要的研究意义。然而配电网负荷单相接入和分布式发电三相功率不一致,将导致配电网三相不平衡现象越发严重。为了应对交直流主动配电网的三相不平衡问题,提出考虑相间耦合与三相不平衡度限制的三相有功无功联合优化方法。首先,建立考虑相间耦合的原始三相潮流模型并对其进行升维映射;其次,采用半正定松弛方法,推导了交直流主动配电网各子系统的完整三相潮流模型以及序分量形式下的三相电压不平衡度约束;再次,提出以总运行成本最小化为目标函数的交直流主动配电网三相有功无功联合优化模型;最后,采用改进IEEE 33节点、69节点、141节点和1056节点交直流配电网算例分析,验证了该文所提方法的有效性。

两阶段金融衍生品清算问题的半定规划松弛方法

在不限制暂时性及永久性价格影响参数大小关系下,研究两阶段金融衍生品清算问题的半定规划(Semi-definite programming,SDP)松弛方法,其优化模型为一个带有线性和单个非凸二次约束的非凸二次规划(Quadratically constrained quadratic program,QCQP)问题。针对该非凸QCQP问题,给出了一个带有Secant割的SDP松弛,并估计了它与原问题之间的间隙。随机例子的数值结果表明该SDP松弛可以得到原问题更紧的上界,从而为寻求原问题的一个好的近似解提供方法。

基于图神经网络的最大化代数连通度算法

随着智能体数量的增加,多智能体系统中潜在的通信链路数量呈指数级增长.过多冗余链路的存在给系统带来了大量的能源浪费和维护成本,而盲目地去除链路又会降低系统的稳定性和安全性.代数连通度是衡量图连通性的重要指标之一.然而,传统的半正定规划(SDP)方法和启发式算法在求解大规模场景下的最大化代数连通度问题时非常耗时.在本文中,我们提出了一种监督式的图神经网络模型来优化多智能体系统的代数连通度.我们将传统的SDP方法应用于小规模任务场景中,得到足够丰富的训练样本和标签.在此基础上,我们训练了一个图神经网络模型,该模型可用于更大规模的任务场景中.实验结果表明,当需要去除15条边时,我们的模型的平均性能达到了传统SDP方法的98.39%.此外,我们的模型计算时间极其有限,可以推广到实时场景中去.

非线性半定规划一个全局收敛的无罚无滤子SSDP算法

提出了一个求解非线性半定规划的无罚函数无滤子序列二次半定规划(SSDP)算法.算法每次迭代只需求解一个二次半定规划子问题确定搜索方向;非单调线搜索保证目标函数或约束违反度函数的充分下降,从而产生新的迭代点.在适当的假设条件下,证明了算法的全局收敛性.最后给出了初步的数值实验结果.

面向阵列互耦扰动DOA估计的原子范数方法

互耦效应是天线阵列工作时阵元相互之间产生的一种干扰影响,会导致理想导向矢量与真实导向矢量之间存在偏差,严重影响参数的估计性能。本文针对阵列互耦扰动下的波达方向(Di-rection of Arrival,DOA)估计问题,提出了一种新的原子范数最小化方法MC-ANM,以提高参数估计精度。由于阵列互耦扰动下的原子结构不满足范德蒙德特性,原问题无法直接转化为半定规划程序。因此,文中基于对偶范数理论,推导了一个新的半定规划优化模型,作为原问题对应的对偶问题的充分近似,并构建了对偶多项式,以求解该半定规划优化中的DOA参数。仿真实验结果显示所提出的MC-ANM方法相较于传统原子范数最小化方法的估计性能有了明显的提升,同时估计精度要好于其他互耦扰动下的DOA估计算法。

基于矩阵分解的0-1二次规划的SDP松弛

0-1二次规划是整数规划中一类重要的最优化问题,广泛应用于工程、经济管理、金融和管理科学等许多重要领域.利用矩阵分解方法,给出了带线性约束的0-1二次规划的一个紧的SDP松弛.通过目标函数的矩阵分解并利用二次项的片段线性逼近技术,得到了原问题的一个凸松弛.再利用锥优化对偶性,证明了寻找凸松弛中的最优参数问题可以归结为求解一个SDP问题,数值结果也表明该SDP松弛能提供原问题的一个更紧的下界.