Approximate Augmented Lagrangian Functions and Nonlinear Semidefinite Programs

In this paper, an approximate augmented Lagrangian function for nonlinear semidefinite programs is introduced. Some basic properties of the approximate augmented Lagrange function such as monotonicity and convexity are discussed. Necessary and sufficient conditions for approximate strong duality results are derived. Conditions for an approximate exact penalty representation in the framework of augmented Lagrangian are given. Under certain conditions, it is shown that any limit point of a sequence of stationary points of approximate augmented Lagrangian problems is a KKT point of the original semidefinite program and that a sequence of optimal solutions to augmented Lagrangian problems converges to a solution of the original semidefinite program.

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.

Passive Localization of Signal Source Based on UAVs in Complex Environment

For the influence caused by multipath fading and non-line-of-sight(NLOS)transmission,it is challenging to accurately localize a moving signal source in complex environment by using the wireless sensor network(WSN)on the ground.In this paper,we establish a special WSN in the sky to address this challenge,where each sensor is loaded on an unmanned aerial vehicle(UAV)and the operation center of all the UAVs is fixed on the ground.Based on the analyzing of the optimal distribution and the position error calibration of all the sensors,we formulate the localization scheme to estimate the position of the target source,which combines the time difference of arrival(TDOA)method and the frequency difference of arrival(FDOA)method.Then by employing the semidefinite programming approach,we accurately obtain the position and velocity of the signal source.In the simulation,the validity of the proposed method is verified through the performance comparison.

Joint Antenna Selection and Robust Beamforming Design in Multi-cell Distributed Antenna System

Most of studies on Distributed Antenna System(DAS) focus on maximizing the sum capacity and perfect channel state information at transmitter(CSIT).However,CSI is inevitable imperfect in practical wireless networks.Based on the sources of error,there are two models.One assumes error lies in a bounded region,the other assumes random error.Accordingly,we propose two joint antenna selection(AS) and robustbeamforming schemes aiming to minimize the total transmit power at antenna nodes subject to quality of service(QoS) guarantee for all the mobile users(MUs) in multicell DAS.This problem is mathematically intractable.For the bounded error model,we cast it into a semidefinite program(SDP) using semidefinite relaxation(SDR) and S-procedure.For the second,we first design outage constrained robust beamforming and then formulate it as an SDP based on the Bernstein-type inequality,which we generalize it to the multi-cell DAS.Simulation results verify the effectiveness of the proposed methods.

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.

Semidefinite Relaxation for Two Mixed Binary Quadratically Constrained Quadratic Programs:Algorithms and Approximation Bounds

This paper develops new semidefinite programming(SDP)relaxation techniques for two classes of mixed binary quadratically constrained quadratic programs and analyzes their approximation performance.The first class of problems finds two minimum norm vectors in N-dimensional real or complex Euclidean space,such that M out of 2M concave quadratic constraints are satisfied.By employing a special randomized rounding procedure,we show that the ratio between the norm of the optimal solution of this model and its SDP relaxation is upper bounded by 54πM2 in the real case and by 24√Mπin the complex case.The second class of problems finds a series of minimum norm vectors subject to a set of quadratic constraints and cardinality constraints with both binary and continuous variables.We show that in this case the approximation ratio is also bounded and independent of problem dimension for both the real and the complex cases.

A new class of states of reversible entanglement manipulation under positive partial transpose operations

We first study the reversibility for a class of states under the operations which completely preserve the positivity of partial transpose（PPT） and show that the entanglement cost is equal to the distillable entanglement for a rank-two mixed state on the 4 4 antisymmetric subspace under PPT operations. By using a similar method in finding the irreversibility,we also find that the value of a new efficiently computable additive lower bound Eη（ρ） for the asymptotic PPT-relative entropy of entanglement presented in [Phys. Rev. Lett. 119, 180506（2017）] is equal to the regularized Rains＇ bound and an upper bound EN（ρ） for distillable entanglement for these states. Furthermore, we find states on the symmetric subspace satisfying the relation mentioned above, generalize the antisymmetric states and symmetric states in higher dimensions, and give a specific value for distillable entanglement and entanglement cost for these states under the PPT operations.

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.

NEW ALGORITHM FOR FIR FILTER DESIGN WITH DISCRETE COEFFICIENTS

This paper develops a new algorithm based on the Projected Gradient Algorithm (PGA) for the design of FIR digital filters with "sum of power of two" coefficients. It is shown that the integer programming involved in the FIR filter design can be solved by this algorithm. It is compared with the reported method for a SemiDefinite Programming (SDP) relaxation- based design. The simulations demonstrate that the new algorithm often yields the similar error performances of the FIR filter design, but the average CPU time of this approach is significantly reduced.

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.

Leader-follower Optimal Selection Method for Distributed Control System in Active Distribution Networks

Aiming at the shortcomings of a traditional centralized control in an active distribution network(AND),this paper proposes a leader-follower distributed group cooperative control strategy to realize multiple operation and control tasks for an ADN.The distributed information exchange protocols of the distributed generation(DG)group devoted to node voltage regulation or exchange power control are developed using a DG power utilization ratio as the consensus variable.On these bases,this study further investigates the leader optimal selection method for a DG group to improve the response speed of the distributed control system.Furthermore,a single or multiple leader selection model is established to minimize the constraints of the one-step convergence factor and the number of leaders to improve the response speed of the distributed control system.The simulation results of the IEEE 33 bus standard test system show the effectiveness of the proposed distributed control strategy.In addition,the response speed of a DG control group can be improved effectively when the single or multiple leaders are selected optimally.

On filter-successive linearization methods for nonlinear semidefinite programming

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.

A Filter Method for Nonlinear Semidefinite Programming with Global Convergence

In this study, a new filter algorithm is presented for solving the nonlinear semidefinite programming. This algorithm is inspired by the classical sequential quadratic programming method. Unlike the traditional filter methods, the sufficient descent is ensured by changing the step size instead of the trust region radius. Under some suitable conditions, the global convergence is obtained. In the end, some numerical experiments are given to show that the algorithm is effective.

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.

New semidefinite programming relaxations for box constrained quadratic program

We establish in this paper optimal parametric Lagrangian dual models for box constrained quadratic program based on the generalized D.C.(difference between convex) optimization approach,which can be reformulated as semidefinite programming problems.As an application,we propose new valid linear constraints for rank-one relaxation.

APPROXIMATION ALGORITHM FOR MAX-BISECTION PROBLEM WITH THE POSITIVE SEMIDEFINITE RELAXATION

Using outward rotations, we obtain an approximation algorithm for Max-Bisection problem, i.e., partitioning the vertices of an undirected graph into two blocks of equal cardinality so as to maximize the weights of crossing edges. In many interesting cases, the algorithm performs better than the algorithms of Ye and of Halperin and Zwick. The main tool used to obtain this result is semidefinite programming.

Voltage Stability Constrained Optimal Power Flow for Unbalanced Distribution System Based on Semidefinite Programming

This paper proposes a voltage stability constrained optimal power flow(VSC-OPF)for an unbalanced distribution system with distributed generators(DGs)based on semidefinite programming(SDP).The AC optimal power flow(ACOPF)for unbalanced distribution systems is formulated as a chordal relaxation-based SDP model.The minimal singular value(MSV)of the power flow Jacobian matrix is adopted to indicate the voltage stability margin.The Jacobian matrix can be explicitly expressed by ACOPF state variables.The nonlinear constraint on the Jacobian MSV is then replaced with its maximal convex subset using linear matrix inequality(LMI),which can be incorporated in the SDP-based ACOPF formulation.A penalty technique is leveraged to improve the exactness of the SDP relaxation.Case studies performed on several IEEE test systems validate the effectiveness of the proposed method.

Conditional Quadratic Semidefinite Programming:Examples and Methods

The conditional quadratic semidefinite programming(cQSDP)refers to a class of matrix optimization problems whose matrix variables are required to be positive semidefinite on a subspace,and the objectives are quadratic.The chief purpose of this paper is to focus on two primal examples of cQSDP:the problem of matrix completion/approximation on a subspace and the Euclidean distance matrix problem.For the latter problem,we review some classical contributions and establish certain links among them.Moreover,we develop a semismooth Newton method for a special class of cQSDP and establish its quadratic convergence under the condition of constraint nondegeneracy.We also include an application in calibrating the correlation matrix in Libor market models.We hope this work will stimulate new research in cQSDP.