“优化与应用”2010前沿讲座.doc

“优化与应用”前沿讲座 时间：2010.7.31-8.1地点：思源楼一层大报告厅主办：数学院“优化与应用”研究中心7月31日下午学术报告（2：00开始）报告题目：An Analysis of Serial Allocation Rule in Group Buying报告者：Jiawei Zhang （张家伟）报告者单位：New York UniversityAbstract: When a seller offers quantity discount, buyers can aggregate their purchasing quantity to obtain lower prices. A cost allocation rule determines how much each buyer would pay for the amount they they purchased. Various cost allocation rules have been used in practice. Different allocation rules may have may different influence on the buyers behavior (i.e., their purchasing quantities) In this paper, we study the serial allocation rule and analyze the equilibrium purchasing quantity under this rule. 报告题目：Approximation algorithms for the facility location problems with linear/submodular penalties报告者：徐大川报告者单位：北京工业大学Abstract: We study two variants of the classical emphfacility location problem (FLP), namely the emphfacility location problem with linear penalties (FLPLP) and the emphfacility location problem with submodular penalties (FLPSP). Our main contribution is to provide greatly improved approximation algorithms for both problems via several novel techniques which exploit the special properties of the linear/submodular penalty function. For the former problem, our LP-rounding based non-combinatorial $1.575$-approximation algorithm offers the currently best approximation ratio (the currently best combinatorial approximation ratio is $1.853$ due to Xu and Xu citexx2). For the latter problem, our LP-rounding based $2.056$-approximation algorithm and the primal-dual with greedy argumentation based $2.375$-approximation algorithm offer the currently best non-combinatorial and combinatorial approximation ratios, respectively. Moreover, we also give the first verifiable dual-fitting based approximation algorithms for both problems. Joint work with Yu Li, Donglei Du, and Naihua Xiu.报告题目：Sparse Signal Reconstruction via Iterative Support Detection 报告者：Wotao Yin （印卧涛）报告者单位：Rice UniversityAbstract: We present a novel sparse signal reconstruction method “ISD”, which reconstructs sparse signals faster from a reduced number of measurements compared to the classical L1 minimization. ISD addresses failed reconstructions of L1 minimization due to insufficient measurements. It estimates a support set from a current reconstruction and obtains a new reconstruction by solving a truncated L1 minimization problem, and it iterates these two steps for a small number of times. The talk will include analysis and theoretical justifications of ISD. ISD has been applied to image reconstruction. The resulting code EdgeCS recovers images of higher qualities from fewer measurements than the current state-of-the-art methods. EdgeCS exactly recovers the 256x256 Shepp-Logan phantom from merely 7 radial lines (or 3.03% k-space), which is impossible for most existing algorithms. It accurately reconstructs a 512512 magnetic resonance image from 21% noisy samples. Moreover, it is also able to reconstruct complex-valued images. This is joint work with Weihong Guo (Case Western) and Yilun Wang (Cornell).7月31日下午学术报告（茶歇20分钟以后开始）报告题目：Approximation Algorithm for Polynomial Function Optimization报告者：Simai He (何斯迈)报告者单位：香港中文大学Abstract: We consider polynomial-time approximation algorithms for optimizing a genericmulti-variate homogeneous polynomial function, subject to ellipsoid constraints.Approximation algorithms are proposed for this problem with the proven worst-case relative approximationperformance ratios, which are dependent only on the dimensions of the model.Furthermore, by applying the Lowner-John theorem, the constraint set is relaxed to a general bounded convex set.Results of our numerical experiments are reported, indicating remarkably good performance of the proposed algorithms for solving the randomly generated test instances.The results can be extended for inhomogeneous polynomial function with ellipsoid constraints.报告题目：DEM Constructoin from Contour lines based on Regional Optimum Control 报告者：DunJiang Song(宋敦江)报告者单位：中国科学院科技政策与管理科学研究所Abstract: Digital Elevation Model (DEM) data are widely used in many research areas such as Geographical Information System (GIS), hydrological analysis and soil erosion models. Traditional contour lines from manual interpretation of landforms are an important kind of data source for DEM construction. DEM of scales 1:10,000, 1:50,000 and 1:250,000 from State Bureau of Surveying and Mapping P.R.C are constructed from contour lines and scattered points using the constrained Triangulated Irregular Network (TIN) method. HASM (High Accuracy Surface Modeling) is a method for surface modeling, based on the theory of surface, which means that, except its position in space, a surface is uniquely defined by its first fundamental coefficients and second fundamental coefficients. Presently, HASM is mainly used for scattered points interpolation, such as DEM construction from scattered points secured by field surveys, soil PH surface modeling. By minimizing the equations of HASM, subjected to equality constraints from discretizing vector contour lines and to bound constraints from regional points between contour lines, a method called HASMROC (Regional Optimum Control) for constructing DEM is presented. “Regional” means that bound constraints is derived from the region between two neighboring contour lines. Contour lines not only contain quantitative information, such as the heights of the points they pass through, it also contain qualitative information, such as bounds on the height of the region between two contour lines. Among a group of contour lines, peaks, valley lines, ridge line and saddle can be extracted. The extracted information can be represented by strict inequality constraints, equality constraints and bound constraints respectively in optimum control. Converting contour lines into grid DEM is a basic research in geosciences, for it is a conversion between two basic spatial data type. It is still unknown that what the rule of conversion error is and what about spatial distribution of conversion error is. One numerical study and one real case study is given, results from HASMROC is compared with methods with two methods, which is TPS(Thin Plate Spline, TPS) and TIN(Triangulated Irregular Network), which are often used by geoscientists. Result from HASMROC is promising, but the main challenge of HASMROC is large-scale optimization (mostly more than 1e6 variables) with inequality constraints, equality constraints and bound constraints.报告题目：Some optimization problems in Electric Energy Systems报告者：Jinyun Yuan (袁锦韵)报告者单位：巴西巴拉那联邦大学Abstract: In this talk, some short review on mathematical problems, specially some optimization problems appeared in electric energy systems is given. The price issue will be discussed with more details.8月1日上午学术报告（9：00-10：00）报告题目：On the Complexity of L_p Minimization报告者：Yinyu Ye (叶荫宇)报告者单位：美国斯坦福大学Abstract: We show that the L_p norm (0 p 1) minimization problem, including the smoothed version, arising from sparse solution construction and compressed sensing is both hard and easy. More precisely, for any fixed 0p1, we prove that checking the global minimal value of the problem is NP-Hard; but computing a local minimizer of the problem is polynomial-time doable. We also establish lower bounds for the absolute value of nonzero entries in every local optimal solution of the model, which can be used to eliminate zero entries precisely in any numerical solution. Finally, we develop an interior-point algorithm with a provable complexity bound and demonstrate preliminary computational results of effectiveness of the algorithm.Joint work with Xiaojun Chen, Dongdong Ge, Xiaoye Jiang, and Fengmin Xu8月1日上午学术报告（10：30-11：30）报告题目：A Dynamic Near-Optimal Algorithm for Online Linear Programming报告者：Yinyu Ye (叶荫宇)报告者单位：美国斯坦福大学Abstract: A natural optimization model that formulates many online resource allocation and revenue management problems is the online linear program (LP) where the constraint matrix is revealed column by column along with the objective function. We provide a