斯坦福EE364a凸优化课程第2章作业题解斯坦福EE364a课程布置的作业答案，内容为第2章《凸集》

文件名称: 斯坦福EE364a凸优化课程第2章作业题解

所属分类: 讲义

开发工具:

文件大小: 85kb

下载次数: 0

上传时间: 2019-03-03

提供者: zli***

下载 (85kb)

不能下载？报告错误

详细说明：斯坦福EE364a课程布置的作业答案，内容为第2章《凸集》3.2 Level sets of conve C, concave, quasiconvex and quasiconcave functions. Some level sets of a function f are shown below. The curve labeled 1 shows a f(a)=1 2 Could f be convex(concave, quasiconvex, quasiconcave)? Explain your answer. Repeat for the level curves shown below 6 Solution. The first function could be quasiconvex because the sublevel sets appear to be convex. It is definitely not concave or quasiconcave because the superlevel sets are not convex It is also not, convex, for the following reason. We plot the function values along the dashed line labeled i Along this line the function passes through the points marked as black dots in the figure below Clearly along this line segment, the function is not convex If we repeat the same analysis for the second function, we see that it could be concave (and therefore it could be quasiconcave). It cannot be convex or quasiconvex, because the sublevel sets are not convex 3.5 Running average of a convec function. Suppose f:R -R is convex, with R+ C don f. Show that its running average F, defined as f(t) dom f=r CJo is convex. You can assume f is differentiable Solution. f is differentiable with (1/m2)/f(t)dt+f()/ P"(x)=(2/x3)/f()t-2f(x)/x2+f(x)/r (f(t)-f(x)-f(x)(t-x) Convexity now follows from the fact that f(t)≥f(x)+∫(x)(t-x) ∈domf, which implies p"(x)≥0 Here's another(simpler? proof. For each s, the function f(s c)is convex in There- ore s c)as is a convex function of T. Now we use the variable substitution t=s. to get f (t)dt 3.6 Functions and epigraphs. When is the epigraph of a function a halfspace? When is the epigraph of a function a convex cone? When is the epigraph of a function a polyhedron? Solution. If the function is convex, and it is affine, positively homogeneous(f(ac) af(a) for a20), and piecewise-affine, respectively 3.15 A family of concave utility functions. For 0< a< l let with dom ua=R+. We also define uo( c)=log c(with dom o=R_+) (a Show that for x>0, uo()=lima-o wa(a) (b) Show that ua are concave, monotone increasing, and all satisfy Wa(1)=0 These functions are often used in economics to model the benefit or utility of some quantity of goods or money. Concavity of wa means that the marginal utility(i.e,, the increase in utility obtained for a fixed increase in the goods decreases as the amount of goods increases. In other words, concavity models the effect of satiation Solution (a) In this limit, both the numerator and denominator go to zero, so we use I'Hopital's lim ua(a)=lim (d/da)(a- -1 gu a→0 (d/da)a 1 loga (b) By inspection we have The derivative is given by which Is pOS sitive for all (since< a< 1), so these functions are increasing. To show concavity, we exanine the second derivative Since this is negative for all t, we conclude that Wa is strictly concave 3.16 For each of the following functions determine whether it is convex, concave, quasicon- yex. or quasiconcave 12OB2 Solution. The Hessian of f is 01 C℃ 10 which is neither positive semidefinite nor negative semidefinite. Therefore, f neither convex nor concave. It is quasiconcave, since its superlevel sets {(xr1,m2)∈R are convex. It is not quasiconvex (c)f(x1,x2)=1/(x1x2)On Solution. The Hessian of f is 2/(x2)1/(x1x2 /( 0 Therefore, f is convex and quasiconvex. It is not quasiconcave or conca (d)f(1,x2)=1/ 2 on R' S OlUTIOn The Hessian of f is 1/x22x1/x2 which is not positive or negative semidefinite. Therefore, f is not convex or concave is quasiconvex and quasiconcave(i c, quasilincar), since the sublevel and su perlevel sets are halfspaces (e)f(c1, x2)=.i/2 on R X R+ Solution. f is convex, as mentioned on page 72.(See also figure 3.3. This is easily verified by working out the Hessian 2/ 2 2x1 2.x2 2|=(2/x2) Therefore, f is convex and quasiconvex. It is not concave or quasiconcave(see the figure) 3.18 Adapt the proof of concavity of the log-determinant function in $3. 1.5 to show the following (b) f(X)=(det X)I/n is concave on dom f=S ++ Solution (b) Define g()=∫(z+V), where zx0andv∈S g(t)=(det (z+tv)) det Z/det(I+tz-12vz/)det z1/2)'1/m (det2)1/(I(1+tx) where Ai, i=1,.,m, are the eigenvalues of Z-1/2VZ-1/2. From the last equality we see that g is a concave function of t on( Z+lV>0, since det Z>0 and the geometric mean(TIm-1ci)/n is concave on Rn 3.24 Some functions on the probability simple. Let a be a real-valued random variable which takes values in ( a1,., an where (1 90%.(B cardinality we mean the number of elements in A Solution. f is integer-valued, so it can not be convex or concave.(A convex or a concave function is always continuous on the relative interior of its domain. f is quasiconcave because its superlevel sets are convex. We have f(p)2 a if and only if ∑ P11<0.9, where k= maxi=l,.,n i< a is the largest integer less than a, and pra the ith largest component of p. We know that 2i=1 piy is a convex function o so the inequality 2i=1 pil<0.9 defines a convex set In general, f(p)is not quasiconvex. For example, we can take n 0 and a2=1,andp2=(0.1,0.9)andp2=(0.9,0.1). Then f(m2)=f(m2)=1,but f(+p2)/2)=f(0.5.0.5)=2. (h) The minimum width interval that contains 90% of the probability, i.e B-a prob(a0.9) Solution. The minimum width interval that contains 90%o of the probability must be of the form[a, ai with1≤a≤≤m, because rob(a )=∑pk orobla where i= min k ak> af, and j=maxk ak y if and only if all intervals of width less than y have a probability less than 90% <0.9 r a ,i that satisfy ai-ai y. This defines a convex set Since the function takes values on a finite set. it is not continuous and therefore neither convex nor concave. In addition it is not quasiconvex in general. Consider he example with n=2.,a1=0,a2=1,p1=(0.95,0.05)andp2=(0.05.095) enf(p1)=0,f(2)=0,butf(2+p2)/2 3.36 Derive the conjugates of the following functions a)Mac function. f(a)=maxi=.n.2 on R Solution. We will show that f*(y) 0ify≥0,17y=1 o otherwise We first verify the domain of f*. First suppose y has a negative component, say yk 1. We choose t=t1 and let t go to infinity to show that y-max w i=t1 y-t is unbounded above. Similarly, when y>0 and 1 y< 1, we choose a=tl and let t go to infinity The remaining case for y is y 20 and 1 y=1. In this case we have y≤max for all and therefore x y-maxiMi <0 for all a, with equality for a-0 Therefore f(9)=0 (d) Power function. f(r)=.p on R++, where p>1. Repeat for p<0 Solution. We'll use standard notation: we define q by the equation 1/p+1/q=1 ie.,q=p/(P-1) We start with the case p> l. Then p is strictly convex on R+. For y0 at w=0, so f*(9)=0. Fo or 0 the function achieves its maximum at =(y/p)i/(p-1), where it has value (y/p)1(p-1)-(y/p)(p-1)=(p-1)(y/p) Therefore we have y (P-1)(y/p)4y For p<0 similar arguments show that dom f *=-R+ and f*(y)=e(y/p)9

(系统自动生成,下载前可以参看下载内容)