Optimization problem in standard form
\[\text{minimize }f_0(x)\]
\[\text{subject to }f_i(x)\leq0\quad{}\land{}\quad{}Ax=b\]
Theorem: Optimal and locally optimal options
Any locally optimal point of a convex problem is (globally) optimal. #### Proof Suppose \(x\) is locally optimal, but there exists a feasible \(y\) with \(f_0(y)<f_0(x)\), for \(z\) in the small neighbour of \(x\), contradiction must exist
Theorem
\(x\) is optimal if and only if it is feasible and
\[\nabla{}f_0(x)^T(y-x)\geq0\quad\text{for all feasible }y\]
Proof
\[f_0(y)\geq{}f_0(x)+\nabla{}f_0(x)^T(y-x)\geq{}f_0(x)\]
\[\text{Suppose }\exists{}y,~s.t.~\nabla{}f_0(x)^T(y-x)<0\]
\[g(t)=f(x+y(y-x)),g^{'}(0)=\nabla{}f_0(x)^T(y-x)<0\] \[\exists{}\bar{t},g(\bar{t})<g(0)=f_0(x)\]
Also, we can view this with Taylor expansion
Equivalent convex problems
Eliminating equality constrains
\[Ax=b\rightarrow{}x=Fz+x_0~\text{for some }z\]
Introducing equality constraints
\[y_i=A_ix+b\]
Introducing slack variables
\[a_i^Tx\leq{}b_i\rightarrow{}a_i^Tx+s_i=b_i\land{}s_i\geq0\]
Quasiconvex optimization
If \(f_0\) is quasiconvex, there exists a family of functions \(\phi_t\) such that:
- \(\phi_t(x)\) is convex in \(x\) for fixed \(t\)
- t-sublevel set of \(f_0\) is 0-sublevel set of \(\phi_t\), i.e. \[f_0(x)\leq{}t\leftrightarrow{}\phi_t(x)\leq0\]
Linear program (LP)
\[\text{minimize }c^Tx+d\] \[\text{subject to }Gx\leq{}h\land{}Ax=b\]
- convex problem with affine objective and constraint functions
- feasible set is a polyhedron
Linear fractional program
\[\text{minimize }f_0(x)\] \[\text{subject to }Gx\leq{}h\land{}Ax=b\] \[f_0(x)=\frac{c^Tx+d}{c^Tx+f}, dom~f_0(x)=\{c^Tx+f>0\}\]
- a quasiconvex optimization problem; can be solved by bisection
- also equivalent to the LP (variables \(y\), \(z\))
\[\text{minimize }c^Ty+dz\]
\[\text{subject to }Gy\leq{}hz,Ay=bz,e^Ty+fz=1,z\geq0\]
Proof
\[\forall{}x\in{}X_1,y=\frac{x}{e^Tx+f},z=\frac{1}{e^Tx+f}\rightarrow{}(y,z)\in{}X_2\rightarrow{}p_1^*\geq{}p_2^*\]
\[\forall{}(y,z)\in{}X_2, z\neq0,x=\frac{y}{z}\in{}X_1\]
\[\forall{}(y,z)\in{}X_2, z=0,\text{Choose }x_0\in{}X_1,x_0+ty\in{}X_1(t\geq0)\]
\[\lim_{t\rightarrow\infty}\frac{c^T(x_0+ty)+d}{e^T(x_0+ty)+f}=c^Ty,p_2^*\geq{}p_1^*\]
Quadratic program (QP)
\[A\in{}R^{m\times{}n},A=U\Sigma{}V^T,\Sigma=diag(\lambda_1,...,\lambda_r,0,...)\]
\[A^\dagger=V\Sigma^\dagger{}U^T,\Sigma^\dagger=diag(1/\lambda_1,...,1/\lambda_r,0,...)\]
Quadratically constrained quadratic program (QCQP)
\[\text{minimize }(1/2)x^TP_0x+q_0^Tx+r_0\] \[\text{subject to }(1/2)x^TP_ix+q_i^Tx+r_i\leq0, Ax=b\]
- \(P_i\in{}S_{+}^{n}\)
- objective and constraints are convex quadratic
Least squares
\[\text{minimize }||Ax-b||_2^2\]
- analytical solution \(x^\star=A^\dagger{}b\)
Robust linear program
\[\text{minimize }c^Tx\]
\[\text{subject to }prob(a_i^Tx\leq{}b_i)\geq\eta,i=1,...,m\]
Semidefinite program (SDP)
\[\text{minimize }c^Tx\]
\[\text{subject to }x_1F_1+x_2F_2+\dots+x_nF_n+G\preceq0,Ax=b\]
- inequality constraint is called linear matrix inequality (LMI)
- includes problems with multiple LMI constraints
