移动式喷灌系统优化设计的数学模型

基于MCM2006A题,建立了均匀喷洒的喷灌系统优化管理模型.首先通过水力学计算,得到喷头射程、间距、数量和布局.然后将喷灌规则的确定转化为用单一小矩形条覆盖矩形区域的二维覆盖问题,针对一般情况设计了算法,得到管道移动方案.对所给喷灌区域,计算结果表明了模型的可行性.     

Research on the Fictitious Source Points of the Hybrid Fundamental Solution⁃Based Finite Element Method for Heat Conduction Problems北大核心CSCD

针对热传导问题,提出了杂交基本解有限元法.首先,假设两个独立场:一个为利用基本解线性组合近似的单元域内温度场,另一个为使用与传统有限元法相同形式的辅助网线温度场.然后,利用修正变分泛函将上述两个独立场关联起来,并导出有限元列式.然而,该方法的准确性很大程度上取决于源点的分布和数量,通常将源点布置在单元外部两种虚拟边界上:与单元相似的边界和圆形边界.此外,还提出了双重虚拟边界,并与上述两种源点布局方式进行对比.通过两个典型数值算例,验证了该文方法在不同源点布局下的有效性和对网格畸变的不敏感性.     

基于AP聚类和集合覆盖模型的农电营业区域电费缴纳点选址研究

农电营业区域的电费缴纳点选址研究是解决用电客户缴费难、购电难的关键课题之一,而当前大数据环境为电费缴纳点的合理布局提供了一个新的研究思路.首先通过运用基于数据点间"消息传递"的AP聚类算法从大量用电客户中筛选出候选电费缴纳选址点,然后采用集合覆盖模型对候选电费缴纳选址点进行再优化,得到最优选址点.并以赤峰市宁城县居民电力缴费记录与低压数据明细为例,为实现"村村都有缴费点"的建设目标,对较少用电客户的台区进行最优电费缴纳点选址研究.在此基础上,对最优电费缴纳点选址下的供电营业厅资源配置进行了分析,为供电公司在农电营业区域电费缴纳点的选址布局提供决策支持.     

基于遗传算法的多约束网格检查对策问题研究

综合考虑物品数量以及列容量约束,将隐藏成本与检查概率引入支付函数,建立一种新的多约束的网格检查对策模型.根据矩阵对策性质及Hlder不等式,将对策论问题转化为非线性整数规划问题.提出一个基于遗传算法的模型求解方法,将归一化处理得到的变量进行二进制编码,通过数据变换将问题转化为无约束问题,采用轮盘赌选择、多点交叉及单点变异操作求解模型.仿真结果表明了模型及所提算法的有效性.     

机械臂运动路径设计问题

针对机械臂运动的逆问题,提出了无障碍空间的牛顿迭代算法.并对牛顿迭代法进行了改进,建立了有障碍空间中避碰问题的一般模型,并对问题进行了求解.对于求出的机械臂指尖的姿态,先采用最大步长调整,再对剩余部分采用一次微调的方法生成指令序列,使生成的序列尽可能的短.针对具体问题①,给出了达到目标点的一个指令序列,步数为89步,精度为0.179mm;对于问题②,离散化裂纹,应用大步长调整的牛顿迭代法,给出了一个运动序列,实现了避碰焊接,各点的平均精度达到0.188mm,并对最低点附近在1mm误差范围内不可达到的区域进行了讨论,用解析和仿真的方法证明和验证了最低点不可达;对于问题③,改进了避碰问题的一般模型和算法,用试探法实现了四个焊接点的无碰焊接,并对圆台内表面在1mm误差范围内不可焊接的区域进行了分析.     

城市消防站点布局的改进启发式算法

面对数量较多需要及时处理的突发事故,为了满足最短应急时间限制,最低应急资源数和最少的出救点等目标,在城市规划决策中,考虑在一个确定应急限制期下的安全消防站选址问题,给出一个反映决策者对时间和费用偏好的折衷选址方案十分必要.从实际应用出发,运用改进启发式算法方法研究时间与资源限制条件下的多出救点组合模型求解问题.给出了应急限制期和安全消防设施点建立的费用模型,从理论上证明了模型求解方法的正确性.在给定限制期条件下,通过分析得出应急服务设施点选择方法.通过算例说明该计算方法的具体应用,为交通安全消防站点选择提供参考,该方法还适用于诸如医院急救站等类似公共设施的规划建设.     

二维混合布局问题的组合优化模型及算法

本文以卫星仪器舱布局优化设计问题为背景，分别以矩形和圆形为各种仪器的表征图元，建立二维混合布局的组合优化模型，并给出其主要性质和算法     

基于贝叶斯信息更新的失事飞机发现概率模型

了目标搜索区域的确定方法以及失事飞机在目标搜索区域的初始概率分布,得到发现概率的计算公式。以发现概率为目标,构造了一个求解最优搜寻策略的Max Max化规划模型,模型可以动基于贝叶斯方法,提出了一个失事飞机的发现概率模型,利用飞机失联前后的信息数据,给出态地对坠机点的概率分布进行更新,使下一步搜寻任务得到及时的修正和调整。考虑到洋流对坠机点的影响,本文还提出了一个关于基点先验概率分布的重构策略。此外,对任务搜索区域最优路径的选取问题做了进一步探讨,给出了一个任务搜索区域上搜寻路径的选取方法     

应急联动区域下选址分配协同优化模型研究

针对我国现有应急储备库按照属地管理布局的不足,例如当受灾点发生重大灾害时,各应急储备库实行均匀配置,导致应急系统救援效率低以及资源的浪费,文章引入集合覆盖选址模型和"覆盖满意度"思想,将应急联动区域内的服务需求分为第一时间救援服务需求和后续救援服务需求,以应急服务成本最小和覆盖满意度最大为目标,建立应急联动下区域储备库选址分配协同优化模型.对四川省地震灾害下的应急储备库选址分配问题进行案例分析,考虑到各区县抗灾能力的不同,采用TOPSIS方法对模型中受灾点的脆弱性进行评价,并利用NSGA-Ⅱ算法对模型求解.研究表明,模型能降低应急联动区域内的应急服务成本,提升应急服务水平,同时模型可以为决策者提供多种优化方案.     

重大突发事件应急设施多重覆盖选址模型及算法

为了解决应对重大突发事件过程中应急需求的多点同时需求和多次需求问题,本文研究了应对重大突发事件的应急服务设施布局中的覆盖问题:针对重大突发事件应急响应的特点,引入最大临界距离和最小临界距离的概念,在阶梯型覆盖质量水平的基础上,建立了多重数量和质量覆盖模型。模型的优化目标是满足需求点的多次覆盖需求和多需求点同时需求的要求条件下,覆盖的人口期望最大,并用改进的遗传算法进行求解;最后给出的算例证明了模型和算法的有效性,从而应急设施的多重覆盖选址模型能够为有效应对重大突发事件的应急设施选址决策提供参考依据。     

Symmetric tensor decomposition by alternating gradient descent

The symmetric tensor decomposition problem is a fundamental problem in many fields, which appealing for investigation. In general, greedy algorithm is used for tensor decomposition. That is, we first find the largest singular value and singular vector and subtract the corresponding component from tensor, then repeat the process. In this article, we focus on designing one effective algorithm and giving its convergence analysis. We introduce an exceedingly simple and fast algorithm for rank-one approximation of symmetric tensor decomposition. Throughout variable splitting, we solve symmetric tensor decomposition problem by minimizing a multiconvex optimization problem. We use alternating gradient descent algorithm to solve. Although we focus on symmetric tensors in this article, the method can be extended to nonsymmetric tensors in some cases. Additionally, we also give some theoretical analysis about our alternating gradient descent algorithm. We prove that alternating gradient descent algorithm converges linearly to global minimizer. We also provide numerical results to show the effectiveness of the algorithm.     

A New Approximation of the Matrix Rank Function and Its Application to Matrix Rank Minimization

The matrix rank minimization problem is widely applied in many fields such as control, signal processing and system identification. However, the problem is NP-hard in general and is computationally hard to directly solve in practice. In this paper, we provide a new approximation function of the matrix rank function, and the corresponding approximation problems can be used to approximate the matrix rank minimization problem within any level of accuracy. Furthermore, the successive projected gradient method, which is designed based on the monotonicity and the Fréchet derivative of these new approximation function, can be used to solve the matrix rank minimization this problem by using the projected gradient method to find the stationary points of a series of approximation problems. Finally, the convergence analysis and the preliminary numerical results are given.     

Relaxed two points projection method for solving the multiple-sets split equality problem

The multiple-sets split equality problem, a generalization and extension of the split feasibility problem, has a variety of specific applications in real world, such as medical care, image reconstruction, and signal processing. It can be a model for many inverse problems where constraints are imposed on the solutions in the domains of two linear operators as well as in the operators’ ranges simultaneously. Although, for the split equality problem, there exist many algorithms, there are but few algorithms for the multiple-sets split equality problem. Hence, in this paper, we present a relaxed two points projection method to solve the problem; under some suitable conditions, we show the weak convergence and give a remark for the strong convergence method in the Hilbert space. The interest of our algorithm is that we transfer the problem to an optimization problem, then, based on the model, we present a modified gradient projection algorithm by selecting two different initial points in different sets for the problem (we call the algorithm as two points algorithm). During the process of iteration, we employ subgradient projections, not use the orthogonal projection, which makes the method implementable. Numerical experiments manifest the algorithm is efficient.     

Optimization of Molecular Similarity Index with Applications to Biomolecules

Molecular similarity index measures the similarity between two molecules. Computing the optimal similarity index is a hard global optimization problem. Since the objective function value is very hard to compute and its gradient vector is usually not available, previous research has been based on non-gradient algorithms such as random search and the simplex method. In a recent paper, McMahon and King introduced a Gaussian approximation so that both the function value and the gradient vector can be computed analytically. They then proposed a steepest descent algorithm for computing the optimal similarity index of small molecules. In this paper, we consider a similar problem. Instead of computing atom-based derivatives, we directly compute the derivatives with respect to the six free variables describing the relative positions of the two molecules.. We show that both the function value and gradient vector can be computed analytically and apply the more advanced BFGS method in addition to the steepest descent algorithm. The algorithms are applied to compute the similarities among the 20 amino acids and biomolecules like proteins. Our computational results show that our algorithm can achieve more accuracy than previous methods and has a 6-fold speedup over the steepest descent method.     

Superconvergent Cluster Recovery Method for the Crouzeix-Raviart Element

In this paper, we propose and numerically investigate a superconvergent cluster recovery (SCR) method for the Crouzeix-Raviart (CR) element. The proposed recovery method reconstructs a $C^0$ linear gradient. A linear polynomial approximation is obtained by a least square fitting to the CR element approximation at certain sample points, and then taken derivatives to obtain the recovered gradient. The SCR recovery operator is superconvergent on uniform mesh of four patterns. Numerical examples show that SCR can produce a superconvergent gradient approximation for the CR element, and provide an asymptotically exact error estimator in the adaptive CR finite element method.     

A combined direction stochastic approximation algorithm

The stochastic approximation problem is to find some root or minimum of a nonlinear function in the presence of noisy measurements. The classical algorithm for stochastic approximation problem is the Robbins-Monro (RM) algorithm, which uses the noisy negative gradient direction as the iterative direction. In order to accelerate the classical RM algorithm, this paper gives a new combined direction stochastic approximation algorithm which employs a weighted combination of the current noisy negative gradient and some former noisy negative gradient as iterative direction. Both the almost sure convergence and the asymptotic rate of convergence of the new algorithm are established. Numerical experiments show that the new algorithm outperforms the classical RM algorithm.     

Approximation of the steepest descent direction for the O-D matrix adjustment problem

In this paper, a method to approximate the directions of Clarke's generalized gradient of the upper level function for the demand adjustment problem on traffic networks is presented. Its consistency is analyzed in detail. The theoretical background on which this method relies is the known property of proximal subgradients of approximating subgradients of proximal bounded and lower semicountinuous functions using the Moreau envelopes. A double penalty approach is employed to approximate the proximal subgradients provided by these envelopes. An algorithm based on partial linearization is used to solve the resulting nonconvex problem that approximates the Moreau envelopes, and a method to verify the accuracy of the approximation to the steepest descent direction at points of differentiability is developed, so it may be used as a suitable stopping criterion. Finally, a set of experiments with test problems are presented, illustrating the approximation of the solutions to a steepest descent direction evaluated numerically. Research supported under Spanish CICYT project TRA99-1156-C02-02.     

A stochastic gradient type algorithm for closed-loop problems

We focus on the numerical solution of closed-loop stochastic problems, and propose a perturbed gradient algorithm to achieve this goal. The main hurdle in such problems is the fact that the control variables are infinite-dimensional, due to, e.g., the information constraints. Alternatively said, control variables are feedbacks, i.e., functions. Such controls have hence to be represented in a finite way in order to solve the problem numerically. In the same way, the gradient of the criterion is itself an infinite-dimensional object. Our algorithm replaces this exact (and unknown) gradient by a perturbed one, which consists of the product of the true gradient evaluated at a random point and a kernel function which extends this gradient to the neighbourhood of the random point. Proceeding this way, we explore the whole space iteration after iteration through random points. Since each kernel function is perfectly known by a small number of parameters, say N, the control at iteration k is perfectly known as an infinite-dimensional object by at most N × k parameters. The main strength of this method is that it avoids any discretization of the underlying space, provided that we can sample as many points as needed in this space. Moreover, our algorithm can take into account the possible measurability constraints of the problem in a new way. Finally, the randomized strategy implemented by the algorithm causes the most probable parts of the space to be the most explored ones, which is a priori an interesting feature. In this paper, we first prove two convergence results of this algorithm in the strongly convex and convex cases, and then give some numerical examples showing the interest of this method for practical stochastic optimization problems. In Memoriam: Jean-Sébastien Roy passed away July 04, 2007. He was 33 years old.     

A Better Approximation Algorithm for Finding Planar Subgraphs

The MAXIMUM PLANAR SUBGRAPH problem—given a graphG, find a largest planar subgraph ofG—has applications in circuit layout, facility layout, and graph drawing. No previous polynomial-time approximation algorithm for this NP-Complete problem was known to achieve a performance ratio larger than 1/3, which is achieved simply by producing a spanning tree ofG. We present the first approximation algorithm for MAXIMUM PLANAR SUBGRAPH with higher performance ratio (4/9 instead of 1/3). We also apply our algorithm to find large outerplanar subgraphs. Last, we show that both MAXIMUM PLANAR SUBGRAPH and its complement, the problem of removing as few edges as possible to leave a planar subgraph, are Max SNP-Hard.