11

I am currently solving an indefinite quadratic program with linear constraints using CPLEX. Moreover, I am trying to determine whether the candidate point CPLEX is feeding my callback function is an extreme point.

I know that a certain $x \in \mathbb{R}^n$ is an extreme point if and only if there is equality in at least $n$ linearly independent rows in the inequality $A x \le b$, but I do not know how to guarantee that the constraints I feed CPLEX (also the ones it generates itself) are linearly independent with respect to the other constraints in the model.

My question thus is: How do I check in CPLEX (or another off-the-shelf MIQP solver) whether a certain candidate $x$ is an extreme point?

Kevin Dalmeijer
  • 6,167
  • 1
  • 17
  • 48
DaPurr
  • 113
  • 5
  • Possible duplicate of Generating all extreme rays – Rob Aug 21 '19 at 13:49
  • 7
    @Rob Checking whether a point is an extreme point is a problem that is very different from finding all extreme points, as the latter is often not doable in practice. Hence, I do not consider this a duplicate. – Kevin Dalmeijer Aug 21 '19 at 14:01
  • @KevinDalmeijer I see the answer there, if you don't then look for another and/or upon finding that we have no duplicate (that one was better than the other) you're free to make your own contrary decision. – Rob Aug 21 '19 at 14:09

1 Answers1

7

If $\bar{y} \in \mathbb{R}^n$ is the point you are feeding, then assuming that you have verified that $\bar{y}$ is feasible to your linear constraints to begin with, then try to find a direction $d$ such that both $\bar{y}+d$ and $\bar{y}-d$ are feasible to your linear constraints. In other words, if the following problem has an optimum objective > 0, then you can conclude that $\bar{y}$ is not a vertex. If the objective is >0, then $\bar{y}$ can be represented as a convex combination of 2 other points, $\bar{y} +d$ and $\bar{y} - d$, where both points are feasible to your linear constraints. If the optimum objective is 0, then we can safely conclude that $d = 0$, so no line segment can pass through $\bar{y}$, lying completely inside the feasible region.

\begin{align} \max_{d \in \mathbb{R}^n} & \,\, \|d \|_1\\ \mbox{s.t. } & A(\bar{y} + d) \leq b \\ &A(\bar{y} - d) \leq b \end{align}

As pointed out in the comments below, the objective is non-convex. However if we are looking for efficiency, then we can overcome the non-convexity issue by instead solving $n$ linear maximization problems instead. Have a look at the comments below for the specification of those $n$ maximization problems. Even if one of $n$ maximization problems has an objective > 0, we can conclude that $\bar{y}$ is not a vertex point.

batwing
  • 1,458
  • 6
  • 15
  • Note that maximizing an $l_1$ norm is non-convex, so you will need to introduce indicator variables to model the $l_1$ objective. You can do this via $\max \sum_i u_i$ where $u_i \geq x_i, u_i \geq - x_i, x_i \leq x_i+M(1-z_i), u_i \leq -x_i+M(z_i), z_i \in {0, 1}$. Since this approach requires indicator variables, there might be more efficient approaches (but I can't think of one off the top of my head). – Ryan Cory-Wright Aug 22 '19 at 18:17
  • Nonetheless, this works, so (+1). – Ryan Cory-Wright Aug 22 '19 at 18:27
  • 1
    @RyanCory-Wright- the issue can be fixed by solving $n$ maximization problems instead of the single maximization problem I had written. The $i^{th}$ maximization will have an objective $e_i^T d$, where $e_i$ is the $i^{th}$ unit vector. The constraints are exactly what was shown in the post. If there existed a $d$ to begin with, then one of those maximization problems will output an objective value > 0. Agree? – batwing Aug 22 '19 at 18:37
  • I think so. But in that case, shouldn't it be possible to elicit the solution by solving one LP, namely $$\min 0 \ \text{s.t.} A(\bar{y}+d) \leq b, A(\bar{y}-d) \leq b, e^\top d=1.$$ – Ryan Cory-Wright Aug 22 '19 at 18:46
  • @RyanCory-Wright - How would you guess what $e$ is? – batwing Aug 22 '19 at 18:50
  • $e$ is a vector of all ones. If $\exists d \neq 0$ so that $y+d$ and $y-d$ are both feasible, then we can certainly rescale $d$ so that $\sum_i d_i=1$. – Ryan Cory-Wright Aug 22 '19 at 18:53
  • @RyanCory-Wright - for a problem in $\mathbb{R}^2$, what if $(1, -1)$ is the only direction of feasibility for $d$, then clearly $e^T d = 0$, where $e = (1, 1)$. – batwing Aug 22 '19 at 18:55
  • 1
    Yes, you are correct, you need the $n$ different problems. – Ryan Cory-Wright Aug 22 '19 at 18:57