课程介绍

EE364a 课程主页：提供了教材和 slides、往年试卷等资料

Convex Optimization edX 课程页面：可以跳转 YouTube 用双语字幕插件学习，同时提供了课程讨论区

CVXPY：一个基于 Python 的凸优化库

Lecture 1 Introduction

Mathematical optimization 最优化

优化问题：在一些约束的情况下，最小化一个目标函数 记法：$f_0(x) → min\ s.t.; f_i(x) \le b_i$ 把 min 和 s.t. 当做 attribute 属性名而不是单词

$x$：优化变量/决策变量 $f_0$：目标函数 决策如何 irritate 刺激 $f_i$：约束 另一种 interpretation 就是资源 $b_i$就是 budget

举三个例子：

  1. 投资 约束：预算、最大最小份额 目标：风险或者回报
  2. 电路设计 约束：制造工艺、频率、空间 目标：最小功率
  3. 机器学习 约束：先验知识、参数之间的耦合 目标：优秀的模型

一般的最优化问题，不是导数为零那么简单，方法都有些妥协（时间复杂度、不是总能找到解） 例外：一些经典问题，如最小二乘、线性规划、凸优化

Quiz The symbol x* usually denotes a solution

Least-squares and linear programming 最小二乘和线性规划

最小二乘也叫 regression 回归 时间复杂度和$n^2k$成正比，$k$可以是案例数量、数据数量，$n$可以是特征、回归量 一个成熟的算法，200 年了

线性规划没有解析表达式 复杂度和最小二乘很类似，变量数平方乘以不等式数 很多看起来不像的问题可以转换成线性规划问题

Quiz Least squares is a special case of convex optimization. - True

Convex optimization 凸优化

目标函数和约束函数是凸的, classical language：The cord lies above the graph. 最小二乘和线性规划是凸优化的特例 判断是否凸函数很困难 有一些技巧能将其他函数转换成凸函数

Quiz By and large, convex optimization problems can be solved efficiently. - True Almost any problem you’d like to solve in practice is convex. - False Convex optimization problems are attractive because they always have a unique solution. - False (They do not always have a unique solution, and even when they do, this is not of primary importance.)

Example 例子

优化一个平面上的光照均匀度 Example 最小二乘：可能出现超出约束的解 负功率 加权最小二乘：目标函数加上约束 近似解 线性规划：近似解 可以证明凸函数，上完课之后就很好解了

这个问题加上一些约束之后可能变得非凸，完全不一样了

Course goals and topics 课程目标和主题

前三周会比较无聊，by week six, my claim is you’ll have been paid back for what happened to you during the first three weeks.

Nonlinear optimization 非线性优化

缩写也是 NLP，by the way, that’s the kind of, very much the western view of the world. All the stuff was developed in the US… 局部最优化方法：需要一个初始点；很快，能解决很多问题；不知道是不是全局最优 全局最优化方法：时间复杂度高 都是基于凸优化

Quiz Local optimization can be quite useful in some contexts, and therefore is widely used. Local optimization can’t guarantee finding a (global) solution.

Brief history of convex optimization 凸优化的简史

单纯形算法、内点 1990 开始在各种工程领域应用

Quiz Convex optimization has become popular:   because the mathematics is elegant.   due to development of effective solution algorithms and powerful computers to run them.

Congratulations! You just completed the first section of your course.