Convex optimisation with nonconvex constraint function

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
0
down vote

favorite
1












May I ask for a convex optimisation problem (convex/concave objective with convex feasible region), if some of the constraint function is not convex, is kkt still sufficient and necessary for optimality (under slater condition)?




optimization convex-optimization non-convex-optimization




share|cite|improve this question


















  • 1




    With constraint qualification, KKT will be necessary, in general not sufficient.
    – user251257
    Nov 28 '16 at 20:01






  • 1




    The condition "some of the constraint function is not convex" is not sufficient information to rule out a possiblility of rewriting the problem so that it becomes a convex optimization problem. As you seem to point out, the key would be arranging for the feasible reason to be convex (which might or might not be the case when one or more constraint functions are not convex, as stated).
    – hardmath
    Nov 28 '16 at 20:01






  • 1




    If you manage to find a KKT point where no non-convex constraints are active then it is the global minimum.
    – A.Γ.
    Nov 28 '16 at 20:15











  • It's not a convex optimization problem if even one of the constraint functions is nonconvex. That is the case even if the feasible region is a convex set.
    – Michael Grant
    Nov 29 '16 at 3:36











  • I don't think you can reasonably claim adherence to a Slater condition with a non-convex constraint, at least not in general.
    – Michael Grant
    Nov 29 '16 at 3:39















up vote
0
down vote

favorite
1












May I ask for a convex optimisation problem (convex/concave objective with convex feasible region), if some of the constraint function is not convex, is kkt still sufficient and necessary for optimality (under slater condition)?




optimization convex-optimization non-convex-optimization




share|cite|improve this question


















  • 1




    With constraint qualification, KKT will be necessary, in general not sufficient.
    – user251257
    Nov 28 '16 at 20:01






  • 1




    The condition "some of the constraint function is not convex" is not sufficient information to rule out a possiblility of rewriting the problem so that it becomes a convex optimization problem. As you seem to point out, the key would be arranging for the feasible reason to be convex (which might or might not be the case when one or more constraint functions are not convex, as stated).
    – hardmath
    Nov 28 '16 at 20:01






  • 1




    If you manage to find a KKT point where no non-convex constraints are active then it is the global minimum.
    – A.Γ.
    Nov 28 '16 at 20:15











  • It's not a convex optimization problem if even one of the constraint functions is nonconvex. That is the case even if the feasible region is a convex set.
    – Michael Grant
    Nov 29 '16 at 3:36











  • I don't think you can reasonably claim adherence to a Slater condition with a non-convex constraint, at least not in general.
    – Michael Grant
    Nov 29 '16 at 3:39













up vote
0
down vote

favorite
1









up vote
0
down vote

favorite
1






1





May I ask for a convex optimisation problem (convex/concave objective with convex feasible region), if some of the constraint function is not convex, is kkt still sufficient and necessary for optimality (under slater condition)?




optimization convex-optimization non-convex-optimization




share|cite|improve this question














May I ask for a convex optimisation problem (convex/concave objective with convex feasible region), if some of the constraint function is not convex, is kkt still sufficient and necessary for optimality (under slater condition)?





optimization convex-optimization non-convex-optimization





share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Jul 10 at 6:56









Rodrigo de Azevedo

12.6k41751




12.6k41751










asked Nov 28 '16 at 19:55









user112758

1776




1776







  • 1




    With constraint qualification, KKT will be necessary, in general not sufficient.
    – user251257
    Nov 28 '16 at 20:01






  • 1




    The condition "some of the constraint function is not convex" is not sufficient information to rule out a possiblility of rewriting the problem so that it becomes a convex optimization problem. As you seem to point out, the key would be arranging for the feasible reason to be convex (which might or might not be the case when one or more constraint functions are not convex, as stated).
    – hardmath
    Nov 28 '16 at 20:01






  • 1




    If you manage to find a KKT point where no non-convex constraints are active then it is the global minimum.
    – A.Γ.
    Nov 28 '16 at 20:15











  • It's not a convex optimization problem if even one of the constraint functions is nonconvex. That is the case even if the feasible region is a convex set.
    – Michael Grant
    Nov 29 '16 at 3:36











  • I don't think you can reasonably claim adherence to a Slater condition with a non-convex constraint, at least not in general.
    – Michael Grant
    Nov 29 '16 at 3:39













  • 1




    With constraint qualification, KKT will be necessary, in general not sufficient.
    – user251257
    Nov 28 '16 at 20:01






  • 1




    The condition "some of the constraint function is not convex" is not sufficient information to rule out a possiblility of rewriting the problem so that it becomes a convex optimization problem. As you seem to point out, the key would be arranging for the feasible reason to be convex (which might or might not be the case when one or more constraint functions are not convex, as stated).
    – hardmath
    Nov 28 '16 at 20:01






  • 1




    If you manage to find a KKT point where no non-convex constraints are active then it is the global minimum.
    – A.Γ.
    Nov 28 '16 at 20:15











  • It's not a convex optimization problem if even one of the constraint functions is nonconvex. That is the case even if the feasible region is a convex set.
    – Michael Grant
    Nov 29 '16 at 3:36











  • I don't think you can reasonably claim adherence to a Slater condition with a non-convex constraint, at least not in general.
    – Michael Grant
    Nov 29 '16 at 3:39








1




1




With constraint qualification, KKT will be necessary, in general not sufficient.
– user251257
Nov 28 '16 at 20:01




With constraint qualification, KKT will be necessary, in general not sufficient.
– user251257
Nov 28 '16 at 20:01




1




1




The condition "some of the constraint function is not convex" is not sufficient information to rule out a possiblility of rewriting the problem so that it becomes a convex optimization problem. As you seem to point out, the key would be arranging for the feasible reason to be convex (which might or might not be the case when one or more constraint functions are not convex, as stated).
– hardmath
Nov 28 '16 at 20:01




The condition "some of the constraint function is not convex" is not sufficient information to rule out a possiblility of rewriting the problem so that it becomes a convex optimization problem. As you seem to point out, the key would be arranging for the feasible reason to be convex (which might or might not be the case when one or more constraint functions are not convex, as stated).
– hardmath
Nov 28 '16 at 20:01




1




1




If you manage to find a KKT point where no non-convex constraints are active then it is the global minimum.
– A.Γ.
Nov 28 '16 at 20:15





If you manage to find a KKT point where no non-convex constraints are active then it is the global minimum.
– A.Γ.
Nov 28 '16 at 20:15













It's not a convex optimization problem if even one of the constraint functions is nonconvex. That is the case even if the feasible region is a convex set.
– Michael Grant
Nov 29 '16 at 3:36





It's not a convex optimization problem if even one of the constraint functions is nonconvex. That is the case even if the feasible region is a convex set.
– Michael Grant
Nov 29 '16 at 3:36













I don't think you can reasonably claim adherence to a Slater condition with a non-convex constraint, at least not in general.
– Michael Grant
Nov 29 '16 at 3:39





I don't think you can reasonably claim adherence to a Slater condition with a non-convex constraint, at least not in general.
– Michael Grant
Nov 29 '16 at 3:39











1 Answer
1






active

oldest

votes

















up vote
0
down vote













So long as the (min) objective function is convex and the feasible region is convex, then the solution is not affected by some (or all) constraints being written in a non-convex form.



The constraints affect the solution's validity only by their description of the feasible region. In particular a non-convex constraint can be added to a problem, and if the new constraint happens to be satisfied on the feasible region already determined by earlier constraints, it does not affect the solution at all.



In other cases one might express a convex feasible region using a non-convex function. For example, we might have constraints:



$$ beginalign* x &ge 0 \
sqrtx &le 2 endalign* $$



Because these constraints define the convex region $x in [0,4]$, the choice to present that feasible region using the non-convex square root function does not invalidate the use of criteria suitable for convex optimization problems. One can in principle always rewrite the constraints that determine a convex region using convex functions.






share|cite|improve this answer




















    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',
    convertImagesToLinks: true,
    noModals: false,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    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%2f2034786%2fconvex-optimisation-with-nonconvex-constraint-function%23new-answer', 'question_page');

    );

    Post as a guest

















    1 Answer
    1






    active

    oldest

    votes








    1 Answer
    1






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes








    up vote
    0
    down vote













    So long as the (min) objective function is convex and the feasible region is convex, then the solution is not affected by some (or all) constraints being written in a non-convex form.



    The constraints affect the solution's validity only by their description of the feasible region. In particular a non-convex constraint can be added to a problem, and if the new constraint happens to be satisfied on the feasible region already determined by earlier constraints, it does not affect the solution at all.



    In other cases one might express a convex feasible region using a non-convex function. For example, we might have constraints:



    $$ beginalign* x &ge 0 \
    sqrtx &le 2 endalign* $$



    Because these constraints define the convex region $x in [0,4]$, the choice to present that feasible region using the non-convex square root function does not invalidate the use of criteria suitable for convex optimization problems. One can in principle always rewrite the constraints that determine a convex region using convex functions.






    share|cite|improve this answer
























      up vote
      0
      down vote













      So long as the (min) objective function is convex and the feasible region is convex, then the solution is not affected by some (or all) constraints being written in a non-convex form.



      The constraints affect the solution's validity only by their description of the feasible region. In particular a non-convex constraint can be added to a problem, and if the new constraint happens to be satisfied on the feasible region already determined by earlier constraints, it does not affect the solution at all.



      In other cases one might express a convex feasible region using a non-convex function. For example, we might have constraints:



      $$ beginalign* x &ge 0 \
      sqrtx &le 2 endalign* $$



      Because these constraints define the convex region $x in [0,4]$, the choice to present that feasible region using the non-convex square root function does not invalidate the use of criteria suitable for convex optimization problems. One can in principle always rewrite the constraints that determine a convex region using convex functions.






      share|cite|improve this answer






















        up vote
        0
        down vote










        up vote
        0
        down vote









        So long as the (min) objective function is convex and the feasible region is convex, then the solution is not affected by some (or all) constraints being written in a non-convex form.



        The constraints affect the solution's validity only by their description of the feasible region. In particular a non-convex constraint can be added to a problem, and if the new constraint happens to be satisfied on the feasible region already determined by earlier constraints, it does not affect the solution at all.



        In other cases one might express a convex feasible region using a non-convex function. For example, we might have constraints:



        $$ beginalign* x &ge 0 \
        sqrtx &le 2 endalign* $$



        Because these constraints define the convex region $x in [0,4]$, the choice to present that feasible region using the non-convex square root function does not invalidate the use of criteria suitable for convex optimization problems. One can in principle always rewrite the constraints that determine a convex region using convex functions.






        share|cite|improve this answer












        So long as the (min) objective function is convex and the feasible region is convex, then the solution is not affected by some (or all) constraints being written in a non-convex form.



        The constraints affect the solution's validity only by their description of the feasible region. In particular a non-convex constraint can be added to a problem, and if the new constraint happens to be satisfied on the feasible region already determined by earlier constraints, it does not affect the solution at all.



        In other cases one might express a convex feasible region using a non-convex function. For example, we might have constraints:



        $$ beginalign* x &ge 0 \
        sqrtx &le 2 endalign* $$



        Because these constraints define the convex region $x in [0,4]$, the choice to present that feasible region using the non-convex square root function does not invalidate the use of criteria suitable for convex optimization problems. One can in principle always rewrite the constraints that determine a convex region using convex functions.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered Nov 30 '16 at 23:04









        hardmath

        28.2k94693




        28.2k94693






















             

            draft saved


            draft discarded


























             


            draft saved


            draft discarded














            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2034786%2fconvex-optimisation-with-nonconvex-constraint-function%23new-answer', 'question_page');

            );

            Post as a guest
































































            -

            這個網誌中的熱門文章

            How to combine Bézier curves to a surface?

            圖片
            Clash Royale CLAN TAG #URR8PPP up vote 2 down vote favorite My aim is to smooth the terrain in a video game. Therefore I contrived an algorithm that makes use of Bézier curves of different orders. But this algorithm is defined in a two dimensional space for now. To shift it into the third dimension I need to somehow combine the Bézier curves. Given two curves in each two dimensions, how can I combine them to build a surface? I thought about something like a curve of a curve. Or maybe I could multiply them somehow. How can I combine them to cause the wanted behavior? Is there a common approach? In the image you can see the input, on the left, and the output, on the right, of the algorithm that works in a two dimensional space. For the real application there is a three dimensional input. The algorithm relays only on the adjacent tiles. Given these it will define the control points of the mentioned Bézier cur...
            閱讀完整內容

            Mutual Information Always Non-negative

            圖片
            Clash Royale CLAN TAG #URR8PPP up vote 10 down vote favorite 6 What is the simplest proof that mutual information is always non-negative? i.e., $I(X;Y)ge0$ probability-theory share | cite | improve this question edited Jun 17 '12 at 15:38 Cameron Buie 83.6k 7 71 154 asked Jun 17 '12 at 15:30 Omri 359 3 13 3 Convexity of the function $tmapsto tlog t$. – Did Jun 17 '12 at 15:33 In addition, the convexity properties require the coefficients in the linear combination sum 1. Then, as p(x,y) is a probability distribution, it fullfits such condition. – Francisco Javier Delgado Ceped Aug 10 at 18:44 add a comment  |  up vote 10 down vote favorite 6 What is the simplest proof that mutual information is always non-negative? i.e., $I(X;Y)ge0$ probability-theory share | cite | improve this question edited Jun 17 ...
            閱讀完整內容

            Why am i infinitely getting the same tweet with the Twitter Search API?

            圖片
            up vote 0 down vote favorite My code workes perfectly for other queries, but for one query I am infinitely getting the same tweet. I can't understand what the problem is. API call: query='Allergic asthma OR Nonallergic asthma OR Occupational asthma OR EIB OR Exercise-induced bronchoconstriction OR Nocturnal asthma OR Cough-variant asthma' new_tweets = api.search(q=searchQuery, count=100, since_id=since_id, lang='en',tweet_mode='extended') if not new_tweets: print("No more tweets found") break for tweet in new_tweets: if True: print(jsonpickle.encode(tweet._json, unpicklable=False)) my_file = open('searchTweets.txt','a') my_file.write(jsonpickle.encode(tweet._json, unpicklable=False)+'n') my_file.close() else: continue Output in file: https://pastebin.com/JmRCsTeE These are the JSONs of the same Tweet. Other queries that work: Breast cancer OR Prostate cancer OR Colon cancer OR Lung cancer Type 2 dia...
            閱讀完整內容