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

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.

• No. Any non-convex optimization problem can be put in this form via epigraph formulation. Change minimize objective subject to constraints; to minimize t subject to objective <= t and original constraints. This now has your "special" form. Jul 28, 2022 at 17:02
• Hello Mark. You are right, I could estate the problem as you suggest so that the new formulation satifies my conditions. However, in that specific form, the global optima will be in the frontier given that the constraint: objective <= t will be active. Jul 29, 2022 at 6:39
• I have been thinking about this a little bit more and I would say it is true. Intuitively, if the feasible region is compact and the objective function is linear, the gradient of the objective function won't be null in the interior of the feasible region. Therefore, the global optima lays in the frontier necessarily. However, in pretty fresh in this field and I can still be totally wrong. Anyway, I truly appreciate your comments. Best regards. Jul 29, 2022 at 6:48

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 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.