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

Solving L1-regularized SVMs and Related linear Programs: Revisiting the Effectiveness of Column and Constraint Generation

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2022年第1期23卷 1-41页

作者： Dedieu, Antoine Mazumder, Rahul Wang, Haoyue Vicarious AI Union CA 94587 USA MIT Sloan Sch Management 77 Massachusetts Ave Cambridge MA 02139 USA MIT Ctr Operat Res 77 Massachusetts Ave Cambridge MA 02139 USA

The linear Support Vector Machine (SVM) is a classic classification technique in machine learning. Motivated by applications in high dimensional statistics, we consider penalized SVM problems involving the minimization of a hinge-loss function with a convex sparsity -inducing regularizer such as: the L1-norm on the coefficients, its grouped generalization and the sorted L1-penalty (aka Slope). Each problem can be expressed as a linear Pro-gram (LP) and is computationally challenging when the number of features and/or sam-ples is large-the current state of algorithms for these problems is rather nascent when compared to the usual L2-regularized linear SVM. To this end, we propose new computa-tional algorithms for these LPs by bringing together techniques from (a) classical column (and constraint) generation methods and (b) first order methods for non-smooth convex optimization-techniques that appear to be rarely used together for solving large scale LPs. These components have their respective strengths;and while they are found to be useful as separate entities, they appear to be more powerful in practice when used together in the context of solving large-scale LPs such as the ones studied herein. Our approach complements the strengths of (a) and (b)-leading to a scheme that seems to significantly outperform commercial solvers as well as specialized implementations for these problems. We present numerical results on a series of real and synthetic data sets demonstrating the surprising effectiveness of classic column/constraint generation methods in the context of challenging LP-based machine learning tasks.

关键词： large scale linear programming L1-penalization slope hinge loss column generation constraint generation first order methods

来源：评论

学校读者我要写书评

暂无评论

Solving L1-regularized SVMs and related linear programs: revisiting the effectiveness of column and constraint generation

The Journal of Machine Learning Research

引用

The Journal of Machine Learning Research 2022年第1期23卷 7389-7429页

作者： Antoine Dedieu Rahul Mazumder Haoyue Wang Vicarious AI Union City CA MIT Sloan School of Management and Operations Research Center Massachusetts Institute of Technology Cambridge MA Operations Research Center Massachusetts Institute of Technology Cambridge MA

The linear Support Vector Machine (SVM) is a classic classification technique in machine learning. Motivated by applications in high dimensional statistics, we consider penalized SVM problems involving the minimization of a hinge-loss function with a convex sparsity-inducing regularizer such as: the L1-norm on the coefficients, its grouped generalization and the sorted L1-penalty (aka Slope). Each problem can be expressed as a linear Program (LP) and is computationally challenging when the number of features and/or samples is large--the current state of algorithms for these problems is rather nascent when compared to the usual L2-regularized linear SVM. To this end, we propose new computational algorithms for these LPs by bringing together techniques from (a) classical column (and constraint) generation methods and (b) first order methods for non-smooth convex optimization--techniques that appear to be rarely used together for solving large scale LPs. These components have their respective strengths; and while they are found to be useful as separate entities, they appear to be more powerful in practice when used together in the context of solving large-scale LPs such as the ones studied herein. Our approach complements the strengths of (a) and (b)--leading to a scheme that seems to significantly outperform commercial solvers as well as specialized implementations for these problems. We present numerical results on a series of real and synthetic data sets demonstrating the surprising effectiveness of classic column/constraint generation methods in the context of challenging LP-based machine learning tasks.

关键词： large scale linear programming ℓ1-penalization slope hinge loss column generation constraint generation first order methods

来源：评论

学校读者我要写书评

暂无评论

On some difficult linear programs coming from set partitioning

引用

DISCRETE APPLIED MATHEMATICS 2002年第1-2期118卷 3-11页

作者： Barahona, F Anbil, R IBM Corp Thomas J Watson Res Ctr Yorktown Hts NY 10598 USA Caleb Technol Corp Austin TX 78759 USA

We deal with the linear programming relaxation of set partitioning problems arising in airline crew scheduling. Some of these linear programs have been extremely difficult to solve with the traditional algorithms, We have used an extension of the subgradient algorithm, the volume algorithm, to produce primal solutions that might violate the constraints by at most 2%, and that are within 1% of the lower bound. This method is fast, requires minimal storage, and can be parallelized in a straightforward way. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： subgradient algorithm volume algorithm large scale linear programming

来源：评论

学校读者我要写书评

暂无评论

The volume algorithm: producing primal solutions with a subgradient method

引用

MATHEMATICAL programming 2000年第3期87卷 385-399页

作者： Barahona, F Anbil, R IBM Corp Thomas J Watson Res Ctr Yorktown Heights NY 10598 USA

We present an extension to the subgradient algorithm to produce primal as well as dual solutions. It can he seen as a fast way to carry out an approximation of Dantzig-Wolfe decomposition. This gives a Fast method for producing approximations for large scale linear programs. It is based on a new theorem in linear programming duality. We present successful experience with linear programs coming from set partitioning, set covering, max-cut and plant location.

关键词： subgradient algorithm Dantzig-Wolfe decomposition large scale linear programming

来源：评论

学校读者我要写书评

暂无评论

A CLUSTERING HEURISTIC TO DETECT STAIRCASE STRUCTURES IN large-scale linear-programming MODELS

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1994年第1期76卷 229-239页

作者： JAYAKUMAR, MD RAMASESH, RV TEXAS CHRISTIAN UNIV FT WORTHTX 76129

The 'staircase' structure is one of the more frequently found structures in large scale linear programs. It is known that the staircase structured problems lend themselves to efficient solution through decomposition based procedures. However, in many large scale problems any underlying structure may be obscured by getting imbedded into other more obvious structures. This paper addresses the identification of the underlying staircase structure in the rectangular matrices of large scale linear programs (LSLPs). The problem is known to be computationally hard. To solve this problem, we propose a heuristic algorithm based on the rank order clustering procedure. The results from the application of this algorithm to a number of test problems of known structure indicate that it runs it linear time of the problem size. We demonstrate the effectiveness of the algorithm through its ability to identify the correct number of diagonal subproblems that make up the staircase structure in the coefficient matrices of the LSLPs of two test sets: the first, collected from the public domain software server, NETLIB;and the second, randomly generated.

关键词： CLUSTERING HEURISTIC FOR DECOMPOSITION large scale linear programming MATHEMATICAL programming

来源：评论

学校读者我要写书评

暂无评论

HOPDM (VERSION-2.12) - A FAST LP SOLVER BASED ON A PRIMAL-DUAL INTERIOR-POINT METHOD

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1995年第1期85卷 221-225页

作者： GONDZIO, J POLISH ACAD SCI SYST RES INSTNEWELSKA 6PL-01447 WARSAWPOLAND

The article presents information on the large scale linear programming software called Higher Order Primal Dual Method (HOPDM). HOPDM is an implementation of the primal-dual interior point method for solving large scale linear programming (LP) problems. Its newest version 2.12 is a robust and efficient code that compares favorably with today's commercial LP solvers. The development of HOPDM started from the joint work with engineer Anna Altman in 1992. Since then the code has been independently developed in two different directions. Motivated with a real life application, Altman extended it to handle separable convex quadratic programs, while others concentrated on improving robustness and efficiency of the basic LP algorithm. The algorithm implemented in HOPDM is a new variant of a primal-dual method. The basic primal-dual algorithm has been developed independently. Recently an engineer proposed a nontrivial modification to this well known algorithm. The new method is more flexible; it plays with a centrality of subsequent iterates, choosing the targets that lie in a wide neighborhood of the central path.

关键词： large scale linear programming INTERIOR POINT METHOD PRIMAL-DUAL ALGORITHM MULTIPLE CENTRALITY CORRECTORS

来源：评论

学校读者我要写书评

暂无评论

Constructing Plantwide Management and Information System

引用

IFAC Proceedings Volumes 1990年第3期23卷 227-232页

作者： K. Yamashita Computer Application Systems Department Toshiba Co. Tokyo Japan

The paper presents a conceptual overview, key technologies and experience in constructing plantwide management and information systems. The necessity of such a system is first described, followed by an outline of the system structure. Then, we present a millwide system, which has been in operation in one of the largest pulp and paper mill in Japan. This system employs key technologies, such as optimization algorithms, an expert system, relational database management, simulation techniques and local area networks. We also make several suggestions on constructing plantwide management and information systems based on our practical experiences in several plantwide systems. Finally, we discuss the future direction in which we expect these system to develop.

关键词： Plantwide system millwide system energy supply optimization production schedule optimization production planning expert system relational database large scale linear programming LAN

来源：评论

学校读者我要写书评

暂无评论

An Algorithm of Feasible Directions for the Aggregation Problem

引用

Optimization 1989年第2期20卷 193-208页

作者： García, L. Academy of Sciences of Cuba Dept. of Cybernetics Mathematics and Physics Havana Cuba

In this paper an algorithm of feasible directions for the aggregation problem is presented. We start by studying the simplest case, when all the variables are aggregated in an only aggregated variable. Afterwards, the... 详细信息

关键词： Iterative aggregation large scale linear programming programming algorithms

来源：评论

学校读者我要写书评

暂无评论

A REGULARIZED DECOMPOSITION METHOD FOR MINIMIZING A SUM OF POLYHEDRAL FUNCTIONS

引用

MATHEMATICAL programming 1986年第3期35卷 309-333页

作者： RUSZCZYNSKI, A 1.Institut für Operations Research Universit?t Zürich Switzerland

A problem of minimizing a sum of many convex piecewise-linear functions is considered. In view of applications to two-stage linear programming, where objectives are marginal values of lower level problems, it is assumed that domains of objectives may be proper polyhedral subsets of the space of decision variables and are defined by piecewise-linear induced feasibility constraints. We propose a new decomposition method that may start from an arbitrary point and simultaneously processes objective and feasibility cuts for each component. The master program is augmented with a quadratic regularizing term and comprises an a priori bounded number of cuts. The method goes through nonbasic points, in general, and is finitely convergent without any nondegeneracy assumptions. Next, we present a special technique for solving the regularized master problem that uses an active set strategy and QR factorization and exploits the structure of the master. Finally, some numerical evidence is given.

关键词： large scale linear programming stochastic programming subgradient methods semidefinite quadratic programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：