How to solve this stochastic optimization problem?

Question

How one can solve the following stochastic optimization problem? \begin{align} \max\quad& \mathbb{E}[\mathbf{1}^{\mathrm{T}}X]\\ \text{s.t.} \quad& \mathbb{E}[\mathbf{A}X]\leq\mathbf{1}_{m\times 1}\qquad(\ast), \end{align} where $\mathbf{A}$ is a random matrix and consequently the solution vector $X$ is also a random vector.

I think about a simpler case. We know that for each realization of $\mathbf{A}$, one can solve the following \begin{align} \tilde{X}=\arg\max\quad& \mathbf{1}^{\mathrm{T}}X\\ \text{s.t.} \quad& \mathbf{A}X\leq\mathbf{1}_{m\times 1}\qquad(\ast\ast), \end{align} and so we can compute $\mathbb{E}[\mathbf{1}^{\mathrm{T}}\tilde{X}]$ by Solving $(\ast\ast)$ several times (for different realizations of $\mathbf{A}$) and then average. But, what can we do about $(\ast)$?

Answer 1

This is a slight addition to RaphaelB4's answer, to explain one approach to extending the discrete case to the general case. This approach begins by thinking about the discrete case in slightly more detail.

Note that RaphaelB4's optimization problem only has one input parameter: the matrix $\hat{A}$ formed by concatenating the finite set of matrices $A_i$ in the (assumed to be discrete) support of the random variable $\mathbf{A}$. Note also that the matrix $\hat{A}$ has the same number of rows as each $A_i$, and that its set of columns is the union of the columns of the $A_i$. So there's really no difference from the case where the matrices $A_i$ are just column vectors. For instance, we could make a new random variable $\mathbf{A}'$ taking values in column vectors, which first randomly picks a matrix $A_i$ and then chooses one of its columns uniformly at random.

Also, note that the optimization problem $$\max_{\mathbb{E}[\mathbf{A}]X \le 1} 1^TX$$ with a deterministic vector $X$ gives a lower bound on the solution to the optimization problem $(*)$. Since the probabilities are actually irrelevant to the problem, we may set them however we like: so in fact, we only care about the convex hull of the set of matrices $A_i$ that show up in the support of the random variable $\mathbf{A}$.

Putting these two ideas together, we see that the answer to the optimization problem $(*)$ only depends of the convex hull $\mathcal{C}$ of the set of column vectors that show up as columns of matrices in the support of $\mathbf{A}$. If $C \in \mathcal{C}$, then we can easily check that $$\max_{\mathbb{E}[\mathbf{A}X]\le 1} \mathbb{E}[1^TX] \ge \max_{Cx \le 1} x = \frac{1}{\max(\max_i C_i, 0)}.$$ In fact, a little thought shows that we have $$\max_{\mathbb{E}[\mathbf{A}X]\le 1} \mathbb{E}[1^TX] = \max_{C \in \mathcal{C}} \frac{1}{\max(\max_i C_i, 0)}.$$ So the problem reduces to minimizing the convex function $\max_i C_i$ over column vectors $C$ in the convex set $\mathcal{C}$. If you have a good description of the support of your random matrix $\mathbf{A}$, then it should be possible to convert this into a good enough description of the convex hull $\mathcal{C}$ to apply a standard convex optimization algorithm (such as the ellipsoid algorithm).

Edit: I seem to have made an implicit assumption. The above is true only if we require that $X \ge 0$ as well. If we don't require the coordinates of $X$ to be positive, then "convex hull" should be replaced by "affine hull" everywhere. This actually makes the problem easier: it should be much simpler to describe the affine hull of the set of columns of matrices in the support of $\mathbf{A}$ than to describe the convex hull.

Answer 2

I consider the case of discrete probability. There exists $n\in \mathbb{N}$, $A_1,\cdots,A_n$ and $p_1,\cdots, p_n>0$ such that $\sum_{i=1}^n p_i = 1$ and $\mathbb{P}(A=A_i)=p_i$. Then we denote $X_1,\cdot,X_n$ such that $X=X_i$ in the event $A=A_i$. The problem ($\star$) becomes $$\max \sum_{i=1}^n p_i 1^T X_i = \hat{1}^T \hat{X},\\ \quad \sum_{i=1}^n p_i A_i X_i = \hat{A} \hat{X}\leq 1_m $$ where $\hat{1}=1_{n p}$, $\hat{A}=(A_1,A_2,\cdots,A_n)\in \mathbb{R}^{m\times np}$ and $\hat{X}=(p_1 X_1,\cdots, p_n X_n)\in \mathbb{R}^{np}$. Therefore it a usual optimisation problem similar as $(\star \star)$ but with $X$ in a larger dimension set.

Remark : In particular for $i_\max$ the event $i$ such that the solution of $(\star,\star)$ with $A_i$ gives the largest value. Then chosing $\hat{X}=(0,\cdots,0,X_{i_{\max}},0,\cdots,0)$ we obtain that the solution of $(\star)$ gives an higher value that the maximum of all possible $(\star,\star)$ and this will also be valid for non discrete probability.