1
$\begingroup$

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)$?

$\endgroup$
4
  • 1
    $\begingroup$ I don't understand your "consequently the solution vector $X$ is also a random vector". You should present a little bit more detail. What is the background, what is $X_i$, dependent or not or even deterministic? More precise: $X \in ?$. $\endgroup$ – Dieter Kadelka May 31 '20 at 12:45
  • $\begingroup$ Is X independent of A? $\endgroup$ – Yuval Peres May 31 '20 at 21:05
  • $\begingroup$ No, X is not independent of $\mathbf{A}$. $\endgroup$ – Math_Y May 31 '20 at 22:53
  • $\begingroup$ If you optimize for each realization you satisfy (*) so you would need to prove that you cannot do any better than this. $\endgroup$ – S.Surace Jun 5 '20 at 18:22
3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ If we replace $1^\mathrm{T}\mathbf{X}$ with $\min_i X_i$ in the objective function, what could we say? $\endgroup$ – Math_Y Jun 17 '20 at 17:18
  • $\begingroup$ In that case the exact probabilities still don't matter, but I think we can no longer split each matrix into its columns separately. We can still say that the answer will only depend on the convex hull of the support of the random matrix $\mathbf{A}$, but beyond that the problem seems to have become somewhat harder. $\endgroup$ – zeb Jun 18 '20 at 7:04
  • $\begingroup$ Thank you. Can I have your email? $\endgroup$ – Math_Y Jun 18 '20 at 16:43
3
+25
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Interestingly, this approach shows that the actual values of the probabilities $p_i$ are irrelevant to the final answer (as long as all the $p_i$ are nonzero). $\endgroup$ – zeb Jun 5 '20 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.