105 research outputs found
On the convergence of the block nonlinear Gauss-Seidel method under convex constraints
No full textWe give new convergence results for the block Gauss–Seidel method for problems where the feasible set is the Cartesian product of m closed convex sets, under the assumption that the sequence generated by the method has limit points. We show that the method is globally convergent for m=2 and that for m>2 convergence can be established both when the objective function f is componentwise strictly quasiconvex with respect to m−2 components and when f is pseudoconvex. Finally, we consider a proximal point modification of the method and we state convergence results without any convexity assumption on the objective functio
Feature selection combining linear support vector machines and concave optimization
No full textIn this work we consider feature selection for two-class linear models, a challenging task arising in several real-world applications. Given an unknown functional dependency that assigns a given input to the class to which it belongs, and that can be modelled by a linear machine, we aim to find the relevant features of the input space, namely we aim to detect the smallest number of input variables while granting no loss in classification accuracy. Our main motivation lies in the fact that the detection of the relevant features provides a better understanding of the underlying phenomenon, and this can be of great interest in important fields such as medicine and biology. Feature selection involves two competing objectives: the prediction capability (to be maximized) of the linear classifier and the number of features (to be minimized) employed by the classifier. In order to take into account both the objectives, we propose a feature selection strategy based on the combination of support vector machines (for obtaining good classifiers) with a concave optimization approach (for finding sparse solutions). We report results of an extensive computational experience showing the efficiency of the proposed methodology
On the convergence of a modified version of SVMlight algorithm
No full textIn this work, we consider the convex quadratic programming problem arising in support vector machine (SVM), which is a technique designed to solve a variety of learning and pattern recognition problems. Since the Hessian matrix is dense and real applications lead to large-scale problems, several decomposition methods have been proposed, which split the original problem into a sequence of smaller subproblems. SVMlight algorithm is a commonly used decomposition method for SVM, and its convergence has been proved only recently under a suitable block-wise convexity assumption on the objective function. In SVMlight algorithm, the size q of the working set, i.e. the dimension of the subproblem, can be any even number. In the present paper, we propose a decomposition method on the basis of a proximal point modification of the subproblem and the basis of a working set selection rule that includes, as a particular case, the one used by the SVMlight algorithm. We establish the asymptotic convergence of the method, for any size q greater than or equal to 2 of the working set, and without requiring any further block-wise convexity assumption on the objective function. Furthermore, we show that the algorithm satisfies in a finite number of iterations a stopping criterion based on the violation of the optimality conditions
Nonlinear optimization and support vector machines
No full textSupport Vector Machine (SVM) is one of the most important class of
machine learning models and algorithms, and has been successfully applied in various
fields. Nonlinear optimization plays a crucial role in SVM methodology, both in defining
the machine learning models and in designing convergent and efficient algorithms
for large-scale training problems. In this paper we present the convex programming
problems underlying SVM focusing on supervised binary classification. We analyze
the most important and used optimization methods for SVM training problems, and
we discuss how the properties of these problems can be incorporated in designing
useful algorithms
Global convergence technique for the Newton method with periodic Hessian evaluation.
No full textThe problem of globalizing the Newton method when the actual Hessian matrix is not used at every iteration is considered. A stabilization technique is studied that employs a new line search strategy for ensuring the global convergence under mild assumptions. Moreover, an implementable algorithmic scheme is proposed, where the evaluation of the second derivatives is conditioned to the behavior of the algorithm during the minimization process and the local convexity properties of the objective function. This is done in order to obtain a significant computational saving, while keeping acceptable the unavoidable degradation in convergence speed. The numerical results reported indicate that the method described may be employed advantageously in all applications where the computation of the Hessian matrix is highly time consuming
Nonmonotone globalization of the finite-difference Newton-GMRES method for nonlinear equations
No full textIn this paper, we study nonmonotone globalization strategies, in connection with the finite-difference inexact Newton-GMRES method for nonlinear equations. We first define a globalization algorithm that combines nonmonotone watchdog rules and nonmonotone derivative-free linesearches related to a merit function, and prove its global convergence under the assumption that the Jacobian is nonsingular and that the iterations of the GMRES subspace method can be completed at each step. Then we introduce a hybrid stabilization scheme employing occasional line searches along positive bases, and establish global convergence towards a solution of the system, under the less demanding condition that the Jacobian is nonsingular at stationary points of the merit function. Through a set of numerical examples, we show that the proposed techniques may constitute useful options to be added in solvers for nonlinear systems of equations. © 2010 Taylor & Francis
A computational study of path-based methods for optimal traffic assignment with both inelastic and elastic demand
No full textIn this work we consider traffic assignment problems with both inelastic and elastic demand. As well-known, the elastic demand problem can be reformulated as a fixed demand problem by a suitable modification of the network representation. Then, the general network equilibrium problem we consider is a constrained convex minimization problem whose variables are the path flows. We define a framework where different path-based methods can be embedded. The framework is a Gauss–Seidel decomposition method, where the subproblems are inexactly solved by a line search along a feasible and descent direction. The key features of the framework are the definition of an initial stepsize based on second order information and the use of an adaptive column generation strategy recently proposed in the literature. The extensive computational experiments, performed even on huge networks, show that path-based methods, suitably designed and implemented, may be an efficient tool for network equilibrium problems. In particular, in the solution of problems with elastic demand, a presented path equilibration algorithm obtained (in all the networks) levels of accuracy never reached (to our knowledge), say a relative gap of the order of 10−14. Therefore, this latter algorithm may represent the state-of-art for traffic assignment problems with elastic demand
On the Global Convergence of Derivative Free Methods for Unconstrained Optimization
No full textIn this paper, starting from the study of the common elements that some globally
convergent direct search methods share, a general convergence theory is established for unconstrained
minimization methods employing only function values. The introduced convergence conditions are
useful for developing and analyzing new derivative-free algorithms with guaranteed global convergence.
As examples, we describe three new algorithms which combine pattern and line search approaches
Globally convergent block-coordinate techniques for unconstrained optimization
No full textIn this paper we define new classes of globally convergent block-coordinate techniques for the unconstrained minimization of a continuously differentiable function. More specifically, we first describe conceptual models of decomposition algorithms based on the interconnection of elementary operations performed on the block components of the variable vector. Then we characterize the elementary operations defined through a suitable line search or the global minimization in a component subspace. Using these models, we establish new results on the convergence of the nonlinear Gauss–Seidel method and we prove that this method with a two-block decomposition is globally convergent towards stationary points, even in the absence of convexity or uniqueness assumptions. In the general case of nonconvex objective function and arbitrary decomposition we define new globally convergent line-search-based schemes that may also include partial global inimizations with respect to some component. Computational aspects are discussed and, in particular, an application to a learning problem in a Radial Basis Function neural network is illustrated
Nonmonotone globalization techniques for the Barzilai-Borwein gradient method
No full textIn this paper we propose new globalization strategies for the Barzilai and Borwein gradient method, based on suitable relaxations of the monotonicity requirements. In particular, we define a class of algorithms that combine nonmonotone watchdog techniques with nonmonotone linesearch rules and we prove the global convergence of these schemes. Then we perform an extensive computational study, which shows the effectiveness of the proposed approach in the solution of large dimensional unconstrained optimization problems
- …
