西瓜皮的博客

I am taking Convex Optimization this semester (2021 Spring). The notes are based on my understanding of the course materials provided by Prof. Zhouchen Lin. The notes only offer concise definition and formulas with few proofs and examples. From this chapter, we start to introduce convex optimization algorithms, including descent methods, newton’s methods, conjugate direction methods, and majorization minimization. I used to consider gradient descent as the simple basis of neural networks, so I d ...

Table of Contents: 纳什均衡 纯策略均衡算法 混合策略均衡算法 实验结果 实验心得 纳什均衡# 纳什均衡是一个策略组合，其中每个博弈者的均衡策略都旨在让自己期望收益达到最大，因而没有人愿意独自背离该均衡。为了方便算法设计，我们可以如下进一步理解这一定义： 对于纯策略纳什均衡，我们理解为“没有博弈者有意愿去改变自己的策略”。 对于混合策略纳什均衡，我们理解为“个人混合策略的选择使得他人的任意选择期望收益一致”。 纳什证明了n人有限博弈中，纳什均衡的普遍存在性。纯策略可以被理解为选定策略概率为1的混合策略特例，因此存在性定理也可以说是必定有混合策略存在。 纯策略均衡算法# 本次实验中只考虑双人博弈情况，朴素的算法可以遍历两人的n2n^2n2对选择，然后考虑行列方向上两人有没有更优的选择，是否能为更高收益背离当前策略。这样的算法复杂度是O(n3)O(n^3)O(n3)的。 假设行博弈者为a，列博弈者为b。考虑借助经济学上常用的“划线法”来优化至O(n2)O(n^2)O(n2)： 固定行，找每列中b收益最大的格子，标记+1 固定列，找每行a收益最大的格子， ...

Table of Contents: 友谊悖论 理论证明 实验结果 实验心得 友谊悖论# 友谊悖论指的是社交网络中，一个人的朋友数通常少于朋友的平均朋友数。从另一个角度来看，友谊悖论表明人们通常会与朋友和自己一样多或者更多的人交友。 假设社交网络是一张无向图G=(V,E)G=( V,E)G=(V,E)，每个顶点是一个人，每条边表示两个端点上的人互为朋友。则对于任意一个人vvv，符合友谊悖论的情况用数学语言表示即： d(v)≤∑v′∈Vd(v′)⋅1{v′∣(v,v′)∈E}(v′)d(v)d(v) \le \frac{\sum_{v'\in V}d(v')\cdot \mathbf{1}_{ \{v'\mid (v,v')\in E \}}(v')}{d(v)} d(v)≤d(v)∑v′∈V​d(v′)⋅1{v′∣(v,v′)∈E}​(v′)​ 理论证明# 在社交网络G=(V,E)G=( V,E)G=(V,E)中，每个节点（人）度数（朋友数）的期望为： Edegree=μ=2∣E∣∣V∣\mathbf{E}_{\text{d ...

Table of Contents: 匹配市场 算法设计 一一对应算法（失败） 受限集+匈牙利算法 实验结果 实验心得 匹配市场# 匹配市场讨论一群卖方和一群同样数量买方的一一匹配问题，旨在找到社会最优的匹配方式。买家对每个卖家有自己的估值，形成n×nn\times nn×n估值矩阵。通过调整卖家的价格至市场清仓价，买方可以得到与估值差价最大的商品，不存在冲突。 这里的“社会最优”指的是所有人对买到的商品的估值总和最大。清仓价格是不唯一的，算法设计部分中的失败案例中会提到案例。 算法设计# 一一对应算法（失败）# 书上介绍的匹配市场算法需要先找到受限买家集合SSS，即SSS中的买家偏好的商品集合S′S'S′满足∣S′∣<∣S∣|S'|<|S|∣S′∣<∣S∣。 开始实现了一个版本，试图找到价格更新后能够一一对应的结果，即试图让每个商品只有一个人偏好。代码如下： import numpy as npdef read_file(file): with open(file, "r+", encoding="utf-8") as f ...

I am taking Convex Optimization this semester (2021 Spring). The notes are based on my understanding of the course materials provided by Prof. Zhouchen Lin. The notes only offer concise definition and formulas with few proofs and examples. This chapter is the last of the basics, in the next chapter we will start to introduce specific algorithms. We first define convex function, how to judge convexity, and properties related with convexity. Next, we discuss operations that preserve convexity just ...

I am taking Convex Optimization this semester (2021 Spring). The notes are based on my understanding of the course materials provided by Prof. Zhouchen Lin. The notes only offer concise definition and formulas with few proofs and examples. In this chapter, we introduce convexity. We define convex sets first and will discuss convex functions in the next chapter. We go from affine sets to convex sets and cones. Later on, we will talk about some operations that could preserve convexity. Also, we wi ...

I am taking Convex Optimization this semester (2021 Spring). Here is the first chapter of my course notes. The notes are based on my understanding of the course materials provided by Prof. Zhouchen Lin. The notes only offer concise definition and formulas with few proofs and examples. Mathematical Backgrounds# Table of Contents: Topology in Rn\mathbb{R}^nRn Analysis in Rn\mathbb{R}^nRn Derivative Second derivative Neural Network Linear Algebra Norms Topology in Rn\mathbb{R}^nRn# open, cl ...

Quantitative Trading Camp(QTC) is a 3-day camp held by Jane Street, basically for students unfamiliar with trading to get a primary understanding of it. In these 3 days, we played games for most of the time and had some lectures regarding market and quantitative trading. This post mainly talks about all the games we played and some of my thoughts on them. Why I applied for QTC# I applied for QTC by accident. I took part in a poker game at school and got a good place (given that I haven’t played ...

也不是不行