首页 > 其他分享 >【最优化方法】期末考试题型讲解部分 - 凸集的证明

【最优化方法】期末考试题型讲解部分 - 凸集的证明

时间:2024-07-22 11:55:52浏览次数:15  
标签:题型 geq y2 凸集 y1 期末考试 x2 x1 lambda

题型

填空(10道题左右)、证明题、计算题、应用题

证明题

考察:第一章习题

题目

在这里插入图片描述

在这里插入图片描述

证明集合 ( S ) 是凸集

集合 ( S ) 定义如下:

S = { ( x 1 , x 2 ) ∣ x 1 + 2 x 2 ≥ 1 , x 1 − x 2 ≥ 1 } S = \{(x_1, x_2) \mid x_1 + 2x_2 \geq 1, x_1 - x_2 \geq 1 \} S={(x1​,x2​)∣x1​+2x2​≥1,x1​−x2​≥1}

为了证明 S S S 是凸集,我们需要验证对任意的 ( x 1 , y 1 ) ∈ S (x_1, y_1)\in S (x1​,y1​)∈S和 ( x 2 , y 2 ) ∈ S (x_2, y_2) \in S (x2​,y2​)∈S,以及任意的 λ ∈ [ 0 , 1 ] \lambda \in [0, 1] λ∈[0,1],线性组合

λ ( x 1 , y 1 ) + ( 1 − λ ) ( x 2 , y 2 ) \lambda (x_1, y_1) + (1 - \lambda) (x_2, y_2) λ(x1​,y1​)+(1−λ)(x2​,y2​)

也在 S S S 中。即,我们需要证明

λ ( x 1 + 2 y 1 ) + ( 1 − λ ) ( x 2 + 2 y 2 ) ≥ 1 \lambda (x_1 + 2y_1) + (1 - \lambda) (x_2 + 2y_2) \geq 1 λ(x1​+2y1​)+(1−λ)(x2​+2y2​)≥1

λ ( x 1 − y 1 ) + ( 1 − λ ) ( x 2 − y 2 ) ≥ 1 \lambda (x_1 - y_1) + (1 - \lambda) (x_2 - y_2) \geq 1 λ(x1​−y1​)+(1−λ)(x2​−y2​)≥1

成立。

第一个不等式

考虑 ( x 1 , y 1 ) ∈ S (x_1, y_1) \in S (x1​,y1​)∈S和 ( x 2 , y 2 ) ∈ S (x_2, y_2) \in S (x2​,y2​)∈S,根据定义有

x 1 + 2 y 1 ≥ 1 和 x 2 + 2 y 2 ≥ 1 x_1 + 2y_1 \geq 1 \quad \text{和} \quad x_2 + 2y_2 \geq 1 x1​+2y1​≥1和x2​+2y2​≥1

对于 λ ∈ [ 0 , 1 ] \lambda \in [0, 1] λ∈[0,1],我们考虑点

z = λ ( x 1 , y 1 ) + ( 1 − λ ) ( x 2 , y 2 ) = ( λ x 1 + ( 1 − λ ) x 2 , λ y 1 + ( 1 − λ ) y 2 ) z = \lambda (x_1, y_1) + (1 - \lambda) (x_2, y_2) = (\lambda x_1 + (1 - \lambda) x_2, \lambda y_1 + (1 - \lambda) y_2) z=λ(x1​,y1​)+(1−λ)(x2​,y2​)=(λx1​+(1−λ)x2​,λy1​+(1−λ)y2​)

那么

z 1 + 2 z 2 = ( λ x 1 + ( 1 − λ ) x 2 ) + 2 ( λ y 1 + ( 1 − λ ) y 2 ) z_1 + 2z_2 = (\lambda x_1 + (1 - \lambda) x_2) + 2 (\lambda y_1 + (1 - \lambda) y_2) z1​+2z2​=(λx1​+(1−λ)x2​)+2(λy1​+(1−λ)y2​)

= λ ( x 1 + 2 y 1 ) + ( 1 − λ ) ( x 2 + 2 y 2 ) = \lambda (x_1 + 2y_1) + (1 - \lambda) (x_2 + 2y_2) =λ(x1​+2y1​)+(1−λ)(x2​+2y2​)

由于 x 1 + 2 y 1 ≥ 1 x_1 + 2y_1 \geq 1 x1​+2y1​≥1 和 x 2 + 2 y 2 ≥ 1 x_2 + 2y_2 \geq 1 x2​+2y2​≥1,我们有

λ ( x 1 + 2 y 1 ) + ( 1 − λ ) ( x 2 + 2 y 2 ) ≥ λ ⋅ 1 + ( 1 − λ ) ⋅ 1 = 1 \lambda (x_1 + 2y_1) + (1 - \lambda) (x_2 + 2y_2) \geq \lambda \cdot 1 + (1 - \lambda) \cdot 1 = 1 λ(x1​+2y1​)+(1−λ)(x2​+2y2​)≥λ⋅1+(1−λ)⋅1=1

因此,第一个不等式成立。

第二个不等式

同样地,考虑 ( x 1 , y 1 ) ∈ S (x_1, y_1) \in S (x1​,y1​)∈S 和 ( x 2 , y 2 ) ∈ S (x_2, y_2) \in S (x2​,y2​)∈S,根据定义有

x 1 − y 1 ≥ 1 和 x 2 − y 2 ≥ 1 x_1 - y_1 \geq 1 \quad \text{和} \quad x_2 - y_2 \geq 1 x1​−y1​≥1和x2​−y2​≥1

对于 λ ∈ [ 0 , 1 ] \lambda \in [0, 1] λ∈[0,1],我们考虑点

z = λ ( x 1 , y 1 ) + ( 1 − λ ) ( x 2 , y 2 ) = ( λ x 1 + ( 1 − λ ) x 2 , λ y 1 + ( 1 − λ ) y 2 ) z = \lambda (x_1, y_1) + (1 - \lambda) (x_2, y_2) = (\lambda x_1 + (1 - \lambda) x_2, \lambda y_1 + (1 - \lambda) y_2) z=λ(x1​,y1​)+(1−λ)(x2​,y2​)=(λx1​+(1−λ)x2​,λy1​+(1−λ)y2​)

那么

z 1 − z 2 = ( λ x 1 + ( 1 − λ ) x 2 ) − ( λ y 1 + ( 1 − λ ) y 2 ) z_1 - z_2 = (\lambda x_1 + (1 - \lambda) x_2) - (\lambda y_1 + (1 - \lambda) y_2) z1​−z2​=(λx1​+(1−λ)x2​)−(λy1​+(1−λ)y2​)

= λ ( x 1 − y 1 ) + ( 1 − λ ) ( x 2 − y 2 ) = \lambda (x_1 - y_1) + (1 - \lambda) (x_2 - y_2) =λ(x1​−y1​)+(1−λ)(x2​−y2​)

由于 x 1 − y 1 ≥ 1 x_1 - y_1 \geq 1 x1​−y1​≥1 和 x 2 − y 2 ≥ 1 x_2 - y_2 \geq 1 x2​−y2​≥1,我们有

λ ( x 1 − y 1 ) + ( 1 − λ ) ( x 2 − y 2 ) ≥ λ ⋅ 1 + ( 1 − λ ) ⋅ 1 = 1 \lambda (x_1 - y_1) + (1 - \lambda) (x_2 - y_2) \geq \lambda \cdot 1 + (1 - \lambda) \cdot 1 = 1 λ(x1​−y1​)+(1−λ)(x2​−y2​)≥λ⋅1+(1−λ)⋅1=1

因此,第二个不等式也成立。

S S S是凸集。

END

标签:题型,geq,y2,凸集,y1,期末考试,x2,x1,lambda
From: https://blog.csdn.net/weixin_73002968/article/details/140217887

相关文章

  • 【算法设计与分析】期末考试复习 - 基础知识(基础知识超详细)
    文章目录前言引言问题问题描述实例目标数学表达步骤示例伪代码解释1.问题的复杂度冒泡排序笔记选择排序笔记插入排序笔记归并排序笔记快速排序笔记一些问题哪个排序算法效率最高?是否可以找到更好的排序算法?排序问题计算难度如何?其他排序算法的复杂度问题计算复杂度估......
  • 求助大佬——期末考试评分标准(浙大)C语言
    最主要的问题是:1.不知道怎么控制输入的结束2.成绩部分既有可能是数字也有可能是汉字,那我该怎么写输入的函数呢浙大某年度期末考试的评分标准是这样的:总评成绩=考勤+作业x20%+阶段测试x25%+ 理论考试x35%+ 实验考试调整分数作业、阶段测试、理论考试是百分制。考......
  • 【期末考试复习】概率论与数理统计(知识点模式 - 复习题2)
    题目:设随机变量XXX的概率密度函数为f(x......
  • Python期末考试知识点(史上最全)
     python简介type()不会认为子类是一种父类类型。isinstance()会认为子类是一种父类类型基础语法运算符:算术运算符:多了一个**,代表幂方5**5就是5的5次方还多了一个//整数除法逻辑运算符:and,or,not与,或,非赋值运算符:没有++,–身份运算符:......
  • 背包题型总结
    概述大致分为以下几类:01背包完全背包混合背包二维背包分组背包以及一个变式:跳楼梯模型,本质是转移顺序的改变。01背包特点:无序加入,每个物品加一次。完全背包特点:无序加入,每个物品无限加。变式:跳楼梯模型:问跳完一段楼梯有多少种不同的方案数。这两者的区别就在于:......
  • 期末考试游记
    在一楼考,神志比较清晰。第一天社会(ZJ的政史地合称),看到前两面直接懵了,感觉题目比前几次难。做到后面就还好,政治地理大题照常写满。因为这边是不让开卷考的,所以题目没那么活,最多也就把一两个知识点写上去写满,所以还算轻松。结束之后判断题最后一题争议有些大,最后的情况是TF都给......
  • 个人python面试准备的一些题型
    Python类方法vs静态方法类方法(ClassMethods)类方法使用@classmethod装饰器定义,它们的第一个参数通常命名为cls,代表类本身。特点:可以访问和修改类的状态不能访问实例的状态可以用来定义替代构造器示例:classMyClass:class_variable=0@classmethoddefi......
  • 复旦大学2023--2024学年第二学期高等代数II期末考试情况分析
    一、期末考试成绩班级前几名的同学施想(95)、侯煜天(94)、刘升(92)、洪临依(92)、王龙晨(92)、文俊(90)、徐亦闵(89)、邓海斌(89)、褚乐一(89)二、总评成绩计算方法作业成绩根据交作业的次数决定。本学期提交作业共13次,10次100分,少1次扣10分。总评成绩=作业成绩*15%+期中成绩*......
  • 老师怎样一键发布期末考试成绩?
    期末考试的钟声一响,老师们便开始了紧张的阅卷工作。成绩出来后,他们又面临着一项繁琐的任务——将成绩单逐一私信给每位学生的家长。这不仅耗费了大量时间,也让老师们在繁忙的期末工作中倍感压力。期末老师的工作已经够多够繁琐,我们该如何为他们减轻负担呢?易查分小程序:老师减......
  • 复旦大学2023--2024学年第二学期(23级)高等代数II期末考试第七大题解答
    七、(10分) 设$V$是$n$阶实矩阵全体构成的实线性空间, $A$是$n$阶正定实对称阵.对任意的$X,Y\inV$,定义二元函数$(X,Y)=\mathrm{tr}(XAY')$.(1)求证:$(-,-)$是$V$上的一个内积.(2)在上述内积下,$V$成为一个欧氏空间. 设$P,Q\inV$,$V$上的线性算子$......