Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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?) –  copper.hat Feb 25 at 4:00
    
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. –  user1496984 Feb 25 at 4:43
    
A more typical notation would be $C \subset \mathbb{R}^2$. –  copper.hat Feb 25 at 5:06
    
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. –  Macavity Feb 25 at 12:57
    
@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? –  user1496984 Feb 25 at 23:09

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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