We propose an active-set algorithm for smooth multiobjective optimization problems subject to box constraints. The method works on one face of the feasible set at a time, treating it as a lower-dimensional region on which the problem simplifies. At each iteration, the algorithm decides whether to remain on the current face or to move to … Read more
This paper considers convex quadratic programs associated with the training of support vector machines (SVM). Exploiting the special structure of the SVM problem a new type of active set method with long cycles and stable rank-one-updates is proposed and tested (CMU: cycling method with updates). The structure of the problem allows for a repeated simple … Read more
In this paper, a class of bilevel programming problems is studied, in which the lower level is a quadratic programming problem, and the upper level problem consists of a nonlinear objective function with coupling constraints. An iterative process is developed to generate a sequence of points, which converges to the solution of this problem. In … Read more
We present a fast branch-and-bound algorithm for solving convex quadratic integer programs with few linear constraints. In each node, we solve the dual problem of the continuous relaxation using an infeasible active set method proposed by Kunisch and Rendl to get a lower bound; this active set algorithm is well suited for reoptimization. Our algorithm … Read more
In the Black-Scholes-Merton model, as well as in more general stochastic models in finance, the price of an American option solves a system of partial differential variational inequalities. When these inequalities are discretized, one obtains a linear complementarity problem that must be solved at each time step. This paper presents an algorithm for the solution … Read more
It has been known for almost 50 years that the discrete l_1 approximation problem can be solved effectively by linear programming. However, improved algorithms involve a step which can be interpreted as a line search, and which is not part of the standard LP solution procedures. l_1 provides the simplest example of a class of … Read more
This paper describes an active-set algorithm for large-scale nonlinear programming based on the successive linear programming method proposed by Fletcher and Sainz de la Maza. The step computation is performed in two stages. In the first stage a linear program is solved to estimate the active set at the solution. The linear program is obtained … Read more
We are interested in the solution of Horizontal Linear Complementarity Problems, HLCPs, that is complementarity problems with more variables than equations. Globally metrically regular HLCPs have nonempty solution sets that are stable with respect to “right-hand-side perturbations” of the data, hence are numerically attractive. The main purpose of the paper is to show how the … Read more
A primal-dual active set method for convex quadratic problems with bound constraints is presented. Based on a guess on the active set, a primal-dual pair $(x,s)$ is computed that satisfies the first order optimality condition and the complementarity condition. If $(x,s)$ is not feasible, a new active set is determined, and the process is iterated. … Read more