We study stochastic programs where the decision-maker cannot observe the distribution of the exogenous uncertainties but has access to a finite set of independent samples from this distribution. In this setting, the goal is to find a procedure that transforms the data to an estimate of the expected cost function under the unknown data-generating distribution, … Read more
We propose a randomized linear programming algorithm for approximating the optimal policy of the discounted Markov decision problem. By leveraging the value-policy duality, the algorithm adaptively samples state transitions and makes exponentiated primal-dual updates. We show that it finds an ε-optimal policy using nearly-linear running time in the worst case. For Markov decision processes that … Read more
Numerical optimization in complex numbers has drawn much less attention than in real numbers. A widespread opinion is that, since a complex number is a pair of real numbers, the best strategy to solve a complex optimization problem is to transform it into real numbers and to solve the latter by a real number solver. … Read more
We present a new approach to the design of D-optimal experiments with multivariate polynomial regressions on compact semi-algebraic design spaces. We apply the moment-sum-of-squares hierarchy of semidefinite programming problems to solve numerically and approximately the optimal design problem. The geometry of the design is recovered with semidefinite programming duality theory and the Christoffel polynomial. Article … Read more
If K is a closed convex cone and if L is a linear operator having L(K) a subset of K, then L is a positive operator on K and L preserves inequality with respect to K. The set of all positive operators on K is denoted by pi(K). If J is the dual of K, … Read more
An important problem in the breeding of livestock, crops, and forest trees is the optimum of selection of genotypes that maximizes genetic gain. The key constraint in the optimal selection is a convex quadratic constraint that ensures genetic diversity, therefore, the optimal selection can be cast as a second-order cone programming (SOCP) problem. Yamashita et … Read more
The sparse bounded degree sum-of-squares (sparse-BSOS) hierarchy of Weisser, Lasserre and Toh [arXiv:1607.01151,2016] constructs a sequence of lower bounds for a sparse polynomial optimization problem. Under some assumptions, it is proven by the authors that the sequence converges to the optimal value. In this paper, we modify the hierarchy to deal with problems containing equality … Read more
The positive semidefinite Procrustes (PSDP) problem is the following: given rectangular matrices $X$ and $B$, find the symmetric positive semidefinite matrix $A$ that minimizes the Frobenius norm of $AX-B$. No general procedure is known that gives an exact solution. In this paper, we present a semi-analytical approach to solve the PSDP problem. First, we characterize … Read more
We consider the problem of minimizing a continuous function f over a compact set K. We compare the hierarchy of upper bounds proposed by Lasserre in [SIAM J. Optim. 21(3) (2011), pp. 864-885] to bounds that may be obtained from simulated annealing. We show that, when f is a polynomial and K a convex body, … Read more
We study the problem of computing weighted analytic center for system of linear matrix inequality constraints. The problem can be solved using the Standard Newton’s method. However, this approach requires that a starting point in the interior point of the feasible region be given or a Phase I problem be solved. We address the problem … Read more