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.展开更多
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.展开更多
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.展开更多
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 introd...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.展开更多
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...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.展开更多
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...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.展开更多
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 se...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.展开更多
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(ACO...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.展开更多
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 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.展开更多
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 ...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.展开更多
基金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.
基金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.
文摘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 National Natural Science Foundation of China (Grant No. 10871098)Science Foundation of Jiangsu Province (Grant No. BK2006214)
文摘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.
基金Supported by National Natural Science Foundation of China(Grant Nos.11061011 and 11361018)Guangxi Fund for Distinguished Young Scholars(Grant No.2012GXNSFFA060003)+2 种基金the Guangxi Fund(Grant No.2013GXNSFDA019002)the first author would like to thank the Project of Guangxi Innovation Team"Optimization method and its engineering application"(Grant No.2014GXNSFFA118001)supported by Guangxi Experiment Center of Information Science and Guangxi Key Laboratory of Automatic Detecting Technology and Instruments
文摘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.
基金supported by National Natural Science Foundation of China (Grant Nos. 11401364, 11322109, 11331012, 11471325 and 11461161005)the National High Technology Research and Development Program of China (863 Program) (Grant No. 2013AA122902)+1 种基金the National Center for Mathematics and Interdisciplinary Sciences, Chinese Academy of SciencesNational Basic Research Program of China (973 Program) (Grant No. 2015CB856002)
文摘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.
基金supported by National Natural Science Foundation of China(Grant Nos. 11001006 and 91130019/A011702)the Fund of State Key Laboratory of Software Development Environment (Grant No. SKLSDE-2011ZX-15.)
文摘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.
基金funded by State Grid Corporation of China(SGCC)under project“Hybrid Energy Storage Management Platform for Integrated Energy System”(No.SGGR0000DLJS1800932).
文摘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.
基金supported by the Engineering and Physical Sciences Research Council Grant(No.EP/K007645/1).
文摘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.
基金supported by the National Natural Science Foundation(No.11561005)the National Science Foundation of Guangxi(No.2016GXNSFAA380248)。
文摘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.
