《凸优化2017课件Lecture4_convex_problems》由会员分享，可在线阅读，更多相关《凸优化2017课件Lecture4_convex_problems（45页珍藏版）》请在金锄头文库上搜索。
1、Convex Optimization ProblemsSpring 2016-2017Yuanming ShiShanghaiTech UniversityOutline1Optimization Problems2Convex Optimization3Quasi-Convex Optimization4Classes of Convex Problems: LP, QP, SOCP, SDP5Multicriterion Optimization (Pareto Optimality)2Optimization Problems in Standard Form Iminimizexf0
2、(x)subject tofi(x) 0i = 1, ,mhi(x) = 0i = 1, ,px = (x1, ,xn) is the optimization variablef0: Rn R is the objective functionfi: Rn Ri = 1, ,m are the inequality constraint functionshi: Rn Ri = 1, ,p are the equality constraint functions3Optimization Problems in Standard Form IIFeasibility:a point x d
3、omf0is feasible if it satisfies all the constraints and infeasible otherwisea problem is feasible if it has at least one feasible point and infeasible otherwise.Optimal value:p?= inff0(x) | fi(x) 0, i = 1, ,m, hi(x) = 0, i = 1, ,pp?= if problem is infeasible (no x satisfies the constraints)p?= if pr
4、oblem is unbounded belowOptimal solution: x?such that f(x?) = p?(and x?feasible).4Global and Local OptimalityA feasible x is optimal if f0(x) = p?; Xoptis the set of optimal points.A feasible x is locally optimal if it is optimal within a ball, i.e., there is an R 0 such that x is optimal forminimiz
5、ezf0(z)subject tofi(z) 0i = 1, ,mhi(z) = 0i = 1, ,pkz xk2 RExample:f0(x) = 1/x, domf0= R+: p?= 0, no optimal pointf0(x) = x3 3x: p?= , local optimum at x = 1.5Implicit ConstraintsThe standard form optimization problem has an explicit constraint:x D =mi=0domfipi=1domhiD is the domain of the problemTh
6、e constraints fi(x) 0,hi(x) = 0 are the explicit constraintsA problem is unconstrained if it has no explicit constraintsExample: minimizexlog(b aTx)is an unconstrained problem with implicit constraint b aTx6Feasibility ProblemSometimes, we dont really want to minimize any objective, justto find a fe
7、asible point:findxxsubject tofi(x) 0i = 1, ,mhi(x) = 0i = 1, ,pThis feasibility problem can be considered as a special case of a general problem:minimizex0subject tofi(x) 0i = 1, ,mhi(x) = 0i = 1, ,pwhere p?= 0 if constraints are feasible and p?= otherwise.7Stationary PointsGiven a smooth function f
8、 : Rn R, a point x Rnis called A stationary point, if f(x) = 0; A local minimum, if x is a stationary point and there exists a neighborhood B Rnof x such that f(x) f(y) for any y B; A global minimum, if x is a stationary point and f(x) f(y) for any y Rn; A strict saddle point, if x is a stationary p
9、oint and for any neighborhood B Rnof x, there exist y,z B such that f(z) f(x) f(y) and min(2f(x) 014Equivalent Reformulations IEliminating/introducing equality constraints:minimizexf0(x)subject tofi(x) 0i = 1, ,mAx = bis equivalent tominimizezf0(Fz + x0)subject tofi(Fz + x0) 0i = 1, ,mwhere F and x0
10、are such that Ax = b x = Fz + x0for some z.15Equivalent Reformulations IIIntroducing slack variables for linear inequalities:minimizexf0(x)subject toaTix bii = 1, ,mis equivalent tominimizex,sf0(x)subject toaTix + si= bii = 1, ,msi 016Equivalent Reformulations IIIEpigraph form: a standard form conve
11、x problem is equivalent tominimizex,ttsubject tof0(x) t 0fi(x) 0i = 1, ,mAx = b17Equivalent Reformulations IVMinimizing over some variables:minimizex,yf0(x,y)subject tofi(x) 0i = 1, ,mis equivalent tominimizexf0(x)subject tofi(x) 0i = 1, ,mwheref0(x) = infyf0(x,y)18Outline1Optimization Problems2Conv
12、ex Optimization3Quasi-Convex Optimization4Classes of Convex Problems: LP, QP, SOCP, SDP5Multicriterion Optimization (Pareto Optimality)19Quasiconvex Optimizationminimizexf0(x)subject tofi(x) 0i = 1, ,mAx = bwhere f0: Rn R is quasiconvex and f1, ,fmare convex Observe that it can have locally optimal
13、points that are not (globally) optimal:20Quasiconvex OptimizationConvex representation of sublevel sets of a quasiconvex function f0: there exists a family of convex functions t(x) forfixed t such thatf0(x) tt(x) 0Example:f0(x) =p(x) q(x)with p convex, q concave, and p(x) 0, q(x) 0 on domf0. We can
14、choose: t(x) = p(x) tq(x) for t 0, t(x) is convex in x p(x)/q(x) t if and only if t(x) 021Quasiconvex OptimizationSolving a quasiconvex problem via convex feasibility problems: the idea is to solve the epigraph form of the problem with a sandwich technique in t:for fixed t the epigraph form of the o
15、riginal problem reduces to a feasibility convex problemt(x) 0,fi(x) 0i,Ax bif t is too small, the feasibility problem will be infeasibleif t is too large, the feasibility problem will be feasiblestart with upper and lower bounds on t (termed u and l, resp.) and use a sandwich technique (bisection me
16、thod): at each iteration use t = (l + u)/2 and update the bounds according to the feasibility or infeasibility of the problem.22Outline1Optimization Problems2Convex Optimization3Quasi-Convex Optimization4Classes of Convex Problems: LP, QP, SOCP, SDP5Multicriterion Optimization (Pareto Optimality)23Clas
