The Experts below are selected from a list of 14562 Experts worldwide ranked by ideXlab platform
Tapio Westerlund - One of the best experts on this subject based on the ideXlab platform.
-
a sequential Cutting Plane algorithm for solving convex nlp problems
European Journal of Operational Research, 2006Co-Authors: Claus Still, Tapio WesterlundAbstract:Abstract In this paper we look at a new algorithm for solving convex nonlinear programming optimization problems. The algorithm is a Cutting Plane-based method, where the sizes of the subproblems remain fixed, thus avoiding the issue with constantly growing subproblems we have for the classical Kelley’s Cutting Plane algorithm. Initial numerical experiments indicate that the algorithm is considerably faster than Kelley’s Cutting Plane algorithm and also competitive with existing nonlinear programming algorithms.
-
solving convex minlp optimization problems using a sequential Cutting Plane algorithm
Computational Optimization and Applications, 2006Co-Authors: Claus Still, Tapio WesterlundAbstract:In this article we look at a new algorithm for solving convex mixed integer nonlinear programming problems. The algorithm uses an integrated approach, where a branch and bound strategy is mixed with solving nonlinear programming problems at each node of the tree. The nonlinear programming problems, at each node, are not solved to optimality, rather one iteration step is taken at each node and then branching is applied. A Sequential Cutting Plane (SCP) algorithm is used for solving the nonlinear programming problems by solving a sequence of linear programming problems. The proposed algorithm generates explicit lower bounds for the nodes in the branch and bound tree, which is a significant improvement over previous algorithms based on QP techniques. Initial numerical results indicate that the described algorithm is a competitive alternative to other existing algorithms for these types of problems.
-
solving pseudo convex mixed integer optimization problems by Cutting Plane techniques
Optimization and Engineering, 2002Co-Authors: Tapio Westerlund, Swedish PolytechnicAbstract:In the present paper a Cutting Plane approach to solve mixed-integer non-linear programming (MINLP) problems, containing pseudo-convex functions, is given. It is shown how valid Cutting Planes for pseudo convex functions can be obtained and, furthermore, it is shown how a class of non-convex MINLP problems with a pseudo-convex objective function and pseudo-convex constraints, can be solved to global optimality with the considered Cutting Plane technique. Finally the numerical efficiency of the procedure, when solving some example problems, is illustrated.
Changshui Zhang - One of the best experts on this subject based on the ideXlab platform.
-
a faster Cutting Plane algorithm with accelerated line search for linear svm
Pattern Recognition, 2017Co-Authors: Changshui ZhangAbstract:Faster Cutting Plane algorithms with accelerated line search are proposed to solve linear SVM.It proposes a novel linear-time line search solver while the existing strategy spends O(mlogm) time.An optimized explicit piecewise linear function finding algorithm for multiclass linear SVM is derived.It can be proved to reduce the total SVM training time.Experiments demonstrate the effectiveness of the proposed algorithm. Cutting Plane algorithm (CPA) is a generalization of iterative first-order gradient method, in which the objective function is approximated successively by supporting hyperPlanes. CPA has been tailored to solve regularized loss minimization in machine learning by exploiting the regularization structure. In particular, for linear Support Vector Machine (SVM) embedding a line search procedure effectively remedies the fluctuations of function value and speeds up the convergence in practical issue. However, the existing line search strategy based on sorting algorithm takes O(mlogm) time. In this paper, we propose a more effective line search solver which spends only linear time. It can be extended to multiclass SVM in which an optimized explicit piecewise linear function finding algorithm is prearranged. The total SVM training time is proved to reduce theoretically and experiments consistently confirm the effectiveness of the proposed algorithms.
-
a faster Cutting Plane algorithm with accelerated line search for linear svm
Pattern Recognition, 2017Co-Authors: Changshui ZhangAbstract:Faster Cutting Plane algorithms with accelerated line search are proposed to solve linear SVM.It proposes a novel linear-time line search solver while the existing strategy spends O(mlogm) time.An optimized explicit piecewise linear function finding algorithm for multiclass linear SVM is derived.It can be proved to reduce the total SVM training time.Experiments demonstrate the effectiveness of the proposed algorithm. Cutting Plane algorithm (CPA) is a generalization of iterative first-order gradient method, in which the objective function is approximated successively by supporting hyperPlanes. CPA has been tailored to solve regularized loss minimization in machine learning by exploiting the regularization structure. In particular, for linear Support Vector Machine (SVM) embedding a line search procedure effectively remedies the fluctuations of function value and speeds up the convergence in practical issue. However, the existing line search strategy based on sorting algorithm takes O(mlogm) time. In this paper, we propose a more effective line search solver which spends only linear time. It can be extended to multiclass SVM in which an optimized explicit piecewise linear function finding algorithm is prearranged. The total SVM training time is proved to reduce theoretically and experiments consistently confirm the effectiveness of the proposed algorithms.
-
efficient maximum margin clustering via Cutting Plane algorithm
SIAM International Conference on Data Mining, 2008Co-Authors: Bin Zhao, Fei Wang, Changshui ZhangAbstract:Maximum margin clustering (MMC) is a recently proposed clustering method, which extends the theory of support vector machine to the unsupervised scenario and aims at finding the maximum margin hyperPlane which separates the data from different classes. Traditionally, MMC is formulated as a non-convex integer programming problem and is thus difficult to solve. Several methods have been proposed in the literature to solve the MMC problem based on either semidefinite programming or alternative optimization. However, these methods are time demanding while handling large scale datasets and therefore unsuitable for real world applications. In this paper, we propose the Cutting Plane maximum margin clustering (CPMMC) algorithm, to solve the MMC problem. Specifically, we construct a nested sequence of successively tighter relaxations of the original MMC problem, and each optimization problem in this sequence could be efficiently solved using the constrained concave-convex procedure (CCCP). Moreover, we prove theoretically that the CPMMC algorithm takes time O(sn) to converge with guaranteed accuracy, where n is the total number of samples in the dataset and s is the average number of non-zero features, i.e. the sparsity. Experimental evaluations on several real world datasets show that CPMMC performs better than existing MMC methods, both in efficiency and accuracy.
Guntram Scheithauer - One of the best experts on this subject based on the ideXlab platform.
-
a Cutting Plane algorithm for the one dimensional Cutting stock problem with multiple stock lengths
European Journal of Operational Research, 2002Co-Authors: Gleb Belov, Guntram ScheithauerAbstract:Abstract A Cutting Plane approach combining Chvatal–Gomory Cutting Planes with column generation is generalized for the case of multiple stock lengths in the one-dimensional Cutting stock problem. Appropriate modifications of the column generation procedure and the rounding heuristic are proposed. A comparison with the branch-and-price method for the problem with one stock type and representative test results are reported.
-
solving one dimensional Cutting stock problems exactly with a Cutting Plane algorithm
Journal of the Operational Research Society, 2001Co-Authors: Guntram Scheithauer, Johannes Terno, A Muller, Gleb BelovAbstract:When solving the one-dimensional Cutting stock problem (1D CSP) as an integer linear programming problem one has to overcome computational difficulties arising from the integrality condition and a huge number of variables. In the Gilmore–Gomory approach the corresponding continuous relaxation is solved via column generation techniques followed by an appropriate rounding of the in general non-integer solution. Obviously, there is no guarantee of obtaining an optimal solution in this way but it is extremely effective in practice. However, in two- and three-dimensional Cutting stock problems the heuristics are not so good which necessitates the research of effective exact methods. In this paper we present an exact solution approach for the 1D CSP which is based on a combination of the Cutting Plane method and the column generation technique. Results of extensive computational experiments are reported.
Kristina Soric - One of the best experts on this subject based on the ideXlab platform.
-
a Cutting Plane algorithm for a single machine scheduling problem
European Journal of Operational Research, 2000Co-Authors: Kristina SoricAbstract:Abstract Each of N part types (production families or items) is to be processed on a single machine. The part types arrive into the buffer in front of the machine at every unit of time at specified rates. The machine can process a finite number of part types at specified rates, but only one part type can be processed at any given time. Each switch from one type to another requires setup time. The objective is to schedule the part types in the sense that the required demand is met and the average work backlog in the system is minimal. Assuming a finite horizon, we define this problem as mixed 0–1 programming problem. In order to strengthen the formulation, we consider its LP relaxation in an enlarged space of variables. By projecting this polyhedron into the space of the original variables we obtain new valid inequalities for the original problem that are then used as Cutting Planes in a Cutting Plane/branch and bound algorithm. At the end we report some computational results that have the objective of empirically estimating the reduction in the integrality gap (the gap between the optimal values of the original problem and its linear programming relaxation). Also, we give and compare the CPU times of the Cutting Plane/branch and bound algorithm proposed in this paper and the branch and bound algorithm applied directly to the original problem.
Hiroshi Konno - One of the best experts on this subject based on the ideXlab platform.
-
a Cutting Plane algorithm for semi definite programming problems with applications to failure discriminant analysis
Journal of Computational and Applied Mathematics, 2002Co-Authors: Hiroshi Konno, Jun-ya Gotoh, Atsushi YukiAbstract:We will propose a new Cutting Plane algorithm for solving a class of semi-definite programming problems (SDP) with a small number of variables and a large number of constraints. Problems of this type appear when we try to classify a large number of multi-dimensional data into two groups by a hyper-ellipsoidal surface. Among such examples are cancer diagnosis, failure discrimination of enterprises. Also, a certain class of option pricing problems can be formulated as this type of problem. We will show that the Cutting Plane algorithm is much more efficient than the standard interior point algorithms for solving SDP.
-
bounding option prices by semidefinite programming a Cutting Plane algorithm
Management Science, 2002Co-Authors: Jun-ya Gotoh, Hiroshi KonnoAbstract:In a recent article, Bertsimas and Popescu showed that a tight upper bound on a Europeantype call option price, given the first n moments of the distribution of the underlying security price, can be obtained by solving an associated semidefinite programming problem (SDP). The purpose of this paper is to improve and extend their results. We will show that a tight lower bound can be calculated by solving another SDP. Also, we will show that these problems can be solved very quickly by a newly developed Cutting Plane algorithm when n is less than six or seven.
-
bounding option prices by semidefinite programming a Cutting Plane algorithm
Management Science, 2002Co-Authors: Jun-ya Gotoh, Hiroshi KonnoAbstract:In a recent article, Bertsimas and Popescu showed that a tight upper bound on a Europeantype call option price, given the first n moments of the distribution of the underlying security price, can be obtained by solving an associated semidefinite programming problem (SDP). The purpose of this paper is to improve and extend their results. We will show that a tight lower bound can be calculated by solving another SDP. Also, we will show that these problems can be solved very quickly by a newly developed Cutting Plane algorithm when n is less than six or seven.
