求解半定规划的新算法

为了提高求解半定规划问题的运算效率,提出了一种新的求解半定规划的非单调信赖域算法。将半定规划的最优性条件转化为无约束优化问题,并构造无约束优化问题的信赖域子问题,修正信赖域半径的校正条件,当初始搜索点处于峡谷附近时仍能搜索到全局最优解。实验结果表明,对于小规模和中等规模的半定规划问题,该算法的迭代次数都比经典的内点算法少,运行速度快。     

求解半定规划的新算法

为了提高求解半定规划问题的运算效率,提出了一种新的求解半定规划的非单调信赖域算法。将半定规划的最优性条件转化为无约束优化问题,并构造无约束优化问题的信赖域子问题,修正信赖域半径的校正条件,当初始搜索点处于峡谷附近时仍能搜索到全局最优解。实验结果表明,对于小规模和中等规模的半定规划问题,该算法的迭代次数都比经典的内点算法少,运行速度快。     

一种求解半定规划的非单调信赖域算法

提出一种求解半定规划的非单调信赖域算法。利用推广至矩阵域的光滑Fischer-Burmeister函数,转化半定规划的最优性条件,改写半定规划的中心路径,得到与其等价的无约束优化问题的非线性可微光滑方程组,在求解信赖域子问题时,利用当前迭代点的一阶梯度信息,给出信赖域半径的选取机制。仿真结果表明,与经典的内点算法相比,对于一般规模(n, m≤30)的半定规划问题,该算法的运行速度较快。对于大规模的半定规划问题(n, m＞30),该算法更适合处理Norm min、Lovasz这2类问题。     

考虑导航误差和摄动影响的椭圆轨道最优交会制导

本文提出了一种新的航天器最优交会制导方法.该方法能够快速精确求解包含J_2项与大气阻力项摄动的椭圆轨道交会问题,并充分考虑非合作目标存在的导航误差,保证交会精度的同时实现所需速度增量最优.首先,本文采用了一种新的状态转移矩阵求解方法,能够对考虑J_2项和大气阻力项摄动的任意偏心率下的相对运动进行描述,得到考虑摄动与偏心率信息的状态约束.其次,建立了导航误差模型,得到描述导航误差的状态约束,并分析其对交会精度与所需速度增量的影响,设计包含加权矩阵的性能指标实现在存在导航误差情况下所需速度增量最优.然后,通过引入松弛变量,将最优交会问题转化为标准二阶锥规划问题进行求解.再者,为了进一步提高相对距离较大的交会任务精度,构建了闭环制导框架.最后,本文通过仿真,验证了设计方法在考虑J_2项与阻力项摄动情况下的有效性,针对椭圆轨道交会问题的精确性以及考虑导航误差情况下所需速度增量的最优性.     

带有自适应学习速率的矩阵指数梯度在线量子态估计算法

针对连续弱测量中存在高斯噪声的情况,提出一种带有自适应学习速率的矩阵指数梯度在线量子态估计算法.将量子态估计问题转化为含量子约束的凸优化问题,通过引入Von Neumann散度(量子相对熵),在一阶最优条件下,推导出指数型的量子态迭代公式,保证量子态密度矩阵的半正定性.再通过对迭代结果进行迹为1的投影,得到最终的量子态估计值.同时在迭代公式中设计自适应的学习速率,进一步加快算法的收敛速度.将所提出的算法分别在1, 2, 3和4个量子位系统上,进行了在线量子态估计的数值仿真实验,并与现有的在线量子态估计算法进行了性能对比.实验结果表明,所提出的算法具有更好的快速收敛性,以及更高的状态估计精度.     

一类混杂系统的最优控制

研究了一类脉冲依赖于状态的混杂系统的最优控制问题.与传统的变分方法不同,通过将跳跃瞬间转化为一个新的待优化参数,得到了该混杂系统的必要最优性条件,从而将最优控制问题转化为一边界值问题,该边界值问题可由数值方法或解析方法解决.此外,利用广义微分的理论,将该必要最优性条件推广到Frechet微分形式.结论表明,在混杂动态系统运行的连续部分,最优解所满足的必要性条件和传统的连续系统相同.在混杂动态系统的脉冲点处,哈密尔顿函数满足连续性条件,协态变量则满足一定的跳跃条件.最后,通过两个实例分析,表明该方法是有效的.     

参数未知的离散系统Q-学习优化状态估计与控制

控制系统的应用中存在状态不能直接测量或测量成本高的实际问题,给模型参数未知的系统完全利用状态数据学习最优控制器带来挑战性难题.为解决这一问题,首先构建具有状态观测器且系统矩阵中存在未知参数的离散线性增广系统,定义性能优化指标;然后基于分离定理、动态规划以及Q-学习方法,给出一种具有未知模型参数的非策略Q-学习算法,并设计近似最优观测器,得到完全利用可测量的系统输出和控制输入数据的非策略Q-学习算法,实现基于观测器状态反馈的系统优化控制策略,该算法的优点在于不要求系统模型参数全部已知,不要求系统状态直接可测,利用可测量数据实现指定性能指标的优化;最后,通过仿真实验验证所提出方法的有效性.     

量子力学系统的输出反馈控制

研究量子系统输出反馈控制问题建模以及控制律设计问题.首先讨论了量子力学VonNeumann测量原理与连续测量模型的一致性;然后在连续测量模型的基础上总结了已有量子反馈模型的结果,归纳出量子输出反馈控制系统模型;最后针对单比特振幅退相干抑制问题,利用线性直接输出反馈控制设计反馈控制律,指出利用最优控制的方法设计线性输出反馈控制的比例系数,可以得到较好的结果.     

线性线性分式型区间系数双层规划问题的遗传算法

针对一类上层为线性规划、下层为线性分式规划的区间系数双层规划问题,提出了一种基于系数取值区间搜索的遗传算法。首先,对下层目标系数进行个体编码,使得对每一编码个体,原问题被转化为确定的双层规划问题;其次,利用分式规划的最优性条件求解得到确定性问题;最后,算法通过不断进化下层目标系数找到最好最优解和最差最优解。数值仿真结果表明,该算法是可行并有效的。     

基于PI 观测器的奇异摄动系统故障诊断和最优容错控制

针对线性奇异摄动系统, 提出一种基于PI (proportional integral) 观测器的故障诊断和最优容错控制方法. 基于奇异摄动系统相关理论和矩阵变换技术, 给出PI 全维观测器存在的条件, 该观测器可以观测系统的快慢状态和故障系统的状态. 在估测到系统状态的基础上进一步考虑最优性, 应用最优控制理论, 设计状态反馈控制器, 提出基于PI 观测器的故障诊断器和最优容错控制器的设计方法. 最后的数值算例验证了所提出方法的可行性和正确性.

     

An explicit semidefinite characterization of satisfiability for Tseitin instances on toroidal grid graphs

This paper is concerned with the application of semidefinite programming to the satisfiability problem, and in particular with using semidefinite liftings to efficiently obtain proofs of unsatisfiability. We focus on the Tseitin satisfiability instances which are known to be hard for many proof systems. For Tseitin instances based on toroidal grid graphs, we present an explicit semidefinite programming problem with dimension linear in the size of the Tseitin instance, and prove that it characterizes the satisfiability of these instances, thus providing an explicit certificate of satisfiability or unsatisfiability. Research partially supported by the Natural Sciences and Engineering Research Council of Canada.     

On the modelling and solving of the truss design problem with global stability constraints

The goal of this paper is to find a computationally tractable formulation of the optimum truss design problem involving a constraint on the global stability of the structure. The stability constraint is based on the linear buckling phenomenon. We formulate the problem as a nonconvex semidefinite programming problem and briefly discuss an interior point technique for the numerical solution of this problem. We further discuss relation to other models. The paper is concluded by a series of numerical examples.     

求解SAT问题的线性半定规划算法

将线性半定规划应用到SAT问题的求解过程中。首先将SAT实例转化为整数规划问题,然后松弛为线性规划模型,最后再转化为一般的线性半定规划模型去求解。用SDPA-M软件求解线性半定规划问题后,规定了如何根据目标函数值去判定SAT实例和当CNF公式可满足时如何根据最优指派的概率X^＊i（i=1,…,n）去进行变元赋值,以期求得该公式的可满足指派。上述算法不仅可以判定SAT问题,而且对于符合算法规定可满足的CNF公式皆可给出一个可满足指派。求解SAT问题的线性半定规划算法在文章中被描述并被给予相应算例。     

联合TDOA-AOA无线传感器网络半定规划定位算法研究

在无线传感器网络定位中,TDOA和AOA联合定位可有效利用多种位置信息提高定位精度.由于传统联合加权最小二乘(WLS)的目标函数非线性,在应用于无线传感器网络定位时,会产生多个局部最优解.因此,针对该问题本文将约束加权最小二乘问题转化为二次约束二次规划问题,之后通过引入半定松弛(SDR)方法将联合定位问题转换为低复杂度的半定规划问题(SDP),进而寻找全局最优解.并且针对实际应用中参考节点带误差的情形分析和推导了定位算法.与已有算法相比,提出的算法在参考节点无误差和有误差时都有更高的精度.此外,提出的SDP算法还能够实现只有两个参考节点下的目标定位.     

SDU: A Semidefinite Programming-Based Underestimation Method for Stochastic Global Optimization in Protein Docking

This paper introduces a new stochastic global optimization method targeting protein-protein docking problems, an important class of problems in computational structural biology. The method is based on finding general convex quadratic underestimators to the binding energy function that is funnel-like. Finding the optimum underestimator requires solving a semidefinite programming problem, hence the name semidefinite programming-based underestimation (SDU). The underestimator is used to bias sampling in the search region. It is established that under appropriate conditions SDU locates the global energy minimum with probability approaching one as the sample size grows. A detailed comparison of SDU with a related method of convex global underestimator (CGU), and computational results for protein-protein docking problems are provided     

Quantifying quantum correlations in fermionic systems using witness operators

We present a method to quantify quantum correlations in arbitrary systems of indistinguishable fermions using witness operators. The method associates the problem of finding the optimal entanglement witness of a state with a class of problems known as semidefinite programs, which can be solved efficiently with arbitrary accuracy. Based on these optimal witnesses, we introduce a measure of quantum correlations which has an interpretation analogous to the Generalized Robustness of entanglement. We also extend the notion of quantum discord to the case of indistinguishable fermions, and propose a geometric quantifier, which is compared to our entanglement measure. Our numerical results show a remarkable equivalence between the proposed Generalized Robustness and the Schliemann concurrence, which are equal for pure states. For mixed states, the Schliemann concurrence presents itself as an upper bound for the Generalized Robustness. The quantum discord is also found to be an upper bound for the entanglement.     

解离散系数滤波器设计问题的分支定界算法

基于离散系数滤波器设计问题已有的半定规划松弛模型,利用文献[6]的方法给出了该问题的二次规划松弛模型,该模型能给出比半定规划模型更好的界,然后运用分支定界方法求解该模型。与随机扰动方法相比,该方法能得到一个性能更好的次优解,对于精度要求较高的滤波器设计问题,这种方法非常有效,并通过了仿真实验的证实。     

A projected gradient method for optimization over density matrices

An ensemble of quantum states can be described by a Hermitian, positive semidefinite and unit trace matrix called density matrix. Thus, the study of methods for optimizing a certain function (energy, entropy) over the set of density matrices has a direct application to important problems in quantum information and computation. We propose a projected gradient method for solving such problems. By exploiting the geometry of the feasible set, which is the intersection of the cone of Hermitian positive semidefinite matrices with the hyperplane defined by the unit trace constraint, we describe an efficient procedure to compute the projection onto this set using the Frobenius norm. Some important applications, such as quantum state tomography, are described and numerical experiments illustrate the effectiveness of the method when compared to previous methods based on fixed-point iterations or semidefinite programming.     

Interest point detection through multiobjective genetic programming

The detection of stable and informative image points is one of the most important low-level problems in modern computer vision. This paper proposes a multiobjective genetic programming (MO-GP) approach for the automatic synthesis of operators that detect interest points. The proposal is unique for interest point detection because it poses a MO formulation of the point detection problem. The search objectives for the MO-GP search consider three properties that are widely expressed as desirable for an interest point detector, these are: (1) stability; (2) point dispersion; and (3) high information content. The results suggest that the point detection task is a MO problem, and that different operators can provide different trade-offs among the objectives. In fact, MO-GP is able to find several sets of Pareto optimal operators, whose performance is validated on standardized procedures including an extensive test with 500 images; as a result, we could say that all solutions found by the system dominate previously man-made detectors in the Pareto sense. In conclusion, the MO formulation of the interest point detection problem provides the appropriate framework for the automatic design of image operators that achieve interesting trade-offs between relevant performance criteria that are meaningful for a variety of vision tasks.     

Shape-Based Object Detection via Boundary Structure Segmentation

We address the problem of object detection and segmentation using global holistic properties of object shape. Global shape representations are highly susceptible to clutter inevitably present in realistic images, and thus can be applied robustly only using a precise segmentation of the object. To this end, we propose a figure/ground segmentation method for extraction of image regions that resemble the global properties of a model boundary structure and are perceptually salient. Our shape representation, called the chordiogram, is based on geometric relationships of object boundary edges, while the perceptual saliency cues we use favor coherent regions distinct from the background. We formulate the segmentation problem as an integer quadratic program and use a semidefinite programming relaxation to solve it. The obtained solutions provide a segmentation of the object as well as a detection score used for object recognition. Our single-step approach achieves state-of-the-art performance on several object detection and segmentation benchmarks.