Global Search Strategies for Solving Multilinear Least-squares Problems

The multilinear least-squares (MLLS) problem is an extension of the linear least-squares problem. The difference is that a multilinear operator is used in place of a matrix-vector product. The MLLS is typically a large-scale problem characterized by a large number of local minimizers. It originates, for instance, from the design of filter networks. We present … Read more

A Class of Dantzig-Wolfe Type Decomposition Methods for Variational Inequality Problems

We consider a class of decomposition methods for variational inequalities, which is related to the classical Dantzig–Wolfe decomposition of linear programs. Our approach is rather general, in that it can be used with set-valued or nonmonotone operators, as well as various kinds of approximations in the subproblems of the functions and derivatives in the single-valued … Read more

A LINEAR TIME ALGORITHM FOR THE KOOPMANS-BECKMANN QAP LINEARIZATION AND RELATED PROBLEMS

An instance of the quadratic assignment problem (QAP) with cost matrix Q is said to be linearizable if there exists an instance of the linear assignment problem (LAP) with cost matrix C such that for each assignment, the QAP and LAP objective function values are identical. The QAP linearization problem can be solved in O(n4) … Read more

Time-inconsistent multistage stochastic programs: martingale bounds

Abstract. It is well known that multistage programs, which maximize expectation or expected utility, allow a dynamic programming formulation, and that other objectives destroy the dynamic programming character of the problem. This paper considers a risk measure at the final stage of a multistage stochastic program. Although these problems are not time consistent, it is … Read more

On the Geometry of Acceptability Functionals

Abstract In this paper we discuss continuity properties of acceptability functionals or risk measures. The dependence of the random variable is investigated first. The main contribution and focus of this paper is to study how acceptability functionals vary whenever the underlying probability measure is perturbed. Abstract It turns out that the Wasserstein distance provides a … Read more

Joint Spectral Radius and Path-Complete Graph Lyapunov Functions

We introduce the framework of path-complete graph Lyapunov functions for approximation of the joint spectral radius. The approach is based on the analysis of the underlying switched system via inequalities imposed among multiple Lyapunov functions associated to a labeled directed graph. Inspired by concepts in automata theory and symbolic dynamics, we define a class of … Read more

Joint Spectral Radius and Path-Complete Graph Lyapunov Functions

We introduce the framework of path-complete graph Lyapunov functions for approximation of the joint spectral radius. The approach is based on the analysis of the underlying switched system via inequalities imposed among multiple Lyapunov functions associated to a labeled directed graph. Inspired by concepts in automata theory and symbolic dynamics, we define a class of … Read more

n-step Conic Mixed Integer Rounding Inequalities

We introduce the n-step conic MIR inequalities for the so-called polyhedral second-order conic (PSOC) mixed integer sets. PSOC sets arise in the polyhedral reformulation of the second-order conic mixed integer programs. Moreover, they are an equivalent representation for any mixed integer set defined by two linear constraints. The simple conic MIR inequalities of Atamtürk and … Read more

A Complete Characterization of the Gap between Convexity and SOS-Convexity

Our first contribution in this paper is to prove that three natural sum of squares (sos) based sufficient conditions for convexity of polynomials via the definition of convexity, its first order characterization, and its second order characterization are equivalent. These three equivalent algebraic conditions, henceforth referred to as sos-convexity, can be checked by semidefinite programming … Read more

Lifts of Convex Sets and Cone Factorizations

In this paper we address the basic geometric question of when a given convex set is the image under a linear map of an affine slice of a given closed convex cone. Such a representation or ‘lift’ of the convex set is especially useful if the cone admits an efficient algorithm for linear optimization over … Read more