An elementary, nice lemma relating to the optimization of multivariable functions says that the smallest “big thing” is still bigger than the biggest “small thing”, in other words,<\/p>\n
\\(\\min_x \\max_y f(x,y) \\ge \\max_y \\min_x f(x,y)\\).
\n<\/p>\n
The proof is almost trivial. Let \\((x^*, y^*)\\) optimize the left hand side and let \\((x_*, y_*)\\) optimize the right hand side. Now note two facts: for any given \\(x\\), \\(f(x, \\arg\\max_y f(x,y)) \\ge f(x,y) \\forall y\\); for any given \\(y\\), \\(f(x, y) \\ge f(\\arg\\min_x f(x,y), y) \\forall x\\).<\/p>\n
So in particular, \\(f(x^*, y^*) \\ge f(x^*, y_*)\\) and \\(f(x^*, y_*) \\ge f(x_*, y_*)\\). So putting everything together, \\(f(x^*, y^*) \\ge f(x_*,y_*)\\). <\/p>\n","protected":false},"excerpt":{"rendered":"
An elementary, nice lemma relating to the optimization of multivariable functions says that the smallest “big thing” is still bigger than the biggest “small thing”, in other words, .<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[977,979,978,980,5,981,189,982,976,394],"class_list":["post-160","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-arg-min","tag-forall","tag-left-hand-side","tag-lemma","tag-math-math","tag-max","tag-min","tag-minimax","tag-multivariable-functions","tag-proof"],"_links":{"self":[{"href":"https:\/\/blog.yhuang.org\/index.php?rest_route=\/wp\/v2\/posts\/160","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.yhuang.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.yhuang.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.yhuang.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.yhuang.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=160"}],"version-history":[{"count":0,"href":"https:\/\/blog.yhuang.org\/index.php?rest_route=\/wp\/v2\/posts\/160\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.yhuang.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=160"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.yhuang.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=160"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.yhuang.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=160"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}