Duality gap in non-convex optimization: Do KKT conditions+constraint qualification imply strong duality? Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern)Help me organize these concepts — KKT conditions and dual problemRecovering the solution of optimization problem from the dual problemStrong duality for nonconvex quadratic program (with multiple constraints)KKT conditions for a convex optimization problem with a L1-penalty and box constraintsDuality theory and nonlinear optimizationWhen do constraint qualifications imply strong duality?Convex optimization and strong dualityIs KKT conditions necessary and sufficient for any convex problems?KKT conditions for general conic optimization problemDuality gap in polynomial optimization problem Lasserre relaxation
Why did Bronn offer to be Tyrion Lannister's champion in trial by combat?
How can I list files in reverse time order by a command and pass them as arguments to another command?
"Destructive power" carried by a B-52?
3D Masyu - A Die
Table formatting with tabularx?
How do Java 8 default methods hеlp with lambdas?
How do you cope with tons of web fonts when copying and pasting from web pages?
Who's this lady in the war room?
Random body shuffle every night—can we still function?
Dinosaur Word Search, Letter Solve, and Unscramble
How does Billy Russo acquire his 'Jigsaw' mask?
Magento 2 - Add additional attributes in register
Was the pager message from Nick Fury to Captain Marvel unnecessary?
Understanding piped commands in GNU/Linux
Magento 2 Editing phtml files in Production Mode
.bashrc alias for a command with fixed second parameter
Is it OK if I do not take the receipt in Germany?
How did 'ликвиди́ровать' semantically shift to mean 'abolish' and 'destroy, kill'?
How to name indistinguishable henchmen in a screenplay?
Can I take recommendation from someone I met at a conference?
Is there night in Alpha Complex?
Who's the Giant Batman in the back of this dark knights metal Batman picture?
How do I find my Spellcasting Ability for my D&D character?
The Nth Gryphon Number
Duality gap in non-convex optimization: Do KKT conditions+constraint qualification imply strong duality?
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern)Help me organize these concepts — KKT conditions and dual problemRecovering the solution of optimization problem from the dual problemStrong duality for nonconvex quadratic program (with multiple constraints)KKT conditions for a convex optimization problem with a L1-penalty and box constraintsDuality theory and nonlinear optimizationWhen do constraint qualifications imply strong duality?Convex optimization and strong dualityIs KKT conditions necessary and sufficient for any convex problems?KKT conditions for general conic optimization problemDuality gap in polynomial optimization problem Lasserre relaxation
$begingroup$
Consider the non-convex optimization problem:
$$undersetxin mathbbR^nmin ~f(x) \
mboxs.t.~h_i(x)=0 ~~~mboxfor~~~i=1,ldots,p \
~~~~~~ g_j(x)leq0 ~~~mboxfor~~~j=1,ldots,m$$
where $f(x),h_i(x)$ and $g_j(x)$ are continuously differential functions, but not necessarily convex. Let's say $barx$ is a global minimizer of the problem, and $barx$ is a KKT point (i.e., the KKT conditions hold at $barx$) with some constraint qualification (e.g: Mangasarian-Fromovitz constraint qualification holds at $barx$). What can be said about the duality gap (assuming that the dual solution exists and is attainable)? Does strong duality hold?
optimization nonlinear-optimization duality-theorems non-convex-optimization
asked Apr 2 at 17:19
Mateus de FreitasMateus de Freitas
84
$endgroup$
add a comment |
$begingroup$
Consider the non-convex optimization problem:
$$undersetxin mathbbR^nmin ~f(x) \
mboxs.t.~h_i(x)=0 ~~~mboxfor~~~i=1,ldots,p \
~~~~~~ g_j(x)leq0 ~~~mboxfor~~~j=1,ldots,m$$
where $f(x),h_i(x)$ and $g_j(x)$ are continuously differential functions, but not necessarily convex. Let's say $barx$ is a global minimizer of the problem, and $barx$ is a KKT point (i.e., the KKT conditions hold at $barx$) with some constraint qualification (e.g: Mangasarian-Fromovitz constraint qualification holds at $barx$). What can be said about the duality gap (assuming that the dual solution exists and is attainable)? Does strong duality hold?
optimization nonlinear-optimization duality-theorems non-convex-optimization
asked Apr 2 at 17:19
Mateus de FreitasMateus de Freitas
84
$endgroup$
add a comment |
$begingroup$
Consider the non-convex optimization problem:
$$undersetxin mathbbR^nmin ~f(x) \
mboxs.t.~h_i(x)=0 ~~~mboxfor~~~i=1,ldots,p \
~~~~~~ g_j(x)leq0 ~~~mboxfor~~~j=1,ldots,m$$
where $f(x),h_i(x)$ and $g_j(x)$ are continuously differential functions, but not necessarily convex. Let's say $barx$ is a global minimizer of the problem, and $barx$ is a KKT point (i.e., the KKT conditions hold at $barx$) with some constraint qualification (e.g: Mangasarian-Fromovitz constraint qualification holds at $barx$). What can be said about the duality gap (assuming that the dual solution exists and is attainable)? Does strong duality hold?
optimization nonlinear-optimization duality-theorems non-convex-optimization
asked Apr 2 at 17:19
Mateus de FreitasMateus de Freitas
84
$endgroup$
Consider the non-convex optimization problem:
$$undersetxin mathbbR^nmin ~f(x) \
mboxs.t.~h_i(x)=0 ~~~mboxfor~~~i=1,ldots,p \
~~~~~~ g_j(x)leq0 ~~~mboxfor~~~j=1,ldots,m$$
where $f(x),h_i(x)$ and $g_j(x)$ are continuously differential functions, but not necessarily convex. Let's say $barx$ is a global minimizer of the problem, and $barx$ is a KKT point (i.e., the KKT conditions hold at $barx$) with some constraint qualification (e.g: Mangasarian-Fromovitz constraint qualification holds at $barx$). What can be said about the duality gap (assuming that the dual solution exists and is attainable)? Does strong duality hold?
optimization nonlinear-optimization duality-theorems non-convex-optimization
optimization nonlinear-optimization duality-theorems non-convex-optimization
asked Apr 2 at 17:19
Mateus de FreitasMateus de Freitas
84
asked Apr 2 at 17:19
Mateus de FreitasMateus de Freitas
84
asked Apr 2 at 17:19
Mateus de FreitasMateus de Freitas
84
asked Apr 2 at 17:19
Mateus de FreitasMateus de Freitas
84
asked Apr 2 at 17:19
Mateus de FreitasMateus de Freitas
84
84
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Presume $f(x),h_i(x)$ and $g_j(x)$ are continuously differential function, then
A constraint qualification is necessary to guarantee that local minimum implies KKT point. I.e., constraint qualification is required to make KKT conditions necessary for minimum.
If one or more of $f(x),h_i(x)$ and $g_j(x)$ are non-convex, then (in general) strong duality does not necessarily hold. That's what makes non-convex optimization difficult.
See https://en.wikipedia.org/wiki/Strong_duality
answered Apr 3 at 0:36
Mark L. StoneMark L. Stone
1,99558
$endgroup$
add a comment |
Your Answer
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%2f3172139%2fduality-gap-in-non-convex-optimization-do-kkt-conditionsconstraint-qualificati%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$
Presume $f(x),h_i(x)$ and $g_j(x)$ are continuously differential function, then
A constraint qualification is necessary to guarantee that local minimum implies KKT point. I.e., constraint qualification is required to make KKT conditions necessary for minimum.
If one or more of $f(x),h_i(x)$ and $g_j(x)$ are non-convex, then (in general) strong duality does not necessarily hold. That's what makes non-convex optimization difficult.
See https://en.wikipedia.org/wiki/Strong_duality
answered Apr 3 at 0:36
Mark L. StoneMark L. Stone
1,99558
$endgroup$
add a comment |
$begingroup$
Presume $f(x),h_i(x)$ and $g_j(x)$ are continuously differential function, then
A constraint qualification is necessary to guarantee that local minimum implies KKT point. I.e., constraint qualification is required to make KKT conditions necessary for minimum.
If one or more of $f(x),h_i(x)$ and $g_j(x)$ are non-convex, then (in general) strong duality does not necessarily hold. That's what makes non-convex optimization difficult.
See https://en.wikipedia.org/wiki/Strong_duality
answered Apr 3 at 0:36
Mark L. StoneMark L. Stone
1,99558
$endgroup$
add a comment |
$begingroup$
Presume $f(x),h_i(x)$ and $g_j(x)$ are continuously differential function, then
A constraint qualification is necessary to guarantee that local minimum implies KKT point. I.e., constraint qualification is required to make KKT conditions necessary for minimum.
If one or more of $f(x),h_i(x)$ and $g_j(x)$ are non-convex, then (in general) strong duality does not necessarily hold. That's what makes non-convex optimization difficult.
See https://en.wikipedia.org/wiki/Strong_duality
answered Apr 3 at 0:36
Mark L. StoneMark L. Stone
1,99558
$endgroup$
Presume $f(x),h_i(x)$ and $g_j(x)$ are continuously differential function, then
A constraint qualification is necessary to guarantee that local minimum implies KKT point. I.e., constraint qualification is required to make KKT conditions necessary for minimum.
If one or more of $f(x),h_i(x)$ and $g_j(x)$ are non-convex, then (in general) strong duality does not necessarily hold. That's what makes non-convex optimization difficult.
See https://en.wikipedia.org/wiki/Strong_duality
answered Apr 3 at 0:36
Mark L. StoneMark L. Stone
1,99558
answered Apr 3 at 0:36
Mark L. StoneMark L. Stone
1,99558
answered Apr 3 at 0:36
Mark L. StoneMark L. Stone
1,99558
answered Apr 3 at 0:36
Mark L. StoneMark L. Stone
1,99558
1,99558
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%2f3172139%2fduality-gap-in-non-convex-optimization-do-kkt-conditionsconstraint-qualificati%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
