11
$\begingroup$

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?

|improve this question
$\endgroup$
  • $\begingroup$ Possible duplicate of Generating all extreme rays $\endgroup$ – Rob Aug 21 at 13:49
  • 7
    $\begingroup$ @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. $\endgroup$ – Kevin Dalmeijer Aug 21 at 14:01
  • $\begingroup$ @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. $\endgroup$ – Rob Aug 21 at 14:09
7
$\begingroup$

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.

|improve this answer
$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Ryan Cory-Wright Aug 22 at 18:17
  • $\begingroup$ Nonetheless, this works, so (+1). $\endgroup$ – Ryan Cory-Wright Aug 22 at 18:27
  • 1
    $\begingroup$ @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? $\endgroup$ – batwing Aug 22 at 18:37
  • $\begingroup$ 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.$$ $\endgroup$ – Ryan Cory-Wright Aug 22 at 18:46
  • 1
    $\begingroup$ Yes, you are correct, you need the $n$ different problems. $\endgroup$ – Ryan Cory-Wright Aug 22 at 18:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.