Trust-region methods without using derivatives: Worst case complexity and the non-smooth case

Trust-region methods are a broad class of methods for continuous optimization that found application in a variety of problems and contexts. In particular, they have been studied and applied for problems without using derivatives. The analysis of trust-region derivative-free methods has focused on global convergence, and they have been proved to generate a sequence of … Read more

A Semi-Infinite Programming Approach for Distributionally Robust Reward-Risk Ratio Optimization with Matrix Moments Constraints

Reward-risk ratio optimization is an important mathematical approach in finance. In this paper, we revisit the model by considering a situation where an investor does not have complete information on the distribution of the underlying uncertainty and consequently a robust action is taken against the risk arising from ambiguity of the true distribution. We propose … Read more

A trust-funnel method for nonlinear optimization problems with general nonlinear constraints and its application to derivative-free optimization

A trust-funnel method is proposed for solving nonlinear optimization problems with general nonlinear constraints. It extends the one presented by Gould and Toint (Math. Prog., 122(1):155-196, 2010), originally proposed for equality-constrained optimization problems only, to problems with both equality and inequality constraints and where simple bounds are also considered. As the original one, our method … Read more

Computing the Maximum Volume Inscribed Ellipsoid of a Polytopic Projection

We introduce a novel scheme based on a blending of Fourier-Motzkin elimination (FME) and adjustable robust optimization techniques to compute the maximum volume inscribed ellipsoid (MVE) in a polytopic projection. It is well-known that deriving an explicit description of a projected polytope is NP-hard. Our approach does not require an explicit description of the projection, … Read more

Object-Parallel Infrastructure for Implementing First-Order Methods, with an Example Application to LASSO

We describe the design of a C++ vector-manipulation substrate that allows first-order optimization algorithms to be expressed in a concise and readable manner, yet still achieve high performance in parallel computing environments. We use standard object-oriented techniques of encapsulation and operator overloading, combined with a novel “symbolic temporaries” delayed-evaluation system that greatly reduces the overhead … Read more

LP formulations for mixed-integer polynomial optimization problems

We present polynomial-time algorithms for constrained optimization problems overwhere the intersection graph of the constraint set has bounded tree-width. In the case of binary variables we obtain exact, polynomial-size linear programming formulations for the problem. In the mixed-integer case with bounded variables we obtain polynomial-size linear programming representations that attain guaranteed optimality and feasibility bounds. … Read more

Regularity of collections of sets and convergence of inexact alternating projections

We study the usage of regularity properties of collections of sets in convergence analysis of alternating projection methods for solving feasibility problems. Several equivalent characterizations of these properties are provided. Two settings of inexact alternating projections are considered and the corresponding convergence estimates are established and discussed. Article Download View Regularity of collections of sets … Read more

Quadratic Cone Cutting Surfaces for Quadratic Programs with On-Off Constraints

We study the convex hull of a set arising as a relaxation of difficult convex mixed integer quadratic programs (MIQP). We characterize the extreme points of our set and the extreme points of its continuous relaxation. We derive four quadratic cutting surfaces that improve the strength of the continuous relaxation. Each of the cutting surfaces … Read more

Robust Inventory Routing with Flexible Time Window Allocation

This paper studies a robust maritime inventory routing problem with time windows and stochastic travel times. One of the novelties of the problem is that the length and placement of the time windows are also decision variables. Such problems arise in the design and negotiation of long-term delivery contracts with customers who require on-time deliveries … Read more

New Semidefinite Programming Relaxations for the Linear Ordering and the Traveling Salesman Problem

In 2004 Newman suggested a semidefinite programming relaxation for the Linear Ordering Problem (LOP) that is related to the semidefinite program used in the Goemans-Williamson algorithm to approximate the Max Cut problem. Her model is based on the observation that linear orderings can be fully described by a series of cuts. Newman shows that her … Read more