A second derivative SQP method: local convergence

Gould and Robinson (NAR 08/18, Oxford University Computing Laboratory, 2008) gave global convergence results for a second-derivative SQP method for minimizing the exact $\ell_1$-merit function for a \emph{fixed} value of the penalty parameter. To establish this result, we used the properties of the so-called Cauchy step, which was itself computed from the so-called predictor step. … Read more

A Sequential Quadratic Programming Algorithm with an Additional Equality Constrained Phase

A sequential quadratic programming (SQP) method is presented that aims to overcome some of the drawbacks of contemporary SQP methods. It avoids the difficulties associated with indefinite quadratic programming subproblems by defining this subproblem to be always convex. The novel feature of the approach is the addition of an equality constrained phase that promotes fast … Read more

Optimizing a Polyhedral-Semidefinite Relaxation of Completely Positive Programs

It has recently been shown (Burer, 2006) that a large class of NP-hard nonconvex quadratic programs (NQPs) can be modeled as so-called completely positive programs (CPPs), i.e., the minimization of a linear function over the convex cone of completely positive matrices subject to linear constraints. Such convex programs are necessarily NP-hard. A basic tractable relaxation … Read more

Short Sales in Log-Robust Portfolio Management

This paper extends the Log-robust portfolio management approach to the case with short sales, i.e., the case where the manager can sell shares he does not yet own. We model the continuously compounded rates of return, which have been established in the literature as the true drivers of uncertainty, as uncertain parameters belonging to polyhedral … Read more

Optimal control of a parabolic equation with time-dependent state constraints

In this paper we study the optimal control problem of the heat equation by a distributed control over a subset of the domain, in the presence of a state constraint. The latter is integral over the space and has to be satisfied at each time. Using for the first time the technique of alternative optimality … Read more

Minimal Spanning Trees with Conflict Graphs

For the classical minimum spanning tree problem we introduce disjunctive constraints for pairs of edges which can not be both included in the spanning tree at the same time. These constraints are represented by a conflict graph whose vertices correspond to the edges of the original graph. Edges in the conflict graph connect conflicting edges … Read more

Effective formulation reductions for the quadratic assignment problem

In this paper we study two formulation reductions for the quadratic assignment problem (QAP). In particular we apply these reductions to the well known Adams and Johnson [2] integer linear programming formulation of the QAP, which we call formulation IPQAP-I. We analyze two cases: In the first case, we study the effect of constraint reduction. … Read more

THE EKELAND VARIATIONAL PRINCIPLE FOR HENIG PROPER MINIMIZERS AND SUPER MINIMIZERS

In this paper we consider, for the first time, approximate Henig proper minimizers and approximate super minimizers of a set-valued map F with values in a partially ordered vector space and formulate two versions of the Ekeland variational principle for these points involving coderivatives in the senses of Ioffe, Clarke and Mordukhovich. As applications we … Read more

Behavior of BFGS with an Exact Line Search on Nonsmooth Examples

We investigate the behavior of the BFGS algorithm with an exact line search on nonsmooth functions. We show that it may fail on a simple polyhedral example, but that it apparently always succeeds on the Euclidean norm function, spiraling into the origin with a Q-linear rate of convergence; we prove this in the case of … Read more

Nonsmooth Optimization via BFGS

We investigate the BFGS algorithm with an inexact line search when applied to nonsmooth functions, not necessarily convex. We define a suitable line search and show that it generates a sequence of nested intervals containing points satisfying the Armijo and weak Wolfe conditions, assuming only absolute continuity. We also prove that the line search terminates … Read more