Reducing the Number of Function Evaluations in Mesh Adaptive Direct Search Algorithms

The mesh adaptive direct search (MADS) class of algorithms is designed for nonsmooth optimization, where the objective function and constraints are typically computed by launching a time-consuming computer simulation. Each iteration of a MADS algorithm attempts to improve the current best-known solution by launching the simulation at a finite number of trial points. Common implementations … Read more

Nonsmooth cone-constrained optimization with applications to semi-infinite programming

The paper is devoted to the study of general nonsmooth problems of cone-constrained optimization (or conic programming) important for various aspects of optimization theory and applications. Based on advanced constructions and techniques of variational analysis and generalized differentiation, we derive new necessary optimality conditions (in both “exact” and “fuzzy” forms) for nonsmooth conic programs, establish … Read more

Level Bundle Methods for oracles with on-demand accuracy

For nonsmooth convex optimization, we consider level bundle methods built using an oracle that computes values for the objective function and a subgradient at any given feasible point. For the problems of interest, the exact oracle information is computable, but difficult to obtain. In order to save computational effort the oracle can provide estimations with … Read more

Subgradient methods for huge-scale optimization problems

We consider a new class of huge-scale problems, the problems with {\em sparse subgradients}. The most important functions of this type are piece-wise linear. For optimization problems with uniform sparsity of corresponding linear operators, we suggest a very efficient implementation of subgradient iterations, which total cost depends {\em logarithmically} in the dimension. This technique is … Read more

A First-Order Smoothing Technique for a Class of Large-Scale Linear Programs

We study a class of linear programming (LP) problems motivated by large-scale machine learning applications. After reformulating the LP as a convex nonsmooth problem, we apply Nesterov’s primal-dual smoothing technique. It turns out that the iteration complexity of the smoothing technique depends on a parameter $\th$ that arises because we need to bound the originally … Read more

Partial Smoothness,Tilt Stability, and Generalized Hessians

We compare two recent variational-analytic approaches to second-order conditions and sensitivity analysis for nonsmooth optimization. We describe a broad setting where computing the generalized Hessian of Mordukhovich is easy. In this setting, the idea of tilt stability introduced by Poliquin and Rockafellar is equivalent to a classical smooth second-order condition. Article Download View Partial Smoothness,Tilt … Read more

An Adaptive Gradient Sampling Algorithm for Nonsmooth Optimization

We present an algorithm for the minimization of f : Rn → R, assumed to be locally Lipschitz and continuously differentiable in an open dense subset D of Rn. The objective f may be non-smooth and/or non-convex. The method is based on the gradient sampling (GS) algorithm of Burke et al. [A robust gradient sampling … Read more

An Infeasible-Point Subgradient Method Using Adaptive Approximate Projections

We propose a new subgradient method for the minimization of convex functions over a convex set. Common subgradient algorithms require an exact projection onto the feasible region in every iteration, which can be efficient only for problems that admit a fast projection. In our method we use inexact adaptive projections requiring to move within a … Read more

Feasible and accurate algorithms for covering semidefinite programs

In this paper we describe an algorithm to approximately solve a class of semidefinite programs called covering semidefinite programs. This class includes many semidefinite programs that arise in the context of developing algorithms for important optimization problems such as sparsest cut, wireless multicasting, and pattern classification. We give algorithms for covering SDPs whose dependence on … Read more

A Sequential Quadratic Programming Algorithm for Nonconvex, Nonsmooth Constrained Optimization

We consider optimization problems with objective and constraint functions that may be nonconvex and nonsmooth. Problems of this type arise in important applications, many having solutions at points of nondifferentiability of the problem functions. We present a line search algorithm for situations when the objective and constraint functions are locally Lipschitz and continuously differentiable on … Read more