Balabala

我想读完Giuseppe C. Calafiore, Laurent El Ghaoui 版本的《Optimization Models》。

1. Introduction

作者列举了若干个例子，并阐述了优化问题的一般形式，最主要的洞见有：

• 一些具有特定性质的问题是 tractable 的：The focus of this book is on tractable models, and a key message is that models that can be formulated in the form of linear algebra problems, or in convex form, are typically tractable.
• 通过一些巧妙的设计可以使问题 tractable：A problem that may seem hard under a certain formulation may well become tractable if we put some more effort and intelligence in the modeling phase.
• 即使是难以进行巧妙的设计的问题，也可能通过近似的方法解决：However, even for intrinsically hard problems, for which exact solutions may be unaffordable, we may often find useful tractable models that provide us with readily computable approximate, or relaxed, solutions.

典型的优化问题分类

• Least squares and linear equations：

  \[\min _x \sum_{i=1}^m\left(\sum_{j=1}^n A_{i j} x_j-b_i\right)^2 \]

  最小二乘的典型应用是求解一组线性方程 \(\sum_{j=1}^n A_{i j} x_j=b_i, \quad i=1, \ldots, m\)

• Low-rank approximations and maximum variance：

  Low-rank approximations：

  \[\min _{x \in \mathbb{R}^n, z \in \mathbb{R}^m} \sum_{i=1}^m\left(\sum_{j=1}^n A_{i j}-z_i x_j\right)^2 \]

  低秩近似的基本思想为用 \(z_ix_j\) 近似 \(A_{ij}\).

  相关的 maximum-variance 为：

  \[\max _x \sum_{i=1}^m\left(\sum_{j=1}^n A_{i j} x_j\right)^2 \text { s.t.: } \sum_{i=1}^n x_i^2=1 . \]

  maximum-variance 问题可用于在高维空间中拟合一条直线。这一点应该跟最小二乘相似，只是这里不计较\(b_i\)，只得到”斜率“即可。

• Linear and quadratic programming

  Linear programming (LP) problem：

  \[\min _x \sum_{j=1}^n c_j x_j \text { s.t.: } \sum_{j=1}^n A_{i j} x_j \leq b_i, \quad i=1, \ldots, m, \]

  Quadratic programming problems：

  \[\min _x \sum_{i=1}^r\left(\sum_{j=1}^n C_{i j} x_j\right)^2+\sum_{j=1}^n c_j x_j \text { s.t.: } \sum_{j=1}^n A_{i j} x_j \leq b_i, i=1, \ldots, m, \]

• Convex optimization

  • Convex optimization problems are problems of the form (1.2), where the objective and constraint functions have the special property of convexity.
  • One key feature of convex problems is that all local minima are actually global.

  容易求解的一类问题。

• Combinatorial optimization

  并没有给明确定义。大致意思是说，整数规划很难，整数与连续变量混合的问题（mixed integer programs ）很难。

• Non-convex optimization

  由于可能存在局部最优点等问题，较难解决。但对于一些特定问题，例如 Low-rank approximations and maximum variance，已有可靠的来自于线性代数的算法。

历史

线性代数起源于古代中国 -> 高斯对线性代数的探索 -> 优化思想在物理中的应用 ->...

比较有意思的故事：

In the Soviet Union at that time, the focus was more towards optimization theory, perhaps due to more restricted access to computing resources. Since nonlinear problems are hard, Soviet researchers went back to the linear programming model, and asked the following (at that point theoretical) question: what makes linear programs easy? Is it really linearity of the objective and constraint functions, or some other, more general, structure? Are there classes of problems out there that are nonlinear but still easy to solve?

In the late 80s, two researchers in the former Soviet Union, Yurii Nesterov and Arkadi Nemirovski, discovered that a key property that makes an optimization problem "easy" is not linearity, but actually convexity.

​