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.

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.

AN EQUIVALENCY CONDITION OF NONSINGULARITY IN NONLINEAR SEMIDEFINITE PROGRAMMING

In this paper,an equivalency condition of nonsingularity in nonlinear semidefinite programming,which can be viewed as a generalization of the equivalency condition of nonsingularity for linearsemidefinite programming,is established under certain conditions of convexity.

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.

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.

UV -theory of a Class of Semidefinite Programming and Its Applications

In this paper we study optimization problems involving convex nonlinear semidefinite programming(CSDP).Here we convert CSDP into eigenvalue problem by exact penalty function,and apply the U-Lagrangian theory to the function of the largest eigenvalues,with matrix-convex valued mappings.We give the first-and second-order derivatives of U-Lagrangian in the space of decision variables Rm when transversality condition holds.Moreover,an algorithm frame with superlinear convergence is presented.Finally,we give one application:bilinear matrix inequality(BMI)optimization;meanwhile,list their UV decomposition results.

A New QP-free Algorithm Without a Penalty Function or a Filter for Nonlinear Semidefinite Programming

In this paper,we present a QP-free algorithm without a penalty function or a filter for nonlinear semidefinite programming.At each iteration,two systems of linear equations with the same coefficient matrix are solved to determine search direction;the nonmonotone line search ensures that the objective function or constraint violation function is sufficiently reduced.There is no feasibility restoration phase in our algorithm,which is necessary for traditional filter methods.The proposed algorithm is globally convergent under some mild conditions.Preliminary numerical results indicate that the proposed algorithm is comparable.

Applications of gauge duality in robust principal component analysis and semidefinite programming

Gauge duality theory was originated by Preund （1987）, and was recently further investigated by Friedlander et al. （2014）. When solving some matrix optimization problems via gauge dual, one is usually able to avoid full matrix decompositions such as singular value and/or eigenvalue decompositions. In such an approach, a gauge dual problem is solved in the first stage, and then an optimal solution to the primal problem can be recovered from the dual optimal solution obtained in the first stage. Recently, this theory has been applied to a class of semidefinite programming （SDP） problems with promising numerical results by Friedlander and Mac^to （2016）. We establish some theoretical results on applying the gauge duality theory to robust principal component analysis （PCA） and general SDP. For each problem, we present its gauge dual problem, characterize the optimality conditions for the primal-dual gauge pair, and validate a way to recover a primal optimal solution from a dual one. These results are extensions of Friedlander and Macedo （2016） from nuclear norm regularization to robust PCA and from a special class of SDP which requires the coefficient matrix in the linear objective to be positive definite to SDP problems without this restriction. Our results provide further understanding in the potential advantages and disadvantages of the gauge duality theory.

Incorporating Convexity in Bond Portfolio Immunization Using Multifactor Model:A Semidefinite Programming Approach

Bond portfolio immunization is a classical issue in finance. Since Macaulaygave the concept of duration in 1938, many scholars proposed different kinds of duration immunization models. In the literature of bond portfolio immunization usingmultifactor model, to the best of our knowledge, researchers only use the first-orderimmunization, which is usually called as duration immunization, and no one hasconsidered second-order effects in immunization, which is well known as “convexity” in the case of single-factor model. In this paper, we introduce the second-orderinformation associated with multifactor model into bond portfolio immunization andreformulate the corresponding problems as tractable semidefinite programs. Bothsimulation analysis and empirical study show that the second-order immunization strategies exhibit more accurate approximation to the value change of bonds and thusresult in better immunization performance.

ON DOUBLY POSITIVE SEMIDEFINITE PROGRAMMING RELAXATIONS

Recently, researchers have been interested in studying the semidefinite programming （SDP） relaxation model, where the matrix is both positive semidefinite and entry-wise nonnegative, for quadratically constrained quadratic programming （QCQP）. Comparing to the basic SDP relaxation, this doubly-positive SDP model possesses additional O（n2） constraints, which makes the SDP solution complexity substantially higher than that for the basic model with O（n） constraints. In this paper, we prove that the doubly-positive SDP model is equivalent to the basic one with a set of valid quadratic cuts. When QCQP is symmetric and homogeneous （which represents many classical combinatorial and non- convex optimization problems）, the doubly-positive SDP model is equivalent to the basic SDP even without any valid cut. On the other hand, the doubly-positive SDP model could help to tighten the bound up to 36%, but no more. Finally, we manage to extend some of the previous results to quartic models.

A Line Search SQP-type Method with Bi-object Strategy for Nonlinear Semidefinite Programming

We propose a line search exact penalty method with bi-object strategy for nonlinear semidefinite programming.At each iteration,we solve a linear semidefinite programming to test whether the linearized constraints are consistent or not.The search direction is generated by a piecewise quadratic-linear model of the exact penalty function.The penalty parameter is only related to the information of the current iterate point.The line search strategy is a penalty-free one.Global and local convergence are analyzed under suitable conditions.We finally report some numerical experiments to illustrate the behavior of the algorithm on various degeneracy situations.

Semidefinite programming detection for OvHDM signal

Non-orthogonal time-frequency division multiplexing （NTFDM） transmission scheme has been proposed to further improve the bandwidth efficiency and overcome the drawbacks of the conventional orthogonal frequency division multiplexing （OFDM） method. Based on such approach, the fast signal detection algorithm, semidefinite programming （SDP） detection, has been studied. As the coefficient matrix tends to be ill conditioned, the modified SDP algorithm combined with successive interference cancellation （SIC） has been developed. The improved algorithm is a good tradeoff between performance and detection complexity. Simulation results show that the proposed algorithm can achieve better performance than cutting plane aided SDP method.

A PRIMAL-DUAL INTERIOR POINT METHOD FOR PARAMETRIC SEMIDEFINITE PROGRAMMING PROBLEMS

On the basis of primal-dual approach, we present in this paper an interior point method that gives parametric E-approximate solutions to parametric semi-definite programming problems. The method is finite, and the number of its iterations is quasi-polynomially bounded.

Limited Memory BFGS Method for Least Squares Semidefinite Programming with Banded Structure

This work is intended to solve the least squares semidefinite program with a banded structure. A limited memory BFGS method is presented to solve this structured program of high dimension.In the algorithm, the inverse power iteration and orthogonal iteration are employed to calculate partial eigenvectors instead of full decomposition of n × n matrices. One key feature of the algorithm is that it is proved to be globally convergent under inexact gradient information. Preliminary numerical results indicate that the proposed algorithm is comparable with the inexact smoothing Newton method on some large instances of the structured problem.