Semidefinite Programming (SDP)#

Semi-definite#

Definition 26 (SDP)

  • minimize \(c^T x\)

  • s.t. \(x_1 F_1 + \cdots + x_n F_n + G \preceq 0\) with \(F_i, G \in S^k\)

  • inequality constraint is called linear matrix inequailty (LMI)

Example 24 (Minimize maximum eigenvalue)

minimize \(\lambda_{\max} (A(x))\) where \(A(x) = A_0 + x_1 A_1 + \cdots + x_n A_n\) (with given \(A_i \in S^k\))

\(\lambda_{\max} (A) = \max_{||y||\le 1} y^T A y\) where \(y\) is the eigenvector of \(A\) equivalent to

  • minimize t

equivalent to (SDP)

  • minimize

  • s.t. \(A(x) - t I \preceq 0\)

Vector optimization#

general vector optimization problem

  • minimize (w.r.t \(K\)) \(f_0(x)\)

  • s.t. \(f_i(x)\le 0\), \(h_i(x)=0\)

vector-valued objective function: \(f_0: R^n \to R^q\), minimized w.r.t proper cone \(K\in R^q\)

Convex vector optimization#

K-convexity for vector-valued functions \(....... \preceq_K ....\) entry-wise

Multicriterion optimization#

Or multi-objective optimization

vector optimization problem with \(K=R_+^q\), \(f_0(x) = (F_1(x), \dots, F_q(x))\)

  • \(q\) different objectives \(F_i\); roughly speaking we want all \(F_i\)’s to be small

Optimal and Pareto optimal points#

set of achievable objective values \(O=\{ f_0(x) \mid x feasible \}\)

  • feasible \(x^*\) is optimal if \(f_0(x^*)\) is a minimum value of \(O\) i.e., y feasible \(\implies \) \(f_0(x^*) \preceq_K f_0(y)\)

  • feasible \(x\) is Pareto optimal if \(f_0(x)\) is a minimal value of \(O\) i.e., y feasible, \(f_0(y) \preceq_K f_0(x)\) implies \(f_0(x) = f_0(y)\)

if there are multiple Pareto optimal values, there is a trade-off between the objectives

Example 25 (Risk return trade-off in portfolio optimization)

  • minimize (w.r.t \(R_+^2\)) \((-p^T x, x^T\Sigma x)\)

  • s.t. \(1^T x = 1, x \succeq 0\)

  • \(x\in R^n\) is investment portfolio; \(x_i\) is fraction invected in asset \(i\)

  • \(p\in R^n\) is vector of asset return, modeled as a random variable with mean \(\bar{p}\), covariance \(\Sigma\)

  • \(\bar{p}^T x = E(p^T x)\) is expected return; \(x^T \Sigma x = Var[p^T x ]\) is return variance

supporting hyperplane: \(\{ z \mid \lambda^T z = \lambda^T u \}\)

Scalarization#

to find Pareto optimal points: choose \(\lambda \succ_{K^*} 0\) and solve scalar problem

  • minimize \(\lambda^T f_0(x)\)

  • s.t. \(f_i(x) \le 0\), \(h_i(x) = 0\)

for convex vector optimization problems, can find (almost) all Pareto optimal points by varying \(\lambda\succ_{K^*} 0\)

Example 26 (Risk return trade-off )

  • minimize (w.r.t \(R_+^2\)) \((-p^T x+ \lambda x^T\Sigma x)\)

  • s.t. \(1^T x = 1, x \succeq 0\)

for fixed \(\gamma>0\), a quadratic program

multi objective