Optimization over a convex cone generated by a set is equal to optimization over the set.

137 Views Asked by At

We considerer the following optimization problem $$ \left\{\begin{array}{cl} \max\limits_{x\in\mathcal{C}} & f(x) \\[2pt] \text{s.t.} & \mathcal{A}x-b \in K \end{array} \right. \tag{1} $$

where $f:\mathbb{R}^{n}\rightarrow \mathbb{R}$ and $\mathcal{A}:\mathbb{R}^{n}\rightarrow \mathbb{R}^{m}$ are linear functions non-zero, $b\in\mathbb{R}^{m}$, $\mathcal{C}$ is a convex cone in $\mathbb{R}^{n}$ and $K$ is a closed convex cone in $\mathbb{R}^{m}$.

Question: If $\mathcal{C}$ is the convex cone generated by a set $U\subset\mathbb{R}^{n}$, can we say that problem $(1)$ is equivalent to the following problem $$ \left\{\begin{array}{cl} \max\limits_{x\in U} & f(x) \\[2pt] \text{s.t.} & \mathcal{A}x-b \in K \end{array} \right. \tag{2} ?$$

My Idea: My idea is to show that if there is an optimal point $x^{*}\in\mathcal{C}$ for the problem $(1)$ then that point must belong to $U$. The problem is the condition $\mathcal{A}x-b \in K$, I feel that I must put conditions in $ K $ because I see no guarantee that points in $A$ will satisfy the condition, I do not know if I am wrong.

1

There are 1 best solutions below

0
On BEST ANSWER

They are not equivalent . For example in dimension one take $f(x) = x, ~ U=\{1\}, ~ A=0, b=0,~ K=\{0\} $

Then first you have $C= [0, +\infty)$, Thus problem one becomes Maximization of $f(x) = x$ over $C= [0, +\infty)$, which is unbounded , but problem two is maximizing $f(x)=x$ over $U=\{1\}$ which has $x=1$ as its maximizer .