3
$\begingroup$

For a nonlinear optimization problem having only linear constraints, by the Linearity Constraint Qualification, no further constraint qualification is required for the Karush-Kuhn-Tucker (KKT) conditions to hold. https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions . In particular, the Jacobian of active constraints need not be full rank.

The Linear Independence Constraint Qualification (LICQ) for KKT is stated as: the Jacobian of active constraints is full rank, i.e., the gradients of the active constraints are linearly independent.

Suppose the following:

1) Jacobian of active nonlinear constraints is full rank

2) Jacobian of active nonlinear constraints is independent of Jacobian of active linear constraints, i.e., rank(Jacobian of all active constraints) = rank(Jacobian of active nonlinear constraints) + rank(Jacobian of active linear constraints)

Is the combination of (1) and (2) a valid constraint qualification for KKT? Note that this would not require that the Jacobian of active linear constraints be full rank. If this is valid, it seems strange that I have never seen LICQ stated this way, because my candidate constraint qualification (of as yet unknown correctness) has a weaker hypothesis, and therefore would be a more powerful and widely applicable constraint qualification, than how I have seen it stated.

I am trying to determine whether I can "get away with" having some redundant (active) linear constraints on a non-pre-solved optimization model when I also have active nonlinear constraint(s). I can get away with it when there are no nonlinear constraints.

I have not found a counterexample, but will hazard a guess that if there is a counterexample, there exists a counterexample having one nonlinear constraint and two linear constraints.

This is not a homework or test problem, but maybe it should be: I.e., prove it true or false.

Thanks.

Bumping this since no one has answered. This seems like it shouldn't be that hard to either prove true or produce a counterexample. I'm more a user of Constraint Qualifications than I ever was a prover of them. But this should be a piece of cake for you math/geometry whizzes.

$\endgroup$
3
$\begingroup$

This is true. It's a particular case of the Constant Rank Constraint Qualification from Janin.

$\endgroup$

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.