美文网首页
凸优化(三)部分集合变换与凸函数

凸优化(三)部分集合变换与凸函数

作者: SaySei | 来源:发表于2018-12-17 20:02 被阅读0次

1. 概述

\quad之前介绍了凸集相关的定义与部分性质,其实不是特别完全,因为单单的几篇博客是无法把凸集这一块完全讲全的,所以凸集变换这里也只讲几个稍微重要的变换。来捋一下学习的脉络吧,凸问题由求解变量、约束与目标函数组成,其中变量的可行域必须是凸集。所以下面要介绍的就是涉及到约束和目标函数的凸函数了。至于求解这个以后会说相关的经典算法的。

2. 集合变换:

(1)仿射变换:定义为对于凸集X,进行线性变换\{AX+b,X\in R^n,A\in R_{m\times n},b\in R^m\},得到的集合仍旧是凸集,可以看出集合X在维数变换后仍旧是凸集,通俗地来讲,对一个集合进行拉伸和位移不会改变凸性,比如说在上节已经提到的球进行拉伸成椭球,依旧是凸集。

(2)透视变换,假设有集合\{[Z,T],T\nleq0,Z\in R^n,T\in R\},则经过如下变换:\{[Z/T],T\nleq0,Z\in R^n,T\in R\}得到的集合仍为凸集。实际上是一种降维操作了,通俗地解释也可以做到,看一下这张图:

透视变换

假设在二维平面上过一点(x_1,x_2)做一条过原点的直线,显然直线方程为x_2x-x_1y=0,然后做一条y=-1的直线,它们会交于点K(-\frac{x_1}{x_2},-1)处。那么透视变换的含义是啥呢?就是将(x_1,x_2)经过原点映射到K(-\frac{x_1}{x_2},-1)点。实现了一次降维,这样得到的集合仍旧为凸集。

(3)线性分数函数:对于集合X为凸集,在经过以下变换之后,其结果仍为凸集:f(x)=\frac{AX+b}{c^TX+d},dom f=\{X|c^TX+d\nleq0\}说明一下,这里是非常常用的变换技巧,因为显然这个变换是个非线性变换,但是得到的集合却仍旧是凸集。用到了两个变换性质,第一就是仿射变换,仿射变换是对凸集进行线性变换后仍旧是凸集,即\{AX+b,X\in R^n,A\in R_{m\times n},b\in R^m\}。然后又进行了透视变换,即将一个R^{n+1}=[Z,T],T\nleq 0的凸集,它有一维数据大于0,然后对其Z的数据除以T,进行降维处理得到的仍旧是凸集。

举个例子:在本科的概率与统计课程中有这样的例子,两个随机变量u,v的联合概率\rightarrow条件概率的映射

联合概率:P_{ij}=P(u=i,v=j),条件概率:f_{ij}=P(u=i|v=j)=\frac{P_{ij}}{\sum^n_{k=1}P_{kj}},其实这个条件映射是一个线性分数映射,大家可以想想看哪个集合充当了X的集合,又是怎样的变换。这里给出解释:就是将[P_{1j},P_{2j},...,P_{nj}]^T向量作为X,分母作为向量的求和,分子则是与这样的向量作了内积:[0,...,1,...,0],只有i处为1的向量。

3. 凸函数

3.1 定义

如果X为在实数向量空间的凸集。并且有映射f:X\rightarrow R,如果f被称为,则有\forall x_1,x_2\in X,\forall t\in[0,1]: f(tx_1+(1-t)x_2)\leq tf(x_1)+(1-t)f(x_2).如果F被称为严格凸,那么有:\forall x_1\ne x_2\in X,\forall t\in(0,1): f(tx_1+(1-t)x_2)\ngeq tf(x_1)+(1-t)f(x_2).

3.2 保持凸性的操作

和之前介绍的集合变换有相通的地方,但是是对函数映射的操作。

(1)取负操作:当f为凸函数的时候,-f为凹函数。

(2)非负加权和:即存在参数向量w=[w_1,w_2,...,w_n]\geq0,f_1,f_2...f_n为凸的,那么w_1f_1+...w_nf_n也为凸函数,特殊的情况就是,有限个凸函数的和为凸函数。(也可以拓展到无限和,积分和期望值(存在的话))

(3)元素最大值:有\{f_i\}_{i\in I}是凸函数的集合。得到新函数g(x)=sup_{i\in I}f_i(x)仍旧为凸函数,这个性质挺重要的,有以下两个特殊情况:
(3.1)若f_1,f_2...f_n为凸函数,则g(x)=max\{f_1(x),f_2(x)...f_n(x)\}r仍为凸函数。
(3.2)若f(x,y)在以x为自变量时为凸函数,那么g(x)=sup_{y\in C}f_i(x)也以x为自变量为凸函数,即使C不是凸集。

(4)组合函数
(4.1)若f和g是凸函数并且g在单变量域上不见效,那么h(x)=g(f(x))也是凸函数。比如当g(x)=e^x时,f为凸函数,那么e^{f(x)}也是凸函数,因为e^x单调且为凸函数。
(4.2)经过仿射变换下(具体见2集合变换)的凸函数仍为凸函数。

(5)最小化:若f(x,y)x,y组成的定义域内为凸函数,那么g(x)=inf_{y\in C}f(x,y)在单变量x上为凸函数,但是要满足C是凸集,且g(x)\neq\infty

相关文章

  • 凸优化(三)部分集合变换与凸函数

    1. 概述 之前介绍了凸集相关的定义与部分性质,其实不是特别完全,因为单单的几篇博客是无法把凸集这一块完全讲全的,...

  • 凸优化&非凸优化

    凸优化指的是,如果得到了局部最优,那么这个局部最优就是全局最优。 讲凸优化就涉及到凸函数和凸集合集合C内任意两点间...

  • 凸优化笔记2-主要内容

    笔记主要内容 凸集、凸函数、凸优化 凸优化理论 若干算法

  • 一、简介

    定义1.1 凸函数和凸集简而言之,凸集满足的性质就是对于集合中的任意两点,他们连线上的点也都是集合中的点凸优化研究...

  • 通俗易懂地理解机器学习理论中的凸优化

    写在前头 凸优化问题(OPT,convex optimization problem)指定义在凸集中的凸函数最优化...

  • 凸优化(三)——凸函数

    〇、说明 凸优化主要学习《凸优化》(Stephen Boyd等著,王书宁等译)[1]这本书。学习过程中,对其内容的...

  • 机器学习(6)——凸优化理论(一)

    概述   凸优化,或叫做凸最优化,凸最小化,是数学最优化的一个子领域,研究定义于凸集中的凸函数最小化的问题。凸优化...

  • 关于凸优化的一些基本概率(2018京东算法岗)

    凸优化是很多机器学习算法的基础,绝大部分的优化算法都是适用在凸函数上的。18年的京东算法岗考的基本都是凸优化的基本...

  • Convex Optimization Note 1 | Int

    凸优化,或叫做凸最优化,凸最小化,是数学最优化的一个子领域,研究定义于凸集中的凸函数最小化的问题。凸优化在某种意义...

  • 深度学习笔记

    什么是凸集、凸函数、凸学习问题? 凸集:若对集合C中任意两点u和v,连接他们的线段仍在集合C中,那么集合C是凸集。...

网友评论

      本文标题:凸优化(三)部分集合变换与凸函数

      本文链接:https://www.haomeiwen.com/subject/dslfkqtx.html