Consider the following constrained optimization problem $\mathcal{P}$.

$$ \min_{x \in X \subseteq \mathbb{R}^n} f(x) \ \text{sub. to: } g(x,y) \leq 0 \ \forall y \in Y \subseteq \mathbb{R}^m $$

Functions $f$ and $g$ are continuous and convex. Sets $X, Y$ are compact and convex.

Note that the constraint "$g(x,y) \leq 0 \ \forall y \in Y$" is infinite dimensional.

Assume that both the optimal value of $\mathcal{P}$ and its optimizer $x^* \in X$ (supposed unique) exist and are bounded.

Suppose we can solve the following "sub-problems" $\mathcal{P}_1$, $\mathcal{P}_2$.

$$\min_{x \in X} f(x) \ \text{sub. to: } g(x,y) \leq 0 \ \forall y \in Y_1 \subset Y $$

$$\min_{x \in X} f(x) \ \text{sub. to: } g(x,y) \leq 0 \ \forall y \in Y_2 \subset Y $$

where $Y_1 \cap Y_2 = \varnothing$ and $Y_1 \cup Y_2 = Y$. Namely, we know the unique optimizers $x_1^*$ and $x_2^*$ of $\mathcal{P}_1$ and $\mathcal{P}_2$, respectively, and hence the optimal values $f(x_1^*)$ and $f(x_2^*)$.

Question: can we compute $x^*$ from the knowledge of $x_1^*$ and $x_2^*$, under one of the following assumptions?

  1. $f$ and $g$ are linear, i.e. $f(x) := c^\top x$ and $g(x,y) := Ax + By$.
  2. $f$ is quadratic, i.e. $f(x) := x^\top C x + c^\top x$ with $C$ positive definite, and $g$ is linear.

  3. No additional assumptions on $f$ and $g$.

Comments. I think this problem is very interesting because would tell how to subdivide a "difficult" optimization problem into two "less difficult" ones. I have looked into the literature of Distributed Robust Optimization to solve this. There actually are convergent algorithms which mainly address the problem whenever the sets $Y_1$ and $Y_2$ (in general, more than $2$ sub-problems are considered) have overlappings. In the latter case, the "solvers" have to communicate to finally "agree" about $x^*$. But I guess that if $Y_1$ and $Y_2$ do not overlap, something better can be done, at least in the linear, or quadratic, case.


I can't comment because I just made this account. But wouldn't $ x^* $ in the linear case just be the first point of the convex combination form $ \alpha x_1^* + (1 - \alpha) x_2^* $ when $ f(x_1^*) < f(x_2^*) $? Or the smallest $ \alpha $ such that that convex combination point $ \in X_2 $. I don't know about the quadratic case. Would have to give it more thought.

  • $\begingroup$ What do you mean by "first point"? By the way, why $x^*$ is supposed to be in the convex combination of $x_1^*$ and $x_2^*$? $\endgroup$
    – user693
    Apr 1 '13 at 20:18
  • $\begingroup$ Actually, I take it all back. $\endgroup$
    – DiegoNolan
    Apr 1 '13 at 20:27
  • $\begingroup$ Actually, I take it all back. $ f(x) is linear $. If $ f ( x_1^*) < f(x_2^*)$ and $ X_1 $ and $ X_2 $ are convex then $ x_2^*$ is the minimizer of $ \text{min} f(x) \text{s.t} x \in X_1 x \in X_2 $. Since the function is linear $ f(x) = \nabla f(x_1^*) * (x-x_1^*) $ You might have to prove this on your own but because its linear $ f(x) \forall x \in X_1 uninary minus X_2 <= f(y) \forall y \in X_2 $ $ x_2^* $ is the minimizer of $ f(x) x \in X_1 $ therefore the minimizer of the internsection should be $ x_2 $. $\endgroup$
    – DiegoNolan
    Apr 1 '13 at 20:34
  • $\begingroup$ Can you please be more clear in your comment and answer? Notice that here we have infinite dimensional constraints... $\endgroup$
    – user693
    Apr 1 '13 at 20:39
  • $\begingroup$ @DiegoNolan: Welcome to MSE! This area is intended for answers to questions as opposed to additional questions from original postings. Regards $\endgroup$
    – Amzoti
    Apr 1 '13 at 20:40

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.