工作时间AM:09:00--PM:20:00

WORKINGTIME

/public/upload/system/2018/07/26/f743a52e720d8579f61650d7ca7a63a0.jpg免费咨询

/public/upload/system/2018/07/26/f743a52e720d8579f61650d7ca7a63a0.jpg
邮箱:
广东省广州市天河区88号
电话:
/public/upload/system/2018/07/26/f743a52e720d8579f61650d7ca7a63a0.jpg
传真:
/public/upload/system/2018/07/26/fe272790a21a4d3e1e670f37534a3a7d.png
手机:
13800000000
地址:
1234567890
盛煌APP下载
当前位置: 首页 > 盛煌APP下载
凸分析和凸优化有什么推荐的教材吗?  上传时间:2024-05-26 09:42:08

《凸分析》和《凸优化》啊。

R. T. Rockafellar. Convex Analysis. Princeton, 1970.

S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge, 2004.

少年,如今这个时代,单纯看书是不够的,请配合大牛的课程vedio一起学习!

(1)如楼上所说的,S. Boyd and L. Vandenberghe. 写的书 <Convex Optimization> 听说不错,我没看过... 然后S.Boyd 还给了配套的课程video可以一起学习 EE364a: Lecture Videos, 听说有新版本的video ,我没找到。

( 2 ) CMU 有个老师叫Ryan T 开了门Convex Optimization上过一些,感觉不错,我没看完,你可以试试,这里是链接:Convex Optimization

(3)Nesterov 的《Introductory Lectures on Convex Programming》推荐你看看前两章引入convex 概念的,写的挺好的。我写过一篇读这个文章的小笔记,你可以辅助着看:从Nesterov的角度看:我们为什么要研究凸优化? - 知乎专栏

(4)关于 Stochastic 的算法 我还推荐你看看 L Bottou 的 [1606.04838]Optimization Methods for Large-Scale Machine Learning 确实写的不错,我看了开头,写了点读书心得,可以对照着看看为什么我们更宠爱“随机”梯度下降?

(5)评论里 @各人 给出的意见感觉还蛮中肯的,故复录于下:入门凸优化的话看el ghaoui那本optimization models可能好点,毕竟从线代开始讲,而且很多proof和一些涉及到几何/分析的东西都被带过了。凸分析必须boyd了,虽然那本实际上还是require不少mathematical maturity的。boyd那本书我非常喜欢,一点废话都没有解释的特别清楚,书后习题也非常有意思,我自己是把lp/qp/duality那几章全部刷了一遍。


如果纯粹学习,看看(1)就够了,想做做research 那么(2)(3)(4)都看完了,也不够,哈哈哈哈哈!!!


最后,你如果热情不减,还想继续了解优化算法,欢迎关注 @未名我的专栏。。。我会写写自己学习凸\\非凸优化的心得,大家一起学习交流。

非凸优化学习之路 - 知乎专栏

第一篇文章是: 从Nesterov的角度看:我们为什么要研究凸优化? - 知乎专栏

第二篇文章是:非凸优化基石:Lipschitz Condition - 知乎专栏

第三篇文章是:当我们谈论收敛速度时,我们都在谈什么? - 知乎专栏


最最后,从大量知识的喜悦中脱离一下,点个赞呗。

泻药@王哲

一句话概括的话,凸分析主要研究凸集和凸函数的各种拓扑和分析性质,凸优化研究凸问题的最优性条件,设计求解算法并分析其迭代复杂度和计算复杂度。

好专著通常出自这两个领域的大师。记住这些凸分析和凸优化大师的名号:R. T. Rockafellar,Hiriart-Urruty,A Nemirovski ,Y. Nesterov, Yinyu Ye(叶荫宇)...更多的看 John von Neumann Theory Prize 历年获奖的大师名单。当然,也不能排除一些非top-class的数学家写作技巧很好,写的入门级教材图文结合,形象易懂(嗯,我这里指的主要是Y. Nesterov的论文很难读).....


入门级

S. Boyd and L. Vandenberghe. Convex Optimization[M]. Cambridge, 2004.

Güler O. Foundations of Optimization[M]. Springer New York, 2010.

Bahlak S, Gazalet J, Lefebvre J E, et al. Convex Optimization: Algorithms and Complexity[J]. Foundations & Trends? in Machine Learning, 2014, 8(3-4):231-357.


进阶版

A Nemirovski 个人主页上一系列的凸优化的slides

Ben-Tal A, Nemirovski A. Lectures on modern convex optimization[M]. SIAM, 2001.

Hiriart-Urruty J B, Lemaréchal C. Fundamentals of Convex Analysis[M]. Grundlehren Text Editions, 2004, 24(2):288-294.

R. T. Rockafellar. Convex Analysis[M]. Princeton, 1970.

Hiriart-Urruty J B, Lemaréchal C. Convex analysis and minimization algorithms[M]. Springer-Verlag, 1993.

Nesterov Y. Introductory Lectures on Convex Optimization[M]. Springer, 2014.


内点算法

Nesterov I E, Nemirovski? A S. Interior Point Polynomial Algorithms in Convex Programming[M]. SIAM, 1994.

Ye Y. Interior point algorithms: theory and analysis[M]. John Wiley & Sons, Inc. 1997.

Wright S J. Primal-dual interior-point methods[M]. SIAM, 1997.

Roos C, Terlaky T, Vial J P. Interior Point Methods for Linear Optimization[M]. Springer, 2006.


如果不读博士做理论研究,好像基本上也不需要凸分析了;学术圈子里认真待个两三年,主动去了解这个领域,这些大师的名字会反复出现在论文和参考文献里,读读他们的专著就很有必要了...当然还有很多大牛,他们只写论文,没空写专著的,这时候就应该好好读论文了...

①备受瞩目的Stephen Boyd的Convex Optimization

我个人认为,这本书作为凸优化的入门图书其实并不适合,主要原因有两点:
内容太多,中文版《凸优化》将近700页,对于初学者,学习主干内容就可以了,可能也就200多页,但是前提是需要有人教学。
算法内容有限,很多同学学习凸优化的目的可能更想学习算法部分,但该书主要讲解内点法,对于现在热门的次梯度法,近邻算子法等没有涉猎。
有更合适的入门书籍《Optimization Model》.

作者:jack0077555
链接:jianshu.com/p/282116480

②本学期凸优化slides及李东风老师的统计计算(最后一张,八十多面,超级精简且说人话)

满200的话拉您进2群,加我微信 jjnuxjp5x

链接: pan.baidu.com/s/1GVj1Q1 提取码: c5pv

若非要深入研究,资料真的很棒的

eg:

③见北大凸优化课程主页bicmr.pku.edu.cn/~wenzw

本课程整理自中国科学技术大学2011年课程《最优化理论》,

  • 主讲人:凌青老师

cse.sysu.edu.cn/content

  • 课程主要教材

Boyd S , Vandenberghe L . Convex Optimization. Cambridge University Press, 2004.

web.stanford.edu/~boyd/

  • 课程视频网上有很多,这里只放一个链接

bilibili.com/video/BV1J

中科大凸优化 知识点笔记
  • 本文内容对应视频lec25-28,本文对应4个知识点,分别为
    • 线性规划
    • 二次规划
    • 半定规划
    • 多目标优化
  • linear program:目标与约束均为线性

? \\min \\quad c^Tx+d ,\\quad c\\in \\mathbb{R}^n,d\\in \\mathbb{R}

? s.t. \\quad Gx\\leq h,G\\in  \\mathbb{R}^{m\	imes n}, h\\in  \\mathbb{R}^m

? Ax=b,A\\in \\mathbb{R}^{k\	imes n},b\\in \\mathbb{R}^k

  • 根据一阶最优条件线性规划的解在边界上
  • 线性规划的等价变换
    \\min \\quad c^Tx+d
    s.t. \\quad Gx+s=h
    ? Ax=b
    ? s\\geq 0
    上式中x可写为x=x^+-x^-,这里x^+,x^-都大于等于0
    等价形式为
    \\min \\quad c^Tx^+-c^Tx^-+d
    s.t.\\quad Gx^+-Gx^-+s=h
    ? Ax^+-Ax^-=b
    ? s\\geq0,x^+\\geq 0,x^-\\geq0
  • 线性规划问题可由matlab中linprog函数求解
  • 典型的线性规划问题有物流调度、食谱问题等。这里以食谱问题为例,
    例1,现要以最低的总价购买一批食物,要求总计食物中的m种营养元素分别不小于b_1,\\dots, b_m,有n种食物,第j种食物中第m种营养为a_{1j},\\dots,a_{mj },\\forall j=1,\\dots,n,每种食物价格为c_j
    • 写为优化问题的形式,设每种食物量分别为x_1,\\dots,x_n
      \\min \\quad \\sum_jc_jx_j
      s.t.\\quad \\sum_ja_{ij}x_j\\geq b_j,\\forall i

? x_j\\geq 0,\\forall j

? 例2,线性分数规划(linear fractional programming)

? \\min \\quad f_0(x)=\\frac{c^Tx+d}{e^Tx+f}dom\\quad f_0=\\{x|e^Tx+f>0\\}

? s.t. \\quad Gx\\leq h

? Ax=b

? 这个问题不是标准的凸问题,可通过如下转化变为线性规划问题,令y=\\frac{x}{e^Tx+f},z=\\frac{1}{e^Tx+f}

? \\min \\quad c^Ty+dz

? s.t. \\quad Gy-hz\\leq0,e^x+fz=1,Ay-bz=0,z\\geq0

  • (quadratic programming, QP)目标函数为二次函数,约束为放射约束
  • \\min \\quad \\frac{1}{2}x^TPx+q^Tx+rP\\in S^n_+

? s.t.\\quad Qx\\leq h,Ax=b

  • QP问题最优解不一定在约束的边上,如下图
  • 二次约束二次规划(Quadratic constraint quadratic programming, QCQP)
    \\min \\quad \\frac{1}{2}x^TPx+q^Tx+r,P\\in S^n_+
    s.t.\\quad \\frac{1}{2}x^TP_ix+q_i^Tx+r_i\\leq 0,P_i\\in S^n_+,\\forall i
    ? Ax=b
  • 例1,带噪声的测量系统b=Ax+e
    \\hat x=\\arg\\min\\limits_x \\|b-Ax\\|_2

=\\arg\\min\\limits_x \\|b-Ax\\|_2^2

? =\\arg\\min\\limits_x x^TA^TAx-2b^TAx+b^Tb

? 这是典型的无约束QP问题,解为x^*=(A^TA)^{-1}A^Tb

  • 例2,若x稀疏(L_1-Regularized least squares)
    \\hat x=\\arg\\min\\limits_x \\|b-Ax\\|_2^2+\\lambda_0 \\|x\\|_0
    ? =\\arg\\min\\limits_x \\|b-Ax\\|_2^2+\\lambda_0 \\|x\\|_1
  • 例3,(L_2-Regularized least squares)岭回归

? \\hat x=\\arg\\min\\limits_x \\|b-Ax\\|_2^2+\\lambda_0 \\|x\\|_2^2

? 以上等价于\\arg\\min\\limits_x \\|b-Ax\\|_2^2s.t.\\quad \\|x\\|^2\\leq \	heta,\	heta\\geq 0,这是一个QCQP问题

  • Semi-definite Programming, SDP 可写为
    \\min \\quad tr(CX)
    s.t. \\quad tr(A_iX)=b_i,i=1,\\dots,p
    ? x\\succeq0
    其中C,A\\in \\mathbb{S}^n
  • 特例:对角矩阵diag \\{x\\}
    \\min \\quad  (diag \\{x\\})^Tdiag \\{x\\}
    s.t. \\quad (diga\\{A_i\\})^Tdiag \\{x\\}=b_i,i=1,\\dots,p
    ? diag\\{x\\}\\geq 0
  • 仅有不等式约束的半定规划问题
    \\min \\quad c^Tx
    s.t. \\quad x_1A_1+\\dots,+x_n A_n\\preceq B
    其中B,A\\in \\mathbb{S}^k
  • 例,求最小化矩阵A(x)=A+x_1A_1+\\dots+x_nA_n,A_i\\in \\mathbb{R}^{p\	imes q}最大奇异值对应的x

\\min \\|A(x)\\|_2

\\|A(x)\\|_2 \\leq \\sqrt s,s>0等价于A^T(x)A(x)-sI\\preceq 0

以上问题可转化为

\\min \\sqrt s

s.t. A^T(x)A(x)-sI\\preceq 0

t^2=s,则以上问题可转化为

\\min t

s.t. | tI \\quad A(x)|

? \\succeq 0

? | A^T(x) \\quad tI|

? t\\geq 0

  • \\min \\quad f_0 (x) 其中f_0:\\mathbb{R}^n\\rightarrow \\mathbb{R}^q
    s.t. \\quad f_i(x)\\leq 0
    ? h_i(x)=0
  • 例如,投资要在总成本限制下,最小化风险,最大化收益;发展要在一定资源限制下,最大化发展速度与发展质量。
  • 此时有多个目标,通常在某个指标上变好,就会在另外一个指标上变差,权衡不同目标,得出最优解的集合称为帕累托曲面(Pareto front)
  • 例,可将某些约束放在目标函数上,这种方法称为罚函数。以岭回归为例
    \\min \\|b-Ax\\|_2^2\\min \\|x\\|_2^2
    \\min \\|b-Ax\\|_2^2+\\lambda \\|x\\|_2^2

? 遍历不同的超参数\\lambda即可得到Pareto曲面

推荐阅读

华年ss:中科大凸优化1-4

华年ss:中科大凸优化5-8

华年ss:中科大凸优化9-12:凸函数

华年ss:中科大凸优化13-16

华年ss:中科大凸优化17-20

华年ss:中科大凸优化21-24:凸优化问题

平台注册入口