0
$\begingroup$

Suppose that we want to optimize the convex function $f(x)$ under some convex constraints

\begin{align} &\underset{\mathbf{x}}{\operatorname{minimize}}& & f(\mathbf{x}) \\ &\operatorname{subject\ to} & &g_i(\mathbf{x}) \leq 0, \quad i = 1, \dots, m \\ &&&h_i(\mathbf{x}) = 0, \quad i = 1, \dots, p \end{align}

Assume that if we dispense with the constraints, the minimum of $f(x)$ does not satisfy the constraints (if we dispense with the constraints, the minimum of $f(x)$ does not lie on the feasible set).

Then, can we be sure that the solution of the constrained problem, $x^*$, lies on the apex of the feasible set? i.e:

\begin{align} && g_i(\mathbf{x^*}) = 0, \quad i = 1, \dots, m \\ && h_i(\mathbf{x^*}) = 0, \quad i = 1, \dots, p \end{align}

Can we be sure that the solution of the constrained problem, $x^*$, lies on the boundary of the feasible set? i.e:

\begin{align} && g_i(\mathbf{x^*}) = 0,\ for\ at\ least\ one \quad i = 1, \dots, m \\ && h_i(\mathbf{x^*}) = 0, \quad i = 1, \dots, p \end{align}

If the answer is no, is there any assumption or condition that we can add to this problem such that it guarantees that the solution of the constrained problem lies on the boundary or apex of the feasible set?

$\endgroup$
8
  • $\begingroup$ Do you assume that the $h$ and $g$ functions are also convex? Or can they be anything? $\endgroup$
    – Zim
    May 2, 2023 at 16:14
  • $\begingroup$ @Zim. Yes assume that they are. (by the way, does the answer differ if we consider them not to be convex?) $\endgroup$
    – alireza
    May 2, 2023 at 16:20
  • 1
    $\begingroup$ The answer to this question does not change (because the answer is no in either case) -- but it does change the existence result slightly. For convex $g_i$, we get at least one inequality which is sharp. However, for general nonsmooth/nonconvex $g_i$ I do not think we have any guarantees. $\endgroup$
    – Zim
    May 2, 2023 at 16:22
  • 1
    $\begingroup$ Oh yes -- convexity guarantees this! The only thing to distinguish is that, it is possible to be on the boundary of the set even if only one of the $g_i$s is an "active" / "sharp" constraint. Here is a graph: desmos.com/calculator/m1cl8go8uj the "feasible area" is the intersection of the red circle and the green band. Several points are highlighted which show where only one of the $g_i$s is active. $\endgroup$
    – Zim
    May 2, 2023 at 16:31
  • 1
    $\begingroup$ In other words, requiring that all of the $g_i$s are equal to zero does not describe the boundary of the feasible set. $\endgroup$
    – Zim
    May 2, 2023 at 16:36

1 Answer 1

2
$\begingroup$

Not in general. Let's consider the in the standard setting, where we assume that $(g_i)_{i=1}^m$ and $(h_i)_{i=1}^p$ are convex. Even for this case, we are guaranteed to get a "sharp" constraint, i.e., at least one $g_i$ which meets their inequality $\leq$ with equality $=$. However, this does not mean that all of the constraints are sharp simultaneously!

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .