Robust regularization

Given a real function on a Euclidean space, we consider its “robust regularization”: the value of this new function at any given point is the maximum value of the original function in a fixed neighbourhood of the point in question. This construction allows us to impose constraints in an optimization problem *robustly*, safeguarding a constraint … Read more

A primal affine-scaling algorithm for constrained convex programs

The affine-scaling algorithm was initially developed for linear programming problems. Its extension to problems with a nonlinear objective performs at each iteration a scaling followed by a line search along the steepest descent direction. In this paper we prove that any accumulation point generated by this algorithm when applied to a convex function is an … Read more

The Trust Region Subproblem and Semidefinite Programming

The trust region subproblem (the minimization of a quadratic objective subject to one quadratic constraint and denoted TRS) has many applications in diverse areas, e.g. function minimization, sequential quadratic programming, regularization, ridge regression, and discrete optimization. In particular, it determines the step in trust region algorithms for function minimization. Trust region algorithms are popular for … Read more

Computation of Minimum Volume Covering Ellipsoids

We present a practical algorithm for computing the minimum volume n-dimensional ellipsoid that must contain m given points a_1, …, a_m \in R^n. This convex constrained problem arises in a variety of applied computational settings, particularly in data mining and robust statistics. Its structure makes it particularly amenable to solution by interior-point methods, and it … Read more

Minimizing nonconvex nonsmooth functions via cutting planes and proximity control

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

Analysis of a Path Following Method for Nonsmooth Convex Programs

Recently Gilbert, Gonzaga and Karas [2001] constructed examples of ill-behaved central paths for convex programs. In this paper we show that under mild conditions the central path has sufficient smoothness to allow construction of a path-following interior point algorithm for non-differentiable convex programs. We show that starting from a point near the center of the … Read more

On a class of nonsmooth composite functions

We discuss in this paper a class of nonsmooth functions which can be represented, in a neighborhood of a considered point, as a composition of a positively homogeneous convex function and a smooth mapping which maps the considered point into the null vector. We argue that this is a sufficiently rich class of functions and … Read more

On differentiability of symmetric matrix valued functions

With every real valued function, of a real argument, can be associated a matrix function mapping a linear space of symmetric matrices into itself. In this paper we study directional differentiability properties of such matrix functions associated with directionally differentiable real valued functions. In particular, we show that matrix valued functions inherit semismooth properties of … Read more

A new exact penalty function

For constrained smooth or nonsmooth optimization problems, new continuously differentiable penalty functions are derived. They are proved exact in the sense that under some nondegeneracy assumption, local optimizers of a nonlinear program are precisely the optimizers of the associated penalty function. This is achieved by augmenting the dimension of the program by a variable that … Read more

Limiting behavior of the central path in semidefinite optimization

It was recently shown that, unlike in linear optimization, the central path in semidefinite optimization (SDO) does not converge to the analytic center of the optimal set in general. In this paper we analyze the limiting behavior of the central path to explain this unexpected phenomenon. This is done by deriving a new necessary and … Read more