How to imply the vanishing gradient condition in KKT?












1












$begingroup$


In Boyd's Convex Optimisation, the following optimisation problem is considered
$$
begin{align}
minquad & f_0(x)\
text{s.t.}quad & f_i(x)le 0,quad i=1:m,quad minBbb Z_{ge 0}\
& h_i(x) = 0,quad j=1:p,quad pinBbb Z_{ge 0}
end{align}tag{P}
$$

For they time being the functions $f_0,f_{1:m},h_{1:p}:Bbb R^ntoBbb R$ are assumed $C^1$ but not necessarily convex. Let $D$ be the the feasible domain specified by the conditions $f_{1:m}(x)le 0$ and $h_{1:p}(x)=0$. Then the associated Lagrangian is
$$L:Dtimes Bbb R^mtimesBbb R^pni(x,lambda,mu)mapsto f_0(x)+lambda^T f(x) + mu^T h(x)inBbb R$$
where $f:=(f_1,cdots,f_m)^T$ and $h:=(h_1,cdots,h_p)^T$,
and the Lagrange function is thus defined as
$$g:Bbb R^mtimes Bbb R^pni(lambda,mu)mapsto inf_{xin D}L(x,lambda,mu)inBbb R.$$
We then formulate the dual problem (as opposed to the primal (P)) as
$$
begin{align}
maxquad & g(lambda, mu)\
text{s.t.}quad & lambda inBbb R_{ge 0}^m\
quad & muinBbb R^p
end{align}tag{D}
$$

Now, suppose $bar x$ and $(barlambda,barmu)$ are a dual feasible pair for (P) and (D), and suppose that strong duality holds. Then we can show easily that
$$DeclareMathOperator*{argmin}{argmin}
f_0(bar x) = g(barlambda,barmu)=inf_{xin color{red}{D}}L(x,barlambda,barmu)le L(bar x, barlambda,barmu)le f_0(bar x)implies bar x=operatorname*{argmin}_{xincolor{red}{D}}L(x,barlambda,barmu).$$

But then Boyd claims that, "since $bar x$ minimises $L$ over $x$, its gradient must vanish at $bar x$", i.e. that $nabla_x L(bar x,barlambda, barmu)=0$. WHY is this true?



Note that Fermat's lemma may not apply: $bar x$ just minimises $L(cdot,barlambda,barmu)$ within the primal feasible domain $color{red}{D}$, to which $bar x$ is NOT necessarily an interior point, and even $D$ itself may not have non-empty interior in $Bbb R^n$. So why can we conclude the gradient w.r.t. $x$ vanishes at $bar x$?



Thank you.






As LittleO kindly pointed out, my problem is actually a non-problem that arose from the confusion over the definition of $D$: it is NOT the feasible region of $(P)$; rather, it is the intersection of domains of $f$ and $h$ which are assumed open (hence making $D$ open too).








share|cite|improve this question











$endgroup$












  • $begingroup$
    @littleO Sorry I seem to have made a hasty assumption about its definition. Indeed Boyd has defined the dom thing as the domain instead of the feasible region.
    $endgroup$
    – Vim
    Dec 10 '18 at 6:46
















1












$begingroup$


In Boyd's Convex Optimisation, the following optimisation problem is considered
$$
begin{align}
minquad & f_0(x)\
text{s.t.}quad & f_i(x)le 0,quad i=1:m,quad minBbb Z_{ge 0}\
& h_i(x) = 0,quad j=1:p,quad pinBbb Z_{ge 0}
end{align}tag{P}
$$

For they time being the functions $f_0,f_{1:m},h_{1:p}:Bbb R^ntoBbb R$ are assumed $C^1$ but not necessarily convex. Let $D$ be the the feasible domain specified by the conditions $f_{1:m}(x)le 0$ and $h_{1:p}(x)=0$. Then the associated Lagrangian is
$$L:Dtimes Bbb R^mtimesBbb R^pni(x,lambda,mu)mapsto f_0(x)+lambda^T f(x) + mu^T h(x)inBbb R$$
where $f:=(f_1,cdots,f_m)^T$ and $h:=(h_1,cdots,h_p)^T$,
and the Lagrange function is thus defined as
$$g:Bbb R^mtimes Bbb R^pni(lambda,mu)mapsto inf_{xin D}L(x,lambda,mu)inBbb R.$$
We then formulate the dual problem (as opposed to the primal (P)) as
$$
begin{align}
maxquad & g(lambda, mu)\
text{s.t.}quad & lambda inBbb R_{ge 0}^m\
quad & muinBbb R^p
end{align}tag{D}
$$

Now, suppose $bar x$ and $(barlambda,barmu)$ are a dual feasible pair for (P) and (D), and suppose that strong duality holds. Then we can show easily that
$$DeclareMathOperator*{argmin}{argmin}
f_0(bar x) = g(barlambda,barmu)=inf_{xin color{red}{D}}L(x,barlambda,barmu)le L(bar x, barlambda,barmu)le f_0(bar x)implies bar x=operatorname*{argmin}_{xincolor{red}{D}}L(x,barlambda,barmu).$$

But then Boyd claims that, "since $bar x$ minimises $L$ over $x$, its gradient must vanish at $bar x$", i.e. that $nabla_x L(bar x,barlambda, barmu)=0$. WHY is this true?



Note that Fermat's lemma may not apply: $bar x$ just minimises $L(cdot,barlambda,barmu)$ within the primal feasible domain $color{red}{D}$, to which $bar x$ is NOT necessarily an interior point, and even $D$ itself may not have non-empty interior in $Bbb R^n$. So why can we conclude the gradient w.r.t. $x$ vanishes at $bar x$?



Thank you.






As LittleO kindly pointed out, my problem is actually a non-problem that arose from the confusion over the definition of $D$: it is NOT the feasible region of $(P)$; rather, it is the intersection of domains of $f$ and $h$ which are assumed open (hence making $D$ open too).








share|cite|improve this question











$endgroup$












  • $begingroup$
    @littleO Sorry I seem to have made a hasty assumption about its definition. Indeed Boyd has defined the dom thing as the domain instead of the feasible region.
    $endgroup$
    – Vim
    Dec 10 '18 at 6:46














1












1








1


1



$begingroup$


In Boyd's Convex Optimisation, the following optimisation problem is considered
$$
begin{align}
minquad & f_0(x)\
text{s.t.}quad & f_i(x)le 0,quad i=1:m,quad minBbb Z_{ge 0}\
& h_i(x) = 0,quad j=1:p,quad pinBbb Z_{ge 0}
end{align}tag{P}
$$

For they time being the functions $f_0,f_{1:m},h_{1:p}:Bbb R^ntoBbb R$ are assumed $C^1$ but not necessarily convex. Let $D$ be the the feasible domain specified by the conditions $f_{1:m}(x)le 0$ and $h_{1:p}(x)=0$. Then the associated Lagrangian is
$$L:Dtimes Bbb R^mtimesBbb R^pni(x,lambda,mu)mapsto f_0(x)+lambda^T f(x) + mu^T h(x)inBbb R$$
where $f:=(f_1,cdots,f_m)^T$ and $h:=(h_1,cdots,h_p)^T$,
and the Lagrange function is thus defined as
$$g:Bbb R^mtimes Bbb R^pni(lambda,mu)mapsto inf_{xin D}L(x,lambda,mu)inBbb R.$$
We then formulate the dual problem (as opposed to the primal (P)) as
$$
begin{align}
maxquad & g(lambda, mu)\
text{s.t.}quad & lambda inBbb R_{ge 0}^m\
quad & muinBbb R^p
end{align}tag{D}
$$

Now, suppose $bar x$ and $(barlambda,barmu)$ are a dual feasible pair for (P) and (D), and suppose that strong duality holds. Then we can show easily that
$$DeclareMathOperator*{argmin}{argmin}
f_0(bar x) = g(barlambda,barmu)=inf_{xin color{red}{D}}L(x,barlambda,barmu)le L(bar x, barlambda,barmu)le f_0(bar x)implies bar x=operatorname*{argmin}_{xincolor{red}{D}}L(x,barlambda,barmu).$$

But then Boyd claims that, "since $bar x$ minimises $L$ over $x$, its gradient must vanish at $bar x$", i.e. that $nabla_x L(bar x,barlambda, barmu)=0$. WHY is this true?



Note that Fermat's lemma may not apply: $bar x$ just minimises $L(cdot,barlambda,barmu)$ within the primal feasible domain $color{red}{D}$, to which $bar x$ is NOT necessarily an interior point, and even $D$ itself may not have non-empty interior in $Bbb R^n$. So why can we conclude the gradient w.r.t. $x$ vanishes at $bar x$?



Thank you.






As LittleO kindly pointed out, my problem is actually a non-problem that arose from the confusion over the definition of $D$: it is NOT the feasible region of $(P)$; rather, it is the intersection of domains of $f$ and $h$ which are assumed open (hence making $D$ open too).








share|cite|improve this question











$endgroup$




In Boyd's Convex Optimisation, the following optimisation problem is considered
$$
begin{align}
minquad & f_0(x)\
text{s.t.}quad & f_i(x)le 0,quad i=1:m,quad minBbb Z_{ge 0}\
& h_i(x) = 0,quad j=1:p,quad pinBbb Z_{ge 0}
end{align}tag{P}
$$

For they time being the functions $f_0,f_{1:m},h_{1:p}:Bbb R^ntoBbb R$ are assumed $C^1$ but not necessarily convex. Let $D$ be the the feasible domain specified by the conditions $f_{1:m}(x)le 0$ and $h_{1:p}(x)=0$. Then the associated Lagrangian is
$$L:Dtimes Bbb R^mtimesBbb R^pni(x,lambda,mu)mapsto f_0(x)+lambda^T f(x) + mu^T h(x)inBbb R$$
where $f:=(f_1,cdots,f_m)^T$ and $h:=(h_1,cdots,h_p)^T$,
and the Lagrange function is thus defined as
$$g:Bbb R^mtimes Bbb R^pni(lambda,mu)mapsto inf_{xin D}L(x,lambda,mu)inBbb R.$$
We then formulate the dual problem (as opposed to the primal (P)) as
$$
begin{align}
maxquad & g(lambda, mu)\
text{s.t.}quad & lambda inBbb R_{ge 0}^m\
quad & muinBbb R^p
end{align}tag{D}
$$

Now, suppose $bar x$ and $(barlambda,barmu)$ are a dual feasible pair for (P) and (D), and suppose that strong duality holds. Then we can show easily that
$$DeclareMathOperator*{argmin}{argmin}
f_0(bar x) = g(barlambda,barmu)=inf_{xin color{red}{D}}L(x,barlambda,barmu)le L(bar x, barlambda,barmu)le f_0(bar x)implies bar x=operatorname*{argmin}_{xincolor{red}{D}}L(x,barlambda,barmu).$$

But then Boyd claims that, "since $bar x$ minimises $L$ over $x$, its gradient must vanish at $bar x$", i.e. that $nabla_x L(bar x,barlambda, barmu)=0$. WHY is this true?



Note that Fermat's lemma may not apply: $bar x$ just minimises $L(cdot,barlambda,barmu)$ within the primal feasible domain $color{red}{D}$, to which $bar x$ is NOT necessarily an interior point, and even $D$ itself may not have non-empty interior in $Bbb R^n$. So why can we conclude the gradient w.r.t. $x$ vanishes at $bar x$?



Thank you.






As LittleO kindly pointed out, my problem is actually a non-problem that arose from the confusion over the definition of $D$: it is NOT the feasible region of $(P)$; rather, it is the intersection of domains of $f$ and $h$ which are assumed open (hence making $D$ open too).





real-analysis optimization convex-optimization karush-kuhn-tucker






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Dec 10 '18 at 6:49







Vim

















asked Dec 10 '18 at 6:23









VimVim

8,12931348




8,12931348












  • $begingroup$
    @littleO Sorry I seem to have made a hasty assumption about its definition. Indeed Boyd has defined the dom thing as the domain instead of the feasible region.
    $endgroup$
    – Vim
    Dec 10 '18 at 6:46


















  • $begingroup$
    @littleO Sorry I seem to have made a hasty assumption about its definition. Indeed Boyd has defined the dom thing as the domain instead of the feasible region.
    $endgroup$
    – Vim
    Dec 10 '18 at 6:46
















$begingroup$
@littleO Sorry I seem to have made a hasty assumption about its definition. Indeed Boyd has defined the dom thing as the domain instead of the feasible region.
$endgroup$
– Vim
Dec 10 '18 at 6:46




$begingroup$
@littleO Sorry I seem to have made a hasty assumption about its definition. Indeed Boyd has defined the dom thing as the domain instead of the feasible region.
$endgroup$
– Vim
Dec 10 '18 at 6:46










1 Answer
1






active

oldest

votes


















2












$begingroup$

$D$ is not the set of all points $x$ where the constraints are satisfied. Rather, as stated at the beginning of section 5.1, $D = cap_i textbf{dom } f_i , cap , cap _i textbf{dom } h_i$.



At the beginning of section 5.5.3, the book assumes that the functions $f_i$ and $h_i$ have open domains. It follows that $D$ is an open set. Thus, Fermat's lemma does apply.



By the way, one way to motivate the Lagrangian intuitively is that we are attempting to replace the hard constraints (which are difficult to handle) with linear penalty terms in the objective function (which are hopefully easy to handle). By introducing the Lagrangian, we hope to solve an unconstrained minimization problem rather than a constrained problem. (But, this strategy requires us to figure out the correct values of the Lagrangian multipliers -- which leads us to solving the dual problem.)






share|cite|improve this answer











$endgroup$













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


    }
    });














    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3033537%2fhow-to-imply-the-vanishing-gradient-condition-in-kkt%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









    2












    $begingroup$

    $D$ is not the set of all points $x$ where the constraints are satisfied. Rather, as stated at the beginning of section 5.1, $D = cap_i textbf{dom } f_i , cap , cap _i textbf{dom } h_i$.



    At the beginning of section 5.5.3, the book assumes that the functions $f_i$ and $h_i$ have open domains. It follows that $D$ is an open set. Thus, Fermat's lemma does apply.



    By the way, one way to motivate the Lagrangian intuitively is that we are attempting to replace the hard constraints (which are difficult to handle) with linear penalty terms in the objective function (which are hopefully easy to handle). By introducing the Lagrangian, we hope to solve an unconstrained minimization problem rather than a constrained problem. (But, this strategy requires us to figure out the correct values of the Lagrangian multipliers -- which leads us to solving the dual problem.)






    share|cite|improve this answer











    $endgroup$


















      2












      $begingroup$

      $D$ is not the set of all points $x$ where the constraints are satisfied. Rather, as stated at the beginning of section 5.1, $D = cap_i textbf{dom } f_i , cap , cap _i textbf{dom } h_i$.



      At the beginning of section 5.5.3, the book assumes that the functions $f_i$ and $h_i$ have open domains. It follows that $D$ is an open set. Thus, Fermat's lemma does apply.



      By the way, one way to motivate the Lagrangian intuitively is that we are attempting to replace the hard constraints (which are difficult to handle) with linear penalty terms in the objective function (which are hopefully easy to handle). By introducing the Lagrangian, we hope to solve an unconstrained minimization problem rather than a constrained problem. (But, this strategy requires us to figure out the correct values of the Lagrangian multipliers -- which leads us to solving the dual problem.)






      share|cite|improve this answer











      $endgroup$
















        2












        2








        2





        $begingroup$

        $D$ is not the set of all points $x$ where the constraints are satisfied. Rather, as stated at the beginning of section 5.1, $D = cap_i textbf{dom } f_i , cap , cap _i textbf{dom } h_i$.



        At the beginning of section 5.5.3, the book assumes that the functions $f_i$ and $h_i$ have open domains. It follows that $D$ is an open set. Thus, Fermat's lemma does apply.



        By the way, one way to motivate the Lagrangian intuitively is that we are attempting to replace the hard constraints (which are difficult to handle) with linear penalty terms in the objective function (which are hopefully easy to handle). By introducing the Lagrangian, we hope to solve an unconstrained minimization problem rather than a constrained problem. (But, this strategy requires us to figure out the correct values of the Lagrangian multipliers -- which leads us to solving the dual problem.)






        share|cite|improve this answer











        $endgroup$



        $D$ is not the set of all points $x$ where the constraints are satisfied. Rather, as stated at the beginning of section 5.1, $D = cap_i textbf{dom } f_i , cap , cap _i textbf{dom } h_i$.



        At the beginning of section 5.5.3, the book assumes that the functions $f_i$ and $h_i$ have open domains. It follows that $D$ is an open set. Thus, Fermat's lemma does apply.



        By the way, one way to motivate the Lagrangian intuitively is that we are attempting to replace the hard constraints (which are difficult to handle) with linear penalty terms in the objective function (which are hopefully easy to handle). By introducing the Lagrangian, we hope to solve an unconstrained minimization problem rather than a constrained problem. (But, this strategy requires us to figure out the correct values of the Lagrangian multipliers -- which leads us to solving the dual problem.)







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited Dec 10 '18 at 7:10

























        answered Dec 10 '18 at 6:45









        littleOlittleO

        29.8k646109




        29.8k646109






























            draft saved

            draft discarded




















































            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.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3033537%2fhow-to-imply-the-vanishing-gradient-condition-in-kkt%23new-answer', 'question_page');
            }
            );

            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







            Popular posts from this blog

            Plaza Victoria

            Puebla de Zaragoza

            Musa