{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 机器学习中的优化 "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 问题1 (30分）\n",
"假设我们有训练数据$D=\\{(\\mathbf{x}_1,y_1),...,(\\mathbf{x}_n,y_n)\\}$, 其中$(\\mathbf{x}_i,y_i)$为每一个样本，而且$\\mathbf{x}_i$是样本的特征并且$\\mathbf{x}_i\\in \\mathcal{R}^D$, $y_i$代表样本数据的标签（label）, 取值为$0$或者$1$. 在逻辑回归中，模型的参数为$(\\mathbf{w},b)$。对于向量，我们一般用粗体来表达。 为了后续推导的方便，可以把b融入到参数w中。 这是参数$w$就变成 $w=(w_0, w_1, .., w_D)$，也就是前面多出了一个项$w_0$, 可以看作是b，这时候每一个$x_i$也需要稍作改变可以写成 $x_i = [1, x_i]$，前面加了一个1。稍做思考应该能看出为什么可以这么写。\n",
"\n",
"请回答以下问题。请用Markdown自带的Latex来编写。\n",
"\n",
"\n",
"\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### (a) ```编写逻辑回归的目标函数```\n",
"请写出目标函数（objective function）, 也就是我们需要\"最小化\"的目标（也称之为损失函数或者loss function)，不需要考虑正则。 把目标函数表示成最小化的形态，另外把$\\prod_{}^{}$转换成$\\log \\sum_{}^{}$\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"$$\\mathcal{L} (\\mathbf{w}) = - \n",
"\\sum_{i = 1}^{n} \\left[\n",
" y_{i} \\log \\sigma (\\mathbf{w}^{\\text{T}} \\mathbf{x}_{i}) +\n",
" (1 - y_{i}) \\log [1 - \\sigma (\\mathbf{w}^{\\text{T}} \\mathbf{x}_{i})]\n",
"\\right]$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### (b) ```求解对w的一阶导数```\n",
"为了做梯度下降法，我们需要对参数$w$求导，请把$L(w)$对$w$的梯度计算一下："
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"$$\\begin{aligned}\n",
"\\frac{\\partial \\mathcal{L} (\\mathbf{w})}{\\partial \\mathbf{w}}\n",
"& = - \\frac{\n",
" \\partial \\sum_{i = 1}^{n} \\left[\n",
" y_{i} \\log \\sigma (\\mathbf{w}^{\\text{T}} \\mathbf{x}_{i}) + \n",
" (1 - y_{i}) \\log [1 - \\sigma (\\mathbf{w}^{\\text{T}} \\mathbf{x}_{i})]\n",
" \\right]\n",
"}\n",
"{\n",
" \\partial \\mathbf{w}\n",
"} \\\\\n",
"& = - \\sum_{i = 1}^{n} \\left[\n",
" y_{i} \\frac{\n",
" \\partial \\log \\sigma (\\mathbf{w}^{\\text{T}} \\mathbf{x}_{i})\n",
" }\n",
" {\n",
" \\partial \\mathbf{w}\n",
" } + \n",
" (1 - y_{i}) \\frac{\n",
" \\partial \\log [1 - \\sigma (\\mathbf{w}^{\\text{T}} \\mathbf{x}_{i})]\n",
" }\n",
" {\n",
" \\partial \\mathbf{w}\n",
" }\n",
"\\right] \\\\\n",
"& = - \\sum_{i = 1}^{n} \\left[\n",
" y_{i} \\left( 1 - \\sigma (\\mathbf{w}^{\\text{T}} \\mathbf{x}_{i} ) \\right) \\mathbf{x}_{i} - \n",
" (1 - y_{i}) \\sigma (\\mathbf{w}^{\\text{T}} \\mathbf{x}_{i} ) \\mathbf{x}_{i}\n",
"\\right] \\\\\n",
"& = \\sum_{i = 1}^{n} \\left[\n",
" \\sigma (\\mathbf{w}^{\\text{T}} \\mathbf{x}_{i}) - y_{i}\n",
"\\right] \\mathbf{x}_{i} \\\\\n",
"\\end{aligned}$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### (c) ```求解对w的二阶导数```\n",
"在上面结果的基础上对$w$求解二阶导数，也就是再求一次导数。 这个过程需要回忆一下线性代数的部分 ^^。 参考： matrix cookbook: https://www.math.uwaterloo.ca/~hwolkowi/matrixcookbook.pdf, 还有 Hessian Matrix。 "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"$$\\begin{aligned}\n",
"\\frac{\\partial^{2} \\mathcal{L}(\\mathbf{w})}{\\partial^{2} \\mathbf{w}}\n",
"& = \\frac{\n",
" \\partial \\sum_{i = 1}^{n} \\left[\n",
" \\sigma (\\mathbf{w}^{\\text{T}} \\mathbf{x}_{i}) - y_{i}\n",
" \\right] \\mathbf{x}_{i}\n",
"}\n",
"{\n",
" \\partial \\mathbf{w}\n",
"} \\\\\n",
"& = \\sum_{i = 1}^{n} \\frac{\n",
" \\partial \\sigma (\\mathbf{w}^{\\text{T}} \\mathbf{x}_{i})\n",
"}\n",
"{\n",
" \\partial \\mathbf{w}\n",
"} \\mathbf{x}_{i}^{\\text{T}} \\\\\n",
"& = \\sum_{i = 1}^{n}\n",
"\\sigma (\\mathbf{w}^{\\text{T}} \\mathbf{x}_{i})\n",
"\\left( 1 - \\sigma (\\mathbf{w}^{\\text{T}} \\mathbf{x}_{i}) \\right)\n",
"\\mathbf{x}_{i} \\mathbf{x}_{i}^{\\text{T}} \\\\\n",
"\\end{aligned}$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### (d) ```证明逻辑回归目标函数是凸函数```\n",
"试着证明逻辑回归函数是凸函数。假设一个函数是凸函数，我们则可以得出局部最优解即为全局最优解，所以假设我们通过随机梯度下降法等手段找到最优解时我们就可以确认这个解就是全局最优解。证明凸函数的方法有很多种，在这里我们介绍一种方法，就是基于二次求导大于等于0。比如给定一个函数$f(x)=x^2-3x+3$，做两次\n",
"求导之后即可以得出$f''(x)=2 > 0$，所以这个函数就是凸函数。类似的，这种理论也应用于多元变量中的函数上。在多元函数上，只要证明二阶导数是posititive semidefinite即可以。 问题（c）的结果是一个矩阵。 为了证明这个矩阵（假设为H)为Positive Semidefinite，需要证明对于任意一个非零向量$v\\in \\mathcal{R}$, 需要得出$v^{T}Hv >=0$\n",
"请写出详细的推导过程："
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"// TODO 请写下推导过程\n",
"\n",
"$$\\begin{aligned}\n",
"\\mathbf{v}^{\\text{T}} \\frac{\\partial^{2} \\mathcal{L}(\\mathbf{w})}{\\partial^{2} \\mathbf{w}} \\mathbf{v}\n",
"& = \\sum_{i = 1}^{n}\n",
"\\sigma (\\mathbf{w}^{\\text{T}} \\mathbf{x}_{i})\n",
"\\left( 1 - \\sigma (\\mathbf{w}^{\\text{T}} \\mathbf{x}_{i}) \\right)\n",
"\\mathbf{v}^{\\text{T}} \\mathbf{x}_{i} \\mathbf{x}_{i}^{\\text{T}} \\mathbf{v}\\\\\n",
"\\end{aligned}$$\n",
"\n",
"由于$0 \\lt \\sigma (\\mathbf{w}^{\\text{T}} \\mathbf{x}_{i}) \\lt 1$，故只需证明$\\mathbf{v}^{\\text{T}} \\mathbf{x}_{i} \\mathbf{x}_{i}^{\\text{T}} \\mathbf{v} \\geq 0$\n",
"\n",
"$$\\mathbf{v}^{\\text{T}} \\mathbf{x}_{i} \\mathbf{x}_{i}^{\\text{T}} \\mathbf{v}\n",
"= \\left( \\mathbf{v}^{\\text{T}} \\mathbf{x}_{i} \\right)^{2}\n",
"\\geq 0\n",
"\\Rightarrow\n",
"\\frac{\\partial^{2} \\mathcal{L}(\\mathbf{w})}{\\partial^{2} \\mathbf{w}}\n",
"\\geq 0\n",
"\\Rightarrow\n",
"\\frac{\\partial^{2} \\mathcal{L}(\\mathbf{w})}{\\partial^{2} \\mathbf{w}}\n",
"\\succeq 0\n",
"$$\n",
"\n",
"即$\\frac{\\partial^{2} \\mathcal{L}(\\mathbf{w})}{\\partial^{2} \\mathbf{w}}$为半正定矩阵，逻辑回归函数是凸函数得证。\n",
"\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 问题2 （20分）\n",
"证明p-norm是凸函数， p-norm的定义为：\n",
"$||x||_p=(\\sum_{i=1}^{n}|x_i|^p)^{1/p}$\n",
"\n",
"hint: Minkowski’s Inequality"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"// TODO: your proof\n",
"\n",
"minkowski’s inequality, if $1 \\leq p \\lt \\infty$, then whenever $\\mathbf{x}, \\mathbf{y} \\in \\mathcal{V}_{F}$, we have\n",
"\n",
"$$\\begin{aligned}\n",
"\\left\\| \\mathbf{x} + \\mathbf{y} \\right\\|_{p} \\leq \\left\\| \\mathbf{x} \\right\\|_{p} + \\left\\| \\mathbf{y} \\right\\|_{p}\n",
"\\end{aligned}$$\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"given two arbitrary points, $\\mathbf{x}$ and $\\mathbf{y}$, and $0 \\leq \\alpha \\leq 1$, let $\\mathbf{z} = \\alpha \\mathbf{x} + (1 - \\alpha)\\mathbf{y}$\n",
"\n",
"$$\\begin{aligned}\n",
"\\| \\mathbf{z} \\| =\n",
"\\| \\alpha \\mathbf{x} + (1 - \\alpha) \\mathbf{y} \\|_{p} \\leq\n",
"\\| \\alpha \\mathbf{x}_{p} \\| + \\| (1 - \\alpha) \\mathbf{y} \\|_{p} =\n",
"\\alpha \\| \\mathbf{x}_{p} \\| + (1 - \\alpha) \\| \\mathbf{y} \\|_{p}\n",
"\\end{aligned}$$\n",
"\n",
"i.e. p-norm is convex"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 问题3 （20分）"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"在第一次课程中，我们讲了在判定凸函数的时候用到一项技术：second-order convexity， 也就是当函数f(x)在每一个点上twice differentiable, 这时候我们就有个性质： f(x)是凸函数，当且仅当 f(x)的二阶为PSD矩阵（半正定矩阵）。 请在下方试着证明一下此理论。 "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"// your proof of second order convexity\n",
"\n",
"1. sufficiency, to prove $\\nabla^{2} f(\\mathbf{x}) \\succeq 0 \\Rightarrow f(\\mathbf{y}) \\geq f(\\mathbf{x}) + {\\nabla f(\\mathbf{x})}^{\\text{T}} (\\mathbf{y} - \\mathbf{x})$\n",
"\n",
"using tayler expansion at $\\mathbf{x}$, let $\\mathbf{y} = \\mathbf{x} + \\Delta \\mathbf{x}$ and $0 \\lt \\theta \\lt 1$,\n",
"\n",
"$$\\begin{aligned}\n",
"f(\\mathbf{y})\n",
"& = f(\\mathbf{x} + \\Delta \\mathbf{x}) \\\\\n",
"& = f(\\mathbf{x}) + {\\nabla f(\\mathbf{x})}^{\\text{T}} \\Delta \\mathbf{x}\n",
"+ \\frac{1}{2} {\\Delta \\mathbf{x}}^{\\text{T}} {\\nabla^{2} f(\\mathbf{x} + \\theta \\Delta \\mathbf{x})} \\Delta \\mathbf{x} \\\\\n",
"& \\because \\nabla^{2} f(\\mathbf{x}) \\succeq 0 \\\\\n",
"& \\therefore {\\Delta \\mathbf{x}}^{\\text{T}} {\\nabla^{2} f(\\mathbf{x} + \\theta \\Delta \\mathbf{x})} \\Delta \\mathbf{x} \\geq 0 \\\\\n",
"f(\\mathbf{y})\n",
"& \\geq f(\\mathbf{x}) + {\\nabla f(\\mathbf{x})}^{\\text{T}} \\Delta \\mathbf{x}\n",
"\\end{aligned}$$\n",
"\n",
"2. necessity, to prove $f(\\mathbf{y}) \\geq f(\\mathbf{x}) + {\\nabla f(\\mathbf{x})}^{\\text{T}} (\\mathbf{y} - \\mathbf{x}) \\Rightarrow \\nabla^{2} f(\\mathbf{x}) \\succeq 0 $\n",
"\n",
"consider tayler expansion, let $0 \\leq \\theta \\leq 1$\n",
"\n",
"$$\\begin{aligned}\n",
"f(\\mathbf{x} + \\Delta \\mathbf{x})\n",
"& = f(\\mathbf{x}) + \\nabla f(\\mathbf{x}) \\Delta \\mathbf{x}\n",
"+ \\frac{1}{2} {\\Delta \\mathbf{x}}^{\\text{T}} \\nabla^{2} f(\\mathbf{x} + \\theta \\Delta \\mathbf{x}) {\\Delta \\mathbf{x}}\n",
"\\end{aligned}$$\n",
"\n",
"for $f$ is convex,\n",
"\n",
"$$\\begin{aligned}\n",
"f(\\mathbf{x} + \\Delta \\mathbf{x}) \\geq f(\\mathbf{x}) + \\nabla f(\\mathbf{x}) \\Delta \\mathbf{x}\n",
"\\end{aligned}$$\n",
"\n",
"then\n",
"\n",
"$$\\begin{aligned}\n",
"{\\Delta \\mathbf{x}}^{\\text{T}} \\nabla^{2} f(\\mathbf{x} + \\theta \\Delta \\mathbf{x}) {\\Delta \\mathbf{x}}\n",
"& = 2 (f(\\mathbf{x} + \\Delta \\mathbf{x})\n",
"- f(\\mathbf{x}) - \\nabla f(\\mathbf{x}) \\Delta \\mathbf{x})\n",
"\\geq 0\n",
"\\end{aligned}$$\n",
"\n",
"for $\\Delta \\mathbf{x}$ is an arbitrary vector, according to the definition of positive semi-definite,\n",
"\n",
"$$\\begin{aligned}\n",
"\\nabla^{2} f(\\mathbf{x} + \\theta \\Delta \\mathbf{x}) \\succeq 0\n",
"\\end{aligned}$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 问题4 （30分）\n",
"在课堂里我们讲过Transportation problem. 重新描述问题： 有两个城市北京和上海，分别拥有300件衣服和500件衣服，另外有三个城市分别是1，2，3分别需要200，300，250件衣服。现在需要把衣服从北京和上海运送到城市1，2，3。 我们假定每运输一件衣服会产生一些代价，比如：\n",
"- 北京 -> 1: 5\n",
"- 北京 -> 2: 6\n",
"- 北京 -> 3: 4\n",
"- 上海 -> 1: 6\n",
"- 上海 -> 2: 3\n",
"- 上海 -> 3: 7\n",
"\n",
"最后的值是单位cost. \n",
"\n",
"问题：我们希望最小化成本。 "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"```(a)``` 请写出linear programming formulation。 利用标准的写法(Stanford form)，建议使用矩阵、向量的表示法。 "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"// your formulation\n",
"\n",
"$\\mathbf{x} = (x_{1}, x_{2}, \\dots, x_{6})$, $\\mathbf{w} = (5, 6, 4, 6, 3, 7)$\n",
"\n",
"$$\\begin{aligned}\n",
"& \\min_{\\mathbf{x}} \\mathbf{w}^{\\text{T}} \\mathbf{x} \\\\\n",
"& s.t. \n",
"\\begin{cases}\n",
" x_{1} + x_{2} + x_{3} \\leq 300 \\\\\n",
" x_{4} + x_{5} + x_{6} \\leq 500 \\\\\n",
" x_{1} + x{3} = 200 \\\\\n",
" x_{2} + x{4} = 300 \\\\\n",
" x_{3} + x{6} = 250 \\\\\n",
" x_{i} \\geq 0\n",
"\\end{cases}\n",
"\\end{aligned}$$\n",
"\n",
"i.e.\n",
"\n",
"$$\\begin{aligned}\n",
"& \\min_{\\mathbf{x}} \\mathbf{w}^{\\text{T}} \\mathbf{x} \\\\\n",
"& s.t. \n",
"\\begin{cases}\n",
" \\mathbf{A}_{\\text{ub}} \\mathbf{x} - \\mathbf{b}_{\\text{ub}} \\leq 0 \\\\\n",
" \\mathbf{A}_{\\text{eq}} \\mathbf{x} - \\mathbf{b}_{\\text{eq}} = 0 \\\\\n",
" - \\mathbf{x} \\leq 0\n",
"\\end{cases}\n",
"\\end{aligned}$$\n",
"\n",
"with\n",
"\n",
"$$\\mathbf{A}_{\\text{ub}} = \\begin{bmatrix}\n",
" 1 & 1 & 1 & 0 & 0 & 0 \\\\\n",
" 0 & 0 & 0 & 1 & 1 & 1\n",
"\\end{bmatrix}$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"```(b)``` 利用lp solver求解最优解。 参考：\n",
"https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linprog.html\n",
" 或者： http://cvxopt.org/"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {},
"outputs": [],
"source": [
"# your implementation\n",
"\n",
"from scipy.optimize import linprog\n",
"import numpy as np"
]
},
{
"cell_type": "code",
"execution_count": 34,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"cost: 3049.999996 with x = [5.00000000e+01 3.80939619e-08 2.49999999e+02 1.50000000e+02\n",
" 2.99999999e+02 1.15679510e-07]\n"
]
}
],
"source": [
"w = np.array([5, 6, 4, 6, 3, 7])\n",
"\n",
"A_ub = np.array([[1, 1, 1, 0, 0, 0], [0, 0, 0, 1, 1, 1]])\n",
"b_ub = np.array([300, 500])\n",
"\n",
"A_eq = np.array([[1, 0, 0, 1, 0, 0], [0, 1, 0, 0, 1, 0], [0, 0, 1, 0, 0, 1]])\n",
"b_eq = np.array([200, 300, 250])\n",
"\n",
"ret = linprog(c=w, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq)\n",
"\n",
"if ret.success:\n",
" x_opt = ret.x\n",
" cost = ret.fun\n",
"else:\n",
" x_opt = None\n",
" cost = None\n",
" \n",
"print(\"cost: {:f} with x = {}\".format(cost, x_opt))"
]
},
{
"cell_type": "code",
"execution_count": 35,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"cost: 3050 with x = [50, 0, 250, 150, 300, 0]\n"
]
}
],
"source": [
"# rounding to integer\n",
"\n",
"x_opt = [int(round(num)) for num in x_opt]\n",
"cost = np.sum(c * x)\n",
"print(\"cost: {:d} with x = {}\".format(cost, x_opt))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"```(c)```: 试着把上述LP转化成Dual formulation，请写出dual form. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"// your formulation\n",
"\n",
"* primal problem:\n",
"\n",
"$$\\begin{aligned}\n",
"& \\min_{\\mathbf{x}} \\mathbf{w}^{\\text{T}} \\mathbf{x} \\\\\n",
"& s.t. \n",
"\\begin{cases}\n",
" \\mathbf{A}_{\\text{ub}} \\mathbf{x} - \\mathbf{b}_{\\text{ub}} \\leq 0 \\\\\n",
" \\mathbf{A}_{\\text{eq}} \\mathbf{x} - \\mathbf{b}_{\\text{eq}} = 0 \\\\\n",
" - \\mathbf{x} \\leq 0\n",
"\\end{cases}\n",
"\\end{aligned}$$\n",
"\n",
"lagrangian formula\n",
"\n",
"$$\\begin{aligned}\n",
"\\mathcal{L}(\\mathbf{x}, \\mathbf{\\alpha}, \\mathbf{\\beta}, \\mathbf{\\gamma})\n",
"& = \\mathbf{w}^{\\text{T}} \\mathbf{x}\n",
"+ \\mathbf{\\alpha}^{\\text{T}} (\\mathbf{A}_{\\text{ub}} \\mathbf{x} - \\mathbf{b}_{\\text{ub}})\n",
"+ \\mathbf{\\beta}^{\\text{T}} (\\mathbf{A}_{\\text{eq}} \\mathbf{x} - \\mathbf{b}_{\\text{eq}})\n",
"- \\mathbf{\\gamma}^{\\text{T}} \\mathbf{x}\n",
"\\end{aligned}$$\n",
"\n",
"with\n",
"\n",
"$$\\mathbf{\\alpha} \\geq 0, \\mathbf{\\gamma} \\geq 0$$\n",
"\n",
"define\n",
"\n",
"$$\\begin{aligned}\n",
"\\mathcal{P}(\\mathbf{x})\n",
"& = \\sup_{\\mathbf{\\alpha} \\geq 0, \\mathbf{\\beta}, \\mathbf{\\gamma} \\geq 0} \\mathcal{L}(\\mathbf{x}, \\mathbf{\\alpha}, \\mathbf{\\beta}, \\mathbf{\\gamma}) \\\\\n",
"& = \\begin{cases}\n",
" \\mathbf{w}^{\\text{T}} \\mathbf{x}, & \\text{if } \\mathbf{x} {\\text{ is feasible}} \\\\\n",
" + \\infty, & \\text{otherwise} \\\\\n",
"\\end{cases}\n",
"\\end{aligned}$$\n",
"\n",
"therefore\n",
"\n",
"$$\\begin{aligned}\n",
"\\min_{\\mathbf{x}} \\mathbf{w}^{\\text{T}} \\mathbf{x}\n",
"& \\Leftrightarrow \\inf_{\\mathbf{x}} \\mathcal{P}(\\mathbf{x})\n",
"= \\inf_{\\mathbf{x}} \\sup_{\\mathbf{\\alpha} \\geq 0, \\mathbf{\\beta}, \\mathbf{\\gamma} \\geq 0} \\mathcal{L}(\\mathbf{x}, \\mathbf{\\alpha}, \\mathbf{\\beta}, \\mathbf{\\gamma})\n",
"\\end{aligned}$$\n",
"\n",
"* dual problem:\n",
"\n",
"define\n",
"\n",
"$$\\begin{aligned}\n",
"\\mathcal{D}(\\mathbf{\\alpha}, \\mathbf{\\beta}, \\mathbf{\\gamma})\n",
"& = \\inf_{\\mathbf{x}} \\mathcal{L}(\\mathbf{x}, \\mathbf{\\alpha}, \\mathbf{\\beta}, \\mathbf{\\gamma}) \\\\\n",
"& = \\mathbf{w}^{\\text{T}} \\mathbf{x}\n",
"+ \\mathbf{\\alpha}^{\\text{T}} (\\mathbf{A}_{\\text{ub}} \\mathbf{x} - \\mathbf{b}_{\\text{ub}})\n",
"+ \\mathbf{\\beta}^{\\text{T}} (\\mathbf{A}_{\\text{eq}} \\mathbf{x} - \\mathbf{b}_{\\text{eq}})\n",
"- \\mathbf{\\gamma}^{\\text{T}} \\mathbf{x} \\\\\n",
"& = (\\mathbf{w}^{\\text{T}} + \\mathbf{\\alpha}^{\\text{T}} \\mathbf{A}_{\\text{ub}} + \\mathbf{\\beta}^{\\text{T}} \\mathbf{A}_{\\text{eq}} - \\mathbf{\\gamma}^{\\text{T}}) \\mathbf{x}\n",
"- \\mathbf{\\alpha}^{\\text{T}} \\mathbf{b}_{\\text{ub}}\n",
"- \\mathbf{\\beta}^{\\text{T}} \\mathbf{b}_{\\text{eq}} \\\\\n",
"& = \\begin{cases}\n",
" - \\mathbf{\\alpha}^{\\text{T}} \\mathbf{b}_{\\text{ub}}\n",
" - \\mathbf{\\beta}^{\\text{T}} \\mathbf{b}_{\\text{eq}},\n",
" & \\text{if } \\mathbf{w}^{\\text{T}} + \\mathbf{\\alpha}^{\\text{T}} \\mathbf{A}_{\\text{ub}} + \\mathbf{\\beta}^{\\text{T}} \\mathbf{A}_{\\text{eq}} - \\mathbf{\\gamma}^{\\text{T}} = 0 \\\\\n",
" - \\infty, & \\text{otherwise} \\\\\n",
"\\end{cases}\n",
"\\end{aligned}$$\n",
"\n",
"therefore, the dual problem\n",
"\n",
"$$\\begin{aligned}\n",
"\\sup_{\\mathbf{\\alpha} \\geq 0, \\mathbf{\\beta}, \\mathbf{\\gamma} \\geq 0} \\mathcal{D}(\\mathbf{\\alpha}, \\mathbf{\\beta}, \\mathbf{\\gamma})\n",
"& = \\sup_{\\mathbf{\\alpha} \\geq 0, \\mathbf{\\beta}, \\mathbf{\\gamma} \\geq 0} \\inf_{\\mathbf{x}} \\mathcal{L}(\\mathbf{x}, \\mathbf{\\alpha}, \\mathbf{\\beta}, \\mathbf{\\gamma})\n",
"\\end{aligned}$$\n",
"\n",
"can be written as\n",
"\n",
"$$\\begin{aligned}\n",
"& \\max_{\\mathbf{\\alpha}, \\mathbf{\\beta}}(- \\mathbf{\\alpha}^{\\text{T}} \\mathbf{b}_{\\text{ub}} - \\mathbf{\\beta}^{\\text{T}} \\mathbf{b}_{\\text{eq}}) \\\\\n",
"& s.t. \n",
"\\begin{cases}\n",
" \\mathbf{w}^{\\text{T}} + \\mathbf{\\alpha}^{\\text{T}} \\mathbf{A}_{\\text{ub}} + \\mathbf{\\beta}^{\\text{T}} \\mathbf{A}_{\\text{eq}} \\geq 0 \\\\\n",
" \\mathbf{\\alpha} \\geq 0 \\\\\n",
"\\end{cases}\n",
"\\end{aligned}$$\n",
"\n",
"i.e.\n",
"\n",
"$$\\begin{aligned}\n",
"& \\min_{\\mathbf{\\alpha}, \\mathbf{\\beta}}(\n",
" \\mathbf{b}_{\\text{ub}}^{\\text{T}} \\mathbf{\\alpha}\n",
" + \\mathbf{b}_{\\text{eq}}^{\\text{T}} \\mathbf{\\beta}\n",
") \\\\\n",
"& s.t. \n",
"\\begin{cases}\n",
" \\mathbf{w}^{\\text{T}} + \\mathbf{\\alpha}^{\\text{T}} \\mathbf{A}_{\\text{ub}} + \\mathbf{\\beta}^{\\text{T}} \\mathbf{A}_{\\text{eq}} \\geq 0 \\\\\n",
" \\mathbf{\\alpha} \\geq 0 \\\\\n",
"\\end{cases}\n",
"\\end{aligned}$$"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.6.9"
}
},
"nbformat": 4,
"nbformat_minor": 2
}