The Freight Train Routing Problem

We consider the following freight train routing problem (FTRP). Given is a transportation network with fixed routes for passenger trains and a set of freight trains (requests), each defined by an origin and destination station pair. The objective is to calculate a feasible route for each freight train such that a sum of all expected … Read more

Fabrication-Adaptive Optimization, with an Application to Photonic Crystal Design

It is often the case that the computed optimal solution of an optimization problem cannot be implemented directly, irrespective of data accuracy, due to either (i) technological limitations (such as physical tolerances of machines or processes), (ii) the deliberate simplification of a model to keep it tractable (by ignoring certain types of constraints that pose … Read more

A scenario decomposition algorithm for 0-1 stochastic programs

We propose a scenario decomposition algorithm for stochastic 0-1 programs. The algorithm recovers an optimal solution by iteratively exploring and cutting-off candidate solutions obtained from solving scenario subproblems. The scheme is applicable to quite general problem structures and can be implemented in a distributed framework. Illustrative computational results on standard two-stage stochastic integer programming and … Read more

Exploiting total unimodularity for classes of random network problems

Network analysis is of great interest for the study of social, biological and technological networks, with applications, among others, in business, marketing, epidemiology and telecommunications. Researchers are often interested in assessing whether an observed feature in some particular network is expected to be found within families of networks under some hypothesis (named conditional random networks, … Read more

On Lower Complexity Bounds for Large-Scale Smooth Convex Optimization

In this note we present tight lower bounds on the information-based complexity of large-scale smooth convex minimization problems. We demonstrate, in particular, that the k-step Conditional Gradient (a.k.a. Frank-Wolfe) algorithm as applied to minimizing smooth convex functions over the n-dimensional box with n ≥ k is optimal, up to an O(ln n)-factor, in terms of … Read more

Theoretical aspects of adopting exact penalty elements within sequential methods for nonlinear programming

In the context of sequential methods for solving general nonlinear programming problems, it is usual to work with augmented subproblems instead of the original ones, tackled by the $\ell_1$-penalty function together with the shortcut usage of a convenient penalty parameter. This paper addresses the theoretical reasoning behind handling the original subproblems by such an augmentation … Read more

Multiperiod Portfolio Optimization with General Transaction Costs

We analyze the properties of the optimal portfolio policy for a multiperiod mean-variance investor facing multiple risky assets in the presence of general transaction costs such as proportional, market impact, and quadratic transaction costs. For proportional transaction costs, we find that a buy-and-hold policy is optimal: if the starting portfolio is outside a parallelogram-shaped no-trade … Read more

RSP-Based Analysis for Sparsest and Least $\ell_1hBcNorm Solutions to Underdetermined Linear Systems

Recently, the worse-case analysis, probabilistic analysis and empirical justification have been employed to address the fundamental question: When does $\ell_1$-minimization find the sparsest solution to an underdetermined linear system? In this paper, a deterministic analysis, rooted in the classic linear programming theory, is carried out to further address this question. We first identify a necessary … Read more

Second-order Characterizations of Tilt Stability with Applications to Nonlinear Programming

The paper is devoted to the study of tilt-stable local minimizers of general optimization problems in finite-dimensional spaces and its applications to classical nonlinear programs with twice continuously differentiable data. The importance of tilt stability has been well recognized from both theoretical and numerical aspects of optimization, and this notion has been extensively studied in … Read more

Convex relaxation for finding planted influential nodes in a social network

We consider the problem of maximizing influence in a social network. We focus on the case that the social network is a directed bipartite graph whose arcs join senders to receivers. We consider both the case of deterministic networks and probabilistic graphical models, that is, the so-called “cascade” model. The problem is to find the … Read more