In Sequential Quadratic Programming we use an active set of the inequality constraints and handle them as equality constraints in the quadratic subproblem.

SQP is said to be able to deal with infeasible points in the design space, which violate the inequality constraints.

Whenever the algorithm takes you to a point which violates a constraint then that constrain is added to the active set for the next iteration.

But if the number of constraints in the current active set is more than the dimensionality of the design space, the quadratic subproblem is not solvable.

When implementing SQP, how can we deal with such over-constrained infeasible points in the design space?


That can't happen. You can have more constraints than variables, but the number of active constraints can not exceed the number of variables. (That's not quite true: Some constraints might be redundant, or degenerate, but then you can remove these constraints from the active set with no ill effect.)

Why my statement above is correct is probably easiest to understand if you read up on the simplex algorithm for linear programs, and in particular on the geometry of the feasible set and how one constructs the bases for each vertex of the polyhedron that describes the feasible set.

  • $\begingroup$ In my particular problem more constraint surfaces happen to meet at an optimum, but my question wasn't about constraints actually being active, but about the active set. All violated constraints should be in the active set and there are points in the infeasible space which violate all constraints. $\endgroup$ Jul 1 at 19:54
  • 1
    $\begingroup$ Take an example: You are in ${\mathbb R}^2$ and you have three inequalities that all meet in one point and that point is the optimum. Then you can say that at that point all three constraints are "active", but in practice the way we think about this is that they are redundant, and that only two of them are active (namely, the two that delineate the feasible region) whereas the third can be removed from the active set without any harm. $\endgroup$ Jul 2 at 2:59
  • 1
    $\begingroup$ Think in 3D of a polygonal cone where all surfaces meet at the apex. None of the constraints is redundant. $\endgroup$ Jul 2 at 6:05
  • $\begingroup$ Oh, I see what you mean. The active set strategy only ever keeps at most $d-1$ constraints active so that you have at least one direction to move in. If you end up with a move that would violate a constraint, you have to cycle that constraint into the active set and evict another constraint. $\endgroup$ Jul 2 at 15:37
  • $\begingroup$ But then I would most likely take a step into a direction which violates the evicted constraint. Wouldn't you just end up going in cycles like that? $\endgroup$ Jul 2 at 19: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.