凸规划是指若最优化问题的目标函数为凸函数，不等式约束函数也为凸函数，等式约束函数是仿射的。凸规划的可行域为凸集，因而凸规划的局部最优解就是它的全局最优解。当凸规划的目标函数为严格凸函数时，若存在最优解，则这个最优解一定是唯一的最优解。
一、凸集
凸集：设\(C\)为\(n\)维欧式空间的一个集合，若\(C\)内任意两点间的线段也均在\(C\)内，则称集合\(C\)为凸集。即
\[\forall x_1, x_2 \in C, \forall \theta \in [0,1]，则 x= \theta * x_1 + (1-\theta)*x_2 \in C \]凸组合（convex combination）： $$λ_1x_1+⋯+λ_kx_k$$
其中，\(λ_1,⋯,λ_k≥0,∑λ_i=1\)，二元 $ k_1 * x_1 + (1-k_1)*x_2$就是一个凸组合。
凸集有良好的运算性质：(1) 交集为凸集。(2) 和集为凸集。(3) 直和为凸集。
超平面hyperplane：\(H=\{x|a^Tx=b\}(a≠0)\);
半平面halfspace：$ H^+={ x|a^Tx \geq b}(a\neq 0) \\ H^-=\{ x|a^Tx \leq b\}(a\neq 0)$;
多面体polyhedra：多个线性不等式所刻画的集合：$$\{ x|a^T_ix\leq b_i,i=1,\cdots,m\}$$ 注：线性等式刻画的集合也是多面体！（可以将等式，转换为两个不等式）
椭球（Ellipsoid）：
\[\{x| (x-x_c)^T P^ {-1} (x-x_c)\leq 1 \}; 其中 P为正定矩阵; 椭球的轴长为\sqrtλ_i \]二、凸函数
设\(f\)为定义在区间\(I\)上的函数，若对\(I\)上的任意两点\(x_1, x_2\)和任意$\lambda \in (0,1) $有
\[f(\lambda x_i + (1-\lambda)x_2)\leq \lambda f(x_i)+(1-\lambda)f(x_2) \]将"\(\leq\)"换成"\(<\)"也成立则就是严格凸函数。
性质1： 设 \(f:R^n–>R^1\)，\(C\)是凸集，若\(f\)是凸函数，则对于任意的\(β\)，水平集\(D_\beta = \{x|f(x) \leq \beta, x \in C\}\)是凸集。
性质2 : 凸优化问题的局部极小值是全局极小值。
性质3： 若\(f\)一阶可微，则函数\(f\)为凸函数当且仅当\(f\)的定义域\(domf\)为凸集，且$ \forall x,y \in domf, f(y)\geq f(x) + \triangledown f(x)^T(y-x)$。
性质4：若\(f\)二阶可微，则函数\(f\)为凸函数当且仅当\(f\)的定义域\(domf\)为凸集，且\(\triangledown ^2f(x)\succeq 0\)。
正定：\(f(x_1,x_2,...,x_n)=x^TAx\)，(所有的二次齐次式都可以写成这个形式）如果对任意的\(x \neq 0均有f(x)>0\)，则称\((f(x)\)为正定二次型，同时称\(A\)为正定矩阵。
[定理] 设\(f(x):{R^n} \to R\)是在凸集\(X \subseteq {R^n}\)上二阶可微。\(f(x)\)是凸函数的充分必要条件是\(f(x)\)的二阶海塞矩阵\({\nabla ^2}f(x)\)是半正定的；\(f(x)\)是凹函数的充分必要条件是\(f(x)\)的二阶海塞矩阵\({\nabla ^2}f(x)\)是半负定的。
例1：判断下述函数的凸凹性: (1)\(f(x) = {e^x}\) (2)\(f(x) = x^{\frac{1}{2}}\) (3)\(f({x_1},{x_2}) = 2 + {x_1} + {x_2} - x_1^2 - x_2^2\) 解： (1) \(f^{\prime \prime}(x)=e^x \geq 0\), 所以 \(f(x)\) 函数是凸集 \(R\) 上的的凸函数. (2) \(f^{\prime \prime}(x)=-\frac{1}{4} x^{-3 / 2} \leq 0\), 所以 \(f(x)\) 函数是凸集 \(R\) 上的的凹函数. (3) \(f\left(x_1, x_2\right)\) 的 Hessian 矩阵为:
\[\nabla^2 f(x)=\left[\begin{array}{cc} -2 & 0 \\ 0 & -2 \end{array}\right] \]为了判断 \(\nabla^2 f(x)\) 的半正 (负) 定性, 计算:
\[\begin{aligned} \operatorname{def}\left(\nabla^2 f(x)-\lambda I\right) & =\operatorname{def}\left[\begin{array}{cc} -2-\lambda & 0 \\ 0 & -2-\lambda \end{array}\right] \\ & =(-2-\lambda)^2=0 \end{aligned} \]那么, \(\lambda_1=\lambda_2=-2\), 所以矩阵 \(\nabla^2 f(x)\) 为负定矩阵, \(f(x)\) 为凸集 \(R\) 上的凹函数.
三、凸规划
基本形式：
\[ minimize f_0(x), x\in R^n\\ s.t. \quad f_i(x)\leq0,i=1...m; \\ h_(x)=0,j=1...p\]优化问题的域 (D=\cap_{i=0}^m domf \cap \cap_{j=1}^p domh_j)
可行点（解）：(x\in D)，且满足约束条件
可行域：所有可行点的集合
最优化值 \((p^* = inf\{f_0(x)|f_i(x)\leq0,i=1...m,h_j(x)=0,j=1...p\}\) 最优化解 \(p^*=f_0(x^*)\)