半无限规划问题的算法研究及其应用

项目名称： 半无限规划问题的算法研究及其应用

项目编号： No.10871113

项目类型： 面上项目

立项/批准年度： 2009

项目学科： 金属学与金属工艺

项目作者： 张立平

作者单位： 清华大学

项目金额： 28万元

中文摘要： 半无限规划问题自从A.Charnes,W.W. Cooper, K.O. Kortanek于1963年提出以来一直是优化和工程领域的研究热点，因为它在逼近理论、最优控制、信号处理、数据挖掘等方面有重要的应用，而且近十年来它的应用更加广泛。但是由于它的约束函数有无限多个，致使算法设计很困难。就目前存在的算法来看对实际应用中出现的问题很难得到快速解决。本项目主要研究半无限规划问题的算法及其在信号处理等方面的应用。一是设计新而有效的交换法则，将半无限维规划转化成一系列有限维子问题来求解, 我们设计了求解半无限凸规划的交换法；二是利用势函数将无限多个约束转化为有限个约束，设计了平衡算法；三是将设计的新算法应用到信号处理、逼近理论等实际问题中，我们将数字信号滤波器问题化为二次约束的二次半无限规划问题，相应的子问题是易计算的锥规划问题，可充分利用最近的MATLAB优化软件(SeDuMi等)。

中文关键词： 半无限规划；算法；信号处理；逼近问题

英文摘要： The semi-infinite programming problem was proposed by A.Charnes,W.W. Cooper and K.O. Kortanek in 1963. Since then, many scholars in the fields of optimization and engineering pay more attention on this problem because it has many important applications in approximation, optimal control, signal processing, data mining, etc., and its applications are more wide in recent 10 years. It is very difficult to design algorithms to solve it because there are infinite number of constraints. Moreover, some existing algorithms do not fastly solve the problem which occurs in signal processing. In this project, we mainly study algorithms for solving SIP and apply them in signal processing. Our study includes the following three tasks: 1) develop a new exchanging rule, which reformate SIP as a sequence of finite optimization problems, we design an exchange method for convex semi-infinite programming; 2) Utilize merit functios to develop new techniques and then use them to reformulate the infinite constraints as finite costraints to handle, then develop equilibrium problem models; 3) Use the obtained new algorithms to solve SIPs appears in signal processing and approximation theory. We reformulate the digital filter design problem as semi-infinite quadratic programs and their corresponding subproblems are conic optimization problems which can be easily solved by using the newest softwares (e.g., SeDuMi, etc.).

英文关键词： semi-infinite programming;algorithm; signal processing;approximation theory