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...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.展开更多
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 （CWL...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.展开更多
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...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.展开更多
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, underes...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 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 equatio...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.展开更多
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 random...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.展开更多
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 ...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.展开更多
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 gen...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.展开更多
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 r...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.展开更多
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 w...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.展开更多
The joint beamforming design challenge for dual-functional radar-communication systems is addressed in this paper.The base station in these systems is tasked with simultaneously sending shared signals for both multi-u...The joint beamforming design challenge for dual-functional radar-communication systems is addressed in this paper.The base station in these systems is tasked with simultaneously sending shared signals for both multi-user communication and target sensing.The primary objective is to maximize the sum rate of multi-user communication,while also ensuring sufficient beampattern gain at particular angles that are of interest for sensing,all within the constraints of the transmit power budget.To tackle this complex non-convex problem,an effective algorithm that iteratively optimizes the joint beamformers is developed.This algorithm leverages the techniques of fractional programming and semidefinite relaxation to achieve its goals.The numerical results confirm the effectiveness of the proposed algorithm.展开更多
互耦效应是天线阵列工作时阵元相互之间产生的一种干扰影响,会导致理想导向矢量与真实导向矢量之间存在偏差,严重影响参数的估计性能。本文针对阵列互耦扰动下的波达方向(Di-rection of Arrival,DOA)估计问题,提出了一种新的原子范数最...互耦效应是天线阵列工作时阵元相互之间产生的一种干扰影响,会导致理想导向矢量与真实导向矢量之间存在偏差,严重影响参数的估计性能。本文针对阵列互耦扰动下的波达方向(Di-rection of Arrival,DOA)估计问题,提出了一种新的原子范数最小化方法MC-ANM,以提高参数估计精度。由于阵列互耦扰动下的原子结构不满足范德蒙德特性,原问题无法直接转化为半定规划程序。因此,文中基于对偶范数理论,推导了一个新的半定规划优化模型,作为原问题对应的对偶问题的充分近似,并构建了对偶多项式,以求解该半定规划优化中的DOA参数。仿真实验结果显示所提出的MC-ANM方法相较于传统原子范数最小化方法的估计性能有了明显的提升,同时估计精度要好于其他互耦扰动下的DOA估计算法。展开更多
基金Fundamental Research Funds for the Central Universities,China(No.2232019D3-38)Shanghai Sailing Program,China(No.22YF1400900)。
文摘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.
基金supported by the National Natural Science Foundation of China(61201282)the Science and Technology on Communication Information Security Control Laboratory Foundation(9140C130304120C13064)
文摘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.
文摘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.
文摘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 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.
文摘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.
文摘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.
文摘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.
基金supported by the National Natural Science Foundation of China(61871050)。
文摘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.
基金supported by the Science and Technology Project of State Grid Corporation of China (No.5204JY20000B)。
文摘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.
基金supported in part by the National Natural Science Foundation of China under Grant No.62201266in part by the Natural Science Foundation of Jiangsu Province under Grant No.BK20210335.
文摘The joint beamforming design challenge for dual-functional radar-communication systems is addressed in this paper.The base station in these systems is tasked with simultaneously sending shared signals for both multi-user communication and target sensing.The primary objective is to maximize the sum rate of multi-user communication,while also ensuring sufficient beampattern gain at particular angles that are of interest for sensing,all within the constraints of the transmit power budget.To tackle this complex non-convex problem,an effective algorithm that iteratively optimizes the joint beamformers is developed.This algorithm leverages the techniques of fractional programming and semidefinite relaxation to achieve its goals.The numerical results confirm the effectiveness of the proposed algorithm.
文摘互耦效应是天线阵列工作时阵元相互之间产生的一种干扰影响,会导致理想导向矢量与真实导向矢量之间存在偏差,严重影响参数的估计性能。本文针对阵列互耦扰动下的波达方向(Di-rection of Arrival,DOA)估计问题,提出了一种新的原子范数最小化方法MC-ANM,以提高参数估计精度。由于阵列互耦扰动下的原子结构不满足范德蒙德特性,原问题无法直接转化为半定规划程序。因此,文中基于对偶范数理论,推导了一个新的半定规划优化模型,作为原问题对应的对偶问题的充分近似,并构建了对偶多项式,以求解该半定规划优化中的DOA参数。仿真实验结果显示所提出的MC-ANM方法相较于传统原子范数最小化方法的估计性能有了明显的提升,同时估计精度要好于其他互耦扰动下的DOA估计算法。
