知识点：线性和非线性规划
知识点概述
根据目标函数和约束函数是否为线性，优化问题分为线性规划（LP）和非线性规划（NLP）。线性规划具有优良的性质和高效的专用算法，是运筹学的基础。
教材原文
线性规划是指问题 (1.1.1) 中目标函数和约束函数都是线性的。当目标函数和约束函数至少有一个是非线性的，那么对应的优化问题的称为非线性规划问题。线性规划问题的研究很早便得到了人们的关注。… 求解线性规划问题最流行的两类方法依然是单纯形法和内点法。
详细解释
- 线性规划 (Linear Programming, LP):
- 形式: 目标函数是线性的（如 ），约束是线性等式或不等式（如 , ）。
- 特点: 可行域是一个多面体。如果存在最优解，则一定可以在多面体的某个顶点上取到。有非常成熟和高效的算法，如单纯形法和内点法。
- 非线性规划 (Nonlinear Programming, NLP):
- 形式: 目标函数或至少一个约束函数是非线性的。
- 特点: 性质非常多样化，求解难度远高于线性规划。包括了凸优化和更广泛的非凸优化问题。其求解算法通常是迭代式的，且不一定能保证找到全局最优解（除非问题是凸的）。
学习要点
- 能够识别一个优化问题是线性规划还是非线性规划。
- 理解线性规划可行域（多面体）和最优解（顶点）的几何特性。
- 知道单纯形法和内点法是求解LP的主要方法。
- 认识到非线性规划的复杂性和多样性。
实践应用
- 线性规划: 生产计划、资源调配、网络流问题、运输问题。
- 非线性规划: 几乎所有现代工程设计、机器学习模型训练（如逻辑回归、神经网络）、经济学模型。
关联知识点
- 前置知识: 2-核心概念-最优化问题的分类
- 后续知识: 42-核心概念-线性规划, 10-核心概念-凸和非凸优化, 66-理论方法-线性规划内点法
- 相关知识: 6-核心概念-连续和离散优化