文档介绍：Convex Optimization Overview (cnt’d)Chuong B. DoOctober 26, 20071 RecapDuring last week’s section, we began our study ofconvex optimization, the study ofmathematical optimization problems of the form,minimizex∈Rnf(x)subject togi(x)≤0, i= 1, . . . , m,hi(x) = 0, i= 1, . . . , p,(1)wherex∈Rnis the optimization variable,f:Rn→Randgi:Rn→Rare convex functions,andhi:Rn→Rare a?ne functions. In a convex optimization problem, the convexity of boththe objective functionfand the feasible region (., the set ofx’s satisfying all constraints)allows us to conclude that any feasible locally optimal point must also be globally fact provides the key intuition for why convex optimization problems can in general besolved e? these lecture notes, we continue our foray into the ?eld of convex optimization. Inparticular, we will introduce the theory of Lagrange duality for convex optimization problemswith inequality and equality constraints. We will also discuss generic yet e?cient algorithmsfor solving convex optimization problems, and then brie?y mention directions for DualityTo explain the fundamental ideas behind duality theory, we start with a motivating examplebased on CS 229 homework grading. We prove a simple weak duality result in this setting,and then relate it to duality in optimization. We then discuss strong duality and the KKToptimality A motivating example: CS 229 homework gradingIn CS 229, students plete four homeworks throughout the quarter, each consistingof ?ve questions apiece. Suppose that during one year that the course is o?ered, the TAs1decide to economize on their work load for the quarter by grading only one problem oneach submitted problem set. Nevertheless, they also require that every student submitan attempted solution to every problem (a requirement which, if violated, would lead toautomatic failure of the course).Because they are extremely cold-hearted1, the TAs always try to ensure that