Optimization and Control (math.OC)

  • PDF
    There is widespread sentiment that it is not possible to effectively utilize fast gradient methods (e.g. Nesterov's acceleration, conjugate gradient, heavy ball) for the purposes of stochastic optimization due to their instability and error accumulation, a notion made precise in d'Aspremont 2008 and Devolder, Glineur, and Nesterov 2014. This work considers these issues for the special case of stochastic approximation for the least squares regression problem, and our main result refutes the conventional wisdom by showing that acceleration can be made robust to statistical errors. In particular, this work introduces an accelerated stochastic gradient method that provably achieves the minimax optimal statistical risk faster than stochastic gradient descent. Critical to the analysis is a sharp characterization of accelerated stochastic gradient descent as a stochastic process. We hope this characterization gives insights towards the broader question of designing simple and effective accelerated stochastic methods for more general convex and non-convex optimization problems.
  • PDF
    In many smart infrastructure applications flexibility in achieving sustainability goals can be gained by engaging end-users. However, these users often have heterogeneous preferences that are unknown to the decision-maker tasked with improving operational efficiency. Modeling user interaction as a continuous game between non-cooperative players, we propose a robust parametric utility learning framework that employs constrained feasible generalized least squares estimation with heteroskedastic inference. To improve forecasting performance, we extend the robust utility learning scheme by employing bootstrapping with bagging, bumping, and gradient boosting ensemble methods. Moreover, we estimate the noise covariance which provides approximated correlations between players which we leverage to develop a novel correlated utility learning framework. We apply the proposed methods both to a toy example arising from Bertrand-Nash competition between two firms as well as to data from a social game experiment designed to encourage energy efficient behavior amongst smart building occupants. Using occupant voting data for shared resources such as lighting, we simulate the game defined by the estimated utility functions to demonstrate the performance of the proposed methods.
  • PDF
    In this paper, we study an optimal excess-of-loss reinsurance and investment problem for an insurer in defaultable market. The insurer can buy reinsurance and invest in the following securities: a bank account, a risky asset with stochastic volatility and a defaultable corporate bond. We discuss the optimal investment strategy into two subproblems: a pre-default case and a post-default case. We show the existence of a classical solution to a pre-default case via super-sub solution techniques and give an explicit characterization of the optimal reinsurance and investment policies that maximize the expected CARA utility of the terminal wealth. We prove a verification theorem establishing the uniqueness of the solution. Numerical results are presented in the case of the Scott model and we discuss economic insights obtained from these results.
  • PDF
    Reference [11] investigated the almost sure weak convergence of a block-coordinate fixed point algorithm and discussed its application to nonlinear analysis and optimization. This algorithm features random sweeping rules to select arbitrarily the blocks of variables that are activated over the course of the iterations and it allows for stochastic errors in the evaluation of the operators. The present paper establishes results on the mean-square and linear convergence of the iterates. Applications to monotone operator splitting and proximal optimization algorithms are presented.
  • PDF
    In this paper, we investigate an optimal design problem motivated by some issues arising in population dynamics. In a nutshell, we aim at determining the optimal shape of a region occupied by resources for maximizing the survival ability of a species in a given box and we consider the general case of Robin boundary conditions on its boundary. Mathematically, this issue can be modeled with the help of an extremal indefinite weight linear eigenvalue problem. The optimal spatial arrangement is obtained by minimizing the positive principal eigenvalue with respect to the weight, under a L 1 constraint standing for limitation of the total amount of resources. The specificity of such a problem rests upon the presence of nonlinear functions of the weight both in the numerator and denominator of the Rayleigh quotient. By using adapted symmetrization procedures, a well-chosen change of variable, as well as necessary optimality conditions, we completely solve this optimization problem in the unidimensional case by showing first that every minimizer is unimodal and bang-bang. This leads to investigate a finite dimensional optimization problem. This allows to show in particular that every minimizer is (up to additive constants) the characteristic function of three possible domains: an interval that sticks on the boundary of the box, an interval that is symmetrically located at the middle of the box, or, for a precise value of the Robin coefficient, all intervals of a given fixed length.
  • PDF
    In this paper, we study the generalized mean-field stochastic control problem when the usual stochastic maximum principle (SMP) is not applicable due to the singularity of the Hamiltonian function. In this case, we derive a second order SMP. We introduce the adjoint process by the generalized mean-field backward stochastic differential equation. The keys in the proofs are the expansion of the cost functional in terms of a perturbation parameter, and the use of the range theorem for vector-valued measures.
  • PDF
    In this paper, we study the stochastic gradient descent (SGD) method for the nonconvex nonsmooth optimization, and propose an accelerated SGD method by combining the variance reduction technique with Nesterov's extrapolation technique. Moreover, based on the local error bound condition, we establish the linear convergence of our method to obtain a stationary point of the nonconvex optimization. In particular, we prove that not only the sequence generated linearly converges to a stationary point of the problem, but also the corresponding sequence of objective values is linearly convergent. Finally, some numerical experiments demonstrate the effectiveness of our method. To the best of our knowledge, it is first proved that the accelerated SGD method converges linearly to the local minimum of the nonconvex optimization.
  • PDF
    We study a very small three player poker game (one-third street Kuhn poker), and a simplified version of the game that is interesting because it has three distinct equilibrium solutions. For one-third street Kuhn poker, we are able to find all of the equilibrium solutions analytically. For large enough pot size, $P$, there is a degree of freedom in the solution that allows one player to transfer profit between the other two players without changing their own profit. This has potentially interesting consequences in repeated play of the game. We also show that in a simplified version of the game with $P>5$, there is one equilibrium solution if $5 < P < P^* \equiv (5+\sqrt{73})/2$, and three distinct equilibrium solutions if $P > P^*$. This may be the simplest non-trivial multiplayer poker game with more than one distinct equilibrium solution and provides us with a test case for theories of dynamic strategy adjustment over multiple realisations of the game. We then study a third order system of ordinary differential equations that models the dynamics of three players who try to maximise their expectation by continuously varying their betting frequencies. We find that the dynamics of this system are oscillatory, with two distinct types of solution. We then study a difference equation model, based on repeated play of the game, in which each player continually updates their estimates of the other players' betting frequencies. We find that the dynamics are noisy, but basically oscillatory for short enough estimation periods and slow enough frequency adjustments, but that the dynamics can be very different for other parameter values.
  • PDF
    We propose a development of the Analytic Hierarchy Process (AHP) permitting to use the methodology also in cases of decision problems with a very large number of alternatives evaluated with respect to several criteria. While the application of the original AHP method involves many pairwise comparisons between alternatives and criteria, our proposal is composed of three steps: (i) direct evaluation of the alternatives at hand on the considered criteria, (ii) selection of some reference evaluations; (iii) application of the original AHP method to reference evaluations; (iv) revision of the direct evaluation on the basis of the prioritization supplied by AHP on reference evaluations. The new proposal has been tested and validated in an experiment conducted on a sample of university students. The new methodology has been therefore applied to a real world problem involving the evaluation of 21 Social Housing initiatives sited in the Piedmont region (Italy). To take into account interaction between criteria, the Choquet integral preference model has been considered within a Non Additive Robust Ordinal Regression approach.