In this paper we obtain Sobolev estimates for weak solutions of first oder variational Mean Field Game systems with coupling terms that are local function of the density variable. Under some coercivity condition on the coupling, we obtain first order Sobolev estimates for the density variable, while under similar coercivity condition on the Hamiltonian we obtain second order Sobolev estimates for the value function. These results are valid both for stationary and time-dependent problems. In the latter case the estimates are fully global in time, thus we resolve a question which was left open in [PS17]. Our methods apply to a large class of Hamiltonians and coupling functions.

Aug 22 2017

math.OC arXiv:1708.06187v1

We show that the sparse polynomial interpolation problem reduces to a discrete super-resolution problem on the n-dimensional torus. Therefore the semidefinite programming approach initiated by Candès \& Fernandez-Granda [7] in the univariate case (and later extended to the multi-variate setting) can be applied. In particular, exact recovery is guaranteed provided that a geometric spacing condition on the " supports " holds and the number of evaluations are sufficiently many (but not many). It also turns out that the (compressed sensing) LP-formulation of \ell 1-norm minimization is also guaranteed to provide exact recovery provided that the evaluations are made in a certain manner and even though the Restricted Isometry Property for exact recovery is not satisfied. (A naive compressed sensing LP-approach does not offer such a guarantee.) Finally we also describe the algebraic Prony method for sparse interpolation, which also recovers the exact decomposition but from less point evaluations and with no geometric spacing condition. We provide two sets of numerical experiments, one in which the super-resolution technique and Prony's method seem to cope equally well with noise, and another in which the super-resolution technique seems to cope with noise better than Prony's method, at the cost of an extra computational burden (i.e. a semidefinite optimization).

Aug 22 2017

math.OC arXiv:1708.06175v1

In this paper, we study approximate and exact controllability of the linear difference equation $x(t) = \sum\_{j=1}^N A\_j x(t - \Lambda\_j) + B u(t)$ in $L^2$, with $x(t) \in \mathbb C^d$ and $u(t) \in \mathbb C^m$, using as a basic tool a representation formula for its solution in terms of the initial condition, the control $u$, and some suitable matrix coefficients. When $\Lambda\_1, \dotsc, \Lambda\_N$ are commensurable, approximate and exact controllability are equivalent and can be characterized by a Kalman criterion. This paper focuses on providing characterizations of approximate and exact controllability without the commensurability assumption. In the case of two-dimensional systems with two delays, we obtain an explicit characterization of approximate and exact controllability in terms of the parameters of the problem. In the general setting, we prove that approximate controllability from zero to constant states is equivalent to approximate controllability in $L^2$. The corresponding result for exact controllability is true at least for two-dimensional systems with two delays.

Aug 22 2017

math.OC arXiv:1708.06166v1

Recently, penalties promoting signals that are sparse within and across groups have been proposed. In this letter, we propose a generalization that allows to encode more intricate dependencies within groups. However, this complicates the realization of the threshold function associated with the penalty, which hinders the use of the penalty in energy minimization. We discuss how to sidestep this problem, and demonstrate the use of the modified penalty in an energy minimization formulation for an inverse problem.

Aug 22 2017

math.OC arXiv:1708.06165v1

This work is concerned with the determination of the diffusion coefficient from distributed data of the state. This long standing problem is related to homogenization theory on the one hand, and to regularization theory on the other hand. Here, a novel approach is proposed which involves total variation regularization combined with a suitably chosen cost functional that promotes the diffusion coefficient assuming preassigned values at each point of the domain. The main difficulty lies in the delicate functional-analytic structure of the resulting nondifferentiable optimization problem with pointwise constraints for functions of bounded variation, which makes the derivation of useful pointwise optimality conditions challenging. To cope with this difficulty, a novel reparametrization technique is introduced. Numerical examples using a regularized semismooth Newton method illustrate the structure of the obtained diffusion coefficient.

The memory-type control charts, such as EWMA and CUSUM, are powerful tools for detecting small quality changes in univariate and multivariate processes. Many papers on economic design of these control charts use the formula proposed by Lorenzen and Vance (1986) [Lorenzen, T. J., & Vance, L. C. (1986). The economic design of control charts: A unified approach. Technometrics, 28(1), 3-10, DOI: 10.2307/1269598]. This paper shows that this formula is not correct for memory-type control charts and its values can significantly deviate from the original values even if the ARL values used in this formula are accurately computed. Consequently, the use of this formula can result in charts that are not economically optimal. The formula is corrected for memory-type control charts, but unfortunately the modified formula is not a helpful tool from a computational perspective. We show that simulation-based optimization is a possible alternative method.

Aug 22 2017

math.OC arXiv:1708.06055v1

Motivated by $\ell_p$-optimization arising from sparse optimization, high dimensional data analytics and statistics, this paper studies sparse properties of a wide range of $p$-norm based optimization problems with $p > 1$, including generalized basis pursuit, basis pursuit denoising, ridge regression, and elastic net. It is well known that when $p > 1$, these optimization problems lead to less sparse solutions. However, the quantitative characterization of the adverse sparse properties is not available. In this paper, by exploiting optimization and matrix analysis techniques, we give a systematic treatment of a broad class of $p$-norm based optimization problems for a general $p > 1$ and show that optimal solutions to these problems attain full support, and thus have the least sparsity, for almost all measurement matrices and measurement vectors. Comparison to $\ell_p$-optimization with $0 < p \le 1$ and implications to robustness are also given. These results shed light on analysis and computation of general $p$-norm based optimization problems in various applications.

Aug 22 2017

math.OC arXiv:1708.06035v1

In this paper we explore the impact of quantiles on optimal strategies under state dynamics driven by both individual noise, common noise and Poisson jumps. We first establish an optimality system satisfied the quantile process under jump terms. We then turn to investigate a new class of finite horizon mean-field games with common noise in which the payoff functional and the state dynamics are dependent not only on the state-action pair but also on conditional quantiles. Based on the best-response of the decision-makers, it is shown that the equilibrium conditional quantile process satisfies a stochastic partial differential equation in the non-degenerate case. A closed-form expression of the quantile process is provided in a basic Ornstein-Uhlenbeck process with common noise.

We consider a wide range of regularized stochastic minimization problems with two regularization terms, one of which is composed with a linear function. This optimization model abstracts a number of important applications in artificial intelligence and machine learning, such as fused Lasso, fused logistic regression, and a class of graph-guided regularized minimization. The computational challenges of this model are in two folds. On one hand, the closed-form solution of the proximal mapping associated with the composed regularization term or the expected objective function is not available. On the other hand, the calculation of the full gradient of the expectation in the objective is very expensive when the number of input data samples is considerably large. To address these issues, we propose a stochastic variant of extra-gradient type methods, namely \textsfStochastic Primal-Dual Proximal ExtraGradient descent (SPDPEG), and analyze its convergence property for both convex and strongly convex objectives. For general convex objectives, the uniformly average iterates generated by \textsfSPDPEG converge in expectation with $O(1/\sqrt{t})$ rate. While for strongly convex objectives, the uniformly and non-uniformly average iterates generated by \textsfSPDPEG converge with $O(\log(t)/t)$ and $O(1/t)$ rates, respectively. The order of the rate of the proposed algorithm is known to match the best convergence rate for first-order stochastic algorithms. Experiments on fused logistic regression and graph-guided regularized logistic regression problems show that the proposed algorithm performs very efficiently and consistently outperforms other competing algorithms.

We introduce a new class of \textitBackward Stochastic Differential Equations with weak reflections whose solution $(Y,Z)$ satisfies the weak constraint $\textbf{E}[\Psi(\theta,Y_\theta)] \geq m,$ for all stopping time $\theta$ taking values between $0$ and a terminal time $T$, where $\Psi$ is a random non-decreasing map and $m$ a given threshold. We study the wellposedness of such equations and show that the family of minimal time $t$-values $Y_t$ can be aggregated by a right-continuous process. We give a nonlinear Mertens type decomposition for lower reflected $g$-submartingales, which to the best of our knowledge, represents a new result in the literature. Using this decomposition, we obtain a representation of the minimal time $t$-values process. We also show that the minimal supersolution of a such equation can be written as a \textitstochastic control/optimal stopping game, which is shown to admit, under appropriate assumptions, a value and saddle points. From a financial point of view, this problem is related to the approximative hedging for American options.

Aug 22 2017

math.OC arXiv:1708.05920v1

We consider the problem of scheduling appointments for a finite customer population to a service facility with customer no-shows, to minimize the sum of customer waiting time and server overtime costs. Since appointments need to be scheduled ahead of time we refer to this problem as an optimization problem rather than a dynamic control one. We study this optimization problem in fluid and diffusion scales and identify asymptotically optimal schedules in both scales. In fluid scale, we show that it is optimal to schedule appointments so that the system is in critical load; thus heavy-traffic conditions are obtained as a result of optimization rather than as an assumption. In diffusion scale, we solve this optimization problem in the large horizon limit. Our explicit stationary solution of the corresponding Brownian Optimization Problem translates the customer-delay versus server-overtime tradeoff to a tradeoff between the state of a reflected Brownian motion in the half-line and its local time at zero. Motivated by work on competitive ratios, we also consider a reference model in which an oracle provides the decision maker with the complete randomness information. The difference between the values of the scheduling problem for the two models, to which we refer as the stochasticity gap (SG), quantifies the degree to which it is harder to design a schedule under uncertainty than when the stochastic primitives (i.e., the no-shows and service times) are known in advance. In the fluid scale, the SG converges to zero, but in the diffusion scale it converges to a positive constant that we compute.

The entropic value-at-risk (EVaR) is a new coherent risk measure, which is an upper bound for both the value-at-risk (VaR) and conditional value-at-risk (CVaR). As important properties, the EVaR is strongly monotone over its domain and strictly monotone over a broad sub-domain including all continuous distributions, while well-known monotone risk measures, such as VaR and CVaR lack these properties. A key feature for a risk measure, besides its financial properties, is its applicability in large-scale sample-based portfolio optimization. If the negative return of an investment portfolio is a differentiable convex function, the portfolio optimization with the EVaR results in a differentiable convex program whose number of variables and constraints is independent of the sample size, which is not the case for the VaR and CVaR. This enables us to design an efficient algorithm using differentiable convex optimization. Our extensive numerical study shows the high efficiency of the algorithm in large scales, compared to the existing convex optimization software packages. The computational efficiency of the EVaR portfolio optimization approach is also compared with that of CVaR-based portfolio optimization. This comparison shows that the EVaR approach generally performs similarly, and it outperforms as the sample size increases. Moreover, the comparison of the portfolios obtained for a real case by the EVaR and CVaR approaches shows that the EVaR approach can find portfolios with better expectations and VaR values at high confidence levels.