Linear objective function in non-convex feasible region: Is the global optima in the frontier?

Question

Considering an optimization problem in which the objective function is linear and the feasible region is a non-convex set: Can we assure that the global optima is still in the frontier of the feasible region? Any proof or counterexample?

I have thought about it, and I would say this holds considering an objective function $f: \mathbb{R}^{2} \rightarrow \mathbb{R}$. However, I do not know if this is true or if it can be generalized.

Maybe this is a very naive question, but I could not find any resource clarifying this.

Thank you in advance for your comments. Best regards.

Answer 1

I assume by "frontier" you mean boundary. Let's assume we are maximizing $f(x)=c^\prime x$ over $X\subseteq \mathbb{R}^n,$ with $c\neq 0.$

Suppose that $X$ has full dimension $n$ and $x$ is a point in the interior of $X.$ Then $x\in B \subseteq X$ for some nontrivial ball $B$, and that ball must contain $x+\lambda c$ for some $\lambda > 0.$ Since $f(x+\lambda c)=c^\prime x + \lambda \left\Vert c \right\Vert^2 > c^\prime x,$ $x$ cannot be a maximum. So the maximum, if one exists, must lie on the boundary of $X.$

Now suppose instead that $X$ has dimension less than $n,$ meaning it is contained in an affine subspace of dimension $d<n.$ Then the interior of $X$ is empty, and technically the boundary of $X$ is $X,$ meaning any maximum is automatically a boundary point. I suspect, though, that you are interested in the relative boundary (the complement in $X$ of the relative interior of $X$). Project $c$ into the affine subspace containing $X.$ If the projection is 0, $f(x)$ is constant over $X$ and every point of $X,$ whether in the relative interior or the relative boundary, is a maximum. If the projection is not 0, apply the previous argument (using the projection of $c$ and a ball of dimension $d$ in the relative interior of $X$) to rule out the possibility of a relative interior point being a maximum.

Note that, without additional assumptions, there is no guarantee that $X$ has a boundary (or, more precisely, that its boundary belongs to it), nor any guarantee that a maximum exists.