Search

We present an approach to regularize and approximate solution mappings of parametric convex optimization problems that combines interior penalty (log-barrier) solutions with Tikhonov regularization. Because the regularized mappings are single-valued and smooth under reasonable conditions, they can be used to build a computationally practical smoothing for the associated optimal value function. The value function in question, while resulting from parameterized convex problems, need not be convex. One motivating application of interest is two-stage (possibly nonconvex) stochastic programming. We show that our approach, being computationally implementable, provides locally bounded upper bounds for the subdifferential of the value function of qualified convex problems. As a by-product of our development, we also recover that in the given setting the value function is locally Lipschitz continuous. Numerical experiments are presented for two-stage convex stochastic programming problems, comparing the approach with the bundle method for nonsmooth optimization. [ABSTRACT FROM AUTHOR]

The V U -algorithm is a superlinearly convergent method for minimizing nonsmooth, convex functions. At each iteration, the algorithm works with a certain V -space and its orthogonal U -space, such that the nonsmoothness of the objective function is concentrated on its projection onto the V -space, and on the U -space the projection is smooth. This structure allows for an alternation between a Newton-like step where the function is smooth, and a proximal-point step that is used to find iterates with promising V U -decompositions. We establish a derivative-free variant of the V U -algorithm for convex finite-max objective functions. We show global convergence and provide numerical results from a proof-of-concept implementation, which demonstrates the feasibility and practical value of the approach. We also carry out some tests using nonconvex functions and discuss the results. [ABSTRACT FROM AUTHOR]

Joint chance constrained problems give rise to many algorithmic challenges. Even in the convex case, i.e., when an appropriate transformation of the probabilistic constraint is a convex function, its cutting-plane linearization is just an approximation, produced by an oracle providing subgradient and function values that can only be evaluated inexactly. As a result, the cutting-plane model may lie above the true constraint. For dealing with such upper inexact oracles, and still solving the problem up to certain precision, a special numerical algorithm must be put in place. We introduce a family of constrained bundle methods, based on the so-called improvement functions, that is shown to be convergent and encompasses many previous approaches as well as new algorithms. Depending on the oracle accuracy, we analyze to what extent the considered methods solve the joint chance constrained program. The approach is assessed on real-life energy problems, arising when dealing with stochastic hydroreservoir management. [ABSTRACT FROM AUTHOR]

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 information for the convex function, and the function and derivatives for the smooth mapping. With this information, it is possible to solve approximately certain proximal linearized subproblems in which the smooth mapping is replaced by its Taylor-series linearization around the current serious step. Our numerical results show the good performance of the Composite Bundle method for a large class of problems. [ABSTRACT FROM AUTHOR]

We consider the problem of minimizing nonsmooth convex functions, defined piecewise by a finite number of functions each of which is either convex quadratic or twice continuously differentiable with positive definite Hessian on the set of interest. This is a particular case of functions with primal-dual gradient structure, a notion closely related to the so-called VU space decomposition: At a given point, nonsmoothness is locally restricted to the directions of the subspace V, while along the subspace U the behavior of the function is twice differentiable. Constructive identification of the two subspaces is important, because it opens the way to devising fast algorithms for nonsmooth optimization (by following iteratively the manifold of smoothness on which superlinear U-Newton steps can be computed). In this work we show that, for the class of functions in consideration, the information needed for this identification can be obtained from the output of a standard bundle method for computing proximal points, provided a minimizer satisfies the nondegeneracy and strong transversality conditions. [ABSTRACT FROM AUTHOR]

The proximal point mapping is the basis of many optimization techniques for convex functions. By means of variational analysis, the concept of proximal mapping was recently extended to nonconvex functions that are prox-regular and prox-bounded. In such a setting, the proximal point mapping is locally Lipschitz continuous and its set of fixed points coincide with the critical points of the original function. This suggests that the many uses of proximal points, and their corresponding proximal envelopes (Moreau envelopes), will have a natural extension from convex optimization to nonconvex optimization. For example, the inexact proximal point methods for convex optimization might be redesigned to work for nonconvex functions. In order to begin the practical implementation of proximal points in a nonconvex setting, a first crucial step would be to design efficient methods of approximating nonconvex proximal points. This would provide a solid foundation on which future design and analysis for nonconvex proximal point methods could flourish. In this paper we present a methodology based on the computation of proximal points of piecewise affine models of the nonconvex function. These models can be built with only the knowledge obtained from a black box providing, for each point, the function value and one subgradient. Convergence of the method is proved for the class of nonconvex functions that are prox-bounded and lower- $${\mathcal{C}}^2$$ and encouraging preliminary numerical testing is reported. [ABSTRACT FROM AUTHOR]