{"id":581,"date":"2018-04-29T19:16:04","date_gmt":"2018-04-29T19:16:04","guid":{"rendered":"http:\/\/wordpress.cs.vt.edu\/optml\/?p=581"},"modified":"2018-04-29T19:16:04","modified_gmt":"2018-04-29T19:16:04","slug":"lagrange-dual","status":"publish","type":"post","link":"https:\/\/wordpress.cs.vt.edu\/optml\/2018\/04\/29\/lagrange-dual\/","title":{"rendered":"Lagrange dual"},"content":{"rendered":"

1. Lagrange dual problem: standard form, Lagrange dual function, and dual problem<\/h3>\n

First, we consider an optimization problem in the standard form<\/strong>:<\/p>\n

minimize \"<\/p>\n

subject to \" i = 1, …, m<\/p>\n

\" i = 1, …, p<\/p>\n

with variable \", domain \" is nonempty. The optimal value is \".<\/p>\n

The idea of lagrangian duality is to take the constraints into account by augmenting the objective function with a weighted sum of the constraint functions.<\/p>\n

Lagrangian \" as:
\n\"L(x,<\/p>\n

with \", \" as the Lagrange multiplier associated with the \" inequality constraint \" and \" as the Lagrange multiplier associated with the \" equality constraint \".<\/p>\n

Lagrange dual function<\/strong> is the minimum value of the Lagrangian.<\/p>\n

For \"
\n\"<\/p>\n

If \", then \".<\/p>\n

Proof:<\/p>\n

If \" is feasible and \", then
\n\"
\nminimizing over all feasible \" gives \"<\/p>\n

The dual problem<\/strong>: what is the best lower bound that can be obtained from the Lagrange dual function?<\/p>\n

maximize \"
\nsubject to \"
\nOptimal value is denoted as \"<\/p>\n

2. Weak and strong duality<\/h3>\n

If\u00a0 \", this property is called weak duality. The weak duality inequality holds when \" and \"d^{*} are infinite while If the equality \" holds then we say that strong duality holds.<\/p>\n

3. Geometric interpretation of dual function and lower bound \"<\/h3>\n

\"\"\"\"<\/p>\n

For a problem with one (inequality) constraint. Given \u03bb, we minimize \" over \"G. This yields a supporting hyperplane with slope \u2212\u03bb. The intersection of this hyperplane with the u = 0 axis gives g(\u03bb). Supporting hyperplanes corresponding to three dual feasible values of \u03bb, i.e, optimum \"\lambda,\u00a0\"\lambda, and\u00a0\"\lambda . As shown in the figures, strong duality does not hold so the optimal duality gap \"p^{\ast is positive.<\/p>\n

4. Price or profit interpretation<\/h3>\n

Suppose the variable x denotes how an enterprise operates and \" denotes the cost of operating at x, then \" is the profit made at the operating condition x.<\/p>\n

Each constraint \" represents some limit on resources (e.g., warehouse space, labor) or a regulatory limit (e.g., environmental). The operating condition that maximizes profit while respecting the limits can be found by solving the problem:<\/p>\n

minimize \"f_{0}(x)<\/p>\n

subject to \", i = 1, …, m.<\/p>\n

The resulting optimal profit is \" resulting optimal profit is \" .<\/p>\n

Now imagine a second scenario in which the limits can be violated, by paying an additional cost which is linear in the amount of violation, measured by \"f_{i}.\u00a0 Enterprise for the \" limit or constraint is\u00a0\" . Payments are also made to the firm for constraints that are not tight; if \" represents a payment to the firm.<\/p>\n

The coefficient\u00a0\" has the interpretation of the price for violating \"; its units are dollars per unit violation. For the same price the enterprise can sell any \u2018unused\u2019 portion of the \" constraint. We assume \"\lambda, i.e., the firm must pay for violations.<\/p>\n

Reference<\/h3>\n

Boyd and Vandenberghe, Chapter 5\u20135.5 https:\/\/web.stanford.edu\/~boyd\/cvxbook\/bv_cvxbook.pdf<\/p>\n","protected":false},"excerpt":{"rendered":"

1. Lagrange dual problem: standard form, Lagrange dual function, and dual problem First, we consider an optimization problem in the standard form: minimize subject to i = 1, …, m i = 1, …, p with variable , domain is nonempty. The optimal value is . The idea of lagrangian duality is to take the … Continue reading Lagrange dual<\/span><\/a><\/p>\n","protected":false},"author":171,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[1],"tags":[],"class_list":["post-581","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p9CQAE-9n","_links":{"self":[{"href":"https:\/\/wordpress.cs.vt.edu\/optml\/wp-json\/wp\/v2\/posts\/581","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.cs.vt.edu\/optml\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.cs.vt.edu\/optml\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.cs.vt.edu\/optml\/wp-json\/wp\/v2\/users\/171"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.cs.vt.edu\/optml\/wp-json\/wp\/v2\/comments?post=581"}],"version-history":[{"count":42,"href":"https:\/\/wordpress.cs.vt.edu\/optml\/wp-json\/wp\/v2\/posts\/581\/revisions"}],"predecessor-version":[{"id":653,"href":"https:\/\/wordpress.cs.vt.edu\/optml\/wp-json\/wp\/v2\/posts\/581\/revisions\/653"}],"wp:attachment":[{"href":"https:\/\/wordpress.cs.vt.edu\/optml\/wp-json\/wp\/v2\/media?parent=581"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.cs.vt.edu\/optml\/wp-json\/wp\/v2\/categories?post=581"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.cs.vt.edu\/optml\/wp-json\/wp\/v2\/tags?post=581"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}