Kuangrepi的博客

内容总结（参考博客https://bruceyuan.com/post/deepseek-r1-paper-reading-notes.html）

1. 基于过程的奖励模型、强化学习、以及搜索算法，如蒙特卡罗树搜索 和束搜索。然而，这些方法都未能达到与 OpenAI 的 o1 系列模型在通用推理能力上的同等水平。

2. 本研究首次尝试使用纯强化学习来提升语言模型的推理能力。探索 LLM 在没有任何监督数据的情况下开发推理能力的潜力，重点关注其通过纯 RL 流程实现的自我演化。

3. 这篇 Paper 一共介绍了三个重要的模型：

   • DeepSeek-R1-Zero
     • 结论是只用 RL 就可以提升模型效果，非常具有启发性。
   • DeepSeek-R1
     • Reasoner 模型很强很强。
     • 通过多阶段的训练，相对于只用 RL，可以进一步提升模型效果。
   • DeepSeek-R1-Distill 的系列模型
     • 结论是：在小模型上，在【大模型上进行蒸馏】效果会好于【用 R1 的方式做训练】。

4. Deepseek-R1-Zero

   • 回答问题的格式要符合以下格式
     • 思考的步骤要包含在 <think>思考过程</think>。
     • 最终的结果要包含在 <answer>最终结果</answer>。
     • 并且需要让模型先思考，然后再问题。
   • 强化学习
     • 使用 GRPO 强化学习算法。
     • 奖励有两种
       • 最终结果的精确奖励。模型最终输出的答案是否正确。
       • 中间格式的格式奖励。模型是否先输出 <think>xxx</think>，然后输出<answer>xxx</answer> 这样的格式。
   • 模型在 RL 的催化下自我进化的能力。具体是指：
     • 越训练，模型的思考越长，输出的 token 越多。
     • 模型会在中间的思考过程中出现【反思、纠正、重新评估、重新探索】等行为增强模型思考和解决问题的能力。

5. Deepseek-R1

   • 收集 long-cot 数据作为冷启动数据来监督微调

   • 增加语言一致的奖励

   • 拒绝采样收集 SFT 数据（推理以及非推理数据）

   • 全场景强化学习：

     • 对于推理数据，我们还是和 deepseek-r1-zero 一样，采用规则奖励的模型作奖励信息训练。

       对于非推理数据，我们采用 reward-model 作为奖励信号，这是为了捕获细微场景的人类偏好

   • 优点

     • 可读性提高：语言一致
     • 推理能力更强
     • 有用性与无害性

6. Deepseek-R1-Distill

   • 方式1：直接用 deepseek-r1 蒸馏数据，让小模型学习（SFT）。
   • 方式2：小模型采用 deepseek-r1 同样的 pipeline 作训练，获得这样的能力。
   • 最终的结果看，蒸馏的效果好于直接用小模型作RL训练。

7. 不成功的尝试

   1. 过程奖励模型 (Process Reward Model, PRM)
      • 难以明确定义细粒度步骤：在通用推理任务中，很难显式地定义每一步的细节。
      • 中间步骤的正确性难以判断：确定当前中间步骤是否正确是一个挑战。使用模型进行自动标注往往无法得到理想结果，而人工标注则难以扩展。
      • 奖励黑客问题 (Reward Hacking)：一旦引入基于模型的 PRM，就不可避免地会出现奖励黑客现象 (Gao et al., 2022)。此外，重新训练奖励模型需要额外的训练资源，使整个训练管道更加复杂。
   2. Monte Carlo Tree Search（MCTS）
      • 在语言模型中，词表太大了，基本都十几K，因此搜索空间太大了。
      • 如果采用最大的探索限制，又容易产生局部最优。
      • value model 很难训练，不好评估当前的步骤是否是好的。

英语单词

1. preliminary 初始的
2. cold-start data 冷启动数据：模型首次启动时来帮助其进入工作状态的数据
3. distilled from 由...蒸馏得到
4. diminish 减少
5. component 组成部分
6. align with 与...一致
7. minimal 最少的
8. reasoning-oriented 面向推理的
9. convergence 收敛
10. rejection sampling 拒绝采样
11. validate 验证
12. incentivize 激励
13. inclusion 包含
14. constraint 约束
15. trajectory 轨迹

内容总结

1. 面对具有挑战性的输入查询，让语言模型在测试阶段有效利用额外的计算，从而提高其响应的准确性。
2. 有部署适应性“计算最优”策略的必要性，即根据提示选择利用测试时计算的具体方法，以最佳利用额外的计算资源。
3. 两种测试时计算修改方法：测试时计算应当修改分布，从而生成比直接从LLM采样更好的输出。
   1. 输入层面：通过在给定提示中增加一组额外的标记，使LLM在此基础上获得修改后的分布（本研究使用通过改变输入tokens直接修改提议分布）
   2. 输出层面：通过从标准语言模型中采样多个候选输出并对这些候选进行处理。（本研究使用验证器）
4. 估计问题难度实现计算优化扩展
   1. 用pass@1率估计难度
   2. 提出一个公式计算在计算预测 N 下针对问题 q 的计算优化扩展策略。
5. 通过验证器扩展测试时计算
   1. 用一种无需人工标签，而是通过从每个解决步骤运行蒙特卡罗展开来监督 PRM 的 PRM 训练方法。（此外提到 PRM 总是优于 ORM）
   2. 答案聚合（Answer aggregation），以确定最佳答案：先逐步聚合获得答案最终评分，然后在答案之间聚合以确认最佳答案。
      1. 逐步聚合：使用PRM在最后一步的预测作为完整答案的评分优于取乘积或最小值来聚合每步评分等方法。
      2. 答案间聚合：使用加权最优（best-of-N weighted）。
   3. 通过 PRM 的搜索方法
      1. Best-of-N
      2. 束搜索（Beam Search）：N 个预测选 M 个分数最高答案，再对每个选出的答案扩展出 N 个下一步，重复此过程。
      3. 前瞻搜索（Lookahead search）：在束搜索每一步向前模拟 k 步，提高 PRM 对当前步骤的价值估计准确性。但是会消耗额外计算资源。
      4. 结果：小预算束搜索明显优于 Best-of-N，预算增加则改进显著减小，前瞻搜索则在相同预算下表现不佳。
      5. 哪些问题适合搜索改进：束搜索在较难问题和较低计算预算下更为有效，而 best-of-N 在较简单问题和较高预算下更具优势。最难问题任何方法都一般。
   4. 改善提议分布：使模型能够迭代地修正自己的答案，从而在测试时动态改善自身的分布。
      1. 修正数据：在上下文中包含最多四个错误答案，具体数量从0到4的均匀分布中随机采样。使用字符编辑距离度量来优先选择与最终正确答案相关的错误答案。
      2. 顺序采样的解决方案表现优于并行采样。
   5. 平衡预训练和测试时计算：在简单和中等难度的问题中，这些问题在模型的能力范围内，或者在推理需求较小的环境中，测试时间计算可以轻松弥补额外的预训练。然而，在更具挑战性的问题上，这些问题超出了给定基础模型的能力，或者在推理需求较高的情况下，预训练更可能对提升性能更加有效。

英语单词

1. non-trivial 不凡的
2. implications 影响
3. tradeoff 权衡
4. primary 主要的
5. adaptively 自适应地
6. compute-optimal 计算最优的
7. install ... into 将...赋予
8. avenue 途径
9. agenic 代理的，自主的
10. proposal distribution 提议分布：为了获取所需样本而设计的一种分布方式。
11. alter 改变
12. efficacy 有效性
13. extent 程度
14. substitute for 替代
15. be 1-to-1 exchangeable with 一一对应的
16. modify 修改
17. knob 方法
18. post-hoc 后验的
19. be reminiscent of 使人想起，类似于
20. aggregate 聚合，汇总
21. canonical 典型的，经典的
22. wherein 其中
23. allocate 分配
24. revision 修正
25. sophisticated 复杂的
26. notion 概念
27. ad-hoc 随意的，临时的
28. discrete 离散的
29. concretely 具体地
30. feasible 可行的
31. incur 招致
32. confounder 混淆因素
33. two-fold cross validation 二折交叉验证。它是一种将数据集分为两部分，一部分用于训练模型，另一部分用于验证模型的方法。
34. vice versa 反之亦然
35. protocol 协议

基础操作

1. 场景编辑
   1. 位移：shift ＋ 鼠标中键
   2. 旋转：长按鼠标中键
   3. 放大缩小：鼠标滚轮
   4. 新建对象：shift + A
2. 视图调整：小键盘
   • 1：正视图
   • 3：侧视图
   • 5：透视图
   • 7：顶视图
   • 实心键：最大化显示
3. 对象编辑：
   1. 独立显示：/
   2. 位移：G
   3. 旋转：R
   4. 缩放：S
   5. X，Y，Z：选择轴进行位移，旋转，缩放
   6. 透显：Alt + Z
   7. 打开编辑：ctrl + tab
   8. 倒角（把角或者边变形）ctrl + B

渲染

1. 分裂出三个窗口，一个显示，一个材质，一个编辑
2. 摄像机
   1. 0：进入计算机视角
   2. 侧边栏
      1. 视图锁定摄像机调节角度
   3. 增大焦距，防止畸变
3. 材质

内容总结（关于test-reasoning)

1. 测试时推理核心是反馈建模和搜索策略

   

2. 反馈建模

   1. 基于分数的反馈：利用验证器
      1. 基于结果的验证器（ORM）：使用最终思维链结果的正确性作为训练反馈。
      2. 基于过程的验证器（PRM）：则基于每个推理步骤的反馈进行训练。不仅评估中间推理步骤，而且比 ORM 更准确地评估整个推理过程。
         1. PRM 需要更多的人力来注释中间步骤的反馈：蒙特卡洛树搜索（MCTS）算法自动收集高质量的过程监督数据。
         2. PRM 应该评估每个步骤对后续推理的优势，而不仅仅关注其正确性：过程优势验证器（PAVs），并通过蒙特卡洛模拟有效地构建训练数据。
         3. 基于分数的反馈建模忽略了大型语言模型的生成能力，使得难以检测细粒度的错误：GenRM利用指令调整使验证器能够回答“答案是否正确（是/否）？”，并使用生成“是”标记的概率作为分数。GenRM 还可以结合思维链，允许验证器在回答“是”或“否”之前生成相应的理由。
         4. CriticRM联合训练评论模型和验证器。在推理过程中，验证器根据答案和评论模型生成的基于语言的反馈进行评分。（这也放在这一段么？）
   2. 基于语言的反馈：充分利用了大型语言模型的指令遵循能力。通过设计特定的指令，它可以进行成对比较，从多个维度评估答案，甚至以自然语言提供修改建议。
      1. 面临诸如长度、位置和困惑度等偏差：精心设计系统指令以减轻偏差的干扰。
      2. 获得更便宜的基于语言的反馈：监督微调评估模型。
      3. 精细的评估维度：分别训练一个单独的评估模型和一个成对排序模型，然后通过权重合并将它们统一到一个大型语言模型中。
      4. 评估标准更灵活，生成的评估数据更多样化，并且与人类行为更一致：确定每个查询的评估标准，并生成相应的语言反馈。

3. 搜索策略

   

   1. 重复采样：采样策略如 top - p 和 top - k 是大型语言模型推理中常用的解码算法。重点在于验证策略，就是怎么评分。
      1. 多数投票
         1. 犯类似错误：在投票前进行验证或过滤。
      2. Best of N
         1. 变体：根据验证器分数对答案进行加权投票。
         2. 效率低：
            1. 修剪得分低的采样，停止其进一步生成。
            2. PRS使大模型能够自我评论和自我纠正，以减少采样次数。
         3. 改进训练：通过 BoN 采样训练模型以近似 BoN 分布，从而减少推理过程中的搜索空间。
   2. 自我纠正：使大型语言模型能够根据外部或内部反馈迭代地修改和完善生成的结果。
      1. 反馈来源
         1. 人类评估
         2. 工具检查：如编译器检查代码。
         3. 外部模型评估：大模型当评论者，多智能体辩论。
         4. 内在反馈：大模型自我评论。
      2. 有效性争议：被质疑有效性是否高：主要性能瓶颈在于定位错误，建议微调特定模型。
      3. 改进训练：监督微调，在线模仿学习，多轮强化学习方法。
   3. 树搜索：搜索算法和价值函数是树搜索中的两个关键组件。
      1. 搜索算法
         1. 无信息搜索：DFS，BFS，Beam search。
         2. 启发式搜索：MCTS 通过选择、扩展、模拟和反向传播四个步骤逐渐优化搜索结果，接近最优解。Long 使用强化学习训练一个大型语言模型控制器来引导大型语言模型推理器的搜索路径。
      2. 价值函数
         1. RAP 设计一系列启发式价值函数，依任务组合。
         2. AlphaMath 和 TS - LLM 用大语言模型价值函数替代手工函数。
         3. 传统 MCTS 只扩展一个轨迹，rStar 保留多候选路径，用另一个大语言模型推理选路径，并选择两个大模型推理一致的路径。
         4. SC - MCTS 用多个外部奖励模型作价值函数。
      3. 改进训练：奖励函数与偏好优化。

英语单词

1. modification 改良

2. calibration 校准

3. modality 模态，形式

4. scarcity 稀缺

5. computational 计算的

6. shortcoming 缺点

7. intuitive 直觉的

8. inference 推理

9. perceptual 概念的

10. pattern 模式

11. assumption 假定

12. generalization 泛化

13. leverages 利用

14. steer 引导

15. modify 修改

16. calibrate 校准

17. preliminary 初步的

18. decompose 分解

19. simulate 模拟

20. remainder 其余部分

21. deliberate 深思熟虑的

22. perceptual 感知的

23. explicitly 明确的，显式的

24. incrementally 逐步的

25. be prone to 容易，倾向于

26. empirical 实证的，经验主义的

27. cumulative 累计的

28. etrieval-augmented 搜索增强的

29. mitigate 减轻

30. utilize 利用

31. finetune 微调

32. taxonomy 分类

33. distribution 分布

34. obtain 获得

35. optimization 优化

36. algorithm 算法

37. auxiliary 辅助的

38. entropy 熵

39. marginal 边际的

40. pitfalls 陷阱

41. trivial 微不足道的

42. regulation 规则化

43. multilingual 多语言的

44. cross-modal 跨模态的

45. retrieval 检索

46. caption 字幕

47. scenarios 场景

48. normalization 归一化

49. propagation 传播

50. covariance 协方差

51. gradient 梯度

52. catastrophic 灾难性的

53. episodic 情节的

54. latency 延迟

55. incremental 增量的

56. exponential 指数的

57. incorporate 结合

58. stem from 源于

59. in-context 上下文的

60. selection 选择

61. objective 目标

62. empirical 实证的

63. semantically 语义上地

64. descending 降序的

65. implicit 隐式的

66. Bayesian 贝叶斯

67. sequentical 顺序的

68. annotation 注释 annotate 注释

69. subsequent 后续的

70. traversal 遍历的

71. bottleneck 瓶颈

72. externalize 外化

73. steering 指导的

74. residual 残差的

75. alleviate 降低

76. hallucination 幻觉

77. toxicity 毒性

78. compromise 影响

79. calibrate 校准

80. contextual 上下文的

81. transferability 可移植性

82. component 组成部分

83. alignment 对齐

84. rationale 理由

85. critique 评论

86. verbal-based 基于语言的

87. interpretability 可解释性

88. pairwise 成对的

89. revision 修改

90. coherence 连贯性

91. alignment 对齐性

92. consistency 一致性

93. biase 偏差

94. perplexity 困惑

95. mitigate 减轻

96. annotation 符号

97. criteria 批评

98. distill 提炼

99. unify ... into 统一成

100. align ... with 符合

101. verify 验证

102. ensemble 集成

103. vanilla 普通的

104. validation 验证

105. executable 可执行的

106. variant 变体

107. surpass 超过

108. prune 修剪

109. threshold 阈值

110. intrinsic 内部的

111. scalability 可扩展性

112. template 模板

113. synthetic 合成的

114. substantial 实质性的

115. be susceptible to 容易受到...的影响

116. adversarial 对抗性的

117. stance 立场

118. topological 拓扑的

119. sparse 稀疏的

120. be inferior to 比...差

121. consensus 共识

122. arithmetic 算术的

123. degradation 下降

124. controversial 争议性的

125. guaranteed 保证的

126. oracle 预言

127. decouple 解耦

128. aforementioned 前面提到的

129. manually 手动的

130. trajectory 轨迹

131. parallel 并行的

132. heuristic 启发式的

133. conjecture 猜想

134. multimoda 多模态

135. cache 缓存

136. compression 压缩

137. speculative 推理的

原博客连接：https://huggingface.co/spaces/HuggingFaceH4/blogpost-scaling-test-time-compute

内容总结

1. 理解：利用奖励模型在推理阶段扩展
2. TTC的两种策略：
   1. 自我优化，利用大模型来评价
   2. 利用奖励模型进行评估（本文利用这种方法）
      1. PRM：可以对每个过程进行评估
      2. ORM：只能评估最后结果
3. 搜索答案方法（类似语言模型的采样方法，分数类似概率）
   1. Best-of-N：所有待选项选择最好的。
   2. Beam search：每次在M个待选答案中保留最高的N个继续搜索，最终选择总体概率最高的路线。
   3. Diverse Verifier Tree Search：独立的进行两个beam search，最后比较各自的最佳结果。
   4. 此外文章还用到了不需要 PRM 的 Majority voting：选重复最多次的答案。
4. 流程
   1. 对问题生成多个答案
   2. 利用PRM评估所有答案，通过搜索策略选择出几个最好答案
   3. 再利用选择答案以及相应提示词继续生成多个答案，循环往复，直到EOS的token。
5. 提出了一个公式，根据你的计算量预算，题目难度来选择搜索方法。

理解

1. 利用test-time compute，可以让小模型的准确率大大提升。
2. 有点类似LoRA，主要依赖一个奖励函数和一套运行逻辑，而不需要改变模型本身参数。

英语单词

1. scaling 扩展 scalable 可扩展的

   Over the last few years, the scaling of train-time compute has dominated the progress of large language models (LLMs).

2. paradigm 模式

3. clusters 集群

4. on the horizon 即将

5. complementary 补充的

6. inference 推理

7. optimally 最佳的，优化的 optimise 优化

8. iterative 迭代的 iteration 迭代

9. self-refinement 自优化

10. allocate 分配

11. rival 匹敌

12. outperform 胜过

13. prompt 提示词

14. counterpart 对应的人或事物

    By adaptively allocating test-time compute per prompt, smaller models can rival—and sometimes even outperform—their larger, more resource-intensive counterparts.

15. constrained 有限的

16. implementation 实现

17. verifier 验证，验证器

18. benchmark 基准测试

19. ingredients 成分

20. subsequent 后续的

21. built-in 内置的

22. mechanism 机制

23. candidate 候选人，候选者

24. sample 采样

25. intermediate 中间的

26. fine-grained 细粒的，详细的，深入的

27. split 拆分

28. overall 整体的

29. diagram 图解

30. derivation 推导

31. PRM 过程奖励模型 ORM 结果奖励模型

32. terminate 结束，终止

33. parameter 参数

34. unsaturated 不饱和性

35. variance 方差

36. incorporate 纳入，包含

37. self-consistency 自洽

38. aggregate 聚合 in aggregate 总的来说

39. quirk 怪癖

40. eval 评估

41. subtlety 微妙之处

42. convert 转换

43. subtract 减去

44. canonical 标准，典型

45. plateau 平稳的

46. approximately 大约 approximation 近似

47. plausible 貌似合理的，似乎可信的

48. variant 变体

49. weighted 加权的

50. identical 相同的

51. prioritise 优先考虑

52. concatenation 连接，拼接

53. extract 提取

54. cumulative 累计的

55. literature 文献

56. product 乘积

57. vanilla 普通的

58. fall short of 未达到

59. criterion 标准

60. partial 部分的

61. token 标记

62. verify 验证

63. hyperparameter 超参数

64. tradeoff 权衡取舍

65. distribution 分布

66. bin...into 将...分为

67. quintiles 五等分

68. assign 分配

69. heuristic 启发式方法

70. oracle 预言机

71. ground truth 通过直接观察获得的信息

72. intuition 直觉

73. collapse 坍塌

74. prompt 促使，提示

75. modification 修改

76. kick in 开始起作用

77. manifest 体现

78. optimal 最优

79. fade in 消失

80. surpass 超过

81. leverage 利用

82. robustness 鲁棒性

83. holy grail 圣杯

84. validate 验证

85. fine-tuning 微调

86. nuanced 细微的

87. sheds light on 阐明

88. integrate 集成

89. incorporate 纳入，包含

90. explicit 明确的

91. resemble 类似于

92. inherently 本质上地

网上发现没人解决这个，自己试出来了。

使用Typora有一个很难受的地方，你想打开两个md文件左右对照看，然后你在打开一个md文件的情况下，点击打开另一个md文件，Typora就会给你展示一下它的欢迎页面，然后就没有然后了。你用Typora里面的打开文件功能也不行。

解决方案

右键点击Typora图标，以管理员身份运行，然后在那个窗口用左上角的文件—打开...打开第一个文件，然后继续打开第二个文件，就能成功打开两个文件了，原理未知。

1. 上下标

   1 2	<sub>下标</sub> <sup>上标</sup>

2. 一些用来复制粘贴的符号，不知道为什么Typora不能用一些公式

   1. 包含：⊆
   2. 等价于：⇔
   3. 任意：∀
   4. lambda λ （笑死了，一直以为是lamda，被周志华的组误导了）
   5. 求和：∑
   6. 连乘：∏
   7. 梯度：∇
   8. 复合：∘
   9. h̃，w̃，z̃，θ，φ

凸集合

1. 仿射，凸集，锥

1. 组合：θ₁x₁+...+θ_kx_k被称为点x₁，...，x_k的...组合当...
   1. 仿射组合： θ₁+...+θ_k = 1
   2. 凸组合：θ₁+...+θ_k = 1；θ₁，...，θ_k > 0
   3. 凸锥组合：θ₁，...，θ_k > 0
2. 包：C ⊆ Rⁿ 中点的所有...组合组成的集合
   1. 仿射包： aff C
   2. 凸包 ：conv C
   3. 锥包：是包含 C 的最小锥
   4. 闭包：cl C
3. 仿射有关：
   1. C 是一个仿射集合且 x₀∈C，则 V = C - x₀ 是一个子空间，即关于加法和数乘是封闭的，经过原点。反之，仿射空间可以表示为一个子空间加上一个偏移。
   2. 仿射维数：C 的仿射维数为其仿射包的维数。
   3. 相对内部 relint C：如果 C ⊆ Rⁿ 的仿射维度小于 n，那么 Rⁿ ≠ Rⁿ 中。C 的相对内部为 Rⁿ 的内部。
   4. 相对边界：cl  relint C

2. 重要的例子

1. 超平面：{ x|a^Tx = b}
   1. 是一个关于 x 的非平凡线性方程的解空间，故是一个仿射集
   2. 可以看作 法线方向 为 a 的超平面，而常数 b 决定这个平面从原点的 偏移。
2. 半空间：{ x|a^Tx ≤ b}
   1. 一个超平面将 Rⁿ 划分为两个半空间。
   2. 是凸的，但不是仿射的。
   3. { x|a^Tx < b} 是半空间 { x|a^Tx ≤ b} 的内部，称为半开空间。
3. 范数有关：设|| · ||是 Rⁿ 中的范数
   1. 范数球：{ x | ||x - x_c|| ≤ r} 以 x_c 为圆心，r 为半径，是凸的。
   2. 范数锥：{ (x,t) | ||x|| ≤ r} ⊆ Rⁿ⁺¹，是凸锥。
4. 多面体：有限个半空间和超平面的交集
   1. 仿射集合，射线，线段，半空间都是多面体，多面体是凸集。
5. 半正定锥：用 Sⁿ 表示对称的 n×n 的矩阵集合，Sⁿ₊ 表示对称半正定矩阵的集合，Sⁿ₊₊ 表示对称正定矩阵的集合。
   1. Sⁿ₊ 是一个凸锥。

3. 保凸运算

1. 交集

2. 仿射函数：函数 f : Rⁿ → R^m 是仿射的，如果它是一个线性函数和一个常数的和，即具有 f (x) = Ax + b 的形式，其中 A ∈ R^n×m，b ∈ R^m。假设 S 包含于 Rⁿ 是凸的，并且 f : Rⁿ → R^m是仿射函数。那么，s 在 f 下的象：f (S) = {f (x)|x ∈ S} 是凸的。

   1. 例子：平移 S + a；伸缩 aS

3. 透视函数：定义 P：Rⁿ⁺¹ → Rⁿ，P(z,t) = z/t 为透视函数，其定义域 dom P = Rⁿ × R₊₊

   1. 例子，例如（2，3，4）经过透视函数后为（2/4，3/4)。

4. 线性分式函数：由透视函数与仿射函数复合而成：f(x) = (Ax + b) / (c^Tx + d) dom f = {x|c^Tx + d > 0}

   1. 可以将仿射函数与透视函数视为特殊的线性分式函数。

   2. 例子： \[ 设 A = \begin{bmatrix}1&2\\3&4\end{bmatrix}, b = \begin{bmatrix}1\\1\end{bmatrix}, c = \begin{bmatrix}1\\2\end{bmatrix}, d = 3, x = \begin{bmatrix}x_1\\x_2\end{bmatrix} \]

      \[ \text{则线性分式函数} y = f(x)=\frac{\begin{bmatrix}1&2\\3&4\end{bmatrix}\begin{bmatrix}x_1\\x_2\end{bmatrix}+\begin{bmatrix}1\\1\end{bmatrix}}{\begin{bmatrix}1&2\end{bmatrix}\begin{bmatrix}x_1\\x_2\end{bmatrix}+3} \]

      \[ \text{所以} y=\begin{bmatrix}\frac{x_1 + 2x_2+1}{x_1 + 2x_2+3}\\\frac{3x_1 + 4x_2+1}{x_1 + 2x_2+3}\end{bmatrix} \]

4. 广义不等式

1. 正常锥：称 K ∈ Rⁿ 为正常锥，如果它满足

   • K 是凸的
   • K 是闭的
   • K 是实的，即具有非空内部
   • K 是尖的，即不包含直线

   正常锥可以定义广义不等式：x ≤_K y ⇔ y - x ∈ K；x <_K y ⇔ y - x ∈ int K

2. 广义不等式的性质：

   • 对于加法保序的
   • 具有传递性
   • 对于非负数乘是保序的
   • 是自反的
   • 是反对称的
   • 对于极限运算是保序的

3. 最小元：对于每个 y ∈ S， 均有 x ≤_K y， 称 x ∈ S 是最小元，最小元唯一。

4. 极小元：如果 y ∈ S， x ≤_K y 推出 y = x 称 x ∈ S 是极小元，极小元可以有多个。

5. 分离与支撑超平面

1. 分离超平面定理：两个不相交凸集 C、D，存在 a ≠ 0 和 b 使得对于所有 x ∈ C 有 a^Tx ≤ b，对于所有 x ∈ D 有 a^Tx ≥ b，超平面 { x|a^Tx = b} 被称为分离超平面。
2. 严格分离，即对于所有 x ∈ C 有 a^Tx < b，对于所有 x ∈ D 有 a^Tx > b：不相交凸集不一定严格分离。
3. 支撑超平面定理：
   1. 设 C ⊆ Rⁿ 而 x₀ 是其边界 bd C 上的一点，即 x₀ ∈ bd C = cl C  int C，如果 a ≠ 0 并且对任意 x ∈ C 满足 a^Tx ≤ a^Tx₀ 那么称超平面 { x|a^Tx = b} 为集合 C 在 x₀ 处的支撑超平面。
   2. 任意非空凸集 C 和 x₀ ∈ bd C，在 x₀ 处存在 C 的支撑超平面。

6. 对偶锥与广义不等式

1. 对偶锥：令 K 为一个锥。集合 K^* = { y | x^Ty ≥ 0, ∀ x ∈ K} 称为 K 的对偶锥，且总是凸的。
2. 对偶锥的性质：
   • K^* 是闭凸锥
   • K₁ ⊆ K₂ 可导出 K^*₁ ⊆ K^*₂
   • 如果 K 有非空内部，则 K^* 是尖的。
   • 如果 K 的闭包是尖的，则 K^* 有非空内部
   • K^** 是 K 的凸包的闭包（如果 K 是闭和凸的，则 K^* = K）
3. 广义不等式的对偶：凸锥 K 是正常锥，可以导出广义不等式 ≤_K。其对偶锥 K^* 也是正常的，也可以导出广义不等式 ≤_K^*,称其为 ≤_K 的对偶。
4. 广义不等式及其对偶的性质：（以下 λ 与 K 中任意两个元素x、y的夹角都小于90°，其可以看作 x 与 y 到 λ 上的投影）
   1. x ≤_K y 当且仅当对于任意 λ ≥_K^* 0 有 λ^Tx ≤ λ^Ty。
   2. x <_K y 当且仅当对于任意 λ ≥_K^* 0 和 λ ≠ 0 有 λ^Tx < λ^Ty。
5. 最小元对偶性质：x 是 S 上关于广义不等式 K 的最小元的充要条件是，对于所有 λ >_K^* 0 ，x 是 z ∈ S 上极小化 λ^Tz 的唯一最优解。(可以理解为 λ^Tz 是 z 到 λ 的投影，只有 z 是 x 的时候 λ^Tz 极小)
   1. 几何上：对于任意λ >_K^* 0，超平面 { y | λ^T(z - x) = 0} 是在 x 处对 S 的一个严格支撑超平面（严格说明只相交于x）
6. 极小元对偶性质： 如果 λ >_K^* 0 ，x 在 z ∈ S 上极小化 λ^Tz ，那么是 x 极小的。逆命题一般不成立：S 上的极小元 x 可以对于任何 λ 都不是 z ∈ S 上极小化 λ^Tz 的解。（需要 S 是凸集才成立，即对于凸集 S 上的任何极小元 x 存在非零的 λ >_K^* 0 是 z ∈ S 上极小化 λ^Tz 的解。）
7. 最小元与极小元的对偶性质的对比：要满足最小元，需要对偶锥中所有的 λ，x 都是在 z ∈ S 上极小化的 λ^Tz，而极小元只需要在一个 λ 上满足 x 是 z ∈ S 上极小化的 λ^Tz。

凸函数

1. 基本性质

1. 一个函数 f: Rⁿ → R 称为凸函数，如果对于任意的 x₁, x₂ ∈ dom f 和 θ ∈ [0, 1]，有以下不等式成立： \[ f(\theta x_1+(1 - \theta)x_2) \leq \theta f(x_1)+(1 - \theta)f(x_2) \]

   1. 将定义中的小于等于改为小于，则定义的为严格凸函数。
   2. 几何意义：函数 f 的图像在任意两点之间的线段位于函数曲线的上方或与函数曲线重合。凸函数的这种性质确保了它们没有局部极小值，任意局部极小点也是全局极小点。

2. 拓展值延伸：将 f(x) 的定义域由原 dom f 扩展到全域，在 dom f 外的函数值定为 +∞。

3. 一阶条件：假设 f 可微（即其梯度 ∇f 在开集 dom f 内处处存在），则函数 f 是凸函数的充要条件是 dom f 是凸集且对于任意 x, y ∈ dom f，下式成立： \[ f(\theta x_1+(1 - \theta)x_2) \leq \theta f(x_1)+(1 - \theta)f(x_2) \]

   1. 将定义中的大于等于改为大于，则定义的为严格凸函数。
   2. 几何意义：这意味着在 f 每个点，函数图像的切线不会超过函数图像本身。

4. 对于二次可微函数，函数 f 是凸的，当且仅当它的 Hessian 矩阵∇²f (x) 是半正定的，即： \[ ∇²f(x) \geq 0 \]

   1. 这表示 Hessian 矩阵的所有特征值都是非负的。
   2. 将定义中的大于等于改为大于，则定义的为严格凸函数。

2. 例子

1. 指数函数：对于任意的a∈R,函数 e^ax在 R 上是凸的。

2. 幂函数：当 a ≥ 1或 a ≤ 0时，x^a  在 R₊₊ 上是凸函数，当 0 ≤ a ≤ 1时，x^a 在 R₊₊ 上是凹函数。

3. 绝对值幂函数：当 p ≥ 1时，函数|x|^p在 R 上是凸函数。

4. 对数函数：函数 log x在 R₊₊ 上是凹函数。

5. 负熵

   1. 定义：负熵 f(x) = xlog(x)，定义域为 R₊₊ 或 R₊，当 x = 0 时定义函数值为0。
   2. 可通过二阶条件证明f^''(x) > 0，所以负熵是严格凸函数。

6. 范数：Rⁿ 上任意范数均为凸函数。（三角不等式可得）

7. 最大值函数：函数 f(x) = max{x₁+...+x_n} 在 Rⁿ 上是凸函数。

8. 二次-线性分式函数：f(x, y) = xⁿ / y，在其定义域为 dom f = R × R₊₊ = {(x, y) ∈ Rⁿ | y > 0}是凸函数。

9. 指数和的函数：函数f(x) = log(∑e^x_i)在 Rⁿ 是凸函数

   1. 这个函数可以看作最大值函数的可微近似.因为

      max{x₁+...+x_n} ≤ f(x) ≤ max{x₁+...+x_n} + log n

10. 几何平均函数：f(x) = （∏x_i)^1/n, 在定义域 dom f = Rⁿ₊₊ 上是凹函数。

11. 对数行列式：f(x) = log det x, 在定义域 dom f = Sⁿ₊₊ 上是凹函数。

3. 有关概念

1. 下水平集

   1. 定义：函数 f:Rⁿ → R 的 α - 下水平集定义为Cα = {x∈dom f|f(x) ≤ α}.
   2. 凸函数的下水平集都是凸集，但下水平集都是凸集的函数不一定是凸函数。例如，函数 f(x) = -e^x在R上不是凸函数(实质上，它是严格凹函数)，但是其所有下水平集均为凸集。
   3. 如果 f 是凹函数，则由 {x∈dom f|f(x) ≥ α} 定义的 α - 上水平集也是凸函数。

2. 上境图 epi f

   1. 定义：函数 f:Rⁿ → R 的图像定义为{(x,f (x))|x∈dom f},它是 Rⁿ⁺¹ 空间的一个子集。函数 f:Rⁿ → R 的上境图定义为： \[ \text{epi } f =\{(x,t)|x\in\text{dom } f,f (x) \leq t\} \] 简单来说，上境图包含了函数图像之上的所有点。

   2. 对应有亚图 hypo ：hypo f = {(x,t)|t <= f (x)} 简单来说，亚图包含了函数图像以下的所有点。

   3. 凸性与上境图的关系：

      1. 凸函数的上境图是凸集，反之，如果一个函数的上境图是凸集，那么这个函数是凸函数。
      2. 凹函数的亚图是凸集，反之如果一个函数的亚图是凸集，那么这个函数是凹函数。

3. Jensen不等式及其扩展

   1. f(θx₁ + (1 - θ)x₂) ≤ θf(x₁) + (1 - θ)f(x₂)
   2. f(θ₁x₁ + ... + θ_kx_k) ≤ θf(x₁) + ... + θ_kf(x_k), S.T. θ₁  + ... + θ_k = 1; θ₁ ，...， θ_k > 0
   3. ...

4, 保凸运算

1. 非负加权求和

2. 复合仿射映射：函数 f:Rⁿ → R，A ∈ R^n×m ，b ∈ R^m ，定义 g R^m → R为： \[ g(x)=f(Ax + b) \]

   1. 若函数 f 是凸函数，则 g 是凸函数；若函数 f 是凹函数，则 g 是凹函数。
   2. 二阶条件可证明

3. 逐点最大：设 f1 (x)，f2 (x)，……，fm (x) 是凸函数，则逐点最大值定义为： \[ f(x)=\max\{f_1(x), f_2(x), \cdots, f_m(x)\} \] 新函数 f (x) 仍然是凸函数。

4. 逐点上确界：设 f (x,y) 是一个关于 x 和 y 的函数，A 是 y 的取值范围，逐点上确界函数 g (x) 定义为： \[ g(x)=\sup_{y\in A} f(x,y) \]

   1. 逐点上确界函数是逐点最大函数的推广,指的是对于每个 x，找到所有函数值的上界。具体来说，固定 x，再根据参数 y 的范围，找到所有对应的函数值 f(x,y) 的上确界 。（前提是 f(x,y) 对x是凸的）

   2. 从上境图的角度理解，一系列函数的逐点上确界对应着这些函数上境图的交集：对于函数 f，g 以及 A， 我们有 \[ \text{epi } g = \prod \text{epi } f(\cdot,y) \] 函数 g 的凸性可以由一系列凸集的交集仍然是凸集得到。

5. 复合：本节给定函数 h：Rⁿ → R 以及 g：Rⁿ → R，定义复合函数 f = h∘g：Rⁿ → R 为 \[ f(x) = h(g(x)), \quad \text{dom } f = \{ x \in \text{dom } g \mid g(x) \in \text{dom } h \} \] 我们考虑当函数 f 保凸或者保凹时，函数 h 和 g 必须满足的条件。

   1. 标量复合：即上面定义中 k = 1 的情况。 h̃ 为函数h的扩展值延伸。

      如果h是凸函数且 h̃ 非减，g 是凸函数，则 f 是凸函数,

      如果h是凸函数且 h̃ 非增，g 是凹函数，则 f 是凸函数,

      如果h是凹函数且 h̃ 非减，g 是凹函数，则 f 是凹函数，

      如果h是凹函数且 h̃ 非增，g 是凸函数，则 f 是凹函数。

      内外凹凸一样，外函数要非减，内外凹凸不一样，外函数要非增，最后复合函数与外函数凹凸性一致。

   2. 矢量复合：即定义中 k ≥ 1 的情况。

      如果 h 是凸函数且在每维分量上 h 非减，g_i 是凸函数，则 f 是凸函数;

      如果 h 是凸函数且在每维分量上 h 非增，g_i 是凹函数，则 f 是凸函数;

      如果 h 是凹函数且在每维分量上 h 非减，g_i 是凹函数，则 f 是凹函数;

      如果 h 是凹函数且在每维分量上 h 非增，g_i 是凸函数，则 f 是凹函数;

6. 最小化：当 f (x,y) 关于 x、y 都是凸函数，C是非空凸集时，有：

   g (x) = inf f (x,y) （y∈C）是凸函数。

   1. 最小化与逐点上确界的区别：最小化的定义中要求 f (x,y) 关于x、y都是凸函数；而逐点上确界仅要求 f (x,y) 关于x是凸函数。

7. 透视函数：给定函数 f:Rⁿ→R，则 f 的透视函数 g: Rⁿ⁺¹→R 定义为： \[ \begin{align*} g(x,t)&=tf\left(\frac{x}{t}\right)& \text{dom }g=\{(x,t)\mid\frac{x}{t}\in\text{dom }f,t > 0\} \end{align*} \]

   1. 几何上，透视函数对应于将低维空间的图形或曲线通过投影的方式拉升到高维空间。（t 是引入的新变量）例如，原来的函数图像在 Rⁿ 中是一条曲线，透视变换后，它会成为在 Rⁿ⁺¹ 中的一张曲面。
   2. 可以通过二阶条件证明。

5. 共轭函数

1. 定义：设函数 f：Rⁿ → R，定义函数 f^*：Rⁿ → R为

   ​ f^* (y) = sup (y^Tx - f(x)) (x 属于 dom f)

   1. f(x) 的共轭函数 f^* (y) 表示过原点以 y 为斜率的直线与 f(x) 差值的最大值。
   2. 如果 f 可微，在满足f' (x) = y 的点 x 处差值最大。
   3. 无论 f 是否是凸函数，f^* 都是凸函数。

2. 例子：

   1. 仿射函数：f (x) = ax + b，

      当且仅当 y = a（常数）时，yx - ax - b 有界，共轭函数 f^* 定义域为单点集 {a}，f^*(a)= -b。

   2. 负对数函数：f (x)= -log x，定义域为 R₊₊。

      当 y ≥ 0 时，函数 xy + log x 无上界；

      当 y < 0 时，在 x = -1/y 处取最大值，dom f^* = { y|y < 0}= -R₊₊，f^*(y) = -log (-y) - 1 (y < 0)。

   3. 指数函数：f (x) = e^x，

      当 y < 0 时，xy - e^x 无界；

      当 y > 0 时，在 x = log y 处取最大值，y = 0 时，f^*(y)=0，dom f^* = R₊，f^*(y)=y log y - y (规定 0 log 0 = 0)。

   4. 负熵函数：f (x)=x log x，定义域为 R₊， (同样规定 0 log 0 = 0)

      对所有 y，xy - x log x 有上界，dom f^* = R，在 x = e^{(y - 1)} 处取最大值，f^*(y) = e^{(y - 1)}。

   5. 反函数：f (x) = 1/x (x∈R₊₊)，

      当 y > 0 时，yx - 1/x 无上界；

      当 y = 0 时，上确界为 0；

      当 y < 0 时，在 x = (-y)^-1/2 处取上确界，f^*(y) = -2 (-y)^1/2，dom f^*= -R₊。

3. 基本性质

   1. Fenchel不等式：由共轭函数定义可知：f(x) + f^*(y) ≥ x^Ty

   2. 凸函数的共轭函数的共轭函数是原函数。

   3. 可微函数 f 的共轭函数亦称为函数 f 的 Legendre 变换：

      设函数 f 如函数且可微，使 y^Tx - f(x) 最大的 x^* 满足 y = ∇f( x^*)，反之也成立。因此，如果 y = ∇f( x^*)，我们有： \[ f^{\ast}(y) = x^{\ast T} \nabla f(x^{\ast}) - f(x^{\ast}) \]

   4. 仿射变换的共轭： \[ g(x) = af(x) + b \quad \longrightarrow \quad g^*(y) = af^*(y^*/a) - b \]

   5. 复合仿射变换的共轭： \[ g(x) = f(Ax + b) \quad \longrightarrow \quad g^{\ast}(y) = f^{\ast}(A^{-T}y) - b^{T}A^{-T}y \]

      1. 以上证明关键步骤：**sup((变量)x - f(x)) = f^*(变量)**

   6. 独立函数的和：如果函数 f(u, v) = f₁(u) + f₂(v)，其中 f₁ 和 f₂ 使凸函数，则：f^*(w, z) = f₁^*(w) + f₂^*(z)

6. 拟凸函数

1. 定义：

   函数 f：Rⁿ → R 被称为拟凸函数 ，如果其定义域及所有的下水平集 S_a = {x ∈ dom f |f (x) ≤ α} 是凸集。

   函数 f 是拟凹函数，如果 -f 是拟凸函数，即每个上水平集 {x ∈ dom f |f (x) ≥ α} 是凸集。

   若某函数既是拟凸函数又是拟凹函数，其为拟线性函数，其定义域和所有水平集{x ∈ dom f |f (x) = α}都是凸集。就是单调函数。

2. 基本性质：

   1. 凸函数是拟凸的：所有凸函数都是拟凸函数。
   2. 局部最小值是全局最小值：对于拟凸函数，如果在某点 x 达到局部最小值，那么它也是全局最小值。
   3. 保凸性：拟凸函数的下水平集是凸的，这一性质使得拟凸函数能够被用于求解某些优化问题。
   4. 变换的 Jensen 不等式：f(θx + (1 - θ)y) ≤ max{f(x), f(y)}。即线段中任意一点的函数值不超过其端点函数值中最大的那个。
   5. 连续函数是拟凸的，则一下至少一个条件成立：
      1. 函数 f 是非减的
      2. 函数 f 是非增的
      3. 存在一点 c ∈ dom f，使得对于 t ≤ c，f 非增，对于 t ≥ c，f 非减，c 可以在全局最小点任取一个。

3. 可微拟凸函数

   1. 一阶条件：对于任意 x₁，x₂，如果 f (x₁) ≤ f (x₂)，则∇f (x₂)ᵀ(x₁ - x₂) ≤ 0

   2. 二阶条件：假设函数 f 二次可微。如果函数 f 是拟凸函数，则对于任意 x ∈ dom f以及任意 y ∈ R ⁿ 有 \[ y^{T}\nabla f(x) = 0 \Rightarrow y^{T}\nabla^{2} f(x)y \geq 0 \] 对于定义在 R 上的拟凸函数，上述条件可以简化为如下条件 \[ f^{\prime}(x) = 0 \Rightarrow f^{\prime\prime}(x) \geq 0 \] 也就是在一阶导为0的点，二阶导必须为正；扩展到高维，即在各个方向上一阶导都为0的点，它的二阶导Hessian 矩阵须为正定的。

4. 保拟凸运算

   1. 非负加权最大：f = max{w₁f₁，...，w_mf_m}
   2. 复合：
      1. 如果函数 g：Rⁿ → R是拟凸函数，且函数h：R → R是非减的，则复合函数 f = h∘g 是拟凸函数。
      2. 和仿射函数或者线性分式函数复合：如果 f 是拟凸函数，则 g(x) = f(Ax + b) 是拟凸函数，且函数 g(x) = (Ax + b)/(c^Tx + d) 是拟凸函数。
   3. 最小化：如果函数 f(x,y) 是 x 和 y 的联合拟凸函数，且 C 是凸集，则函数：g(x) = inf f(x,y) (y ∈ C) 是拟凸函数。

7. 对数-凹函数和对数-凸函数

1. 定义：如果对所有的 x ∈ dom f 有 f(x) > 0 且 log f 是凸函数或者凹函数，则称函数对数凸或者对数凹函数。

   1. 函数是对数凸的，当且仅当 1/f 是对数凹的

2. 对数凸函数性质：

   1. f(θx₁ + (1 - θ)x₂) ≤ f(x₁)^θf(x₂)^{1 - θ}
   2. log f(θx₁ + (1 - θ)x₂) ≤ θ log f(x₁) + (1 - θ) log f(x₂)

3. 例子

   1. 仿射函数：函数 f(x) = a^Tx + b 在{x | a^Tx + b > 0} 上是对数凹函数。
   2. 幂函数：函数 f(x) = x^a 在 R₊₊ 上当 a ≤ 0 是对数凸函数；当 a ≥ 0 时是对数凹函数。
   3. 指数函数：函数 f(x) = e^ax 既是对数凸函数又是对数凹函数。

4. 二次可微的对数-凸/凹函数：设函数 f 二次可微，其中 dom f 是凸集，我们有 \[ \nabla^{2}\log f(x) = \frac{1}{f(x)}\nabla^{2}f(x)-\frac{1}{f(x)^{2}}\nabla f(x)\nabla f(x)^{T} \] 事实上，函数 f 是对数 - 凸函数，当且仅当对任意 x∈dom f，下式成立（二阶条件） \[ f(x)\nabla^{2}f(x) \geq \nabla f(x)\nabla f(x)^{T} \] 函数 f 是对数 - 凹函数，当且仅当对任意 x∈dom f，下式成立（二阶条件） \[ f(x)\nabla^{2}f(x) \leq \nabla f(x)\nabla f(x)^{T} \]

5. 乘积、和、以及积分运算

   1. 对数-凹/对数-凸函数的乘积是对数-凹/对数-凸函数；
   2. 对数-凹函数的和一般不是对数-凹函数；
   3. 对数-凸函数的和仍然是对数-凸函数；
   4. 对数-凹/对数-凸函数的积分是对数-凹/对数-凸函数。

凸优化问题

1. 优化问题

1. 基本术语

   1. 基本形式： \[ \begin{align*} &\text{minimize} & f_0(x)\\ &\text{subject to} & f_i(x) \leq 0, & i = 1,\cdots,m\\ & & h_i(x) = 0, & i = 1,\cdots,p \end{align*} \] 三个部分分布称为：目标函数、不等式约束、等式约束。

      我们称这个形式为优化问题的标准形式

   2. 可行域：对目标和所有约束函数有定义的点的集合。 \[ \mathcal{D} = \bigcap_{i = 0}^{m} \text{dom } f_i \cap \bigcap_{i = 1}^{p} \text{dom } h_i \] 如果 D 为空集，那么原问题的最优解就是 +∞。

      如果最优值 = -∞，则称问题无下界。

   3. ε-次优集

      满足 f₀(x) ≤ p^* + ε (其中 ε > 0， p^*为最优解的函数值)  的可行解 x 称为 ε -次优。所有 ε -次优解的集合称为问题的 ε -次优集。

   4. 极小值，局部最优

      我们称可行解 x 为局部最优，如果存在 R > 0 使得 \[ f_0(x) = \inf \{ f_0(z) \mid f_i(z) \leq 0, \; i = 1,\cdots,m, \\ h_i(z) = 0, \; i = 1,\cdots,p, \; \| z - x \|_2 \leq R \} \] 或换言之 x 是关于 z 的优化问题 \[ \begin{align*} &\text{minimize} & f_0(z)\\ &\text{subject to} & f_i(z) \leq 0, & i = 1,\cdots,m\\ & & h_i(z) = 0, & i = 1,\cdots,p\\ & & \| z - x \|_2 \leq R \end{align*} \]

2. 等价问题

1. 变量变换：就是让 x 和 z 一一映射

2. 目标函数和约束函数的变换

   1. 目标函数：若 φ₀ 单调增，则 f₀(x) 与 φ₀(f₀(x)) 等价。
   2. 不等式约束：若 φ_i 满足 当且仅当 u ≤ 0 时， φ_i (u) ≤ 0 则 f_i(x) 与 φ_i(f_i(x)) 等价。
   3. 等式约束：若 φ_i 满足 当且仅当 u = 0 时， φ_i (u) = 0 则 h_i(x) 与 φ_i(h_i(x)) 等价。

3. 松弛变量：若有不等式约束 f_i(x) ≤ 0，可以引入松弛变量 s_i ≥ 0 使得 f_i(x) + s_i = 0

4. 消除等式约束：就是通过等式约束，解出 x = φ(z) 代入即可。

5. 引入等式约束：消除等式约束的逆过程。

6. 优化部分变量：如果优化参数有多个参数，且对每个参数的约束相互独立，则可先优化部分参数，以下为例子：

   设变量 x∈Rⁿ 被分为 x = (x₁，x₂)，其中 x₁∈Rⁿ¹ x₂∈Rⁿ²，并且 n₁ + n₂ = n。考虑问题 \[ \begin{align*} &\text{minimize} & f_0(x_1,x_2)\\ &\text{subject to} & f_{i_1}(x_1)\leq 0, & i = 1,\cdots,m_1\\ & & f_{i_2}(x_2)\leq 0, & i = 1,\cdots,m_2 \end{align*} \] 其约束相互独立，也就是说每个约束函数只与 x₁ 或 x₂ 相关。我们首先优化 x₂。定义 x₁ 的函数 f₀ 为 \[ \tilde{f}_0(x_1) = \inf \{ f_0(x_1,z) \mid \tilde{f}(z)\leq 0, \; i = 1,\cdots,m_2 \} \] 则问题等价于 \[ \begin{align*} &\text{minimize} & \tilde{f}_0(x_1)\\ &\text{subject to} & f_{i_1}(x_1)\leq 0, & i = 1,\cdots,m_1 \end{align*} \]

7. 上境图问题形式：标准问题的上境图形式为： \[ \begin{align*} &\text{minimize} & t\\ &\text{subject to} & f_0(x)-t\leq 0\\ & & f_i(x)\leq 0, & i = 1,\cdots,m\\ & & h_i(x)= 0, & i = 1,\cdots,p \end{align*} \] 上境图将一个优化问题（即最小化问题）等价地转化为对一个集合的判定。

   几何解释：找到上境图中“最低”一点。

8. 隐式与显式约束：就是改改定义域

3. 凸优化

1. 标准形式： \[ \begin{align*} &\text{minimize} & f_0(x)\\ &\text{subject to} & f_i(x) \leq 0, & i = 1,\cdots,m\\ & & a_i^T x = b_i, & i = 1,\cdots,p \end{align*} \] 和普通优化问题（4.1）相比较，凸优化问题有三个条件：

   1. 目标函数必须是凸的，（如果是拟凸的，则是拟凸优化的标准形式）。
   2. 不等式约束函数必须是凸的。
   3. 等式约束函数 h_i(x) = a_i^Tx - b 必须是仿射的。

2. 性质：

   1. 凸优化问题的可行集是凸的。
   2. 凸优化问题的局部最优解就是全局最优解。

3. 可微目标函数的最优性准则：设凸优化问题的目标函数 f₀  是可微的，对于所有的 x, y ∈ dom f₀ 有 \[ f_0(y) \geq f_0(x)+\nabla f_0(x)^T(y - x) \] 令 X 表示其可行集，即 \[ X = \{ x \mid f_i(x) \leq 0, \; i = 1,\cdots,m, \; h_i(x) = 0, \; i = 1,\cdots,p \} \] 那么，x 是最优解，当且仅当 x ∈ X 且 \[ \nabla f_0(x)^T(y - x) \geq 0, \quad \forall y\in X. \] 几何解释：

   1. 当x点梯度大于0时，y就比x大，所以x处的函数值就比任意y处的函数值小，x是最优解；
   2. 当x点梯度小于0时，y就比x小，所以x处的函数值就比任意y处的函数值小，x是最优解；
   3. 如果 ∇f₀(x) ≠ 0，那么意味着 -∇f₀(x) 在 x 处定义了可行集的一个支撑超平面。

4. 无约束问题：无约束问题中x是最优解的充要条件是：∇f₀(x) = 0。

5. 只含等式约束的问题：用Lagrange乘子法：将约束问题转换为无约束问题，引入Lagrange乘子 v，构造拉格朗日函数： \[ L(x, v) = f_0(x) + v^T(Ax - b) \] 然后通过求解拉格朗日函数梯度为 0 的条件，得到优化条件。

   例子： \[ \begin{align*} &求解凸优化问题\\ &\quad \min_{x} \quad x^2\\ &\quad \text{s.t.} \quad Ax - b=0\\ &\quad 其中A是m\times n矩阵，b是m维向量。\\ &1. 构造Lagrange函数\\ &\qquad L(x,\lambda)=x^2+\lambda^T(Ax - b)\\ &2. 求偏导数并令其为0\\ &\qquad \nabla_x L(x,\lambda)=2x+A^T\lambda = 0，可得x=-\frac{1}{2}A^T\lambda\\ &\qquad \nabla_{\lambda} L(x,\lambda)=Ax - b = 0，将x=-\frac{1}{2}A^T\lambda代入可得：\\ &\qquad A(-\frac{1}{2}A^T\lambda)-b = 0\\ &\qquad 解出\lambda，再代入x=-\frac{1}{2}A^T\lambda得到最优解x^*。\\ \end{align*} \]

6. 非负象限中的极小化：凸函数在非负象限中的极小化由两种情况

   1. 最优解x处的梯度为0，
   2. 最优解x处的梯度 ∇f₀(x) 不为0时，∇f₀(x) > 0且 x=0。

4. 拟凸优化

1. 最优解条件 \[ x \in X, \quad \nabla f_0(x)^T(y - x)>0, \quad \forall y \in X \backslash \{x\} \] 这个条件表示：在 x 处的梯度方向不会使 f(x) 减小。

   与凸优化问题的不同

   1. 但这个条件为拟凸优化问题的最优性的充分条件
   2. 要求 ∇f₀(x) 非 0

2. 解决拟凸优化问题的方法

   1. 凸可行性问题： \[ \begin{align*} &\quad\text{find } \quad\quad\quad\quad x \\ &\text{ subject to } \quad \phi_t(x) \leq 0,\\ &\quad\quad\qquad\qquad f_i(x) \leq 0,\\ &\quad\quad\qquad\qquad Ax = b \end{align*} \] 其中，φ_t(x) 是拟凸函数 f(x) 的水平集。f₀(x) ≤ t ⇔ φ_t(x) ≤ 0

   2. 判断可行性问题的解：

      • 若可行，则表明拟凸优化问题的最优值p^* ≤ t；
      • 若不可行，则说明p^* ≥ t。

   3. 使用二分法来调整t的值，不断缩小包含最优解的区间，从而得到拟凸优化问题的近似最优解。

5. 线性规划问题

1. 定义：当目标函数和约束函数都是仿射时，问题称作线性规划（LP）。一般的线性规划具有以下形式： \[ \begin{align*} \text{minimize}\quad & c^T x + d \\ \text{subject to} \quad & Gx \leq h \\ & Ax = b \end{align*} \] 其中 G ∈ R^m×n, A ∈ R^p×n。线性规划是凸优化问题。（d 常省略）

2. 标准形式与不等式形式

   1. 标准形式：在标准形式线性规划中仅有的不等式都是分量的非负约束 x ≥ 0： \[ \begin{align*} \text{minimize}\quad & c^T x \\ \text{subject to}\quad & Ax = b \\ & x \geq 0 \end{align*} \]

   2. 不等式形式：如果线性规划问题没有等式约束，则称为不等式形式线性规划，常写作： \[ \begin{align*} \text{minimize} \quad & c^T x \\ \text{subject to} \quad & Ax \leq b \end{align*} \]

3. 将线性规划转换为标准形式：将一般的线性规划形式转化为标准的线性规划形式

   1. 第一步是为不等式引入松弛变量 s_i，得到 \[ \begin{align*} \text{minimize} \quad & c^T x + d \\ \text{subject to} \quad & Gx + s = h \\ & Ax = b \\ & s \geq 0 \end{align*} \]

   2. 第二步是将变量 x 表示为两个非负变量 x⁺ 和 x^- 的差，即 x = x⁺ - x^- ，其中 x⁺ > 0 、 x^- > 0，从而得到问题 \[ \begin{align*} \text{minimize} \quad & c^T x^+ - c^T x^- + d \\ \text{subject to} \quad & Gx^+ - Gx^- + s = h \\ & Ax^+ - Ax^- = b \\ & x^+ \geq 0, \quad x^- \geq 0, \quad s \geq 0 \end{align*} \] 这是标准形式的线性规划，其优化变量是 x⁺、x^- 和 s 。

6. 线性分式规划

1. 定义：在多面体上极小化仿射函数之比的问题称为线性分式规划： \[ \begin{align*} \text{minimize} \quad & f_0(x) \\ \text{subject to} \quad & Gx \succeq h \\ & Ax = b \end{align*} \] 其目标函数由 \[ f_0(x) = \frac{c^T x + d}{e^T x + f}, \quad \text{dom} f_0 = \{x \mid e^T x + f > 0\} \] 给出。这个目标函数是拟凸的（事实上是拟线性的），因此线性分式规划是一个拟凸优化问题。

2. 转化为线性规划：如果可行集 \[ \{x \mid Gx \preceq h, Ax = b, e^T x + f > 0\} \] 非空，线性分式规划可以转换为等价的线性规划 \[ \begin{align*} \text{minimize} \quad & c^T y + dz \\ \text{subject to} \quad & Gy - hz \preceq 0 \\ & Ay - bz = 0 \\ & e^T y + fz = 1 \\ & z \geq 0 \end{align*} \] 其优化变量为 y，z。

   为显示这个等价性，我们首先说明如果 x 是线性分式规划的可行解，那么 \[ y = \frac{x}{e^T x + f}, \quad z = \frac{1}{e^T x + f}，\quad x = \frac{y}{z} \] 是线性规划的可行解，且具有相同的目标函数值 c^Ty + dz = f₀(x)。

7. 二次优化问题

1. 定义：当凸优化问题的目标函数是(凸)二次型并且约束函数为仿射时，该问题称为二次规划（QP）。二次规划可以表述为 \[ \begin{align*} \text{minimize} \quad & (1/2)x^T P x + q^T x + r \\ \text{subject to} \quad & Gx \preceq h \\ & Ax = b \end{align*} \] 本质是在二次规划问题中，在多面体上极小化一个凸二次函数。

   如果不仅目标函数，其不等式约束也是(凸)二次型，该问题称为二次约束二次规划（QCQP）。二次约束二次规划可以表述为 \[ \begin{align*} \underset{x}{\text{minimize}} \quad & (1/2)x^T P_0 x + q_0^T x + r_0 \\ \text{subject to} \quad & (1/2)x^T P_i x + q_i^T x + r_i \leq 0, \quad i = 1, \ldots, m \\ & Ax = b \end{align*} \] 本质是在椭圆的交集构成的可行集上极小化凸二次函数。

8. 几何规划

几何规划的自然形式并不是凸的。但通过变量替换或目标函数、约束函数的变换，可以将它们转换为凸优化问题。

1. 单项式与正项式

   1. 单项式定义：函数 f：Rⁿ → R，dom f = Rⁿ₊₊ 定义为 \[ f(x) = c x_1^{a_1} x_2^{a_2} \cdots x_n^{a_n}, \quad c > 0, \quad a_i \in \mathbb{R} \] 它被称为单项式函数或简称为单项式。单项式的指数 a_i 可以是任意实数，包括分数或负数，但系数 c 必须非负。

   2. 正项式定义:单项式的和是正项式函数（或简称为正项式）： \[ f(x) = \sum_{k = 1}^{K} c_k x_1^{a_{1k}} x_2^{a_{2k}} \cdots x_n^{a_{nk}}, \quad c_k > 0 \]

2. 几何规划（GP）形式： \[ \begin{align*} \text{minimize} \quad & f_0(x) \\ \text{subject to} \quad & f_i(x) \leq 1, \quad i = 1, \ldots, m \\ & h_i(x) = 1, \quad i = 1, \ldots, p \end{align*} \] 被称为几何规划（GP）其中 f₀，...，f_m 为正项式，h₁，...，h_p 为单项式，这个问题定义域为 D = Rⁿ₊₊， 约束 x ＞ 0 式隐式的。

3. 几何规划转换为凸优化

   几何规划(一般)不是凸优化问题，但是通过变量代换以及目标、约束函数的转换，它们可以被转换为凸问题。本质是优化问题的等价变换：变量变换+复合变换。

   1. 单项式转换方法：我们用 y_i = log x_i 定义变量，因此 x_i = e^y_i 。

      如果 f 是 x 的单项式函数，即： \[ f(x) = c x_1^{a_1} x_2^{a_2} \cdots x_n^{a_n} \] 那么 \[ \begin{align*} f(x) &= f(e^{y_1}, \ldots, e^{y_n}) \\ &= c (e^{y_1})^{a_1} \cdots (e^{y_n})^{a_n} \\ &= e^{a^T y + b} \end{align*} \] 其中 b = log c，变量变换 y_i = log x_i ，将一个单项式函数转换为以仿射函数为指数的函数。

   2. 正项式转换方法：类似的，如果 f 是正项式，即 \[ f(x) = \sum_{k = 1}^{K} c_k x_1^{a_{1k}} x_2^{a_{2k}} \cdots x_n^{a_{nk}} \] 于是 \[ f(x) = \sum_{k = 1}^{K} e^{a_k^T y + b_k} \] 其中a_k = (a_1k，...，a_2k) b_k = log c_k，变量变换 y_i = log x_i ，将正项式函数转换为以仿射函数为指数的函数的和。

   3. 几何规划问题的转换

      几何规划用新变量 y 表示： \[ \begin{align*} \text{minimize} \quad & \sum_{k = 1}^{K_0} e^{a_{0k}^T y + b_{0k}} \\ \text{subject to} \quad & \sum_{k = 1}^{K_i} e^{a_{ik}^T y + b_{ik}} \leq 1, \quad i = 1, \ldots, m \\ & \sum_{k = 1}^{K_i} e^{a_{ik}^T y + b_{ik}} = 1, \quad i = 1, \ldots, p \end{align*} \] 其中 a^ik ∈Rⁿ，i = 0，...，m，包含了以正项式为指数的不等式约束，g_i ∈Rⁿ，i = 0，...，p，包含了原几何规划中以单项式为指数的等式约束。

      采用对数函数将目标函数和约束函数进行转换，得到问题： \[ \begin{align*} \text{minimize} \quad & \tilde{f}_0(y) = \log \left(\sum_{k = 1}^{K_0} e^{a_{0k}^T y + b_{0k}}\right) \\ \text{subject to} \quad & \tilde{f}_i(y) = \log \left(\sum_{k = 1}^{K_i} e^{a_{ik}^T y + b_{ik}}\right) \leq 0, \quad i = 1, \ldots, m \\ & \tilde{h}_i(y) = g_i^T y + h_{i0} = 0, \quad i = 1, \ldots, p \end{align*} \] 因为函数 f_i 是凸的 h_i 是仿射的，所以该问题是一个凸优化问题。我们称其为凸形式的几何规划。为将其与原始的几何规划相区别，我们称原本的含正项式的为正项式形式的几何规划。

对偶

1. Language 函数

1. Language：考虑标准形式的优化问题： \[ \begin{align*} &\text{minimize} & f_0(x)\\ &\text{subject to} & f_i(x) \leq 0, & i = 1,\cdots,m\\ & & h_i(x) = 0, & i = 1,\cdots,p \end{align*} \] 这里没有假设问题是凸优化问题。

   其Language函数定义为： \[ L(x, \lambda, \nu) = f_0(x) + \sum_{i = 1}^{m} \lambda_i f_i(x) + \sum_{i = 1}^{p} \nu_i h_i(x) \] λ_i 称为第 i 个不等式约束 f_i(x) ≤ 0 对应的 Language乘子，v_i 称为第 i 个不等式约束 h_i(x) = 0 对应的 Language乘子。向量 λ 和 v 称为对偶变量或者是问题的 Language乘子向量

   拉格朗日函数的目标是通过引入乘数将约束 “惩罚” 融入到目标函数中。具体来说，λ 和 v 为调整各约束 “惩罚” 权重的因子：

   • 当约束 f_i(x) ≤ 0 被破坏（即 f_i(x) ≥ 0）时，对应的项 λ_if_i(x) 对函数值产生负面影响。
   • 当约束 h_i(x) = 0 不成立（即 h_i(x) ≠ 0）时，项 v_ih_i(x) 亦产生偏移。

2. Language 对偶函数

1. 定义：为 Language 函数关于 x 取得的最小值 \[ g(\lambda, \nu) = \inf_{x \in D} L(x, \lambda, \nu) = \inf_{x \in D} \left( f_0(x) + \sum_{i = 1}^{m} \lambda_i f_i(x) + \sum_{i = 1}^{p} \nu_i h_i(x) \right) \] 如果 Language 函数关于 x 无下界，则对偶函数取值为 -∞。因为对偶函数是一族关于 (λ , v) 的仿射函数的逐点下确界，所以即使原问题不是凸的，对偶函数也是凸函数。

2. 最优值的下界：对偶函数构成了原问题最优值 p^* 的下界:即对任意 λ ≥ 0和 v 下式成立: \[ g(\lambda, \nu) \leq p^* \] 设 x 是原问题一个可行解，即 f_i(x) ≤ 0 且 h_i(x) = 0 根据假设，λ_i ≥ 0，我们有： \[ \sum_{i = 1}^{m} \lambda_i f_i(x) + \sum_{i = 1}^{p} \nu_i h_i(x) \leq 0 \] 称满足 λ ≥ 0 以及 (λ , v) ∈ dom g 即 g (λ , v) > -∞ 的 (λ , v) 是对偶可行的。

3. Lagrange对偶函数和共轭函数

   回忆共轭函数定义： \[ f^*(y) = \sup_{x \in \text{dom} f} (y^T x - f(x)) \] 考虑一个优化问题，具有线性不等式和等式约束： \[ \begin{align*} \text{minimize} \quad & f_0(x) \\ \text{subject to} \quad & Ax \preceq b \\ & Cx = d \end{align*} \] 利用函数 f₀ 的共轭函数，我们可以将问题的对偶函数表述为 \[ \begin{align*} g(\lambda, \nu) &= \inf_{x} \left( f_0(x) + \lambda^T (Ax - b) + \nu^T (Cx - d) \right) \\ &= -b^T \lambda - d^T \nu + \inf_{x} \left( f_0(x) + (A^T \lambda + C^T \nu)^T x \right) \\ &= -b^T \lambda - d^T \nu - f_0^*(-A^T \lambda - C^T \nu) \end{align*} \] 函数 g 的定义域也可以由 f₀^* 的定义域得到： \[ \text{dom } g = \{ (\lambda, \nu) \mid -A^T \lambda - C^T \nu \in \text{dom } f_0^* \} \]

3. Lagrange对偶问题

1. 定义：Lagrange 对偶函数给出了优化问题的最优值 p*的一个下界。那么Lagrange 对偶函数的最大值就是原问题的最好下界。

   所以Lagrange 对偶问题为： \[ \begin{align*} \text{maximize} \quad & g(\lambda, \nu) \\ \text{subject to} \quad & \lambda \succeq 0 \end{align*} \] 对偶可行的 (λ , v) 是对偶问题的一个可行解。称最优解为对偶最优解或者最优 Language 乘子。

2. 标准形式线性规划的Language对偶

   标准形式线性规划 \[ \begin{align*} \text{minimize} \quad & c^T x \\ \text{subject to} \quad & Ax = b \\ & x \geq 0 \end{align*} \] 的 Lagrange 对偶函数为 \[ g(\lambda, \nu) = \begin{cases} - b^T \nu & A^T \nu - \lambda + c = 0 \\ -\infty & \text{其他情况} \end{cases} \] 所以对偶问题为 \[ \begin{align*} \text{maximize} \quad & g(\lambda, \nu) = \begin{cases} - b^T \nu & A^T \nu - \lambda + c = 0 \\ -\infty & \text{其他情况} \end{cases}\\ \text{subject to} \quad & \lambda \geq 0 \end{align*} \] 该问题等式约束条件为隐式的，写成显示表达对偶约束为： \[ \begin{align*} \text{maximize} \quad & - b^T \nu \\ \text{subject to} \quad & A^T \nu - \lambda + c = 0 \\ & \lambda \geq 0 \end{align*} \] 可进一步简化为 \[ \begin{align*} \text{maximize} \quad & - b^T \nu \\ \text{subject to} \quad & A^T \nu + c \geq 0 \end{align*} \]

3. 不等式形式线性规划的 Lagrange 对偶

   不等式形式的线性规划问题 \[ \begin{align*} \underset{x}{\text{minimize}} \quad & c^T x \\ \text{subject to} \quad & Ax \leq b \end{align*} \] Lagrange函数为 \[ L(x, \lambda) = c^T x + \lambda^T (Ax - b) = -b^T \lambda+(A^T \lambda + c)^T x, \] 对偶函数为 \[ g(\lambda)=\inf_{x} L(x, \lambda)=-b^T \lambda+\inf_{x}(A^T \lambda + c)^T x. \] 若线性函数不是恒值，则线性函数的下确界是 -∞，因此上述问题的对偶函数为 \[ g(\lambda) = \begin{cases} - b^T \lambda & A^T \lambda + c = 0 \\ -\infty & \text{其他情况} \end{cases} \] 显式表达对偶可行的条件并作为约束来重新描述对偶问题： \[ \begin{align*} {\text{maximize}} \quad & -b^T \lambda \\ \text{subject to} \quad & A^T \lambda + c = 0 \\ & \lambda \geq 0, \end{align*} \] 我们注意到标准形式线性规划和不等式形式线性规划以及它们的对偶问题之间的有趣的对称性，标准形式线性规划的对偶问题是只含有不等式约束的线性规划问题，反之亦然。

4. 对偶性

1. 弱对偶性：Language 对偶问题的最优值，我们用 d^* 表示，根据定义，这是通过 Language 函数得到原问题最优值 p^* 的最好下界。特别的，我们有下面简单但是非常重要的不等式 \[ d^* \leq p^* \] 即使原问题不是凸问题，上述不等式亦成立。这个性质被称为弱对偶性。

   定义差值 p^* - d^* 是原问题的最优对偶间隙。

2. 强对偶性：如果等式 d^* = p^* 成立，即最优对偶间隙为零，那么强对偶性成立。这说明从 Language 对偶函数得到的最好下界是紧的。

3. Slater 约束准则：一般强对偶性不成立，但是，如果目标函数是凸函数，不等式约束函数是凸函数，等式约束函数是仿射函数，即 \[ \begin{align*} &\text{minimize} & f_0(x)\\ &\text{subject to} & f_i(x) \leq 0, & i = 1,\cdots,m\\ & & a_i^T x = b_i, & i = 1,\cdots,p \end{align*} \] 除此之外还需要满足一些强对偶性条件，这些条件称为约束准则。

   1. 一个简单的约束准则是 Slater 约束准则：存在一点 x ∈ relint D 使得式 f_i(x) < 0 成立，即不等式约束严格成立。
   2. 弱化的Slater约束准则：简言之，当约束函数 f_i 是仿射函数时，不等式约束不需要严格成立，但当约束函数 f_i 不是仿射函数时，不等式约束需要严格成立。称为弱化的Slater约束准则。

5. 几何解释

6. 鞍点解释

1. 定义：我们称 w̃ ∈ W，z̃ ∈ Z 是函数 f（以及 W 和 Z）的鞍点，如果对于任意 w ∈ W，z ∈ Z 下式成立 \[ f(\overline w, z) \leq f(\overline w,\overline z) \leq f(w,\overline z) \] 换言之，f(w, z̃) 在 w̃ 处取得最小值（关于变量 w ∈ W），f(w̃, z) 在 z̃ 处取得最大值（关于变量 z ∈ Z）： \[ f(\tilde{w}, \hat{z}) = \inf_{w \in W} f(w, \hat{z})\quad f(\tilde{w}, \hat{z}) = \sup_{z \in Z} f(\tilde{w}, z) \] 上式意味着强极大极小性质成立 \[ \sup_{z \in Z} \inf_{w \in W} f(w, z) = \inf_{w \in W} \sup_{z \in Z} f(w, z) \] 且共同值为 f(w̃, z̃)。

2. 关于 Language 对偶：如果 x* 和 λ* 是原问题和对偶问题的最优点，且强对偶性成立，则它们是 Language 函数的一个鞍点。反之亦然。

7. 最优性条件

1. 互补松弛性：如果强对偶性成立，在原问题最优点 x* 处有 \[ \sum_{i = 1}^{m} \lambda_i^* f_i(x^*) = 0. \] 事实上，求和项的每一项都非正，因此有 \[ \lambda_i^* f_i(x^*) = 0. \quad i = 1,\cdots,m \] 上述条件称为互补松弛性：它对任意原问题最优解 x*以及对偶问题最优解( λ* , v*) 成立（当强对偶性成立时）。我们也可以将其写成 \[ \lambda_i^* > 0 \quad \Rightarrow \quad f_i(x^*) = 0, \] 或 \[ f_i(x^*) < 0 \quad \Rightarrow \quad \lambda_i^* = 0. \] 上式意味着在最优点处，除了第 i 个约束起作用的情况，最优 Language 乘子的第 i 项都为零。

2. KKT最优性条件

   1. 非凸问题的KKT条件：和前面一样，令 x* 和 ( λ* , v*) 分别是原问题和对偶问题的某对最优解，对偶间隙为零。因为 L( x*, λ* , v*) 关于 x 求极小在 x* 处取得最小值，因此函数在 x* 处的导数必须为零，即 \[ \nabla f_0(x^*) + \sum_{i = 1}^{m} \lambda_i^* \nabla f_i(x^*) + \sum_{i = 1}^{p} \nu_i^* \nabla h_i(x^*) = 0 \] 因此，我们有 \[ \begin{align*} f_i(x^*) &\leq 0, \quad i = 1, \ldots, m \\ h_i(x^*) &= 0, \quad i = 1, \ldots, p \\ \lambda_i^* &\geq 0, \quad i = 1, \ldots, m \\ \lambda_i^* f_i(x^*) &= 0, \quad i = 1, \ldots, m \quad(互补松弛性) \\ &\nabla f_0(x^*) + \sum_{i = 1}^{m} \lambda_i^* \nabla f_i(x^*) + \sum_{i = 1}^{p} \nu_i^* \nabla h_i(x^*) = 0 \end{align*} \] 我们称上式为Karush - Kuhn - Tucker (KKT)条件。 总之，如果强对偶性成立，那么任意一对原问题和对偶问题的最优解必须满足 KKT 条件。

   2. 凸问题的KKT条件：满足KKT条件的点一定是原问题和对偶问题的最优解。 （而在非凸问题中，KKT条件只是必要条件）

数学知识

1. 范数

1. 范数具有如下性质： \[ \begin{align*} & 1. \|x\| \geq 0，且 \|x\| = 0 的充分必要条件是 x = 0；\\& 2. \|\lambda x\| = |\lambda| \cdot \|x\|（对于任意 \lambda \in \mathbb{R}）；\\& 3. \|x + y\| \leq \|x\| + \|y\|（三角不等式），\\& 以及 Cauchy - Schwarz 不等式 \\& |\langle x,y\rangle| \leq \|x\| \cdot \|y\|， 且等号成立的充分必要条件是：x 与 y 共线，即存在 \lambda，使得 x = \lambda y。\\& 将不等式写成分量形式为：\\& \left|\sum_{i = 1}^{n} x_i y_i\right| \leq \left(\sum_{i = 1}^{n} x_i^2\right)^{\frac{1}{2}} \left(\sum_{i = 1}^{n} y_i^2\right)^{\frac{1}{2}}\\& \end{align*} \]

2. 常见的范数：

   1. P - 范数： \[ \|x\|_p = \left(\sum_{i = 1}^{n} |x_i|^p\right)^{\frac{1}{p}} \quad (1 \leq p < \infty)\\ \]

   2. 1 - 范数： \[ \|x\|_p = \sum_{i = 1}^{n} |x_i|\\ \]

   3. 2 - 范数： \[ \|x\|_2 = \left(\sum_{i = 1}^{n} x_i^2\right)^{\frac{1}{2}}\\ \]

   4. ∞ - 范数：

   \[ \|x\|_{\infty} = \max_{1 \leq i \leq n} |x_i| \]

3. 对偶范数：定义如下 \[ \| y \|_* = \sup_{\| x \| \leq 1} y^T x \]

   1. 1 - 范数的对偶范数是 ∞ - 范数
   2. 2 - 范数的对偶范数是 2 - 范数
   3. ∞ - 范数的对偶范数是 1 - 范数

题目总结

1. 将问题转换为线性规划

1. \[ \begin{align*} \min_{X\in\mathbb{R}^n}\|AX - b\|_1&=\min_{X\in\mathbb{R}^n}\sum_{i = 1}^{n}|AX_i - b| =\min_{\substack{X\in\mathbb{R}^n\\z\in\mathbb{R}^n}}\sum_{i = 1}^{n}z_i\\ \text{subject to}&\quad -z\leq AX - b\leq z \end{align*} \]

2. \[ \left\| x \right\|_{\infty} \leq 1 \Rightarrow - 1 \leq x \leq 1 \]

3. \[ \begin{align*} \min_{X\in\mathbb{R}^n}\|X\|_{\infty}=\min_{X\in\mathbb{R}^n}\max_{(i)}\left(|x_i|\right)=\min_{\substack{\\t\in\mathbb{R_+}}}\sum_{i = 1}^{n}t\\ \text{subject to} \quad -t\mathbf{1} \leq X \leq t\mathbf{1} \end{align*} \]

4. \[ \begin{align*} \min_{X\in\mathbb{R}^n}\sum_{i = 1}^{m}\max\{0,a_i^T x + b_i\}\ =\min_{\substack{X\in\mathbb{R}^n\\z\in\mathbb{R_+}^n}}\sum_{i = 1}^{m}z_i\\ \text{subject to}\quad z_i\geq a_i^T x + b_i \end{align*} \]

2. 验证是凸集

1. 验证 λx₁ + (1-λ)x₂ ∈ S

3. 验证是凸函数

1. Hesse矩阵 \[ H(f)=\begin{pmatrix} \frac{\partial^{2}f}{\partial x_{1}^{2}}&\frac{\partial^{2}f}{\partial x_{1}\partial x_{2}}&\cdots&\frac{\partial^{2}f}{\partial x_{1}\partial x_{n}}\\ \frac{\partial^{2}f}{\partial x_{2}\partial x_{1}}&\frac{\partial^{2}f}{\partial x_{2}^{2}}&\cdots&\frac{\partial^{2}f}{\partial x_{2}\partial x_{n}}\\ \vdots&\vdots&\ddots&\vdots\\ \frac{\partial^{2}f}{\partial x_{n}\partial x_{1}}&\frac{\partial^{2}f}{\partial x_{n}\partial x_{2}}&\cdots&\frac{\partial^{2}f}{\partial x_{n}^{2}} \end{pmatrix} \] 证明 H(f) 是半正定的即可验证是凸函数（二阶条件）

   1. 计算 Hesse 矩阵的 H(f) 特征值。对于矩阵A，其特征值 λ 满足 det(A - λI) = 0，其中 I 是单位矩阵。如果所有特征值λ_i ≥ 0，则 H(f) 矩阵是半正定的，函数是 f 凸函数。
   2. 定义法：证明对于任意非零向量 x，x^TAx ≥ 0。

4. Jensen 不等式的证明

1. 数学归纳法：从 m 到 m+1 的关键步骤： \[ \begin{align*} & f(\lambda_1 x^{(1)} + \lambda_2 x^{(2)} + \cdots + \lambda_m x^{(m)} + \lambda_{m + 1} x^{(m + 1)}) \\ & = f\left( \sum_{i = 1}^{m} \lambda_i \left( \frac{\lambda_1}{\sum_{i = 1}^{m} \lambda_i} x^{(1)} + \frac{\lambda_2}{\sum_{i = 1}^{m} \lambda_i} x^{(2)} + \cdots + \frac{\lambda_m}{\sum_{i = 1}^{m} \lambda_i} x^{(m)} \right) + \lambda_{m + 1} x^{(m + 1)} \right) \end{align*} \] 记 \[ \hat{x} = \sum_{i = 1}^{m} \frac{\lambda_1}{\sum_{i = 1}^{m} \lambda_i} x^{(1)} + \sum_{i = 1}^{m} \frac{\lambda_2}{\sum_{i = 1}^{m} \lambda_i} x^{(2)} + \cdots + \sum_{i = 1}^{m} \frac{\lambda_m}{\sum_{i = 1}^{m} \lambda_i} x^{(m)} \] 再利用凸函数的定义即可解决。

5. 求共轭函数

1. 建立共轭函数表达式，分情况讨论（一般根据 y 值）。下给例题：

   1. 这一题根据 y 分类。 \[ \begin{flalign} &求下列函数的共轭函数：最大值函数：f(x)=\max x_{i}。 \\&若\|y\|_{1} \leq 1且y \geq 0，则y与x内积时不会改变x分量的符号，且一定成立 y^{T} x \leq \max x_{i}, 故此时f^{*}(y)=0。 \\&若不然，则或有\|y\|_{1}>1。不妨设j=\arg \max x_{i}且y_{j}=1+\delta(\delta>0且 其他坐标取0)，那么 \\& \qquad f^{*}(y)=\sup \left\{y^{T} x - x_{j}\right\} \\& \qquad =\sup \left\{\delta x_{j}\right\} \\& \qquad \rightarrow \infty。 \\&又或存在i使得y_{i}<0，类似可证f^{*}(y)不存在。 \\&综上，f^{*}(y)=0，定义域是\left\{y \in \mathbb{R}^{n} | y \geq 0,\|y\|_{1} \leq 1\right\}。 \end{flalign} \]

   2. 这题既有 y 分类，也有 x 分类，注意最后结论需要考虑 x 所有取值。 \[ \begin{flalign} &对于f(x) = |x|： \\&当x\geqslant0时，f^*(y)=\sup_{x\geqslant0}(xy - x)=\sup_{x\geqslant0}x(y - 1)。 \\& \quad 如果y>1，则当x\to+\infty时，x(y - 1)\to+\infty，所以f^*(y)=+\infty。 \\& \quad 如果y\leqslant1，则x(y - 1)\leqslant0，上确界为0。 \\&当x<0时，f^*(y)=\sup_{x<0}(xy + x)=\sup_{x<0}x(y + 1)。 \\& \quad 如果y< - 1，则当x\to-\infty时，x(y + 1)\to+\infty，所以f^*(y)=+\infty。 \\& \quad 如果y\geqslant - 1，则x(y + 1)\leqslant0，上确界为0。 \\&综合起来，f^*(y)=\left\{\begin{matrix}0, &|y|\leqslant1\\ +\infty, &|y|>1\end{matrix}\right. \end{flalign} \]

2. 求导方式求sup(y^Tx - f(x))。下给例题： \[ \begin{flalign} &证明 计算 f(x) = \frac{1}{2}\|x\|^{2} 的共轭函数 f^*(y) \\&对于函数 f(x) = \frac{1}{2}\|x\|^{2}，共轭函数的定义是： \\& \qquad f^*(y) = \sup_{x\in\mathbb{R}^{n}} \left( \langle y,x \rangle - \frac{1}{2}\|x\|^{2} \right) \\&展开目标函数：\langle y,x \rangle - \frac{1}{2}\|x\|^{2} = \langle y,x \rangle - \frac{1}{2} \sum_{i = 1}^{n} x_{i}^{2} \\&对 x 求导并令其为零： \frac{\partial}{\partial x} \left( \langle y,x \rangle - \frac{1}{2}\|x\|^{2} \right) = y - x = 0 \\&因此，最优解为 x = y。将 x = y 代入原目标函数： \\&f^*(y) = \langle y,y \rangle - \frac{1}{2}\|y\|^{2} = \frac{1}{2}\|y\|^{2} \\&因此， f^*(y) = \frac{1}{2}\|y\|^{2}。 \end{flalign} \]

6. 转换为标准几何规划

1. 注意标准几何规划，用指数形式，＝1，≤ 1： \[ \begin{align*} \text{minimize} \quad & f_0(x,y) = \frac{x}{y} & {\text{minimize}} \quad & f_0(x,y) = x^{-1}y\\ \text{subject to} \quad & 1 \leq x \leq 4 & \text{subject to} \quad & x^{-1} \leq 1 ,\quad\frac{1}{4}x \leq 1\\ & x^2 \leq y^2 && x^2y^{-2} \leq 1\\ & \frac{x}{y^3} = 3 && \frac{1}{3}xy^{-3} = 1\\ \end{align*} \]

7. 求对偶问题

1. 构建拉格朗日函数，求对偶函数（分类讨论和求导），Lagrange 对偶函数的最大值就是原问题的最好下界。（注意把求对偶问题的分类条件放入约束条件）。 \[ \begin{align*} \text{maximize} \quad & g(\lambda, \nu) \\ \text{subject to} \quad & \lambda \succeq 0 \end{align*} \]

8. 求KKT条件与最优解

1. 自带的约束条件，λ ≥ 0，互补松弛性。求导等于0： \[ \begin{align*} f_i(x^*) &\leq 0, \quad i = 1, \ldots, m \\ h_i(x^*) &= 0, \quad i = 1, \ldots, p \\ \lambda_i^* &\geq 0, \quad i = 1, \ldots, m \\ \lambda_i^* f_i(x^*) &= 0, \quad i = 1, \ldots, m \quad(互补松弛性) \\ &\nabla f_0(x^*) + \sum_{i = 1}^{m} \lambda_i^* \nabla f_i(x^*) + \sum_{i = 1}^{p} \nu_i^* \nabla h_i(x^*) = 0 \end{align*} \] 注意：

   1. 求导等于0这里，如果有多个变量，则分别列多个等式，每个等式是对某个变量求导。
   2. λ 是针对不等式约束的，没有不等式约束就没有 λ ≥ 0 和互补松弛性。

2. 最优解：简单方法，直接代入看一下目标值即可。

1. 国内的hexo init指令安装支持真的好慢。

2. 网站Next主题的子主题线上显示不出来，发现要清除缓存才行。

3. 搞了半天评论系统看不到效果，结果发现要点进文章里面才能评论。。。

4. 渲染Latex半天才搞好，网上教程不太靠谱

   1. 使用pandoc巨逆天，开始看的几个教程都没说要自己另外安装一个pandoc，并且安装完要重启，不然就出bug。

   2. Next主题的_config.yml文件的mathjax部分删去了某些代码，导致我以为不需要，结果还是得像旧版本一样有

      1	cdn: //cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML

      这尼玛谁想得到，试麻了。

5. 百度爬虫太幽默了，先不说因为疯狂爬github导致了不能用github.io的域名，我换了个域名，然后你验证失败，连接不上服务器，莫名其妙了。

这里记录一下更新hexo需要的东西，以免以后忘了。

文章有关指令：

建立新文章：

1

hexo new (文章标题)

文章添加图片方法1：全局文件夹

1. 在resourse文件夹下添加一个叫images的文件夹（叫什么都行），在里面放入文章所需图片。

2. 使用md语法：

   1	 #注意"自己看的备注"前面有个空格

预览与上传：

1. 预览指令：

   1

   hexo s

2. 更新上传指令（更新完记得 CTRL + f5 强制更新网页，不然可能显示不出来更新后结果）

   1 2	hexo g # 编译 hexo d # 上传

3. 如果线上还是不更新，在编译上传之前先清除缓存

   1	hexo clean