{"id":583,"date":"2025-04-23T20:53:08","date_gmt":"2025-04-23T12:53:08","guid":{"rendered":"https:\/\/www.toothlessos.xyz\/?p=583"},"modified":"2025-04-23T20:53:12","modified_gmt":"2025-04-23T12:53:12","slug":"the-optimization-set-convex-optimization","status":"publish","type":"post","link":"https:\/\/www.toothlessos.xyz\/index.php\/2025\/04\/23\/the-optimization-set-convex-optimization\/","title":{"rendered":"The optimization set: Convex optimization"},"content":{"rendered":"<div class=\"wp-block-aioseo-table-of-contents\"><ul><li><a class=\"aioseo-toc-item\" href=\"#aioseo-definition\">Convex optimization problem<\/a><\/li><li><a class=\"aioseo-toc-item\" href=\"#aioseo-convex-function\">Convex function<\/a><ul><li><a class=\"aioseo-toc-item\" href=\"#aioseo-first-order-condtions\">First-order conditions<\/a><\/li><li><a class=\"aioseo-toc-item\" href=\"#aioseo-second\">Second-order conditions<\/a><\/li><li><a class=\"aioseo-toc-item\" href=\"#aioseo-example\">Example<\/a><\/li><li><a class=\"aioseo-toc-item\" href=\"#aioseo-practical-methods-for-determining-convexity\">Practical methods for determining convexity<\/a><\/li><\/ul><\/li><li><a class=\"aioseo-toc-item\" href=\"#aioseo-duality\">Duality &#8211; Convert for ease<\/a><ul><li><a class=\"aioseo-toc-item\" href=\"#aioseo-the-lagrangian\">The Lagrangian (Step 1)<\/a><\/li><li><a class=\"aioseo-toc-item\" href=\"#aioseo-the-lagrangian-dual-function-step-2\">The Lagrangian Dual Function (Step 2)<\/a><\/li><li><a class=\"aioseo-toc-item\" href=\"#aioseo-the-dual-problem\">The dual problem<\/a><\/li><li><a class=\"aioseo-toc-item\" href=\"#aioseo-wee\">Week &amp; Strong duality<\/a><\/li><li><a class=\"aioseo-toc-item\" href=\"#aioseo-geometric-interpretation-of-duality\">Geometric interpretation of duality<\/a><\/li><li><a class=\"aioseo-toc-item\" href=\"#aioseo-complementary-slackness\">Complementary slackness<\/a><\/li><li><a class=\"aioseo-toc-item\" href=\"#aioseo-kkt-conditions\">KKT Conditions<\/a><\/li><\/ul><\/li><\/ul><\/div>\n\n\n<p>This log will cover one of the most important optimization problems: <strong>the convex optimization<\/strong>. We will look at the math derivations in detail and get some hand-on practice.<\/p>\n\n\n\n<p>Reference: <a href=\"https:\/\/web.stanford.edu\/~boyd\/cvxbook\/\">Convex Optimization \u2013 Boyd and Vandenberghe<\/a>; Slides from Prof. Sun, Peng&#8217;s MATH304 course at DKU.<\/p>\n\n\n<pre><\/pre>\n\n\n<h2 class=\"wp-block-heading\" id=\"aioseo-definition\">Convex optimization problem<\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"387\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/04\/image-7-1024x387.png\" alt=\"\" class=\"wp-image-589\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-7-1024x387.png 1024w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-7-300x113.png 300w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-7-768x290.png 768w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-7-1536x580.png 1536w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-7.png 1546w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"487\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/04\/image-8-1024x487.png\" alt=\"\" class=\"wp-image-592\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-8-1024x487.png 1024w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-8-300x143.png 300w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-8-768x365.png 768w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-8.png 1528w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"aioseo-convex-function\">Convex function<\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"131\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/04\/image-10-1024x131.png\" alt=\"\" class=\"wp-image-600\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-10-1024x131.png 1024w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-10-300x38.png 300w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-10-768x98.png 768w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-10-1536x196.png 1536w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-10.png 1587w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>Geometrically, it is helpful to visualize every point on the function as the endpoints of the vectors <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-c72ea8c330fcb4d42cc15a6e38cc3944_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#40;&#120;&#95;&#48;&#44;&#32;&#102;&#40;&#120;&#95;&#48;&#41;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"80\" style=\"vertical-align: -5px;\"\/>. The basic equality involved in this definition is also called <strong>Jensen&#8217; inequality<\/strong>.<\/p>\n\n\n\n<figure class=\"wp-block-image aligncenter size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"479\" height=\"413\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/04\/image-11.png\" alt=\"\" class=\"wp-image-603\" style=\"width:293px;height:auto\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-11.png 479w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-11-300x259.png 300w\" sizes=\"auto, (max-width: 479px) 100vw, 479px\" \/><\/figure>\n\n\n\n<p><\/p>\n\n\n\n<p>At the same time, the extended-value definitions gives us a simpler expression:<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"409\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/04\/image-12-1024x409.png\" alt=\"\" class=\"wp-image-607\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-12-1024x409.png 1024w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-12-300x120.png 300w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-12-768x307.png 768w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-12.png 1498w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>When checking if a function is convex\/using the convex conditions, we don&#8217;t have to use the original definition all the time. Instead, we can use the <strong>first-order conditions<\/strong> and the <strong>second-order conditions<\/strong>. Both are <strong>necessary &amp; sufficient<\/strong> conditions for convex functions.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"aioseo-first-order-condtions\">First-order conditions<\/h3>\n\n\n\n<p>We utilize the first-order Taylor expansion for the first-order conditions:<\/p>\n\n\n\n<p>Suppose <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-9c09a708375fde2676da319bcdfe8b24_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#102;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"10\" style=\"vertical-align: -4px;\"\/> is differentiable. Then <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-9c09a708375fde2676da319bcdfe8b24_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#102;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"10\" style=\"vertical-align: -4px;\"\/> is convex if and only if <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-89e23b1224adf2e4144dfc3a482d59ee_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#100;&#111;&#109;&#32;&#102;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"44\" style=\"vertical-align: -4px;\"\/> is convex and<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 22px;\"><span class=\"ql-right-eqno\"> &nbsp; <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-329b1fe65311fa390167294ab01dd30b_l3.png\" height=\"22\" width=\"227\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#91;&#32;&#102;&#40;&#121;&#41;&#32;&#92;&#103;&#101;&#32;&#102;&#40;&#120;&#41;&#32;&#43;&#32;&#32;&#92;&#110;&#97;&#98;&#108;&#97;&#32;&#102;&#40;&#120;&#41;&#94;&#84;&#40;&#121;&#32;&#45;&#32;&#120;&#41;&#32;&#92;&#93;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>holds for all <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-8b92be124e934b5e03ed33a161e3f435_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#120;&#44;&#32;&#121;&#32;&#92;&#105;&#110;&#32;&#100;&#111;&#109;&#32;&#102;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"93\" style=\"vertical-align: -4px;\"\/><\/p>\n\n\n\n<p>The graph below visualizes the first-order conditions. Note that the <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-9a4248d7aad9c4de184d39c625b4c119_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#110;&#97;&#98;&#108;&#97;&#32;&#102;&#40;&#120;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"48\" style=\"vertical-align: -5px;\"\/> is reduced to simply <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-b4caaf19541a3bc05129a71ac72b0bd0_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#102;&#39;&#40;&#120;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"38\" style=\"vertical-align: -5px;\"\/> in the 1-D case:<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"914\" height=\"277\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/04\/image-13.png\" alt=\"\" class=\"wp-image-614\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-13.png 914w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-13-300x91.png 300w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-13-768x233.png 768w\" sizes=\"auto, (max-width: 914px) 100vw, 914px\" \/><\/figure>\n\n\n\n<p>For the special case where <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-cc015b38ed27398a75fa0a28143fb629_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#110;&#97;&#98;&#108;&#97;&#32;&#102;&#40;&#120;&#95;&#48;&#41;&#32;&#61;&#32;&#48;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"90\" style=\"vertical-align: -5px;\"\/>, then for all <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-1edaa084bb0dce8499941ebd18d1f559_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#121;&#32;&#92;&#105;&#110;&#32;&#100;&#111;&#109;&#32;&#102;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"75\" style=\"vertical-align: -4px;\"\/>, <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-2e1490a506426d8d357b39f80f14ddf6_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#102;&#40;&#121;&#41;&#32;&#92;&#103;&#101;&#32;&#102;&#40;&#120;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"91\" style=\"vertical-align: -5px;\"\/>. This suggests that <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-87f2a80bc63f8d7bc3df68c45a787402_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#120;&#95;&#48;\" title=\"Rendered by QuickLaTeX.com\" height=\"11\" width=\"17\" style=\"vertical-align: -3px;\"\/> is in fact a <strong>global minimizer<\/strong> of the function <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-9c09a708375fde2676da319bcdfe8b24_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#102;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"10\" style=\"vertical-align: -4px;\"\/>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"aioseo-second\">Second-order conditions<\/h3>\n\n\n\n<p>Just like the first-order, the second-order conditions utilize the <strong>second-order Taylor expansion<\/strong>.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"402\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/04\/image-14-1024x402.png\" alt=\"\" class=\"wp-image-618\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-14-1024x402.png 1024w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-14-300x118.png 300w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-14-768x302.png 768w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-14-1536x603.png 1536w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-14.png 1599w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"521\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/04\/image-15-1024x521.png\" alt=\"\" class=\"wp-image-619\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-15-1024x521.png 1024w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-15-300x153.png 300w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-15-768x391.png 768w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-15.png 1518w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>The following proof tells us why the positive semi-definite condition must hold for ALL <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-cc77fab99b9db247af3ede80140a6e37_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#120;&#32;&#92;&#105;&#110;&#32;&#100;&#111;&#109;&#32;&#102;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"76\" style=\"vertical-align: -4px;\"\/>:<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"327\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/04\/image-16-1024x327.png\" alt=\"\" class=\"wp-image-622\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-16-1024x327.png 1024w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-16-300x96.png 300w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-16-768x245.png 768w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-16-1536x491.png 1536w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-16.png 1597w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"511\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/04\/image-17-1024x511.png\" alt=\"\" class=\"wp-image-623\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-17-1024x511.png 1024w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-17-300x150.png 300w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-17-768x383.png 768w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-17.png 1257w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"465\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/04\/image-18-1024x465.png\" alt=\"\" class=\"wp-image-624\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-18-1024x465.png 1024w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-18-300x136.png 300w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-18-768x349.png 768w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-18.png 1483w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"aioseo-example\">Example<\/h3>\n\n\n\n<p>With the definitions above, we can practice on checking the convexity of a few problems!<\/p>\n\n\n\n<p><strong>Least-square objective<\/strong>: <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-cdd86031d8bf8d64b4926c82f27f0230_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#102;&#40;&#120;&#41;&#32;&#61;&#32;&#124;&#124;&#65;&#120;&#32;&#45;&#32;&#98;&#124;&#124;&#95;&#50;&#94;&#50;\" title=\"Rendered by QuickLaTeX.com\" height=\"20\" width=\"138\" style=\"vertical-align: -5px;\"\/><\/p>\n\n\n\n<p>(Reference: <a href=\"https:\/\/math.stackexchange.com\/questions\/2864585\/hessian-on-linear-least-squares-problem\">Hessian on linear least squares problem &#8211; Mathematics Stack Exchange<\/a>)<\/p>\n\n\n\n<p>First, we want the find the Hessian matrix:<\/p>\n\n\n\n<p>We observe that <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-93d2b0d38fcd5d7d633545b922f9bd88_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#102;&#40;&#120;&#41;&#32;&#61;&#32;&#103;&#40;&#104;&#40;&#120;&#41;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"114\" style=\"vertical-align: -5px;\"\/>, where <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-c6231fc0c2a3d3de6654c4a7667ef4f8_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#104;&#40;&#120;&#41;&#32;&#61;&#32;&#65;&#120;&#32;&#45;&#32;&#98;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"111\" style=\"vertical-align: -5px;\"\/> and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-6a6e86bcc40ff8d874bd29619424752a_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#103;&#40;&#121;&#41;&#32;&#61;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#49;&#125;&#123;&#50;&#125;&#32;&#124;&#124;&#121;&#124;&#124;&#94;&#50;\" title=\"Rendered by QuickLaTeX.com\" height=\"22\" width=\"103\" style=\"vertical-align: -6px;\"\/>. Therefore, we can apply the chain rule:<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 22px;\"><span class=\"ql-right-eqno\"> &nbsp; <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-c01208853b69456c5812af1ec0f099fb_l3.png\" height=\"22\" width=\"163\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#91;&#92;&#110;&#97;&#98;&#108;&#97;&#32;&#102;&#40;&#120;&#41;&#32;&#61;&#32;&#65;&#94;&#123;&#84;&#125;&#40;&#65;&#120;&#32;&#45;&#32;&#98;&#41;&#92;&#93;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>Then we can take the second derivative to find the Hessian:<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 22px;\"><span class=\"ql-right-eqno\"> &nbsp; <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-fb73202f5139381f31df9d1b905a7d10_l3.png\" height=\"22\" width=\"111\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#91;&#72;&#102;&#40;&#120;&#41;&#32;&#61;&#32;&#65;&#94;&#123;&#84;&#125;&#65;&#92;&#93;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>Furthermore, we know that <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-1d328ab94678e8a3ab6221487adbd449_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#65;&#94;&#123;&#84;&#125;&#65;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"37\" style=\"vertical-align: 0px;\"\/> is positive semi-definite, since for any vector <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-ede05c264bba0eda080918aaa09c4658_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#120;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"10\" style=\"vertical-align: 0px;\"\/> we have:<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 22px;\"><span class=\"ql-right-eqno\"> &nbsp; <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-86195595e9e6b4bfaf805a46dc2af1a5_l3.png\" height=\"22\" width=\"298\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#91;&#120;&#94;&#84;&#40;&#65;&#94;&#84;&#65;&#41;&#120;&#32;&#61;&#32;&#40;&#65;&#120;&#41;&#94;&#84;&#40;&#65;&#120;&#41;&#32;&#61;&#32;&#124;&#124;&#65;&#120;&#124;&#124;&#95;&#50;&#94;&#50;&#32;&#92;&#103;&#101;&#32;&#48;&#32;&#92;&#93;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>Now you can see why the least square problem is a special case of convex optimization problems!<\/p>\n\n\n\n<p>(Note: on the relationship of positive semi-definite and eigenvalues, refer to: <a href=\"https:\/\/math.stackexchange.com\/questions\/518890\/prove-that-every-positive-semidefinite-matrix-has-nonnegative-eigenvalues\">linear algebra &#8211; Prove that every positive semidefinite matrix has nonnegative eigenvalues &#8211; Mathematics Stack Exchange<\/a>)<\/p>\n\n\n\n<p><strong>Quadratic functions<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"493\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/04\/image-19-1024x493.png\" alt=\"\" class=\"wp-image-634\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-19-1024x493.png 1024w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-19-300x144.png 300w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-19-768x369.png 768w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-19-1536x739.png 1536w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-19.png 1576w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p><strong>Other common examples of convex functions<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"142\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/04\/image-20-1024x142.png\" alt=\"\" class=\"wp-image-636\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-20-1024x142.png 1024w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-20-300x42.png 300w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-20-768x106.png 768w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-20-1536x213.png 1536w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-20.png 1842w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"aioseo-practical-methods-for-determining-convexity\">Practical methods for determining convexity<\/h3>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"430\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/04\/image-21-1024x430.png\" alt=\"\" class=\"wp-image-637\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-21-1024x430.png 1024w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-21-300x126.png 300w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-21-768x323.png 768w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-21-1536x645.png 1536w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-21.png 1747w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"aioseo-duality\">Duality &#8211; Convert for ease<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"aioseo-the-lagrangian\">The Lagrangian (Step 1)<\/h3>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"891\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/04\/image-22-1024x891.png\" alt=\"\" class=\"wp-image-641\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-22-1024x891.png 1024w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-22-300x261.png 300w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-22-768x668.png 768w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-22.png 1080w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"aioseo-the-lagrangian-dual-function-step-2\">The Lagrangian Dual Function (Step 2)<\/h3>\n\n\n\n<p>(Extended reading: <a href=\"https:\/\/mldemystified.com\/posts\/basics-of-ml\/duality\/post\/\">Understanding Duality and Lagrangians in Optimization | MLDemystified<\/a>)<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"340\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/04\/image-23-1024x340.png\" alt=\"\" class=\"wp-image-643\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-23-1024x340.png 1024w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-23-300x100.png 300w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-23-768x255.png 768w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-23.png 1200w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>The dual function <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-f80304a2d93c3db32dbcead590efabac_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#103;&#40;&#92;&#108;&#97;&#109;&#98;&#100;&#97;&#44;&#32;&#92;&#110;&#117;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"50\" style=\"vertical-align: -5px;\"\/> is the pointwise infimum of a family of affine functions of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-bb3023427517c72de1aa3076e56ff727_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#40;&#92;&#108;&#97;&#109;&#98;&#100;&#97;&#44;&#32;&#92;&#110;&#117;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"40\" style=\"vertical-align: -5px;\"\/>. Therefore, <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-f80304a2d93c3db32dbcead590efabac_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#103;&#40;&#92;&#108;&#97;&#109;&#98;&#100;&#97;&#44;&#32;&#92;&#110;&#117;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"50\" style=\"vertical-align: -5px;\"\/> is concave, even when the original problem is not convex (Since we are taking the pointwise infimum on <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-ede05c264bba0eda080918aaa09c4658_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#120;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"10\" style=\"vertical-align: 0px;\"\/>, we can treat the functions containing <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-ede05c264bba0eda080918aaa09c4658_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#120;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"10\" style=\"vertical-align: 0px;\"\/> as constants).<\/p>\n\n\n\n<figure class=\"wp-block-image aligncenter size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"668\" height=\"362\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/04\/image-24.png\" alt=\"\" class=\"wp-image-647\" style=\"width:392px;height:auto\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-24.png 668w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-24-300x163.png 300w\" sizes=\"auto, (max-width: 668px) 100vw, 668px\" \/><\/figure>\n\n\n\n<p>Here is the most important takeaway: The dual function gives us an <strong>lower bound<\/strong> for the original optimization problem.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"393\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/04\/image-25-1024x393.png\" alt=\"\" class=\"wp-image-649\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-25-1024x393.png 1024w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-25-300x115.png 300w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-25-768x295.png 768w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-25-1536x590.png 1536w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-25.png 1878w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>Below are two examples on constructing the dual problems:<\/p>\n\n\n\n<p><strong>Standard form LP<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"436\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/04\/image-26-1024x436.png\" alt=\"\" class=\"wp-image-650\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-26-1024x436.png 1024w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-26-300x128.png 300w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-26-768x327.png 768w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-26.png 1463w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p><strong>Least-norm solution of linear equations<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"599\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/04\/image-27-1024x599.png\" alt=\"\" class=\"wp-image-651\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-27-1024x599.png 1024w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-27-300x176.png 300w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-27-768x450.png 768w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-27.png 1189w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"aioseo-the-dual-problem\">The dual problem<\/h3>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"473\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/04\/image-28-1024x473.png\" alt=\"\" class=\"wp-image-653\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-28-1024x473.png 1024w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-28-300x138.png 300w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-28-768x354.png 768w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-28-1536x709.png 1536w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-28.png 1688w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"aioseo-wee\">Week &amp; Strong duality<\/h3>\n\n\n\n<p>Recall that <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-056d0d61832f61479d6d7133f4c38f9c_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#112;&#42;\" title=\"Rendered by QuickLaTeX.com\" height=\"13\" width=\"18\" style=\"vertical-align: -4px;\"\/> is the optimal solution for the original problem, while <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-a58117c883bcac1b4440f131a88fcec8_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#100;&#42;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"17\" style=\"vertical-align: 0px;\"\/> is the optimal solution for the dual problem. <\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Weak duality: <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-bd945b5c71b39cc6772429b05828c6d4_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#112;&#42;&#32;&#92;&#103;&#101;&#32;&#100;&#42;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"59\" style=\"vertical-align: -4px;\"\/><\/li>\n\n\n\n<li>Strong duality: <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-72e1e913a01fc0675a498d92bc203271_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#112;&#42;&#32;&#61;&#32;&#100;&#42;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"59\" style=\"vertical-align: -4px;\"\/> <\/li>\n<\/ol>\n\n\n\n<p>Strong duality is a favorable condition, as solving the dual problem (which is usually easier) will give us the solution for the original problem. One of the sufficient condition for strong duality is <strong>Slater&#8217;s constraint qualification<\/strong>.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"372\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/04\/image-29-1024x372.png\" alt=\"\" class=\"wp-image-658\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-29-1024x372.png 1024w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-29-300x109.png 300w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-29-768x279.png 768w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-29.png 1314w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>Example: <strong>Quadratic problem<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"422\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/04\/image-30-1024x422.png\" alt=\"\" class=\"wp-image-661\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-30-1024x422.png 1024w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-30-300x124.png 300w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-30-768x317.png 768w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-30-1536x634.png 1536w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-30.png 1753w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>During the derivation, we will encounter the following expression:<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 22px;\"><span class=\"ql-right-eqno\"> &nbsp; <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-0600acb0a36a47e411a6387eeafedfe9_l3.png\" height=\"22\" width=\"69\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#91;&#32;&#40;&#80;&#94;&#123;&#45;&#49;&#125;&#41;&#94;&#123;&#84;&#125;&#80;&#32;&#92;&#93;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>Recall that in the problem definition, the matrix <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-650eb7688af6737ac325425b5c9a5982_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#80;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"14\" style=\"vertical-align: 0px;\"\/> is required to be positive semi-definite, which implies that P is a symmetric matrix. Therefore:<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 22px;\"><span class=\"ql-right-eqno\"> &nbsp; <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-754fbec628a70c056fe60efc48b383d8_l3.png\" height=\"22\" width=\"102\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#91;&#32;&#40;&#80;&#94;&#123;&#45;&#49;&#125;&#41;&#94;&#123;&#84;&#125;&#80;&#32;&#61;&#32;&#73;&#92;&#93;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p>(I personally missed this point when doing the derivation myself, so I decide to add a note here)<\/p>\n\n\n\n<p>Example: <strong>A non-convex problem with strong duality<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"514\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/04\/image-31-1024x514.png\" alt=\"\" class=\"wp-image-663\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-31-1024x514.png 1024w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-31-300x150.png 300w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-31-768x385.png 768w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-31-1536x770.png 1536w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-31.png 1683w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"411\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/04\/image-32-1024x411.png\" alt=\"\" class=\"wp-image-664\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-32-1024x411.png 1024w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-32-300x120.png 300w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-32-768x308.png 768w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-32-1536x617.png 1536w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-32.png 1683w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"aioseo-geometric-interpretation-of-duality\">Geometric interpretation of duality<\/h3>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"521\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/04\/image-33-1024x521.png\" alt=\"\" class=\"wp-image-665\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-33-1024x521.png 1024w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-33-300x152.png 300w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-33-768x390.png 768w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-33.png 1442w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"448\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/04\/image-34-1024x448.png\" alt=\"\" class=\"wp-image-666\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-34-1024x448.png 1024w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-34-300x131.png 300w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-34-768x336.png 768w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-34-1536x671.png 1536w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-34.png 1782w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>Always bear in mind the range of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-43fe27dc3e528266a619764d90fce60b_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#117;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"10\" style=\"vertical-align: 0px;\"\/> (<img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-f83af2727144c9b9550038915825ff14_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#117;&#32;&#92;&#112;&#114;&#101;&#99;&#101;&#113;&#32;&#48;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"43\" style=\"vertical-align: -3px;\"\/>) when going through these visualizations.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"aioseo-complementary-slackness\">Complementary slackness<\/h3>\n\n\n\n<p>(Important assumption!) <strong>Strong duality holds, <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-c674b8a19afef366cde8b4327cf616a6_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#120;&#94;&#42;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"16\" style=\"vertical-align: 0px;\"\/> is primal optimal, and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-0b81c07b5a3196bb040601d4ee36f1c3_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#40;&#92;&#108;&#97;&#109;&#98;&#100;&#97;&#94;&#42;&#44;&#32;&#92;&#110;&#117;&#94;&#42;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"55\" style=\"vertical-align: -5px;\"\/> is dual optimal<\/strong>, we have:<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"404\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/04\/image-35-1024x404.png\" alt=\"\" class=\"wp-image-668\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-35-1024x404.png 1024w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-35-300x118.png 300w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-35-768x303.png 768w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-35-1536x606.png 1536w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-35.png 1707w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>We call the condition<\/p>\n\n\n\n<p><p class=\"ql-center-displayed-equation\" style=\"line-height: 19px;\"><span class=\"ql-right-eqno\"> &nbsp; <\/span><span class=\"ql-left-eqno\"> &nbsp; <\/span><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-ef7c900e3b0d63da427406ad277e55bc_l3.png\" height=\"19\" width=\"173\" class=\"ql-img-displayed-equation quicklatex-auto-format\" alt=\"&#92;&#91;&#32;&#92;&#108;&#97;&#109;&#98;&#100;&#97;&#95;&#123;&#105;&#125;&#94;&#42;&#102;&#95;&#123;&#105;&#125;&#40;&#120;&#94;&#42;&#41;&#32;&#61;&#32;&#48;&#44;&#32;&#105;&#32;&#61;&#32;&#49;&#32;&#46;&#46;&#46;&#32;&#109;&#32;&#92;&#93;\" title=\"Rendered by QuickLaTeX.com\"\/><\/p><\/p>\n\n\n\n<p><strong>Complementary slackness<\/strong><\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"aioseo-kkt-conditions\">KKT Conditions<\/h3>\n\n\n\n<p>KKT conditions give us a way to <strong>rewrite<\/strong> primal optimization problems with differentiable <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.toothlessos.xyz\/wp-content\/ql-cache\/quicklatex.com-634d4d389d0d057c656c0a8ec0e6209a_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#102;&#95;&#123;&#105;&#125;&#44;&#32;&#104;&#95;&#123;&#105;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"37\" style=\"vertical-align: -4px;\"\/> and strong duality. This form can make the problem easier to solve under some circumstances. Note that the primal problem is not necessarily convex.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"493\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/04\/image-36-1024x493.png\" alt=\"\" class=\"wp-image-671\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-36-1024x493.png 1024w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-36-300x144.png 300w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-36-768x369.png 768w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-36-1536x739.png 1536w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-36.png 1738w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>Example: <strong>Equality constrained convex quadratic minimization<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"475\" src=\"http:\/\/38.246.252.17:8080\/wp-content\/uploads\/2025\/04\/image-37-1024x475.png\" alt=\"\" class=\"wp-image-673\" srcset=\"https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-37-1024x475.png 1024w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-37-300x139.png 300w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-37-768x356.png 768w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-37-1536x712.png 1536w, https:\/\/www.toothlessos.xyz\/wp-content\/uploads\/2025\/04\/image-37.png 1549w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n","protected":false},"excerpt":{"rendered":"<p>This log will cover one of the most important optimizat [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[37,9],"class_list":["post-583","post","type-post","status-publish","format-standard","hentry","category-math","tag-optimization","tag-review"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/www.toothlessos.xyz\/index.php\/wp-json\/wp\/v2\/posts\/583","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.toothlessos.xyz\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.toothlessos.xyz\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.toothlessos.xyz\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.toothlessos.xyz\/index.php\/wp-json\/wp\/v2\/comments?post=583"}],"version-history":[{"count":59,"href":"https:\/\/www.toothlessos.xyz\/index.php\/wp-json\/wp\/v2\/posts\/583\/revisions"}],"predecessor-version":[{"id":674,"href":"https:\/\/www.toothlessos.xyz\/index.php\/wp-json\/wp\/v2\/posts\/583\/revisions\/674"}],"wp:attachment":[{"href":"https:\/\/www.toothlessos.xyz\/index.php\/wp-json\/wp\/v2\/media?parent=583"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.toothlessos.xyz\/index.php\/wp-json\/wp\/v2\/categories?post=583"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.toothlessos.xyz\/index.php\/wp-json\/wp\/v2\/tags?post=583"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}