一类亚半正定矩阵的左右逆特征值问题

1．引言在工程技术中常常遇到这样一类逆特征值问题：要求在一个矩阵集合S中，找具有给定的部分右特征对（特征值及相应的特征向量）和给定的部分左特征对（特征值及相应的特征向量）的矩阵．文［2］，［3］讨论了S为。x。实矩阵集合的情形．文［4］－［7］对S为nxn实对称矩阵．对称正定矩阵，对称半正定矩阵集合的情形进行了讨论．文【川讨论了S为亚正定阵集合的情形．并提到了对于亚半正定矩阵的情形目下无人涉及，有待进一步研究．本文将对S为nxn亚半正定矩阵集合的情形进行讨论．给出了亚半正定矩阵的左右逆特征值问题有解的充要条件…     

线性流形上矩阵方程AX=B的一类反问题及数值解法

1．引言本文用＊-"m表示全体nX。实矩阵的集合，人表示n阶单位矩阵，汉"m一《ME＊""叫rank（川一r），＊＊"""＝HE＊"""卜"A＝v，＊＊"""一仰E＊"""卜"一M｝，SR；""（SR7""）表示全体7。阶实对称半正定（正定）阵集合．N（A）表示矩阵A的零空间，即N（A）＝（xlAx＝0），ID叫D表示Frobenius范数，A"表示矩阵A的Moors－Penrose广义逆，［EI十表示在Frobenius范数意义下n阶方阵E在SR；""中唯一的最佳k逼近解，即口一［E］＋11-inf。。、。。x，IllE-All．（［E］十求法见文［7］）．还用A三0（A三0）表示A（的k阶顺序主子矩…     

一类线性约束凸规划的内椭球算法

1引言自从1984年Karmarkar的著名算法——梯度投影算法发表以来,由其理论上的多项式收敛性及实际计算的有效性,使得内点算法成为近十几年来优化界研究的热点（［1］）．通过中外学者的深入研究,线性规划与凸二次规划的内点算法研究已取得了不少成果（［2」、［3〕）．这些算法大致可分为四种类型：梯度投影算法、仿射尺度算法、路径跟踪法和势函数减少法吸3］、〔9〕）．近来,人们开始着手将这些方法推广到非线性规划中的凸规划问题、线性互补问题和非线性互补问题（【6」、［7」、〔sj、［10」、Ill〕）．例如：文［8」对一类凸可分规…     

关于对广义正定矩阵的进一步研究

文［１］定义了广义正定矩阵集合Ｐ（Ｉ）．文［２］定义了较Ｐ（Ｉ）更广泛的另一个广义正定矩阵集合Ｐ（Ｓ＋）．本文把Ｐ（Ｉ）中矩阵的某些性质，推广到Ｐ（Ｓ＋）中从而丰富了Ｐ（Ｓ＋）矩阵集合的结果。     

求解最大割问题的半定规划松驰的序列线性规划方法

本文基于最大割问题的半定规划松弛,利用矩阵分解的方法给出了与半定规划松弛等价的非线性规划模型,提出一种序列线性规划方法求解该模型.并在适当的条件下,证明了算法的全局收敛性.数值实验表明:序列线性规划方法在时间上要优于半定规划的内点算法.所以序列线性规划方法能更有效地求解大规模的最大割问题的半定规划松弛.     

亚半正定阵左右逆特征值问题的进一步研究

１　引　言文［１］研究了亚半正定阵的左右逆特征值问题,它的更一般提法是问题Ｉ给定Ｘ、Ｚ使得其中Ｒｎ×ｍ表示全体ｎ×ｍ实阵的集合;即表示全体亚半正定阵集合［２］．文［１］得到了问题１有解的充要条件及解的通式,但从文［１］中主要定理给出的通式来看,子矩阵Ａ１３、Ａ１４及Ａ４３的表达式还没有得到,因此有必要对问题Ⅰ的通解作进一步的研究．本文将通过建立一个亚半正定阵的判定准则,圆满地解决以上问题． 为方便起见,本文用 及Ⅰ分别表示Ｒｎ×ｍ中秩为ｒ的矩阵集合、ｎ×正交矩阵集合及单位矩阵;而用　分别表示ｎ ×…     

关于正定矩阵的几个问题

本文推广了文［１］的主要定理，给出了用低阶矩阵判定高阶矩阵正定的判定定理，同时给出了矩阵方程ＡＸ＝Ｂ的反问题在正定矩阵类中解存在的充要条件及解的一般形式．     

四元数矩阵方程AX=B的实部半正定解(英文)

一个ｎ×ｎ实四元数矩阵称为实部半正定（或正定）矩阵，如果对于任意的非零ｎ维四元数列向量ｘ，有Ｒｅ［ｘＡｘ］≥０（或＞０）．本文给出了四元数矩阵方程ＡＸ＝Ｂ有实部半正定（或正定）矩阵解的充要条件及其通解的表达式，并给出了四元数分块阵为实部半正定（或正定）矩阵的一个判别法则     

一类求解单调变分不等式的隐式方法

1．引言变分不等式是一个非常有趣。非常困难的数学问题［"］．它具有广泛的应用（例如，数学规划中的许多基本问题都可以归结为一个变分不等式问题），因而得到深入的研究并有了不少算法［1，2，5－8，17－21］．对线性单调变分不等式，我们最近提出了一系列投影收缩算法Ig－13］．本文考虑求解单调变分不等式其中0CW是一闭凸集，F是从正p到自身的一个单调算子，一即有我们用比（·）表示到0上的投影．求解单调变分不等式的一个简单方法是基本投影法［1，6］，它的迭代式为然而，如果F不是仿射函数，只有当F一致强单调且LIPSChitZ连续…     

二次半定规划的原始对偶内点算法的H..K..M搜索方向的存在唯一性

主要是将半定规划(Semidefinite Programming,简称SDP)的内点算法推广到二次半定规划(Quadratic Semidefinite Programming,简称QSDP),重点讨论了其中搜索方向的产生方法.首先利用Wolfe对偶理论推导得到了求解二次半定规划的非线性方程组,利用牛顿法求解该方程组,得到了求解QSDP的内点算法的H..K..M搜索方向,接着证明了该搜索方向的存在唯一性,最后给出了搜索方向的具体计算方法.     

Analyticity of the central path at the boundary point in semidefinite programming

In this paper we study the limiting behavior of the central path for semidefinite programming (SDP). We show that the central path is an analytic function of the barrier parameter even at the limit point, provided that the semidefinite program has a strictly complementary solution. A consequence of this property is that the derivatives – of any order – of the central path have finite limits as the barrier parameter goes to zero.     

Convex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation

We present a decomposition-approximation method for generating convex relaxations for nonconvex quadratically constrained quadratic programming (QCQP). We first develop a general conic program relaxation for QCQP based on a matrix decomposition scheme and polyhedral (piecewise linear) underestimation. By employing suitable matrix cones, we then show that the convex conic relaxation can be reduced to a semidefinite programming (SDP) problem. In particular, we investigate polyhedral underestimations for several classes of matrix cones, including the cones of rank-1 and rank-2 matrices, the cone generated by the coefficient matrices, the cone of positive semidefinite matrices and the cones induced by rank-2 semidefinite inequalities. We demonstrate that in general the new SDP relaxations can generate lower bounds at least as tight as the best known SDP relaxations for QCQP. Moreover, we give examples for which tighter lower bounds can be generated by the new SDP relaxations. We also report comparison results of different convex relaxation schemes for nonconvex QCQP with convex quadratic/linear constraints, nonconvex quadratic constraints and 0–1 constraints.     

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

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

Enhancing RLT relaxations via a new class of semidefinite cuts

In this paper, we propose a mechanism to tighten Reformulation-Linearization Technique (RLT) based relaxations for solving nonconvex programming problems by importing concepts from semidefinite programming (SDP), leading to a new class of semidefinite cutting planes. Given an RLT relaxation, the usual nonnegativity restrictions on the matrix of RLT product variables is replaced by a suitable positive semidefinite constraint. Instead of relying on specific SDP solvers, the positive semidefinite stipulation is re-written to develop a semi-infinite linear programming representation of the problem, and an approach is developed that can be implemented using traditional optimization software. Specifically, the infinite set of constraints is relaxed, and members of this set are generated as needed via a separation routine in polynomial time. In essence, this process yields an RLT relaxation that is augmented with valid inequalities, which are themselves classes of RLT constraints that we call semidefinite cuts. These semidefinite cuts comprise a relaxation of the underlying semidefinite constraint. We illustrate this strategy by applying it to the case of optimizing a nonconvex quadratic objective function over a simplex. The algorithm has been implemented in C++, using CPLEX callable routines, and two types of semidefinite restrictions are explored along with several implementation strategies. Several of the most promising lower bounding strategies have been implemented within a branch-and-bound framework. Computational results indicate that the cutting plane algorithm provides a significant tightening of the lower bound obtained by using RLT alone. Moreover, when used within a branch-and-bound framework, the proposed lower bound significantly reduces the effort required to obtain globally optimal solutions.     

半定规划的PRP~+共轭梯度法(英文)

本文对半定规划(SDP)的最优性条件提出一价值函数并研究其性质.基此,提出半定规划的PRP+共轭梯度法.为得到PRP+共轭梯度法的收敛性,提出一Armijo-型线搜索.无需水平集有界及迭代点列聚点的存在,算法全局收敛.     

Necessary and sufficient global optimality conditions for NLP reformulations of linear SDP problems

In this paper we consider the standard linear SDP problem, and its low rank nonlinear programming reformulation, based on a Gramian representation of a positive semidefinite matrix. For this nonconvex quadratic problem with quadratic equality constraints, we give necessary and sufficient conditions of global optimality expressed in terms of the Lagrangian function.     

Alternating direction augmented Lagrangian methods for semidefinite programming

We present an alternating direction dual augmented Lagrangian method for solving semidefinite programming (SDP) problems in standard form. At each iteration, our basic algorithm minimizes the augmented Lagrangian function for the dual SDP problem sequentially, first with respect to the dual variables corresponding to the linear constraints, and then with respect to the dual slack variables, while in each minimization keeping the other variables fixed, and then finally it updates the Lagrange multipliers (i.e., primal variables). Convergence is proved by using a fixed-point argument. For SDPs with inequality constraints and positivity constraints, our algorithm is extended to separately minimize the dual augmented Lagrangian function over four sets of variables. Numerical results for frequency assignment, maximum stable set and binary integer quadratic programming problems demonstrate that our algorithms are robust and very efficient due to their ability or exploit special structures, such as sparsity and constraint orthogonality in these problems.     

A full-NT-step infeasible interior-point algorithm for SDP based on kernel functions

This paper proposes an infeasible interior-point algorithm with full Nesterov-Todd (NT) steps for semidefinite programming (SDP). The main iteration consists of a feasibility step and several centrality steps. First we present a full NT step infeasible interior-point algorithm based on the classic logarithmical barrier function. After that a specific kernel function is introduced. The feasibility step is induced by this kernel function instead of the classic logarithmical barrier function. This kernel function has a finite value on the boundary. The result of polynomial complexity, O(nlogn/ε), coincides with the best known one for infeasible interior-point methods.     

An inexact interior point method for L 1-regularized sparse covariance selection

Sparse covariance selection problems can be formulated as log-determinant (log-det) semidefinite programming (SDP) problems with large numbers of linear constraints. Standard primal–dual interior-point methods that are based on solving the Schur complement equation would encounter severe computational bottlenecks if they are applied to solve these SDPs. In this paper, we consider a customized inexact primal–dual path-following interior-point algorithm for solving large scale log-det SDP problems arising from sparse covariance selection problems. Our inexact algorithm solves the large and ill-conditioned linear system of equations in each iteration by a preconditioned iterative solver. By exploiting the structures in sparse covariance selection problems, we are able to design highly effective preconditioners to efficiently solve the large and ill-conditioned linear systems. Numerical experiments on both synthetic and real covariance selection problems show that our algorithm is highly efficient and outperforms other existing algorithms.     

Primal-Dual Path-Following Algorithms for Determinant Maximization Problems With Linear Matrix Inequalities

Primal-dual path-following algorithms are considered for determinant maximization problem (maxdet-problem). These algorithms apply Newton's method to a primal-dual central path equation similar to that in semidefinite programming (SDP) to obtain a Newton system which is then symmetrized to avoid nonsymmetric search direction. Computational aspects of the algorithms are discussed, including Mehrotra-type predictor-corrector variants. Focusing on three different symmetrizations, which leads to what are known as the AHO, H..K..M and NT directions in SDP, numerical results for various classes of maxdet-problem are given. The computational results show that the proposed algorithms are efficient, robust and accurate.