漫步最优化四——约束

本文主要是介绍漫步最优化四——约束，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

$\textbf{你从天而降的那刻起，我的世界变得难以言喻。}$
$\textbf{从陌生到熟悉，我从来没有奢望过爱情的到来。}$
$\textbf{但是我却忙于快乐，忙于感动，忙于牵挂。}$
$\textbf{这一刻，我想勇敢地说：宝宝，我爱你。}$
$\qquad\qquad\qquad\qquad\textbf{——畅宝宝的傻逼哥哥}$

在许多优化问题中，变量之间是相互关联的，比如质量或能量守恒定律，基尔霍夫电压与电流定律，以及其他一些的方程组。从效果上看，如下所示的等式形式：

$$a_i(\textbf{x})=0\quad for\ \textbf{x}\in E^n$$

其中$i=1,2,\ldots,p$，在求解问题之前，必须满足。在其他优化问题中，变量或参数上会强加一些不等式约束，从而确保实际性，可靠性，兼容性或者简化问题，例如电路中电流超过给定的上限，那么能耗就会急剧增加或者电路中电流低于某个下限，系统会不稳定等等，对于这种问题，下面的不等式形式：

$$c_j(\textbf{x})\geq 0\quad for\ \textbf{x}\in E^n$$

其中$j=1,2,\ldots,q$，在求解问题之前，必须满足。

优化问题可能包含一系列等式约束与不等式约束，对于这种情况，我们称该问题为约束优化问题，大部分约束优化问题数学上表示为：

$$\begin{align*} minimize f(\textbf{x})\qquad for\ \textbf{x}\in E^n\\ subject\ to:\ a_i(\textbf{x})=0\quad for\ i=1,2,\ldots,p\\ c_j(\textbf{x})\geq0\quad for\ j=1,2,\ldots,q \end{align*}$$

不包含等式与不等式约束的问题称为无约束优化问题。

直觉上约束优化问题比无约束优化问题难，所以目前目前对约束优化问题的研究策略就是将其重写成无约束优化问题，通过重定义目标函数，使得最小化目标函数的同时满足约束条件就能实现，如下面的例子所示。

$\textbf{例1：}$$q_1,q_2,\ldots,q_m$表示某公司$m$个工厂产出的同一产品量，他们位于不同的地方。这些产品被送到$n$个零售商那里，分别需要的量为$b_1,b_2,\ldots,b_n$，假设从$i$工厂到$j$零售商那里的单位运运送成本为$c_{ij}$，其中$i=1,2,\ldots,m$，$j=1,2,\ldots,n$，那么找出从$i$场到$j$零售商最小的$x_{ij}$，即

$$minimize\ C=\sum_{i=1}^m\sum_{j=1}^nc_{ij}x_{ij}$$

这就是运输问题，现在讲起表示成优化问题。

$\textbf{解：}$需要注意到变量$x_{ij}$上是有约束的。首先，每个工厂生产的量是一定的，因此

$$\sum_{j=1}^nx_{ij}=q_i\quad for\ i=1,2,\ldots,m$$

其次，零售商收到的总量也是一定的

$$\sum_{i=1}^mx_{ij}=b_j\quad for\ j=1,2,\ldots,n$$

另外，$x_ij$是非负的，所以

$$x_{ij}>0\quad for\ i=1,2,\ldots,m\quad and\quad j=1,2,\ldots,n$$

如果令

$$\begin{align*} &\textbf{c}=[c_{11}\ \cdots c_{1n}\ c_{21}\ \cdots c_{2n}\ \cdots c_{m1}\ \cdots\ c_{mn}]^T\\ &\textbf{x}=[x_{11}\ \cdots x_{1n}\ x_{21}\ \cdots x_{2n}\ \cdots x_{m1}\ \cdots\ x_{mn}]^T\\ &\textbf{b}=[q_1\ \cdots\ q_m\ b_1\ \cdots\ b_n]^T \end{align*}$$

那么最小化问题可以写成
$$\begin{align*} minimize\ C=\textbf{c}^T\textbf{x}\\ subject to:\ \textbf{Ax=b}\\ \textbf{x}\geq\textbf{0} \end{align*}$$

其中$\textbf{c}^T\textbf{x}$是$\textbf{c,x}$的内积，因为目标函数与约束均是线性的，所有该问题称为线性规划(LP)问题。

这篇关于漫步最优化四——约束的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---