《最优化期末考试》由会员分享，可在线阅读，更多相关《最优化期末考试（7页珍藏版）》请在金锄头文库上搜索。
1、Definition: Convex combinationDefinition: Convex combination n1Let be a sequence in R that converges to *We say that the convergence is Q-linear if there is aconstant 0,1 such that*lim *Further, ifkkkkxxrxxrxx1*lim0 *the convergence is said to be Q-superlinearkkkxxxx1 2And a even more rapid converge
2、nce, Q-quadratic convergenc, is defined when the following inequality holds*lim *for all sufficiently large. where is a poskk kxxM xxkM itive constant, not necessarily less than 1. 12222 123122312P-1 Let be a given n-vector, and A be a given nth-order symmetric matrix. Find out the gradient and Hess
3、ian ofand P-2 Let 322432and assume can be reTTafxa xfxx Axf xxxxx xx xxxf x 222 2111writed as 2 then find out , and , where . P-3 Compute the gradient and Hessian of the function1001TTf xx AxbxcA bcAAf xxxx12 12112 1212Let , and , be nonnegativescalars and 1, the linear combinationis defined as a co
4、nvex combination of ,kn kkk ik kkx xxRkxxxx xx LLLL A set is a convex set if for any two points and , we have 1 for a arbitrary scalar 0,1 . That is, the “line segment“ joining them is still in . nDRxD yDxyDD Theorem: Properties of convex setsDefinition: Convex functionsTheorem: Properties of convex
5、 functionsTheorem: First-order ConditionsTheorem: Second-order ConditionsTheorem: Second-order Conditions 1212111212 1212Let , be three convex sets of , we have thefollowing properties1 , is a convex set for anyscalar 2 and is a convex set3 , is a convex setnD D DRDy yx xDDDx xDxDDDxx xD xDI 1212 12
6、124 , is a convex setDDxx xD xD Let be a function defined on a convex , isconvex if for any , and 0,1 , we have11Further, is strictly convex if the above inequalityholds strictly whenever f xD f xx yDfxyf xfyf xxy and 01.We say is concave if is convex, and strictlyconcave if is strictly convex.f xf
7、xf x 1212Assume , and are convex, then we have1 is convex for any 02 is a concave3 is convex for any 0,0fxfxf xkf xkf xfxfx Suppose is a differentiable function defined on aconvex set . then is convex if and only ifholds for all ,Tf xDf xfyf xf xyxx yD 2Suppose is twice differentiable on nonempty op
8、enconvex set . Then is convex if and only if its Hessianis positive semidefinite, i.e. for all 0f xDf xxDf x 2Suppose is twice differentiable on nonempty openconvex set . Then is convex if and only if its Hessianis positive semidefinite, i.e. for all 0Further, if f xDf xxDf x 20, then is strictly co
9、nvex. however, the converse is not always true.f xf xQuestions: Definition: Convex programmingTheorem: Properties of convex programmingThe geometrical properties for linear programming The feasible region D for a LP is convex if D is nonempty. If there is a feasible solution, then there is at least
10、one basic feasible solution. A feasible solution is a basic feasible one if and only if it is an extreme point of the feasible region D If a LP has optimal solutions, then at least one such solution is a basic feasible one. If a LP is feasible and bounded, then it has at least one optimal solution.？
11、Show that the following model is convex programming 2 121 2 3222 41122222 5112261 1221, , , 0,2, 2, , xn nnfxxxRfxexRfxxxfxxx xxxRfxxx xxxRfxc xc xc xxR L Let be a convex set and be a convexfunction defined on , the following mathematicalprogramming is called to be convex programming.min nDRf xDf xx
12、D 1 The objective function is convex when the goalis minimization, otherwise is concave.2 The feasible region is convex when is nonempty.3 The optimal solution set * is convex if * is f xf xDDDD notempty (4) Any local optimal solution is also globally optimal.(5) If the objective function is strictl
13、y convex andthe optimal solution set * is nonempty , then thereis just onf xD ly one optimal solution. Suppose that the feasible region is not empty and the mathematicl model is asmin . . 0, 0, jwhere is convex, all the equaijnDf xstcxiEcxIxRf x lity constraint functionsare liner and all the inequal
14、ity constraint functions are concave？Show that the following results ？Determine whether the following statements are true or not The linear programming is a kind of convex programming. If x* is the only optimal solution to a LP, then it is just an extreme point of the feasible region. For a LP, the optimal solution must be one of extreme points of the feasible region. For a LP, the optimal basic feasible solution must be one of extreme points of the feasible region. For a LP, if the feasible region is nonempty, then there certainly exist at least one optimal solution. 对偶单纯形法The dual theore
