我的凸优化引论课程的期末作业,花了一些时间,贴上来纪念一下吧。 Review of Primal-Dual Interior-Point Methods介绍内点法(Interior-Point Methods)是用于解决最优化问题的一类迭代算法,它从问题的可行区域内部出发,不断逼近最优点。与之相对的,是在问题可行区域边界搜索最优解,如单纯形法。内点法高效地解决了一系列数学规划问题,尤其在线性规划领域(LP),从理论和实际效率方面均击败了多年来占统治地位的单纯形法。目前许多用于求解优化问题的软件包(CPLEX, Excel Solver, LINDO/LINGO等)内核都包含了以内点法为基础的算 ...
Combinatorial Optimization-Matroid
前言拟阵这个概念在各个场合听了很多遍了,一直没有系统地整理过。本篇基于组合优化经典教材Combinatorial Optimization-Algorithms and Complexity第12章, 主要介绍拟阵的一些基本性质和两拟阵交算法。 独立集系统和拟阵定义独立集系统$S=(E, \mathcal{I})$, $E$是基本元素的集合, $\mathcal{I} \subseteq 2^{E}$, $\mathcal{I}$中的元素称为独立集。$\mathcal{I}$需要满足遗传性: 如果$A \in \mathcal{I}, B \subseteq A$, 那么$B \in \mat ...
Binpacking-First Fit
有关Binpacking问题的定义和其他近似算法见我之前的文章, 本篇主要补充Binpacking问题First Fit算法可以做到1.7的渐进近似比。First Fit算法: 依次考虑每个物品, 逐个检查当前已经开着的箱子, 发现第一个能装下它的箱子就装。如果都装不下,开一个新的箱子装它。 证明框架设第$i$个物品的体积是$s_i$.设计一个权函数$w(x)$, $w(S):= \sum_{i \in S}{w(s_i)}$.我们用$w(I)$作为桥梁,证明$ALG(I) - \epsilon \leq w(I) \leq 1.7 OPT(I)$, 从而证明1.7的渐进近似比。权函数$w(x ...
Coding Theory-Expander Codes
IntroductionExpander Code是一种特殊的Linear Code, 特殊之处在于它的check matrix对应某个(bipartite) expander graph的临接矩阵. 这样一来,编码的一些性质(如距离、解码)就可以和图的性质对应起来。 为了只会阐述方便,我们先约定一些记号: 用$G(L \cup R, E)$表示一个二分图, $L, R$分别表示左右两个点集。 定义点集$S$的邻居$N(S):=\{v| v \text{ is incident to some vertex } u\in S \}$. 定义点集$S$的唯一邻居$U(S) :=\{v| v ...
Coding Theory-Some Bounds
本节主要介绍关于编码的一些上下界。 The Main Coding Theory Problem定义$A_q(n, d)$为长度为$n$, 最小距离是$d$的编码, size最大能是多少。$B_q(n, d)$为长度为$n$, 最小距离是$d$的线性码, size最大能是多少。 确定它们的值或者上下界成为The Main Coding Theory Problem. 首先是几个非常trivial的bound: $B_q(n, d) \leq A_q(n, d) \leq q^n$. $B_q(n, 1) = A_q(n, 1) = 1$. $B_q(n, n) = A_q(n, n) = n ...
Coding Theory-Linear Code
Introduction编码的目的:将信息通过某种方式编码后传输(比如ASCII码将字母变成8位01串),使之满足下面的某些性质: 编码速度快。 编码结果易于传输。 解码速度快。 极大化信息传输率(可以理解为用尽可能少的长度表示尽可能多的信息)。 检测/纠正传输错误。 Basic ConceptsNotations code alphabet. 用于编码的字符集, 字符集中的元素成为code symbol, 一般用$q$表示字符集的大小。 通常用字母C表示编码的集合,其中的元素成为codeword, 每个codeword可以看做是长度为$n$的向量, 向量的每个分量取值来自code alp ...
Approximation Algorithm(9)-The Maxcut Problem
Week 9: Maximum Cut and Semi-Definite Programming Problem Definition给定边权非负的无向图$G=(V,E)$, 将其分成两个点集$(S, G \backslash S)$, 最大化$\sum_{e \in cut(S, G \backslash S)}{w_e}$. Simple 2-approximation Algorithms假设对于每个点, 有$p$的概率选入集合$S$, 那么 E(output) = \sum_{e:=(u, v)}{w_e Pr[u, v \text{ belong to different par ...
Approximation Algorithm(8)-The Facility Location Problem
Week 8: The Facility Location Problem Problem Definition小区里要建某种公共设施, 可以建造设施的位置集合为$\mathcal{F}$, 在第$i$个位置建造设施的花费是$f_i$. 设顾客集合为$\mathcal{C}$, $c_{ij}$表示顾客$j$与设施$i$之间的距离, 且约定这个距离满足三角形不等式(即$c_{ij}$就是设施$i$和顾客$j$的最短距离)。显然,每个顾客会选择离自己最近的设施。作为政府,一个目标是建造设施的代价尽可能少,另一个目标是不能让顾客离设施太远。定义总代价为建造设施的代价加上每个顾客到离自己最近的建好的 ...