Let's say I have the following optimization problem:

$$ \begin{align*} \min_{\mathbf{x},\mathbf{y}} & \sum_i x_i-y_i \\ \mathrm{s.t.} & \{\mathbf{x},\mathbf{y}\} \in C(\mathbf{x},\mathbf{y}), \end{align*} $$ where $\mathbf{x}$ and $\mathbf{y}$ are vectors, $x_i$ and $y_i$ are the $i^{\mathrm{th}}$ elements of these vectors, and $C(\mathbf{x},\mathbf{y})$ is a well-defined convex set in these variables.

I want to minimize this difference $\sum_i \left(x_i - y_i\right)$, but also want to make sure that $\mathbf{x}$ is also the smallest it can be element-wise. In other words, if there are many $\{\mathbf{x},\mathbf{y}\}$ that minimize the difference and that are feasible, I'd like to obtain with the element-wise smallest $\mathbf{x}$.

I thought about this, and it would seem to me that this is naturally true, but I'm not positive. Any insights on this? If not, how can I guarantee this property?

  • $\begingroup$ I do not understand the notation $\{x,y\} \in C(x,y)$. What are $a,b$? And what does $x-y$ mean? (Are x,y reals?) $\endgroup$ – copper.hat Feb 25 '14 at 4:00
  • $\begingroup$ I'm sorry, the $a$ and $b$ were typos from the first time I typed the problem. They should be $x$ and $y$, as they appear in the current question. By $C(x,y)$, I mean a general set, such as $C(x,y) := \{x,y \ |\ x\le 4, y\le 3\}$, for instance. $\endgroup$ – user1496984 Feb 25 '14 at 4:43
  • $\begingroup$ A more typical notation would be $C \subset \mathbb{R}^2$. $\endgroup$ – copper.hat Feb 25 '14 at 5:06
  • $\begingroup$ What do you mean by minimising the vector $x-y$? Is it minimising some norm like Euclidean distance? In that case the minimum seems zero and you pick the "smallest" $x$ in whatever way you define small for the vector. $\endgroup$ – Macavity Feb 25 '14 at 12:57
  • $\begingroup$ @Macavity Oops, sorry again. I tried to simplify the notation as much as possible, but screwed up in the process. The current one should make more sense. Any thoughts now? $\endgroup$ – user1496984 Feb 25 '14 at 23:09

If you know that $\sigma = \min f(\mathbf{x})$ subject to $\mathbf{x}\in C$and you want to want to minimize $g(\mathbf{x})$ for all such $\mathbf{x}$, I think all you have to do is

$$ \min_{\mathbf{x}} g(\mathbf{x}) \;\;\; \mathrm{s.t.} \;\;\; f(\mathbf{x})=\sigma \wedge \mathbf{x} \in C. $$

So, if you can solve the original problem and get the minimum value of the function, you can then use that to minimize $g(\mathbf{x})$ over all possible solutions by solving the second optimization problem above.

There is also a somewhat related post here.


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.