Dgdrxrt

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?

0

$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

share|cite|improve this question

asked Apr 2 at 17:19

Mateus de FreitasMateus de Freitas

84

$endgroup$

add a comment | 

0

$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

share|cite|improve this question

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

share|cite|improve this question

asked Apr 2 at 17:19

Mateus de FreitasMateus de Freitas

84

$endgroup$

share|cite|improve this question

asked Apr 2 at 17:19

Mateus de FreitasMateus de Freitas

84

share|cite|improve this question

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

1 Answer
1

active

oldest

votes

0

$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

share|cite|improve this answer

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
);



);

draft saved

draft discarded

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

Name

Email

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

Name

Email

Required, but never shown

0

$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

share|cite|improve this answer

answered Apr 3 at 0:36

Mark L. StoneMark L. Stone

1,99558

$endgroup$

add a comment | 

0

$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

share|cite|improve this answer

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

share|cite|improve this answer

answered Apr 3 at 0:36

Mark L. StoneMark L. Stone

1,99558

$endgroup$

share|cite|improve this answer

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