# Distribution of the Objective Value and the Variables in an Optimization Program

For random variables $X$ and $Y$, where $X\sim f(X;\theta)$ ($X$ is drawn from some distribution with pdf $f$ which is parametrized by $\theta$ ), $Y=g(X)$; we know that we can find the pdf of $Y$ if $g(X)$ satisfies certain properties (For example by using determinant of Jacobian method if $g$ in one to one).

I have two related, but different questions.

Now assume that:

$$Y= \min_Z g(X,Z), ~~~~~~~X\sim f(\theta)$$

In particular, we can see this as a minimization program:

$$\text{minimize}_Z g(X,Z)~~~\text{subject to}~~~AZ\leq b$$

1) What can we say about the distribution of $Y$ (the optimal value of the objective)?

2) What can be said about the distribution of $Z^*$ where $Z^*=\arg\min_Z g(X,Z)$ (the solution of the optimization problem) ?

In general $g$ can be a complicated function, but you can assume that $g$ is convex, and therefore there exist some unique real scalar $Y$ and real vector $Z$ for a fixed $X$.

I tried to simplify the problem by setting $g(X,Z)=Z^TX=\sum_i Z_iX_i$, and $X$ being drawn from some multivariate normal distribution: $X\sim\mathcal{N}(\mu,\Sigma)$, but didn't have much success in this simplified version neither.

I'm using this for analyzing the effect of perturbations of the known parameters of the model in the results of the optimization program.

Thanks!

• Why did you tag this as convex optimization? Do you have any reason to believe your problem is convex? Commented Mar 24, 2014 at 14:50
• If I can solve it for simpler $g$'s (e.g. convex function) that still helps. Specially since, by this assumption there exist a unique minimum, and it is meaningful to talk about the distribution of such minimums. In the simplest case, $g(X,Z)$ is bilinear in its arguments and we have: $$\text{minimize}_Z g(X,Z)~~~\text{subject to}~~~AZ\leq b$$ (constrained to a polyhedron), Note that I'm not claiming that the whole problem can be formulated as a convex optimization program, but if you see the $X$'s as known parameters on the hindsight, then this specific minimization is a convex program.
– Alt
Commented Mar 24, 2014 at 18:26

Some stuff can be said about the case $g(X,Z)=Z^TX=∑_iZ_iX_i$ where $AX\le b$. For a given value of $X$, if $\min_Z Z^TX$ is bounded, then the minimizing value of $Z$ will be one of the vertices of the simplex/polyhedron $AZ\le b$. The number of vertices is at most $K-1$, where $K$ is the number of constraints in $AZ\le b$. Thus in $(Z^*)^TX$, where $Z^* = \arg\min_Z Z^TX$, the values of $Z^*$ come from a set of size atmost $K-1$, lets say this set is $\{Z_1,Z_2,\cdots,Z_L\}$ with $L\le K-1$.

Now the set of values of $X$ for which the optimum value of $Z$ is $Z_i$ is the region $S_i = \{X: Z_i^TX \le Z_j^TX \ \ \forall j\ne i\}$ which can be rewritten in the form $\{X: B_i^TX < 0\}$ for some matrix $B_i$. Thus each $S_i$ is a region enclosed by linear boundaries.

On the whole $Y$ has the form $Y = \sum_{i=1}^{L} I_i(X) Z_i^T X$ where $I_i(X)$ is an scalar indicator variable that is $1$ if $X\in S_i$ and $0$ otherwise. The CDF of $Y$ is

$Pr\{Y<y\} = \sum_{i=1}^{L} Pr\{B_i^TX < 0\} Pr\{Z_i^T X <y |\ B_i^T X < 0\}$.

Helps some, but not much.

• "The number of vertices is at most $K-1$, where $K$ is the number of constraints in $AZ\le b$." not really, the number of constraints is equal to the number of hyper-planes and the number of vertices is exponential in the $K$.
– Alt
Commented Mar 26, 2014 at 21:02