检索结果-内蒙古大学图书馆

Annual Conference on Neural Information Processing Systems

作者： Ian E.H. Yen Kai Zhong Cho-Jui Hsieh Pradeep Ravikumar Inderjit S. Dhillon University of Texas at Austin University of California at Davis

ISBN: (纸本)9781510825024

Over the past decades, linear programming (LP) has been widely used in different areas and considered as one of the mature technologies in numerical optimization. However, the complexity offered by state-of-the-art algorithms (i.e. interior-point method and primal, dual simplex methods) is still unsatisfactory for problems in machine learning with huge number of variables and constraints. In this paper, we investigate a general LP algorithm based on the combination of Augmented Lagrangian and Coordinate Descent (AL-CD), giving an iteration complexity of O((log(1/∈))~2) with O(nnz(A)) cost per iteration, where nnz(A) is the number of non-zeros in the m × n constraint matrix A, and in practice, one can further reduce cost per iteration to the order of non-zeros in columns (rows) corresponding to the active primal (dual) variables through an active-set strategy. The algorithm thus yields a tractable alternative to standard LP methods for large-scale problems of sparse solutions and nnz(A) ＜＜ mn. We conduct experiments on large-scale LP instances from ?_1 -regularized multi-class SVM, Sparse Inverse Covariance Estimation, and Nonnegative Matrix Factorization, where the proposed approach finds solutions of 10~(-3) precision orders of magnitude faster than state-of-the-art implementations of interior-point and simplex methods.

关键词： iterative methods linear programming descent Simplex method Coordinates Dual matrix decomposition Simplex

来源：评论

学校读者我要写书评

暂无评论

Airborne gravimetry data sparse reconstruction via L1-norm convex quadratic programming

引用

Applied Geophysics 2015年第2期12卷 147-156,273页

作者：杨亚鹏吴美平唐刚国防科学技术大学机电工程与自动化学院长沙410073 北京化工大学机电工程学院北京100029

In practice, airborne gravimetry is a sub-Nyquist sampling method because of the restrictions imposed by national boundaries, financial cost, and database size. In this study, we analyze the sparsity of airborne gravimetry data by using the discrete Fourier transform and propose a reconstruction method based on the theory of compressed sensing for large- scale gravity anomaly data. Consequently, the reconstruction of the gravity anomaly data is transformed to a Ll-norm convex quadratic programming problem. We combine the preconditioned conjugate gradient algorithm （PCG） and the improved interior-point method （IPM） to solve the convex quadratic programming problem. Furthermore, a flight test was carried out with the homegrown strapdown airborne gravimeter SGA-WZ. Subsequently, we reconstructed the gravity anomaly data of the flight test, and then, we compared the proposed method with the linear interpolation method, which is commonly used in airborne gravimetry. The test results show that the PCG-IPM algorithm can be used to reconstruct large-scale gravity anomaly data with higher accuracy and more effectiveness than the linear interpolation method.

关键词： Compressed sensing interior-point method sub-Nyquist sampling airborne gravimetry Fourier transform

来源：评论

学校读者我要写书评

暂无评论

Addressing Rank Degeneracy in Constraint-Reduced interior-point methods for linear Optimization

引用

JOURNAL OF OPTIMIZATION theory AND APPLICATIONS 2014年第1期160卷 127-157页

作者： Winternitz, Luke B. Tits, Andre L. Absil, P-A Univ Maryland Dept Elect & Comp Engn College Pk MD 20742 USA Univ Maryland Syst Res Inst College Pk MD 20742 USA Catholic Univ Louvain ICTEAM Inst Dept Engn Math B-1348 Louvain Belgium

In earlier works (Tits et al. SIAM J. Optim., 17(1):119-146, 2006;Winternitz et al. Comput. Optim. Appl., 51(3):1001-1036, 2012), the present authors and their collaborators proposed primal-dual interior-point (PDIP) algorithms for linear optimization that, at each iteration, use only a subset of the (dual) inequality constraints in constructing the search direction. For problems with many more variables than constraints in primal form, this can yield a major speedup in the computation of search directions. However, in order for the Newton-like PDIP steps to be well defined, it is necessary that the gradients of the constraints included in the working set span the full dual space. In practice, in particular in the case of highly sparse problems, this often results in an undesirably large working set-or in an expensive trial-and-error process for its selection. In this paper, we present two approaches that remove this non-degeneracy requirement, while retaining the convergence results obtained in the earlier work.

关键词： linear programming linear optimization Constraint reduction Primal-dual interior point Regularization

来源：评论

学校读者我要写书评

暂无评论

A New Procedure for Solving Integer linear programming Problems

引用

ARABIAN JOURNAL FOR SCIENCE AND ENGINEERING 2014年第6期39卷 5265-5269页

作者： Tantawy, S. F. Helwan Univ Dept Math Fac Sci Cairo 11795 Egypt

This paper presents a new procedure for solving the integer linear programming problem when the objective function is a linear function and the set of constraints is in the form of linear inequality constraints. The proposed procedure is based on the conjugate gradient projection method together with the use of the spirit of Gomory cut. The main idea behind our method is to move through the feasible region through a sequence of points in the direction that improves the objective function. Since methods based on vertex information may have difficulties as the problem size increases, therefore, the present method can be considered as an interior point method, which had been proved to be less sensitive to problem size. A simple production example is given to clarify the theory of this new procedure.

关键词： linear program Integer linear programming Conjugate gradient

来源：评论

学校读者我要写书评

暂无评论

Solving large-scale optimization problems related to Bell's Theorem

引用

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS 2014年 263卷 392-404页

作者： Gondzio, Jacek Gruca, Jacek A. Hall, J. A. Julian Laskowski, Wieslaw Zukowski, Marek Univ Edinburgh Sch Math Edinburgh EH9 3JZ Midlothian Scotland Univ Edinburgh Maxwell Inst Math Sci Edinburgh EH9 3JZ Midlothian Scotland Univ Gdansk Inst Theoret Phys & Astrophys PL-80952 Gdansk Poland

Impossibility important fact in foundations of quantum physics, gaining now new applications in quantum information theory. We present an in-depth description of a method of testing the existence of such models, which involves two levels of optimization: a higher-level non-linear task and a lower-level linear programming (LP) task. The article compares the performances of the existing implementation of the method, where the LPs are solved with the simplex method, and our new implementation, where the LPs are solved with an innovative matrix-free interior point method. We describe in detail how the latter can be applied to our problem, discuss the basic scenario and possible improvements and how they impact on overall performance. Significant performance advantage of the matrix-free interior point method over the simplex method is confirmed by extensive computational results. The new method is able to solve substantially larger problems. Consequently, the noise resistance of the non-classicality of correlations of several types of quantum states, which has never been computed before, can now be efficiently determined. An extensive set of data in the form of tables and graphics is presented and discussed. The article is intended for all audiences, no quantum-mechanical background is necessary. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Quantum information Large-scale optimization interior point methods Matrix-free methods

来源：评论

学校读者我要写书评

暂无评论

线性规划的一个新的Mehrotra型预估-矫正算法

引用

首都师范大学学报（自然科学版） 2015年第1期36卷 5-9页

作者：刘长河吴丹河南科技大学数学与统计学院洛阳471023

在线性规划的内点算法中,理论和实践之间存在着数值效果好的算法具有较差复杂性的矛盾.目前大多数内点算法软件的执行采用Mehrotra型预估-矫正算法.本文提出了求解线性规划问题的一个新的Mehrotra型预估-矫正算法,证明了该算法的迭代复... 详细信息

在线性规划的内点算法中,理论和实践之间存在着数值效果好的算法具有较差复杂性的矛盾.目前大多数内点算法软件的执行采用Mehrotra型预估-矫正算法.本文提出了求解线性规划问题的一个新的Mehrotra型预估-矫正算法,证明了该算法的迭代复杂性是O(槡n L),这是内点算法所具有的最好的复杂性结果.

关键词：线性规划内点法 Mehrotra型预估-矫正算法多项式复杂性

来源：评论

学校读者我要写书评

暂无评论

Incremental Approximate Saddle-point Computation in Zero-sum Matrix Games 53

Incremental Approximate Saddle-point Computation in Zero-sum...

引用

53rd IEEE Annual Conference on Decision and Control (CDC)

作者： Bopardikar, Shaunak D. Langbort, Cedric United Technol Res Ctr Inc Berkeley CA 94720 USA Univ Illinois Dept Aerosp Engn Urbana IL USA

ISBN: (纸本)9781467360906

We consider the problem of approximately and efficiently computing saddle-point values for zero-sum matrix games. This problem arises in scenarios where the game's exact value is hard to compute, either because the columns of the matrix are revealed incrementally in time, or because the game's strategy space is too large for traditional methods (e.g., linear programming) to be effective in practice. We leverage the established adaptive multiplicative weights algorithm but introduce a novel simple criterion to determine whether the minimizer's best strategy needs to be approximately re-computed as a new column of the matrix is introduced. Our main results are two-fold. First, we show that our proposed incremental approach achieves the same accuracy as applying the adaptive multiplicative weights algorithm on the entire matrix, if known a priori. Secondly, we argue that our approach can be computationally more efficient than simply re-computing the minimizer's best strategy upon addition of every new column of the matrix. Specifically, for the case when the columns of the matrix are generated independently and from the same distribution, we characterize the probability that the expected number of times the best response is re-computed exceeds a given fraction of the total number of columns in the matrix. Numerical simulations indicate even more significant computational improvement as compared to the analytic result.

关键词： Matrix Games Game theory Computational methods Probabilistic methods

来源：评论

学校读者我要写书评

暂无评论

Bi-objective Optimization of a Continuous Biological Process

Bi-objective Optimization of a Continuous Biological Process

引用

IEEE International Conference on Systems Biology.

作者： Gongxian Xu Ying Liu Chao Yu Dan Su Department of Mathematics Bohai University Jinzhou China

ISBN: (纸本)9781479972951

This paper addresses the bi-objective optimization of continuous bio-dissimilation process of glycerol to 1, 3-propanediol. A bi-objective optimization model is firstly proposed to maximize the production rate of 1, 3-propanediol, simultaneously maximize the conversion rate of glycerol and ensure the bioprocess is operated under steady-state conditions. Then this bi-objective problem can be transformed into a sequence of single objective problems by using the weighted-sum and normal-boundary intersection methods respectively. Finally, these single objective problems are solved by an interior point method. The results show that the weighted-sum and normal-boundary intersection methods can obtain the approximate Pareto-optimal set of the proposed bi-objective optimization problem.

关键词： Optimization Production Mathematical model Substrates linear programming Biological system modeling Kinetic theory

来源：评论

学校读者我要写书评

暂无评论

Information Geometry and interior-point Algorithms in Semidefinite Programs and Symmetric Cone Programs

引用

JOURNAL OF OPTIMIZATION theory AND APPLICATIONS 2013年第3期157卷 749-780页

作者： Kakihara, Satoshi Ohara, Atsumi Tsuchiya, Takashi Natl Grad Inst Policy Studies Minato Ku Tokyo 1068677 Japan Univ Fukui Grad Sch Engn Fukui 9108507 Japan

We develop an information geometric approach to conic programming. Information geometry is a differential geometric framework specifically tailored to deal with convexity, naturally arising in information science including statistics, machine learning and signal processing etc. First we introduce an information geometric framework of conic programming. Then we focus on semidefinite and symmetric cone programs. Recently, we demonstrated that the number of iterations of Mizuno-Todd-Ye predictor-corrector primal-dual interior-point methods is (asymptotically) expressed with an integral over the central trajectory called "the curvature integral". The number of iterations of the algorithm is approximated surprisingly well with the integral even for fairly large linear/semidefinite programs with thousands of variables. Here we prove that "the curvature integral" admits a rigorous differential geometric expression based on information geometry. We also obtain an interesting information geometric global theorem on the central trajectory for linear programs. Together with the numerical evidence in the aforementioned work, we claim that "the number of iterations of the interior-point algorithm is expressed as a differential geometric quantity.".

关键词： interior-point methods Iteration complexities Curvature integral Semidefinite programs Symmetric cone programs Conic programming Information geometry

来源：评论

学校读者我要写书评

暂无评论

Warmstarting the homogeneous and self-dual interior point method for linear and conic quadratic problems

引用

MATHEMATICAL programming COMPUTATION 2013年第1期5卷 1-25页

作者： Skajaa, Anders Andersen, Erling D. Ye, Yinyu Tech Univ Denmark Dept Informat & Math Modelling 2800 Kgs Lyngby Denmark MOSEK ApS DK-2100 Copenhagen Denmark Stanford Univ Dept Management Sci & Engn Stanford CA 94305 USA

We present two strategies for warmstarting primal-dual interior point methods for the homogeneous self-dual model when applied to mixed linear and quadratic conic optimization problems. Common to both strategies is their use of only the final (optimal) iterate of the initial problem and their negligible computational cost. This is a major advantage when compared to previously suggested strategies that require a pool of iterates from the solution process of the initial problem. Consequently our strategies are better suited for users who use optimization algorithms as black-box routines which usually only output the final solution. Our two strategies differ in that one assumes knowledge only of the final primal solution while the other assumes the availability of both primal and dual solutions. We analyze the strategies and deduce conditions under which they result in improved theoretical worst-case complexity. We present extensive computational results showing work reductions when warmstarting compared to coldstarting in the range 30-75% depending on the problem class and magnitude of the problem perturbation. The computational experiments thus substantiate that the warmstarting strategies are useful in practice.

关键词： Warmstart interior point method Homogeneous model Conic programming

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：