For a risk-averse multistage stochastic optimization problem with a finite scenario tree, we introduce a new scenario decomposition method and we prove its convergence. The method is applied to a risk-averse inventory and assembly problem. In addition, we develop a partially regularized bundle method for nonsmooth optimization. Citation RUTCOR, Rutgers University, Piscataway, NJ 08854 Article … Read more
We consider minimization of nonsmooth functions which can be represented as the composition of a positively homogeneous convex function and a smooth mapping. This is a sufficiently rich class that includes max-functions, largest eigenvalue functions, and norm-1 regularized functions. The bundle method uses an oracle that is able to compute separately the function and subgradient … Read more
Proximal bundle methods have been shown to be highly successful optimization methods for unconstrained convex problems with discontinuous first derivatives. This naturally leads to the question of whether proximal variants of bundle methods can be extended to a nonconvex setting. This work proposes an approach based on generating cutting-planes models, not of the objective function … Read more
In this paper a new algorithm to locally minimize nonsmooth, nonconvex functions is developed. We introduce the notion of secants and quasisecants for nonsmooth functions. The quasisecants are applied to find descent directions of locally Lipschitz functions. We design a minimization algorithm which uses quasisecants to find descent directions. We prove that this algorithm converges … Read more
For a real world problem — transporting pallets between warehouses in order to guarantee sufficient supply for known and additional stochastic demand — we propose a solution approach via convex relaxation of an integer programming formulation, suitable for online optimization. The essential new element linking routing and inventory management is a convex piecewise linear cost … Read more
We introduce a new approach to minimizing a function defined as the pointwise maximum over finitely many convex real functions (next referred to as the “component functions”), with the aim of working on the basis of “incomplete knowledge” of the objective function. In fact, a descent algorithm is proposed which does not necessarily require at … Read more
We propose a dynamic version of the bundle method to get approximate solutions to semidefinite programs with a nearly arbitrary number of linear inequalities. Our approach is based on Lagrangian duality, where the inequalities are dualized, and only a basic set of constraints is maintained explicitly. This leads to function evaluations requiring to solve a … Read more
Semidefinite Programming (SDP) has recently turned out to be a very powerful tool for approximating some NP-hard problems. The nature of the Quadratic Assignment Problem suggests SDP as a way to derive tractable relaxation. We recall some SDP relaxations of QAP and solve them approximately using the Bundle Method. The computational results demonstrate the efficiency … Read more
We introduce an algorithm to minimize a function of several variables with no convexity nor smoothness assumptions. The main peculiarity of our approach is the use of an the objective function model which is the difference of two piecewise affine convex functions. Bundling and trust region concepts are embedded into the algorithm. Convergence of the … Read more
We describe an extension of the classical cutting plane algorithm to tackle the unconstrained minimization of a nonconvex, not necessarily differentiable function of several variables. The method is based on the construction of both a lower and an upper polyhedral approximation to the objective function and it is related to the use of the concept … Read more