信息检索与数据挖掘 2019/4/22 17 优化问题(Optimization problems) Source:《Convex Optimization》,Stephen Boyd ·日标函数 fo(x) Chapter 4 Convex optimization problems 。不等式约束 fi(x),i=1,....,m 。等式约束 hx),i=1,…p We use the notation minimize fo(z) subject to f(r)≤0，i=1,.,m (4.1) h(x)=0,i=1,..,p to describe the problem of finding an x that minimizes fo(r)among all r that satisfy the conditions fi(x)≤0，i=1,,m,andh(c)=0,i=l,.,p.We call r∈R" the optimization variable and the function fo:R"-R the objective function or cost function.The inequalities fi(r)<0 are called inequality constraints,and the corresponding functions fi:R"-R are called the inequality constraint functions. The equations hi(r)=0 are called the equality constraints,and the functions hi:R"-R are the equality constraint functions.If there are no constraints (i.e., m =p=0)we say the problem (4.1)is unconstrained
信息检索与数据挖掘 2019/4/22 17 优化问题（Optimization problems） • 目标函数 f0 (x) • 不等式约束 f i (x), i=1,…,m • 等式约束 hi (x) , i=1,…,p Source: 《Convex Optimization》,Stephen Boyd Chapter 4 Convex optimization problems
信息检索与数据挖掘 2019/4/2218 QP问题 ·linear program(LP) minimize cTx+d subject to Gx≤h Ax=b G∈Rmxn and A∈Rpxn minimize (1/2)xTPx +qTa+r quadratic program (OP) subject to Gx≤h Ax =b. P∈S,G∈Rmxn,and A E Rpxn Find w and b such that (w)=%wTw is minimized: and for all ((xi)):y (wTxi+b)>1 Source:《Convex Optimization》,Stephen Boyd Chapter 4 Convex optimization problems
信息检索与数据挖掘 2019/4/22 18 QP问题 • linear program (LP) • quadratic program (QP) Source: 《Convex Optimization》,Stephen Boyd Chapter 4 Convex optimization problems Find w and b such that Φ(w) =½ wTw is minimized; and for all {(xi ,yi )}: yi (wTxi + b) ≥ 1
信息检索与数据挖掘 2019/4/22 20 拉格朗日对偶 Source:《Convex Optimization》,Stephen Boyd Chapter 4 Convex optimization problems minimize fo(x) subject to i=1,.,m h(x)=0,i=1,,p The basic idea in Lagrangian duality is to take the constraints into account by augmenting the objective function with a weighted sum of the constraint functions. L(c,入，v)=fo(a)+∑if(e)+∑hi() i=1 i三1 The vectors and v are called the dual variables or Lagrange multiplier vectors associated with the Problem. A=e=s(o+三i+豆A》 x∈D
信息检索与数据挖掘 2019/4/22 20 拉格朗日对偶 • The basic idea in Lagrangian duality is to take the constraints into account by augmenting the objective function with a weighted sum of the constraint functions. • The vectors λ and ν are called the dual variables or Lagrange multiplier vectors associated with the Problem. Source: 《Convex Optimization》,Stephen Boyd Chapter 4 Convex optimization problems
信息检索与数据挖掘 2019/4/22 21 不等式约束 Solving the Optimization Problem Find w and b such that (w)=%wTw is minimized; and for all ((xi)):y(wxi+b)>1 上述问题实际上是在线性约束条件下的二次函数优化问题。该问题是数学中的 基本问题之一，存在很多解决算法（比如，有一些二次规划库） L= 2uP-∑an*{(u2n+)-1 每个拉格朗日因子α对应一个 不等式约束1-y:(wX+b)≤0 The solution involves constructing a dual problem where a Lagrange multiplier a;is associated with every constraint in the primary problem: Find a...av such that Q(a)ax is maximized and (1)ay,=0 (2)o,≥0 for all a
信息检索与数据挖掘 2019/4/22 21 Solving the Optimization Problem Find w and b such that Φ(w) =½ wTw is minimized; and for all {(xi ,yi )}: yi (wTxi + b) ≥ 1 Find α1…αN such that Q(α) =Σαi - ½ΣΣαiαj yi yjxi Txj is maximized and (1) Σαi yi = 0 (2) αi ≥ 0 for all αi 上述问题实际上是在线性约束条件下的二次函数优化问题。该问题是数学中的 基本问题之一，存在很多解决算法 (比如，有一些二次规划库) The solution involves constructing a dual problem where a Lagrange multiplier αi is associated with every constraint in the primary problem: 不等式约束 每个拉格朗日因子αi对应一个 不等式约束 1 - yi (wTxi + b) ≤ 0
信息检索与数据挖掘 L(w,b,a)-lwo-c(wx+)-1 根据拉格朗日对偶性，原始的约束最优化问题可等价于极大极小的对偶问题： max min L(w,b,a) a w,b 将L(w,b,a)对w,b求偏导并令其等于0，则 aL N N 8w =0一 C=0→w= QiyiTi =1 i=1 aL N ab a=0→ a=0 将上述式子代入拉格朗日函数（③）中，对偶问题转为 1 NN max 等价于最优化问题： 1 NN N min a aaj(c·)- -1-1 N s.t. ∑a=0 =1 https://www.cnblogs.com/en-heng/p/5965438.html ai≥0，i=1,2,…,N
信息检索与数据挖掘 2019/4/22 22 https://www.cnblogs.com/en-heng/p/5965438.html