「Algorithm」凸优化/带权二分学习笔记

理解图像意义理解了大半天

Brief Introduction

dp凸优化和带权二分实际上是一个东西，它用来解决一类恰好选k个某种物品的最优化问题

这个最优解与选择的物品数量之间的关系如果用一个函数图像表示，那么这个图像是凸的。换句话说，选的物品越多时，每多选一个物品，最优解增长的速度就越慢

一般而言，在具体题目中这个物品并不好直接选出（可能的状态太多或限制不好满足），但我们可以比较快速地求出没有选择物品数量的限制下的最优解

考虑这样一个模型：有个物品，每个物品有一个权值（可以为负），你需要从中选出恰好个，使得选出来的物品权值和尽量大

显然可以直接排序，但是这只是一个模型，真正题目中物品并不好直接选出。这里我们考虑一种另外的做法

假设没有选择物品的限制，当每个物品的价值越大时，最优情况下选出的物品就越多；每个物品价值越小时，最优情况下选出的物品越少

换句话说，把每个物品的权值都加上一个 $k$ ，那么 $k$ 越大，选出的物品就会越多； $k$ 越小，选出的物品就越少

考虑这样一个做法：

以上基本把凸优化的做法讲完了，感性理解一下很有道理

但是，如果把问题抽象化，仅仅给出原函数是凸的这个条件，我们并不能严谨证明出当每个物品价值越大时，最优情况下选出的物品就越多这一重要性质

其实单从这个角度考虑只能感性理解，严谨证明这个能够二分还需要从几何角度入手

首先注意到一个显然的事情：把每个物品减去之后，在选择物品数目相同的情况下（假设为）的最优策略与原来的策略是一样的

19-3-25-1

在这个图像中，横坐标表示选出的物品个数，纵坐标表示最优策略下选出来的物品价值

绿色的函数是原函数，紫色的函数是原函数每个点减去之后的函数（即原函数减去一个正比例函数）

图中给出的是随便一个 $k$ 的情况

从图像上来看， $C$ 点就是当前最优策略，也就是说 $y_C + k\times x_C = y_A$

设 $B(0, y_C)$ ，那么 $k_{AB} = \frac{AC}{BC} = \frac{k\times x_C}{x_C} = k$ ，即直线 $AB$ 的斜率就等于 $k$ ！(注：这是一个语气助词，不是阶乘)

此外，还有一个特别妙的性质

考虑在 $A, B, C$ 不断移动时，直线 $AB$ 的斜率都为 $k$ ，它是不会改变的

由前面的结论我们知道，当前策略最优时， $C$ 是紫色函数的最高点，即 $B$ 点的纵坐标最大

整理一下信息，我们知道，最优策略下直线 $AB$ 的斜率为 $k$ ，截距最大，且直线与原函数有交点

不难发现，直线 $AB$ 就是过原函数 $A$ 点的切线斜率！

又因为原函数是凸的，所以我们可以二分 $k$ ！(注：这依旧不是阶乘)

直到这里，我们才严谨证明出前面的内容，这也就是原函数需要是凸的的原因

咕咕咕