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

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

多目标半定规划的互补弱鞍点和G-鞍点最优性条件

对于含矩阵函数半定约束和多个目标函数的多目标半定规划问题，给出Lagrange函数在弱有效意义下的互补弱鞍点和Geofrrion恰当有效意义下的G-鞍点的定义及其等价定义．然后，在较弱的凸性条件下，利用含矩阵和向量约束的择一性定理，建立多目标半定规划的互补弱鞍点和G-鞍点充分必要条件．     

解半定规划的二次摄动方法

半定规划在系统论,控制论,组合优化,和特征值优化等领域有着广泛的应用。本文将半定规划摄动成二次半定规划,它的唯一解恰为原问题的解,并且对其偶问题等价于一个线性对称的投影方程,可方便地用投影收缩方法求解,从而获得原半定规划问题的解。文章给出了算法及其收敛性分析,数值试验结果表明摄动方法是解半定规划的一种有效的方法。     

非线性半定规划若干进展

讨论非线性半定规划的四个专题, 包括半正定矩阵锥的变分分析、非凸半定规划问题的最优性条件、非凸半定规划问题的扰动分析和非凸半定规划问题的增广Lagrange方法.     

非线性半定规划若干进展

讨论非线性半定规划的四个专题,包括半正定矩阵锥的变分分析、非凸半定规划问题的最优性条件、非凸半定规划问题的扰动分析和非凸半定规划问题的增广Lagrange方法．     

电路二等分问题的一个强化半定松驰模型

由于电路二等分问题在超大规模集成电路 (VLSI)设计中的基础地位 ,电路二等分半定松驰问题一直引人关注 .能否找到更好的半定规划模型 ,使其为电路二等分问题提供一个更好的下界 ,成为一个重要的研究方向 ;本文在已有半定规划松驰模型的基础上 ,通过增加非线性约束 ,得出电路二等分问题的等价模型 ,再利用提升技巧 ,得到一个强化半定规划松驰模型 .理论证明该模型给出了原有问题的一个更好的下界 ,数值实验也说明了这一点 .     

多目标半定规划的最优性条件及对偶理论

在不变凸的假设下来讨论多目标半定规划的最优性条件、对偶理论以及非凸半定规划的最优性条件．首先给出了非凸半定规划的一个KKT条件成立的充分必要条件, 并利用此定理证明了其最优性必要条件．其次讨论了多目标半定规划的最优性必要条件、充分条件, 并对其建立Wolfe对偶模型, 证明了弱对偶定理和强对偶定理．     

半定规划的逆问题

本文提出了半定规划的逆问题,利用半定规划的最优性条件,分别给出了其在ｌ∞,ｌ１,ｌ２ 模意义下的数学模型,它们仍为半定规划问题．     

半定规划的限制逆问题与广义逆问题

本文提出了半定规划的限制逆问题与广义逆问题，利用半定规划的最优性条件，分别给出了其在l∞，l1,l2模意义下的数学模型，它们仍为半定规划问题。     

稠密k-子图问题的双非负松弛

稠密k-子图问题是组合优化里面一类经典的优化问题,其在通常情况下是非凸且NP-难的。本文给出了求解该问题的一个新凸松弛方法-双非负松弛方法,并建立了问题的相应双非负松弛模型,而且证明了其在一定的条件下等价于一个新的半定松弛模型。最后,我们使用一些随机例子对这些模型进行了数值测试,测试的结果表明双非负松弛的计算效果要优于等价的半定松弛。     

Nonsingularity of FB system and constraint nondegeneracy in semidefinite programming

For a KKT point of the linear semidefinite programming (SDP), we show that the nonsingularity of the B-subdifferential of Fischer-Burmeister (FB) nonsmooth system, the nonsingularity of Clarke’s Jacobian of this system, and the primal and dual constraint nondegeneracies, are all equivalent. Also, each of these conditions is equivalent to the nonsingularity of Clarke’s Jacobian of the smoothed counterpart of FB nonsmooth system, which particularly implies that the FB smoothing Newton method may attain the local quadratic convergence without strict complementarity assumption. We also report numerical results of the FB smoothing method for some benchmark problems.     

Quadratic convergence of a smoothing Newton method for symmetric cone programming without strict complementarity

This paper deals with symmetric cone programming (SCP), which includes the linear programming (LP), the second-order cone programming (SOCP), the semidefinite programming (SDP) as special cases. Based on the Chen?CMangasarian smoothing function of the projection operator onto symmetric cones, we establish a smoothing Newton method for SCP. Global and quadratic convergence of the proposed algorithm is established under the primal and dual constraint nondegeneracies, but without the strict complementarity. Moreover, we show the equivalence at a Karush?CKuhn?CTucker (KKT) point among the primal and dual constraint nondegeneracies, the nonsingularity of the B-subdifferential of the smoothing counterpart of the KKT system, and the nonsingularity of the corresponding Clarke??s generalized Jacobian.     

Semidefinite resolution and exactness of semidefinite relaxations for satisfiability

This paper explores new connections between the satisfiability problem and semidefinite programming. We show how the process of resolution in satisfiability is equivalent to a linear transformation between the feasible sets of the relevant semidefinite programming problems. We call this transformation semidefinite programming resolution, and we demonstrate the potential of this novel concept by using it to obtain a direct proof of the exactness of the semidefinite formulation of satisfiability without applying Lasserre’s general theory for semidefinite relaxations of 0/1 problems. In particular, our proof explicitly shows how the exactness of the semidefinite formulation for any satisfiability formula can be interpreted as the implicit application of a finite sequence of resolution steps to verify whether the empty clause can be derived from the given formula.     

A regularized strong duality for nonsymmetric semidefinite least squares problem

The nonsymmetric semidefinite least squares problem (NSDLS) is to find a nonsymmetric semidefinite matrix which is closest to a given matrix in Frobenius norm. It is an extension of the semidefinite least squares problem (SDLS) and has important application in the area of robotics and automation. In this note, by developing the minimal representation of the underlying cone with the linear constraints, we obtain a regularized strong duality with low-dimensional projection for NSDLS. Further, we study the generalized differential properties and nonsingularity of the first order optimality system about the dual problem. These theoretical results demonstrate that we can solve NSDLS as good as the current Lagrangian dual approaches to SDLS.     

Positive semidefinite matrix completions on chordal graphs and constraint nondegeneracy in semidefinite programming

Let G=(V,E) be a graph. In matrix completion theory, it is known that the following two conditions are equivalent: (i) G is a chordal graph; (ii) Every G-partial positive semidefinite matrix has a positive semidefinite matrix completion. In this paper, we relate these two conditions to constraint nondegeneracy condition in semidefinite programming and prove that they are each equivalent to (iii) For any G-partial positive definite matrix that has a positive semidefinite completion, constraint nondegeneracy is satisfied at each of its positive semidefinite matrix completions.     

Constrained Markov decision processes with uncertain costs

We consider a finite state-action discounted constrained Markov decision process with uncertain running costs and known transition probabilities. We propose equivalent linear programming, second-order cone programming and semidefinite programming problems for the robust constrained Markov decision processes when the uncertain running cost vectors belong to polytopic, ellipsoidal, and semidefinite cone uncertainty sets, respectively. As an application, we study a variant of a machine replacement problem and perform numerical experiments on randomly generated instances of various sizes.     

Comparing SOS and SDP relaxations of sensor network localization

We investigate the relationships between various sum of squares (SOS) and semidefinite programming (SDP) relaxations for the sensor network localization problem. In particular, we show that Biswas and Ye’s SDP relaxation is equivalent to the degree one SOS relaxation of Kim et al. We also show that Nie’s sparse-SOS relaxation is stronger than the edge-based semidefinite programming (ESDP) relaxation, and that the trace test for accuracy, which is very useful for SDP and ESDP relaxations, can be extended to the sparse-SOS relaxation.     

Nonsingularity in second-order cone programming via the smoothing metric projector

Based on the differential properties of the smoothing metric projector onto the second-order cone,we prove that,for a locally optimal solution to a nonlinear second-order cone programming problem,the nonsingularity of the Clarke's generalized Jacobian of the smoothing Karush-Kuhn-Tucker system,constructed by the smoothing metric projector,is equivalent to the strong second-order sufficient condition and constraint nondegeneracy,which is in turn equivalent to the strong regularity of the Karush-Kuhn-Tucker p...