1、rrinirriiEe/(T)subject tx 0where J and g are convex. Let t* denote the constrained mimmizer and p* = /(t*).The dual function is defined as Zi(A) = miiij f (t) 4- 以 and given appropriate conditiorLSj vce have max a /i(A) = p*. Why is that?Lets plot all the possible values thatcan take for every point

2、 in the domain.)This gives us a. 2-dimensional shape in R . Ent oboiLsly, for optimizaLon purposes we can ignore the bulk of the points in this curve and focus on the lower boundaj or envelope.g(x)Now, the problem is to find the minimum value that犬x) can possible take given that (x) is less than or

3、equal to zero. As you can see, this corresponds to the point circled in the graph, which is located at (g(z*) J(h*) = (0,p*).Now consider adding 入g(H)to /(x). To do this, we add a line Ag(x) to the above graph.g(x)Tlie black line is the envelope of (g(x),.Rx) and the blue line is the plot of g(d),人g

4、(i). Now, plot (。(了), / + 入。(r) for a particular A.(X)6V + (X)J (x)6y + (X)一max 入 minxf(x) + Xg(x)g(x)I Irv4ntod h il Q 901 /iow I ln*/ntocAs you can see. adding Ap(z) has the effect of tiltiiig the curve. Let us plot f (r) + Xg(x) for several values of A:3於+3g(x)Each of the colored lines is/(x) + A

5、(r) for a different value of A. But what do we notice? The circled red point, corresponding to the constrained minimum, remains unaffected! In hindsight, this is obvious because ) = 0, therefore f (虻)+ Ag(r*) = p* is independent of A.Now, because every curve passes through the circled red point (O.p3), the minimum of that curve must always be equal to or less than p*.In order to get th correct answer, we have to find A so that th colored piifvq is niiniinized at the circled red point. In order to do this, we have to tilt the function just right