When is LICQ useful in KKT conditions?
$begingroup$
KKT establishes a set of criteria for differentiable optimisation problems related to strong duality (i.e. when primal optimal equals dual optimal). In particular, KKT conditions are necessary for strong duality in all cases, and also sufficient when the primal problem becomes convex (i.e. when the objective and inequality constraints all become convex and the equality constraints are affine).
However, in one of my class slides it presents a different version of KKT conditions with the additional LICQ (i.e. active inequality constraints and equality constraints have linearly independent gradients). I'm really confused why LICQ is needed here at all. Does requiring LICQ additionally improve or generalise the usual LICQ-free version of KKT? I don't see how it can (the conclusion the slide shows doesn't seem strengthened, despite requiring more). So I'm curious to know where LICQ can come into play. Thanks.
optimization convex-optimization nonlinear-optimization karush-kuhn-tucker
asked Dec 11 '18 at 17:58
VimVim
8,11431348
$endgroup$
|
show 2 more comments
$begingroup$
KKT establishes a set of criteria for differentiable optimisation problems related to strong duality (i.e. when primal optimal equals dual optimal). In particular, KKT conditions are necessary for strong duality in all cases, and also sufficient when the primal problem becomes convex (i.e. when the objective and inequality constraints all become convex and the equality constraints are affine).
However, in one of my class slides it presents a different version of KKT conditions with the additional LICQ (i.e. active inequality constraints and equality constraints have linearly independent gradients). I'm really confused why LICQ is needed here at all. Does requiring LICQ additionally improve or generalise the usual LICQ-free version of KKT? I don't see how it can (the conclusion the slide shows doesn't seem strengthened, despite requiring more). So I'm curious to know where LICQ can come into play. Thanks.
optimization convex-optimization nonlinear-optimization karush-kuhn-tucker
asked Dec 11 '18 at 17:58
VimVim
8,11431348
$endgroup$
$begingroup$
How does LICQ change the KKT conditions other than turning them into necessary conditions?
$endgroup$
– LinAlg
Dec 11 '18 at 18:32
$begingroup$
@LinAlg it seems that in Boyd's book there's no mention of LICQ in the KKT conditions.
$endgroup$
– Vim
Dec 12 '18 at 1:32
$begingroup$
LICQ is an alternative to Slater's condition
$endgroup$
– LinAlg
Dec 12 '18 at 1:37
1
$begingroup$
Vandenberghe and Boyd use Slater's condition rather than LICQ. You need some kind of constraint qualification to make the KKT conditions necessary- there are many constraint qualification conditions.
$endgroup$
– Brian Borchers
Dec 13 '18 at 4:03
$begingroup$
@BrianBorchers thanks. May I ask a converse question: if the problem is convex and $C^1$, KKT conditions are satisfied, but no CQ is assumed, then does it necessarily imply optimality? (Namely are KKT still sufficient?)
$endgroup$
– Vim
Dec 13 '18 at 7:07
|
show 2 more comments
$begingroup$
KKT establishes a set of criteria for differentiable optimisation problems related to strong duality (i.e. when primal optimal equals dual optimal). In particular, KKT conditions are necessary for strong duality in all cases, and also sufficient when the primal problem becomes convex (i.e. when the objective and inequality constraints all become convex and the equality constraints are affine).
However, in one of my class slides it presents a different version of KKT conditions with the additional LICQ (i.e. active inequality constraints and equality constraints have linearly independent gradients). I'm really confused why LICQ is needed here at all. Does requiring LICQ additionally improve or generalise the usual LICQ-free version of KKT? I don't see how it can (the conclusion the slide shows doesn't seem strengthened, despite requiring more). So I'm curious to know where LICQ can come into play. Thanks.
optimization convex-optimization nonlinear-optimization karush-kuhn-tucker
asked Dec 11 '18 at 17:58
VimVim
8,11431348
$endgroup$
KKT establishes a set of criteria for differentiable optimisation problems related to strong duality (i.e. when primal optimal equals dual optimal). In particular, KKT conditions are necessary for strong duality in all cases, and also sufficient when the primal problem becomes convex (i.e. when the objective and inequality constraints all become convex and the equality constraints are affine).
However, in one of my class slides it presents a different version of KKT conditions with the additional LICQ (i.e. active inequality constraints and equality constraints have linearly independent gradients). I'm really confused why LICQ is needed here at all. Does requiring LICQ additionally improve or generalise the usual LICQ-free version of KKT? I don't see how it can (the conclusion the slide shows doesn't seem strengthened, despite requiring more). So I'm curious to know where LICQ can come into play. Thanks.
optimization convex-optimization nonlinear-optimization karush-kuhn-tucker
optimization convex-optimization nonlinear-optimization karush-kuhn-tucker
asked Dec 11 '18 at 17:58
VimVim
8,11431348
asked Dec 11 '18 at 17:58
VimVim
8,11431348
asked Dec 11 '18 at 17:58
VimVim
8,11431348
asked Dec 11 '18 at 17:58
VimVim
8,11431348
asked Dec 11 '18 at 17:58
VimVim
8,11431348
8,11431348
$begingroup$
How does LICQ change the KKT conditions other than turning them into necessary conditions?
$endgroup$
– LinAlg
Dec 11 '18 at 18:32
$begingroup$
@LinAlg it seems that in Boyd's book there's no mention of LICQ in the KKT conditions.
$endgroup$
– Vim
Dec 12 '18 at 1:32
$begingroup$
LICQ is an alternative to Slater's condition
$endgroup$
– LinAlg
Dec 12 '18 at 1:37
1
$begingroup$
Vandenberghe and Boyd use Slater's condition rather than LICQ. You need some kind of constraint qualification to make the KKT conditions necessary- there are many constraint qualification conditions.
$endgroup$
– Brian Borchers
Dec 13 '18 at 4:03
$begingroup$
@BrianBorchers thanks. May I ask a converse question: if the problem is convex and $C^1$, KKT conditions are satisfied, but no CQ is assumed, then does it necessarily imply optimality? (Namely are KKT still sufficient?)
$endgroup$
– Vim
Dec 13 '18 at 7:07
|
show 2 more comments
$begingroup$
How does LICQ change the KKT conditions other than turning them into necessary conditions?
$endgroup$
– LinAlg
Dec 11 '18 at 18:32
$begingroup$
@LinAlg it seems that in Boyd's book there's no mention of LICQ in the KKT conditions.
$endgroup$
– Vim
Dec 12 '18 at 1:32
$begingroup$
LICQ is an alternative to Slater's condition
$endgroup$
– LinAlg
Dec 12 '18 at 1:37
1
$begingroup$
Vandenberghe and Boyd use Slater's condition rather than LICQ. You need some kind of constraint qualification to make the KKT conditions necessary- there are many constraint qualification conditions.
$endgroup$
– Brian Borchers
Dec 13 '18 at 4:03
$begingroup$
@BrianBorchers thanks. May I ask a converse question: if the problem is convex and $C^1$, KKT conditions are satisfied, but no CQ is assumed, then does it necessarily imply optimality? (Namely are KKT still sufficient?)
$endgroup$
– Vim
Dec 13 '18 at 7:07
$begingroup$
How does LICQ change the KKT conditions other than turning them into necessary conditions?
$endgroup$
– LinAlg
Dec 11 '18 at 18:32
$begingroup$
How does LICQ change the KKT conditions other than turning them into necessary conditions?
$endgroup$
– LinAlg
Dec 11 '18 at 18:32
$begingroup$
@LinAlg it seems that in Boyd's book there's no mention of LICQ in the KKT conditions.
$endgroup$
– Vim
Dec 12 '18 at 1:32
$begingroup$
@LinAlg it seems that in Boyd's book there's no mention of LICQ in the KKT conditions.
$endgroup$
– Vim
Dec 12 '18 at 1:32
$begingroup$
LICQ is an alternative to Slater's condition
$endgroup$
– LinAlg
Dec 12 '18 at 1:37
$begingroup$
LICQ is an alternative to Slater's condition
$endgroup$
– LinAlg
Dec 12 '18 at 1:37
1
1
$begingroup$
Vandenberghe and Boyd use Slater's condition rather than LICQ. You need some kind of constraint qualification to make the KKT conditions necessary- there are many constraint qualification conditions.
$endgroup$
– Brian Borchers
Dec 13 '18 at 4:03
$begingroup$
Vandenberghe and Boyd use Slater's condition rather than LICQ. You need some kind of constraint qualification to make the KKT conditions necessary- there are many constraint qualification conditions.
$endgroup$
– Brian Borchers
Dec 13 '18 at 4:03
$begingroup$
@BrianBorchers thanks. May I ask a converse question: if the problem is convex and $C^1$, KKT conditions are satisfied, but no CQ is assumed, then does it necessarily imply optimality? (Namely are KKT still sufficient?)
$endgroup$
– Vim
Dec 13 '18 at 7:07
$begingroup$
@BrianBorchers thanks. May I ask a converse question: if the problem is convex and $C^1$, KKT conditions are satisfied, but no CQ is assumed, then does it necessarily imply optimality? (Namely are KKT still sufficient?)
$endgroup$
– Vim
Dec 13 '18 at 7:07
|
show 2 more comments
1 Answer
1
active
oldest
votes
$begingroup$
It's possible for a convex optimization problem to have an optimal solution but no KKT points. Constraint qualifications such as Slater's condition, LICQ, MFCQ, etc. are necessary to ensure that an optimal solution will satisfy the KKT conditions.
For example, consider the problem
$min x_{2}$
subject to
$(x_{1}-1)^{2}+x_{2}^{2} leq 1$
$(x_{1}+1)^{2}+x_{2}^{2} leq 1$
Here, the only feasible point is $x^{*}_{1}=0$, $x^{*}_{2}=0$. Thus that point is an optimal solution. However, you can check and you'll find that the KKT conditions are not satisfied at $x^{*}$.
answered Dec 13 '18 at 16:29
Brian BorchersBrian Borchers
6,12111320
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3035579%2fwhen-is-licq-useful-in-kkt-conditions%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
It's possible for a convex optimization problem to have an optimal solution but no KKT points. Constraint qualifications such as Slater's condition, LICQ, MFCQ, etc. are necessary to ensure that an optimal solution will satisfy the KKT conditions.
For example, consider the problem
$min x_{2}$
subject to
$(x_{1}-1)^{2}+x_{2}^{2} leq 1$
$(x_{1}+1)^{2}+x_{2}^{2} leq 1$
Here, the only feasible point is $x^{*}_{1}=0$, $x^{*}_{2}=0$. Thus that point is an optimal solution. However, you can check and you'll find that the KKT conditions are not satisfied at $x^{*}$.
answered Dec 13 '18 at 16:29
Brian BorchersBrian Borchers
6,12111320
$endgroup$
add a comment |
$begingroup$
It's possible for a convex optimization problem to have an optimal solution but no KKT points. Constraint qualifications such as Slater's condition, LICQ, MFCQ, etc. are necessary to ensure that an optimal solution will satisfy the KKT conditions.
For example, consider the problem
$min x_{2}$
subject to
$(x_{1}-1)^{2}+x_{2}^{2} leq 1$
$(x_{1}+1)^{2}+x_{2}^{2} leq 1$
Here, the only feasible point is $x^{*}_{1}=0$, $x^{*}_{2}=0$. Thus that point is an optimal solution. However, you can check and you'll find that the KKT conditions are not satisfied at $x^{*}$.
answered Dec 13 '18 at 16:29
Brian BorchersBrian Borchers
6,12111320
$endgroup$
add a comment |
$begingroup$
It's possible for a convex optimization problem to have an optimal solution but no KKT points. Constraint qualifications such as Slater's condition, LICQ, MFCQ, etc. are necessary to ensure that an optimal solution will satisfy the KKT conditions.
For example, consider the problem
$min x_{2}$
subject to
$(x_{1}-1)^{2}+x_{2}^{2} leq 1$
$(x_{1}+1)^{2}+x_{2}^{2} leq 1$
Here, the only feasible point is $x^{*}_{1}=0$, $x^{*}_{2}=0$. Thus that point is an optimal solution. However, you can check and you'll find that the KKT conditions are not satisfied at $x^{*}$.
answered Dec 13 '18 at 16:29
Brian BorchersBrian Borchers
6,12111320
$endgroup$
It's possible for a convex optimization problem to have an optimal solution but no KKT points. Constraint qualifications such as Slater's condition, LICQ, MFCQ, etc. are necessary to ensure that an optimal solution will satisfy the KKT conditions.
For example, consider the problem
$min x_{2}$
subject to
$(x_{1}-1)^{2}+x_{2}^{2} leq 1$
$(x_{1}+1)^{2}+x_{2}^{2} leq 1$
Here, the only feasible point is $x^{*}_{1}=0$, $x^{*}_{2}=0$. Thus that point is an optimal solution. However, you can check and you'll find that the KKT conditions are not satisfied at $x^{*}$.
answered Dec 13 '18 at 16:29
Brian BorchersBrian Borchers
6,12111320
answered Dec 13 '18 at 16:29
Brian BorchersBrian Borchers
6,12111320
answered Dec 13 '18 at 16:29
Brian BorchersBrian Borchers
6,12111320
answered Dec 13 '18 at 16:29
Brian BorchersBrian Borchers
6,12111320
6,12111320
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3035579%2fwhen-is-licq-useful-in-kkt-conditions%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
How does LICQ change the KKT conditions other than turning them into necessary conditions?
$endgroup$
– LinAlg
Dec 11 '18 at 18:32
$begingroup$
@LinAlg it seems that in Boyd's book there's no mention of LICQ in the KKT conditions.
$endgroup$
– Vim
Dec 12 '18 at 1:32
$begingroup$
LICQ is an alternative to Slater's condition
$endgroup$
– LinAlg
Dec 12 '18 at 1:37
1
$begingroup$
Vandenberghe and Boyd use Slater's condition rather than LICQ. You need some kind of constraint qualification to make the KKT conditions necessary- there are many constraint qualification conditions.
$endgroup$
– Brian Borchers
Dec 13 '18 at 4:03
$begingroup$
@BrianBorchers thanks. May I ask a converse question: if the problem is convex and $C^1$, KKT conditions are satisfied, but no CQ is assumed, then does it necessarily imply optimality? (Namely are KKT still sufficient?)
$endgroup$
– Vim
Dec 13 '18 at 7:07