1,720,990 research outputs found
Nonsmooth optimization: Theory and algorithms
No full textThis is a summary of the author's PhD thesis supervised by Manlio Gaudioso and Maria Flavia Monaco and defended on 21 February 2008 at the Università della Calabria. The thesis is a survey on nonsmooth optimization methods for both convex and nonconvex functions. The main contribution of the dissertation is the presentation of a new bundle type method. The thesis is written in English and is available from http://www2.deis.unical.it/logilab/gorgone. © 2009 Springer-Verlag
Gradient set splitting in nonconvex nonsmooth numerical optimization
No full textWe present a numerical bundle-type method for local minimization of a real function of several variables, which is supposed to be locally Lipschitz. We provide a short survey of some optimization algorithms from the literature, which are able to deal with both nonsmoothness and nonconvexity of the objective function. We focus on possible extensions of classical bundle-type methods, originally conceived to deal with convex nonsmooth optimization. They are all based on a convex cutting plane model which has the property of both minorizing everywhere and interpolating at certain points the objective function. Such properties may be lost whenever nonconvexity is present and the case may be described in terms of possible negative values of certain linearization errors. We describe some alternative ways the problem is dealt with in the literature. Here, on the basis of a classification of the limit points of gradient sequences, we define two distinct cutting plane approximations. We derive an algorithm which uses both such models. In particular, only the convex model is primarily adopted to find a tentative displacement from the current stability centre, while the concave one enters into the play only when the convex model has failed in providing a sufficient decrease step. Termination of the method is proved and the results of some numerical experiments are reported
Separation of convex sets by Clarke subdifferential
No full textIn this article we consider a separation technique proposed in J. Grzybowski, D. Pallaschke, and R. Urbanski (A pre-classification and the separation law for closed bounded convex sets, Optim. Method Softw. 20(2005), pp. 219-229) for separating two convex sets A and B with another convex set C. We prove that in a finite dimension C can be chosen as the Clarke subdifferential at the origin of minfpA,pBg, where pA, pB denotes the support functions of A and B respectively. © 2010 Taylor & Francis
Non-smoothness in classification problems
No full textWe review the role played by non-smooth optimization techniques in many recent applications in classification area. Starting from the classical concept of linear separability in binary classification, we recall the more general concepts of polyhedral, ellipsoidal and max-min separability. Finally we focus our attention on the support vector machine (SVM) approach and on the more recent transductive SVM technique
A Library for Continuous Convex Separable Quadratic Knapsack Problems
Full text linkThe Continuous Convex Separable Quadratic Knapsack problem (CQKnP) is an easy but useful model that has very many different applications. Although the problem can be solved quickly, it must typically be solved very many times within approaches to (much) more difficult models; hence an
efficient solution approach is required. We present and discuss a small open-source library for its solution that we have recently developed and
distributed
Piecewise linear approximations in nonconvex nonsmooth optimization
No full textWe present a bundle type method for minimizing nonconvex nondifferentiable functions of several variables. The algorithm is based on the construction of both a lower and an upper polyhedral approximation of the objective function. In particular, at each iteration, a search direction is computed by solving a quadratic program aiming at maximizing the difference between the lower and the upper model. A proximal approach is used to guarantee convergence to a stationary point under the hypothesis of weak semismoothness. © 2009 Springer-Verlag
Difference of Convex programming in adversarial SVM
Full text linkWe present two models in adversarial machine learning, focussing on the Support Vector Machine framework. In particular, we consider both an evasion and a poisoning problem. The first model is aimed at constructing effective sparse perturbation of the dataset samples, while the objective of the second is to induce a substantial rotation of the hyperplane defining the classifier. The two models are formulated as Difference of Convex nonsmooth optimization problems. Numerical results on both synthetic and real life datasets are reported
Generalized Bundle Methods for Sum-Functions with "Easy" Components: Applications to Multicommodity Network Design
No full textWe propose a version of the bundle scheme for convex nondifferentiable optimization suitable for the case of a sum-function where some of the components are "easy", that is, they are Lagrangian functions of explicitly known compact convex programs. This corresponds to a stabilized partial Dantzig-Wolfe decomposition, where suitably modified representations of the "easy" convex subproblems are inserted in the master problem as an alternative to iteratively inner-approximating them by extreme points, thus providing the algorithm with exact information about a part of the dual objective function. The resulting master problems are potentially larger and less well-structured than the standard ones, ruling out the available specialized techniques and requiring the use of general-purpose solvers for their solution; this strongly favors piecewise-linear stabilizing terms, as opposed to the more usual quadratic ones, which in turn may have an adverse effect on the convergence speed of the algorithm, so that the overall performance may depend on appropriate tuning of all these aspects. Yet, very good computational results are obtained in at least one relevant application: the computation of tight lower bounds for Fixed-Charge Multicommodity Min-Cost Flow problems
A method for convex minimization based on translated first-order approximations
No full textWe describe an algorithm for minimizing convex, not necessarily smooth, functions of several variables, based on a descent direction finding procedure that inherits some characteristics both of standard bundle method and of Wolfe’s conjugate subgradient method. This is obtained by allowing appropriate upward shifting of the affine approximations of the objective function which contribute to the classic definition of the cutting plane function. The algorithm embeds a proximity control strategy. Finite termination is proved at a point satisfying an approximate optimality condition and some numerical results are provided
- …
