常见最优化问题

semi-definite programming
x 是半正定矩阵，SDP 有两种对偶形式


QP
f(x) quadratic
约束为线性
MLPR by Bishop p335 discusses algorithms for QP.

QCQP

f(x) quadratic
约束为 quadratic 和线性

SOCP
f(x) = c^T x
约束为
||Ax+c||<=a^x + b


Norm approximation
minimize ||Ax-b||=||r||，和 residual 紧密相关
这是很广泛的一类
linear regression, 图像和信号处理中的 auto regression 都属于这一类
只要 residual r_i 可以表示为 a^T x - b_i
意即只要每个 residual 都是 x  的仿射函数，就为 norm approximation
若为 l2 norm, 则为 least-squares
l_\infty norm, 称为 chebyshev approximation
l1 norm, sum of absolute residuals
后两者可以转好为 LP

Q:
minimize ||Ax-b||_2 + r||x||_1
如何转好为 SOCP

conic programming

上图中，总结了 conic programming 的两种形式，standard form 和 inequities form
注意 LP, SOCP, SDP 都属于 conic programming, 因此也都有这两种形式


quasi-convex
quasi-convex 求解可以转化为一系列 convex problem 的 feasibility problem，并用两分法求解
一个非常重要的 quasi convex 函数是

f(x)=\frac{\parallel Ax+b \parallel}{c^T x+d}

l1 regularized least squares

可以转化为 QP