1,720,989 research outputs found
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
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
A clustering heuristic to improve a derivative-free algorithm for nonsmooth optimization
Full text linkIn this paper we propose an heuristic to improve the performances of the recently
proposed derivative-free method for nonsmooth optimization CS-DFN. The heuristic
is based on a clustering-type technique to compute an estimate of Clarke’s generalized
gradient of the objective function, obtained via calculation of the (approximate)
directional derivative along a certain set of directions. A search direction
is then calculated by applying a nonsmooth Newton-type approach. As such, this
direction (as it is shown by the numerical experiments) is a good descent direction
for the objective function. We report some numerical results and comparison with
the original CS-DFN method to show the utility of the proposed improvement on a
set of well-known test problems
Lower and upper bounds for the spanning tree with minimum branch vertices
No full textWe study a variant of the spanning tree problem where we require that, for a given connected graph, the spanning tree to be found has the minimum number of branch vertices (that is vertices of the tree whose degree is greater than two). We provide four different formulations of the problem and compare different relaxations of them, namely Lagrangian relaxation, continuous relaxation, mixed integer-continuous relaxation. We approach the solution of the Lagrangian dual both by means of a standard subgradient method and an ad-hoc finite ascent algorithm based on updating one multiplier at the time. We provide numerical result comparison of all the considered relaxations on a wide set of benchmark instances. A useful follow-up of tackling the Lagrangian dual is the possibility of getting a feasible solution for the original problem with no extra costs. We evaluate the quality of the resulting upper bound by comparison either with the optimal solution, whenever available, or with the feasible solution provided by some existing heuristic algorithms
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
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
Forecasting Methods and Optimization Models for the Inventory Management of Perishable Products: The Case of “La Centrale del Latte di Vicenza SpA”
Full text linkThis paper is a report on a joint project by the Department of Management, Economics and Quantitative Methods of the University of Bergamo (in collaboration with the Department of Economics and Management of the University of Brescia) and the Italian company “La Centrale del Latte di Vicenza SpA” producing different types of milk, yogurt, vegetable drinks, cream, butter, cheese, eggs and vegetables. The aim of the project was to provide forecasting methods and optimization models, to improve the demand forecasts of perishable products and to better manage inventory levels in a Material Requirements Planning (MRP) setting
The forwarder planning problem in a two‐echelon network
No full textThis paper is motivated by the case of a forwarder dealing with inland transportation planning, from a seaport, of inbound containers filled with pallets having different destinations in the land-side. Although the forwarder is not the owner nor controls any vehicle, he is required to plan both the assignment of containers to intermediate depots, where the pallets are unpacked, and the assignment of pallets to the vehicles used for the distribution from depots to consignees. We present a mathematical model supporting the forwarder in this two-echelon network to minimize assignment costs, while accounting for a balanced workload among all carriers involved in this distribution scheme. We discuss a tailor-made implementation of the model in a realistic context and present a heuristic method to solve realistic-sized instances. Our computational experiments confirm the viability of this method
OMEGA one multi ethnic genetic approach
No full textThe genetic algorithm (GA) is a quite efficient paradigm to solve several optimization problems. It is substantially a search technique that uses an ever-changing neighborhood structure related to a population which evolves according to a number of genetic operators. In the GA framework many techniques have been devised to escape from a local optimum when the algorithm fails in locating the global one. To this aim we present a variant of the GA which we call OMEGA (One Multi Ethnic Genetic Approach). The main difference is that, starting from an initial population, k different sub-populations are produced at each iteration and they independently evolve in k different environments. The resulting sub–populations are then recombined and the process is iterated. Our basic algorithmic scheme is tested on a recent and well-studied variant of the classic problem of the minimum spanning tree: the Minimum Labeling Spanning Tree problem. We compare our algorithm with several approaches drawn from the literature. The results are encouraging in view of future application of OMEGA to other classes of problems
- …
