Random order coalition structure values

Recently, attention has been focused on generalizations of the Shapley value obtained by relaxing the symmetry postulate. Shapley defined the class of weighted values and these have been characterized by Kalai and Samet. Random order values, treated by Weber, provide the most general approach to values without symmetry. This paper extends the random order idea to games with coalition structures. The symmetric CS value was defined by Owen; axiomatic characterizations have been given by Owen and Hart and Kurz. Levy and McLean extended their work and analyzed various classes of weighted CS values. The random order CS values of this paper include all the CS values described above as special cases.     

Risk-adjusted probability measures in portfolio optimization with coherent measures of risk

We consider the problem of optimizing a portfolio of n assets, whose returns are described by a joint discrete distribution. We formulate the mean–risk model, using as risk functionals the semideviation, deviation from quantile, and spectral risk measures. Using the modern theory of measures of risk, we derive an equivalent representation of the portfolio problem as a zero-sum matrix game, and we provide ways to solve it by convex optimization techniques. In this way, we reconstruct new probability measures which constitute part of the saddle point of the game. These risk-adjusted measures always exist, irrespective of the completeness of the market. We provide an illustrative example, in which we derive these measures in a universe of 200 assets and we use them to evaluate the market portfolio and optimal risk-averse portfolios.     

Approximate methods for convex minimization problems with series–parallel structure

Consider a problem of minimizing a separable, strictly convex, monotone and differentiable function on a convex polyhedron generated by a system of m linear inequalities. The problem has a series–parallel structure, with the variables divided serially into n disjoint subsets, whose elements are considered in parallel. This special structure is exploited in two algorithms proposed here for the approximate solution of the problem. The first algorithm solves at most min{m, ν − n + 1} subproblems; each subproblem has exactly one equality constraint and at most n variables. The second algorithm solves a dynamically generated sequence of subproblems; each subproblem has at most ν − n + 1 equality constraints, where ν is the total number of variables. To solve these subproblems both algorithms use the authors’ Projected Newton Bracketing method for linearly constrained convex minimization, in conjunction with the steepest descent method. We report the results of numerical experiments for both algorithms.     

A family of projective splitting methods for the sum of two maximal monotone operators

A splitting method for two monotone operators A and B is an algorithm that attempts to converge to a zero of the sum A + B by solving a sequence of subproblems, each of which involves only the operator A, or only the operator B. Prior algorithms of this type can all in essence be categorized into three main classes, the Douglas/Peaceman-Rachford class, the forward-backward class, and the little-used double-backward class. Through a certain “extended” solution set in a product space, we construct a fundamentally new class of splitting methods for pairs of general maximal monotone operators in Hilbert space. Our algorithms are essentially standard projection methods, using splitting decomposition to construct separators. We prove convergence through Fejér monotonicity techniques, but showing Fejér convergence of a different sequence to a different set than in earlier splitting methods. Our projective algorithms converge under more general conditions than prior splitting methods, allowing the proximal parameter to vary from iteration to iteration, and even from operator to operator, while retaining convergence for essentially arbitrary pairs of operators. The new projective splitting class also contains noteworthy preexisting methods either as conventional special cases or excluded boundary cases. Dedicated to Clovis Gonzaga on the occassion of his 60th birthday.     

An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation

Given a finite set V, and a hypergraph H⊆2^V, the hypergraph transversal problem calls for enumerating all minimal hitting sets (transversals) for H. This problem plays an important role in practical applications as many other problems were shown to be polynomially equivalent to it. Fredman and Khachiyan [On the complexity of dualization of monotone disjunctive normal forms, J. Algorithms 21 (1996) 618-628] gave an incremental quasi-polynomial-time algorithm for solving the hypergraph transversal problem. In this paper, we present an efficient implementation of this algorithm. While we show that our implementation achieves the same theoretical worst-case bound, practical experience with this implementation shows that it can be substantially faster. We also show that a slight modification of the original algorithm can be used to obtain a stronger bound on the running time.More generally, we consider a monotone property π over a bounded n-dimensional integral box. As an important application of the above hypergraph transversal problem, pioneered by Bioch and Ibaraki [Complexity of identification and dualization of positive Boolean functions, Inform. and Comput. 123 (1995) 50-63], we consider the problem of incrementally generating simultaneously all minimal subsets satisfying π and all maximal subsets not satisfying π, for properties given by a polynomial-time satisfiability oracle. Problems of this type arise in many practical applications. It is known that the above joint generation problem can be solved in incremental quasi-polynomial time via a polynomial-time reduction to a generalization of the hypergraph transversal problem on integer boxes. In this paper we present an efficient implementation of this procedure, and present experimental results to evaluate our implementation for a number of interesting monotone properties π.     

MARM Processes Part I: General Theory

This paper introduces a new class of real vector-valued stochastic processes, called MARM (Multivariate Autoregressive Modular) processes, which generalizes the class of (univariate) ARM (Autoregressive Modular) processes. Like ARM processes, the key advantage of MARM processes is their ability to fit a strong statistical signature consisting of first-order and second-order statistics. More precisely, MARM processes exactly fit an arbitrary multi-dimensional marginal distribution and approximately fit a set of leading autocorrelations and cross-correlations. This capability appears to render the MARM modeling methodology unique in its ability to fit a multivariate model to such a class of strong statistical signatures. The paper describes the construction of two flavors of MARM processes, MARM ⁺ and MARM ^? , studies the statistics of MARM processes (transition structure and second order statistics), and devises MARM-based fitting and forecasting algorithms providing point estimators and confidence intervals. The efficacy of the MARM fitting and forecasting methodology will be illustrated on real-life data in a companion paper.     

Risk measurement and risk-averse control of partially observable discrete-time Markov systems

We consider risk measurement in controlled partially observable Markov processes in discrete time. We introduce a new concept of conditional stochastic time consistency and we derive the structure of risk measures enjoying this property. We prove that they can be represented by a collection of static law invariant risk measures on the space of function of the observable part of the state. We also derive the corresponding dynamic programming equations. Finally we illustrate the results on a machine deterioration problem.     

Comments on a Simplified Form of Block-Iterative Operator Splitting,and an Asynchronous Algorithm Resembling the Multi-block Alternating Direction Method of Multipliers

This note gives an improved version of the proof of Proposition 4.2 in “A Simplified Form of Block-Iterative Operator Splitting, and an Asynchronous Algorithm Resembling the Multi-block Alternating Direction Method of Multipliers,” Journal of Optimization Theory and Applications 173(1): 155–182 (2017).