目标函数f0和不等式约束条件fi必须都是convex function,等式约束条件hi必须是affinie function
满足上述条件才是凸函数.

上述问题的最优解定义为p∗=inf{ f0 | fi(x)≤0,i=1,...,m,hi(x)=0,i=1,...,p}
其中inf表示集合的最小值，而min则是函数，是一个求解运算过程.

如果问题不可行，即x不满足x∈D且fi≤0,和hi(x)=0，那么p∗=≁(空集的下确界为≁), 如果存在可行解xk满足：当xk→≁时,f0(xk)→−≁，那么p∗=−≁,并且称问题无下界
注意，凸优化问题的定义域实际上是一个凸集:

这个凸集由目标函数定义域(凸集)、m个(凸的)下水平集{x|fi(x)≤0}和p个超平面{hi(x)=0}的交集构成. 我们是在一个凸集上极小化一个凸的目标函数.

2. 等价问题

2.1 变量变换与消除等式约束

$x为原始参数变量，z为变换后参数变量，即x=\psi(z) \\ 如果x为原始问题的最优解，那么z = \psi^{-1}(x)为变换后问题的最优解 \\ 如果求解了变换后问题，得到z，那么x=\psi(x)为原始问题的最优解.$

2.2 优化部分变量

infx,yf(x,y)=infxg(x)其中g(x)=infyf(x,y). 优化部分变量对两部分变量分步优化，首先先优化一部分变量，然后再优化另一部分变量. 先后别对两部分变量优化等价于优化整个函数.

例4.4 在约束条件下优化二次函数的部分变量里提到的Schur Complement Lemma可以参见这里, 这里的证明部分也挺有意思的.

2.3 Parameter and oracle problem descriptions

analytical/closed form solution: given by a formula or expression that involves the variables x as well as some parameters.
oracle models/black box/subroutine models:in oracle model, we never really know the function; we only know the function value (and some derivatives) at the points where we have quried the oracle. (We also know some given prior information about the function, such as differentiability and convexity.)

3. 可微函数f0的最优性准则

3.1 标准凸优化问题

3.2 无约束问题

即 m = 0, p = 0.

3.3 只含等式的约束问题

即m = 0.

4. 凸优化问题的划归转化

• 消除等式约束
• 引入等式约束
• 松弛变量

• 上镜图问题

  minimize tsubject tof0(x)−t≤0fi(x)≤0,i=1,...,mhi(x)=0,i=1,...,p

  转换成上镜图形式之后, 目标函数是线性的,并且引入的新变量f0(x)−t是(x,t)上的凸函数，因此上镜图形式的问题也是凸问题.
  任何凸优化问题都可以很容易地通过上述方式转换为具有线性目标函数的问题，因此称线性目标函数对凸优化问题是普适的.

• 极小化部分变量
  与优化部分变量得到的等价问题一致的原理.

  5. 拟凸优化问题的求解

  拟凸优化问题的标准形式是:

  minimize f0(x)subject tofi(x)≤0,i=1,...,mhi(x)=0,i=1,...,p

  其中目标函数f0(x)是拟凸的.
  通过一组具有0-下水平集的凸函数等价的表示凸目标函数:

  find xsubject toψt(x)≤0fi(x)≤0,i=1,...,mhi(x)=0,i=1,...,p

  ψt(x)是t的非递增函数, 是拟凸函数f的t-下水平集的凸函数的0-下水平集表示形式，即:

  f(x)≤<t⟺ψt(x)≤0

如果拟凸优化问题是可行的，总有p∗≤t, 反之，如果问题不可行，总有p∗≥t.
因此，可以通过如下二分法求解拟凸优化问题:

每次迭代得到一个上述凸可行问题的一个解. k次迭代之后区间的总长度为2−k(u−l). 算法复杂度为⌈log2(u−l)/ϵ⌉

4. 线性规划、二阶锥规划、几何规划以及半正定规划

• Linear Programs，线性规划

  minimize cTx+dsubject toGx⪯hAx=b

  其中目标函数和约束函数都是仿射函数.
  图形解释如下图:
  

• Quadratic Problems, 二次规划

  minimize (1/2)xTPx+qTx+rsubject toGx⪯hAx=b

  其中，P∈Sn+,G∈Rm×n and A∈Rp×n. 目标函数是凸二次型并且约束函数均是仿射函数.
  图形解释如下图:
  
  例子:多面体的Chebyshev 中心:

  maximize rsubject to aTixc+r∥ai∥2≤bi,i=1,...,m

  Section 4.3.1: Compute the Chebyshev center of a polyhedron

    % Boyd & Vandenberghe "Convex Optimization"
    % Joëlle Skaf - 08/16/05
    %
    % The goal is to find the largest Euclidean ball (i.e. its center and
    % radius) that lies in a polyhedron described by linear inequalites in this
    % fashion: P = {x : a_i'*x <= b_i, i=1,...,m}
  
    % Generate the data
    randn('state',0);
    n = 10; m = 2*n;
    A = randn(m,n);
    b = A*rand(n,1) + 2*rand(m,1);
    norm_ai = sum(A.^2,2).^(.5);
  
    % Build and execute model
    fprintf(1,'Computing Chebyshev center...');
    cvx_begin
        variable r(1)
        variable x_c(n)
        dual variable y
        maximize ( r )
        y: A*x_c + r*norm_ai <= b;
    cvx_end
    fprintf(1,'Done! \n');
  
    % Display results
    fprintf(1,'The Chebyshev center coordinates are: \n');
    disp(x_c);
    fprintf(1,'The radius of the largest Euclidean ball is: \n');
    disp(r);
  

• Second-order cone Programming, 二阶锥规划

  minimize fTxsubject to∥Ai+bi∥2≤cTix+di,i=1,...,mFx=g

  其中,x∈Rn为优化变量，Ai∈Rni×n且F∈Rp×n
  ∥Ai+bi∥2≤cTix+di,i=1,...,m 称为二次锥约束.
  即仿射函数(Ax+b,cTx+d)在Rk+1的二阶锥中.
  The second-order cone in Rk+1 is defined as

  Kk:={(x,y)∈Rk+1:∥x∥2≤y}

  This set is convex, since it is the intersection of (an infinite number of) half-spaces:

  Kk=⋂u:∥u∥2≤1{(x,y)∈Rk+1:xTu≤y}

  It is a cone, since it is invariant by scaling: if x∈Kp, so does ax for any a≥0.
  图形解释例子:
  

  The second-order cone in R3. The set actually extends to infinity upwards. For some strange reason, this set is called an "ice-cream cone".

  参考这里看图形解释:Standard Forms of SOCP 和 Second-Order Cone Programming

• Geometric Programming, 几何规划

  例子cantilever_beam_rec：
  % The problem can be posed as a geometric program (posynomial form)

  minimize∑Ni=1wi∗his.t.wmin≤wi<=wmax,i=1,...,Nhmin≤hi≤hmax,i=1,...,NSmin≤hi/wi≤Smax,i=1,...,N 6∗i∗F/(wi∗h2i)≤sigmamax,i=1,...,Ny1≤ymax

    % optimization variables
    N = 8;
  
    % constants
    wmin = .1; wmax = 100;
    hmin = .1; hmax = 6;
    Smin = 1/5; Smax = 5;
    sigma_max = 1;
    ymax = 10;
    E = 1; F = 1;
  
    cvx_begin gp
      % optimization variables
      variables w(N) h(N)
  
      % setting up variables relations
      % (recursive formulation)
      v = cvx( zeros(N+1,1) );
      y = cvx( zeros(N+1,1) );
      for i = N:-1:1
        fprintf(1,'Building recursive relations for index: %d\n',i);
        v(i) = 12*(i-1/2)*F/(E*w(i)*h(i)^3) + v(i+1);
        y(i) = 6*(i-1/3)*F/(E*w(i)*h(i)^3)  + v(i+1) + y(i+1);
      end
  
      % objective is the total volume of the beam
      % obj = sum of (widths*heights*lengths) over each section
      % (recall that the length of each segment is set to be 1)
      minimize( w'*h )
      subject to
        % constraint set
        wmin <= w    <= wmax;
        hmin <= h    <= hmax;
        Smin <= h./w <= Smax;
        6*F*[1:N]'./(w.*(h.^2)) <= sigma_max;
        y(1) <= ymax;
    cvx_end
  

• Semidefinite Programming, 半正定规划

  例子Section 4.6.3: Find the fastest mixing Markov chain on a graph:

    % Boyd & Vandenberghe "Convex Optimization"
    % Joëlle Skaf - 09/26/05
    %
    % The 'fastest mixing Markov chain problem' is to find a transition
    % probability matrix P on a graph E that minimizes the mixing rate r, where
    % r = max{ lambda_2, -lambda_n } with lambda_1>=...>=lambda_n being the
    % eigenvalues of P.
  
    % Generate input data
    n = 5;
    E = [0 1 0 1 1; ...
         1 0 1 0 1; ...
         0 1 0 1 1; ...
         1 0 1 0 1; ...
         1 1 1 1 0];
  
    % Create and solve model
    cvx_begin
        variable P(n,n) symmetric
        minimize(norm(P - (1/n)*ones(n)))
        P*ones(n,1) == ones(n,1);
        P >= 0;
        P(E==0) == 0;
    cvx_end
    e = flipud(eig(P));
    r = max(e(2), -e(n));
  
    % Display results
    disp('------------------------------------------------------------------------');
    disp('The transition probability matrix of the optimal Markov chain is: ');
    disp(P);
    disp('The optimal mixing rate is: ');
    disp(r);
  

5. Exercise

CVX Example library

参考文献:

1. Convex Optimization by Stephen Boyd and Lieven Vandenberghe
2. Convex Optimization Edx
3. Schur Complement Lemma
4. Standard Forms of SOCP
5. Second-Order Cone Programming
6. convex optimization 这里很多列出了很多凸优化的书籍
7. Introduction to Semidefinite Programming
8. SEMIDEFINITE PROGRAMMING by tephen Boyd and Lieven Vandenberghe, 1996.
9. CS 8292: Advanced Topics in Convex Optimization and its Applications