Get global maximum slope











up vote
1
down vote

favorite












I have a function which computes values on images with the size of 32x32 pixels. Therefore, the function is applied on every single pixel $x_i$ but also depends on all 32x32 input pixels. The input is constrained to $-1 leq x_i leq 1$.



More formal: A function $f_i:mathbb [-1,1]^{1024} rightarrow mathbb R$ and an input vector $vec{x} in mathbb [-1,1]^{1024}$.



Now I am looking for the global maximum slope of $f_i$ (for any input) numerically. A local maximum slope is easy to find as one goes in the direction of the gradient. How to find the global maximum? I am not sure if brute force is an option because when the pixel values have a high precision (e.g. 1e-10) then the total number of input permutations is ridiculously high. The brute force method might work with a lower precision but this doesn't make sense in this scenario.



Can someone give me a hint? Is this even possible?










share|cite|improve this question






















  • Does this answer your question?
    – zenith
    11 hours ago















up vote
1
down vote

favorite












I have a function which computes values on images with the size of 32x32 pixels. Therefore, the function is applied on every single pixel $x_i$ but also depends on all 32x32 input pixels. The input is constrained to $-1 leq x_i leq 1$.



More formal: A function $f_i:mathbb [-1,1]^{1024} rightarrow mathbb R$ and an input vector $vec{x} in mathbb [-1,1]^{1024}$.



Now I am looking for the global maximum slope of $f_i$ (for any input) numerically. A local maximum slope is easy to find as one goes in the direction of the gradient. How to find the global maximum? I am not sure if brute force is an option because when the pixel values have a high precision (e.g. 1e-10) then the total number of input permutations is ridiculously high. The brute force method might work with a lower precision but this doesn't make sense in this scenario.



Can someone give me a hint? Is this even possible?










share|cite|improve this question






















  • Does this answer your question?
    – zenith
    11 hours ago













up vote
1
down vote

favorite









up vote
1
down vote

favorite











I have a function which computes values on images with the size of 32x32 pixels. Therefore, the function is applied on every single pixel $x_i$ but also depends on all 32x32 input pixels. The input is constrained to $-1 leq x_i leq 1$.



More formal: A function $f_i:mathbb [-1,1]^{1024} rightarrow mathbb R$ and an input vector $vec{x} in mathbb [-1,1]^{1024}$.



Now I am looking for the global maximum slope of $f_i$ (for any input) numerically. A local maximum slope is easy to find as one goes in the direction of the gradient. How to find the global maximum? I am not sure if brute force is an option because when the pixel values have a high precision (e.g. 1e-10) then the total number of input permutations is ridiculously high. The brute force method might work with a lower precision but this doesn't make sense in this scenario.



Can someone give me a hint? Is this even possible?










share|cite|improve this question













I have a function which computes values on images with the size of 32x32 pixels. Therefore, the function is applied on every single pixel $x_i$ but also depends on all 32x32 input pixels. The input is constrained to $-1 leq x_i leq 1$.



More formal: A function $f_i:mathbb [-1,1]^{1024} rightarrow mathbb R$ and an input vector $vec{x} in mathbb [-1,1]^{1024}$.



Now I am looking for the global maximum slope of $f_i$ (for any input) numerically. A local maximum slope is easy to find as one goes in the direction of the gradient. How to find the global maximum? I am not sure if brute force is an option because when the pixel values have a high precision (e.g. 1e-10) then the total number of input permutations is ridiculously high. The brute force method might work with a lower precision but this doesn't make sense in this scenario.



Can someone give me a hint? Is this even possible?







real-analysis numerical-methods






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked yesterday









Tobi

83




83












  • Does this answer your question?
    – zenith
    11 hours ago


















  • Does this answer your question?
    – zenith
    11 hours ago
















Does this answer your question?
– zenith
11 hours ago




Does this answer your question?
– zenith
11 hours ago










1 Answer
1






active

oldest

votes

















up vote
0
down vote













This is a convex optimization problem. You can get a global minimum $implies$ that the local minimum from gradient descent if both your domain and the function that you are optimizing is convex.



In your case, you are maximizing $f'(x):[-1,1]rightarrow mathbb R$ (most probably as I don't know the domain of the derivative)in a $32times32$ discrete grid. As you can understand the domain is convex as it in an interval in $mathbb R$. Only need to check if the function is convex or not.



PS: And I think you can apply Newton's method or other faster algorithms depending upon the smoothness of the function.






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: 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%2f3006666%2fget-global-maximum-slope%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








    up vote
    0
    down vote













    This is a convex optimization problem. You can get a global minimum $implies$ that the local minimum from gradient descent if both your domain and the function that you are optimizing is convex.



    In your case, you are maximizing $f'(x):[-1,1]rightarrow mathbb R$ (most probably as I don't know the domain of the derivative)in a $32times32$ discrete grid. As you can understand the domain is convex as it in an interval in $mathbb R$. Only need to check if the function is convex or not.



    PS: And I think you can apply Newton's method or other faster algorithms depending upon the smoothness of the function.






    share|cite|improve this answer

























      up vote
      0
      down vote













      This is a convex optimization problem. You can get a global minimum $implies$ that the local minimum from gradient descent if both your domain and the function that you are optimizing is convex.



      In your case, you are maximizing $f'(x):[-1,1]rightarrow mathbb R$ (most probably as I don't know the domain of the derivative)in a $32times32$ discrete grid. As you can understand the domain is convex as it in an interval in $mathbb R$. Only need to check if the function is convex or not.



      PS: And I think you can apply Newton's method or other faster algorithms depending upon the smoothness of the function.






      share|cite|improve this answer























        up vote
        0
        down vote










        up vote
        0
        down vote









        This is a convex optimization problem. You can get a global minimum $implies$ that the local minimum from gradient descent if both your domain and the function that you are optimizing is convex.



        In your case, you are maximizing $f'(x):[-1,1]rightarrow mathbb R$ (most probably as I don't know the domain of the derivative)in a $32times32$ discrete grid. As you can understand the domain is convex as it in an interval in $mathbb R$. Only need to check if the function is convex or not.



        PS: And I think you can apply Newton's method or other faster algorithms depending upon the smoothness of the function.






        share|cite|improve this answer












        This is a convex optimization problem. You can get a global minimum $implies$ that the local minimum from gradient descent if both your domain and the function that you are optimizing is convex.



        In your case, you are maximizing $f'(x):[-1,1]rightarrow mathbb R$ (most probably as I don't know the domain of the derivative)in a $32times32$ discrete grid. As you can understand the domain is convex as it in an interval in $mathbb R$. Only need to check if the function is convex or not.



        PS: And I think you can apply Newton's method or other faster algorithms depending upon the smoothness of the function.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered yesterday









        zenith

        918




        918






























             

            draft saved


            draft discarded



















































             


            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3006666%2fget-global-maximum-slope%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

            Berounka

            Sphinx de Gizeh

            Different font size/position of beamer's navigation symbols template's content depending on regular/plain...