# Quadratic programming using CPLEX: how to check whether candidate is an extreme point?

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?

• Possible duplicate of Generating all extreme rays
– Rob
Commented Aug 21, 2019 at 13:49
• @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. Commented Aug 21, 2019 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
Commented Aug 21, 2019 at 14:09

## 1 Answer

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.

• 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). Commented Aug 22, 2019 at 18:17
• Nonetheless, this works, so (+1). Commented Aug 22, 2019 at 18:27
• @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? Commented Aug 22, 2019 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.$$ Commented Aug 22, 2019 at 18:46
• Yes, you are correct, you need the $n$ different problems. Commented Aug 22, 2019 at 18:57