A class of polynomial primal-dual interior-point algorithms for semidefinite optimization

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.

Complexity analysis of interior-point algorithm based on a new kernel function for semidefinite optimization

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.

THE SYMMETRIC AND SYMMETRIC POSITIVE SEMIDEFINITE SOLUTIONS OF LINEAR MATRIX EQUATION——B^TXB = D ON LINEAR MANIFOLDS

This paper discusses the solutions of the linear matrix equation BT X B=Don some linear manifolds.Some necessary and sufficient conditions for the existenceof the solution and the expression of the general solution are given.And also someoptimal approximation solutions are discussed.

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.

Reduction of truss topology optimization

A reduction of truss topology design problem formulated by semidefinite optimization （SDO） is considered. The finite groups and their representations are introduced to reduce the stiffness and mass matrices of truss in size. Numerical results are given for both the original problem and the reduced problem to make a comparison.

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.

An Effective Algorithm for Quadratic Optimization with Non-Convex Inhomogeneous Quadratic Constraints

This paper considers the NP (Non-deterministic Polynomial)-hard problem of finding a minimum value of a quadratic program (QP), subject to m non-convex inhomogeneous quadratic constraints. One effective algorithm is proposed to get a feasible solution based on the optimal solution of its semidefinite programming (SDP) relaxation problem.

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.

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

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

0-1多项式规划问题的SDP松弛方法(英文)

本文提出了一类新的构造0-1多项式规划的半定规划(SDP)松弛方法.我们首先利用矩阵分解和分片线性逼近给出一种新的SDP松弛,该松弛产生的界比标准线性松弛产生的界更紧.我们还利用拉格朗日松弛和平方和(SOS)松弛方法给出了一种构造Lasserre的SDP松弛的新方法.

A note on semidefinite programming relaxations for polynomial optimization over a single sphere

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.

不确定平方和凸多项式优化的SDP松弛与鲁棒鞍点刻画

考虑一类带不确定参数的平方和凸多项式优化问题.首先,借助鲁棒优化方法给出该不确定平方和凸多项式优化问题的鲁棒对等优化模型;然后,借助一类鲁棒型特征锥约束规格,建立该优化问题的精确半正定规划(SDP)松弛问题;最后,引入该不确定平方和凸多项式优化问题的Langrange函数,并借助平方和条件给出该不确定平方和凸多项式优化问题的鲁棒鞍点定理.

Complexity Analysis of an Interior Point Algorithm for the Semidefinite Optimization Based on a Kernel Function with a Double Barrier Term

In this paper, we establish the polynomial complexity of a primal-dual path-following interior point algorithm for solving semidefinite optimization（SDO） problems. The proposed algorithm is based on a new kernel function which differs from the existing kernel functions in which it has a double barrier term. With this function we define a new search direction and also a new proximity function for analyzing its complexity. We show that if q1 〉 q2 〉 1, the algorithm has O（（q1 ＋ 1） nq1＋1/2（q1-q2）logn/ε）and O（（q1 ＋ 1）2（q1-q2）^3q1-2q2＋1√n logn/c） complexity results for large- and small-update methods, respectively.

A Full-Newton Step Feasible IPM for Semidefinite Optimization Based on a Kernel Function with Linear Growth Term

In this paper,we propose and analyze a full-Newton step feasible interior-point algorithm for semidefinite optimization based on a kernel function with linear growth term.The kernel function is used both for determining the search directions and for measuring the distance between the given iterate and theμ-center for the algorithm.By developing a new norm-based proximity measure and some technical results,we derive the iteration bound that coincides with the currently best known iteration bound for the algorithm with small-update method.In our knowledge,this result is the first instance of full-Newton step feasible interior-point method for SDO which involving the kernel function.

An Efficient Parameterized Logarithmic Kernel Function for Semidefinite Optimization

In this paper,we present a primal-dual interior point algorithm for semidefinite optimization problems based on a new class of kernel functions.These functions constitute a combination of the classic kernel function and a barrier term.We derive the complexity bounds for large and small-update methods respectively.We show that the best result of iteration bounds for large and small-update methods can be achieved,namely O(q√n(log√n)^q+1/q logn/ε)for large-update methods and O(q^3/2(log√q)^q+1/q√nlogn/ε)for small-update methods.We test the efficiency and the validity of our algorithm by running some computational tests,then we compare our numerical results with results obtained by algorithms based on different kernel functions.

A Wide Neighborhood Interior-Point Algorithm for Convex Quadratic Semidefinite Optimization

In this paper,we propose an interior-point algorithm based on a wide neighborhood for convex quadratic semidefinite optimization problems.Using the Nesterov–Todd direction as the search direction,we prove the convergence analysis and obtain the polynomial complexity bound of the proposed algorithm.Although the algorithm belongs to the class of large-step interior-point algorithms,its complexity coincides with the best iteration bound for short-step interior-point algorithms.The algorithm is also implemented to demonstrate that it is efficient.

LQR与SDP相结合的电网暂稳态耦合控制研究

电网的优化控制需要解决不同时间尺度(年月级规划、小时级调度、毫秒级频率调节)问题,忽略任一时间尺度均会威胁电网安全。为此,提出了稳态运行、暂态稳定性及电网控制的耦合控制模型,将涉及系统安全的多时间尺度问题进行联合控制。首先将电力系统的稳态运行表示为凸优化问题,然后利用线性时不变系统来表示电网的暂态动态特性,并将线性二次型控制器表示为半正定规划进行最优控制,最后建立包含稳态运行变量的线性二次型控制器成本矩阵函数,将凸稳态运行模型和由线性二次型控制器转换的半正定规划公式融合为半正定规划问题。通过算例模拟了稳态运行与暂态控制的耦合优化控制,结果验证了控制算法的有效性。

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

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

智能反射面辅助的MU-MISO车联网毫米波通信联合波束赋形

近年来,车联网通信系统提出了大规模数据传输,通信连接稳定等需求。高频段通信凭借超高传输速率,低时延的特点被引入了该系统,但是,高频段通信仍面临着阻塞问题的挑战。因此,智能反射面作为一种可解决高频段通信阻塞问题的技术,成为车联网高频通信的热点议题。智能反射面由超材料构成,其表面的多个无源反射单元均匀排布形成阵列,所有反射单元的反射系数均可通过智能控制器实时调节,控制反射波束的方向和形状,来实现对无线传输环境的智能调控,提供增强视距通信、扩展通信覆盖范围等服务。针对MU-MISO车联网毫米波通信场景下,基站与车辆用户视线通信链路因遮蔽,车辆高速移动等因素,面临随机中断的问题,将智能反射面引入该系统,并结合该系统提出了基于半定松弛问题的交替迭代优化算法,以提高通信稳定性。该方法将系统中基站波束赋形矩阵优化和智能反射面相移矩阵优化分解为两个子问题,通过定义半定矩阵变量并适当放松特定的约束条件将两个子问题近似成为半定松弛问题,随后,使用交替优化技术对其进行迭代求解以实现联合优化,通过最大化同时刻通信车辆中的最小信干噪比来确保通信稳定性。仿真结果表明,该方法显著提高了车辆用户的信干噪比和基站的总频带利用率,确保了动态场景中车辆与基站的通信稳定性。

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

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