Navigator

• Basic model
• • cvx code
  • yalmip code
• A simple QP with inequalities constraints
• • cvx code
  • yalmip code
• Reference

Basic model

LMIs and SDPs with one variable. The generalized eigenvalues of a matrix pair ( A , B ) (A, B) (A,B), where A , B ∈ S n A, B\in\mathcal{S}^n A,B∈Sn, are defined as the roots of the polynomial det ⁡ ( λ B − A ) \det(\lambda B-A) det(λB−A).
Suppose B B B is nonsingular, and that A A A and B B B can be simltaneously diagonalized by a congruence, i.e., there exists a nonsingular, and that A A A and B B B can simultaneously diagonalized by a congruence, i.e, there exists a nonsingular R ∈ R n × n R\in\mathbb{R}^{n\times n} R∈Rn×n such that
R T A R = d i a g ( a ) R T B R = d i a g ( b ) R^TAR=diag(a)\\ R^TBR=diag(b) RTAR=diag(a)RTBR=diag(b)
where a , b ∈ R n a, b\in\mathbb{R}^n a,b∈Rn.
Moreover, a sufficient condition for this to hold is that there exists t 1 , t 2 t_1, t_2 t1​,t2​ such that t 1 A + t 2 B ≻ 0 t_1A+t_2B\succ 0 t1​A+t2​B≻0.

Try to find the optimal t t t that would maximize c ∗ t c*t c∗t while A − t ∗ B A-t*B A−t∗B is still P.S.D, we could solve the following SDP:
min ⁡ c ∗ t s . t . t B ≺ A \min c*t\\ s.t.\quad tB\prec A minc∗ts.t.tB≺A

cvx code

%% generate input data
rng(1);
n = 4;
A = randn(n); A = 0.5*(A'+A);
B = randn(n); B = B'*B;
c = -1;

%% cvx
cvx_begin sdp
    variable t
    minimize c*t
    t*B<=A;
cvx_end

disp('the optimal t obtained is');
disp(t);

yalmip code

%% yalmip
t = sdpvar;
F = [t*B<=A];
obj = c*t;
optimize(F, obj);

disp('the optimal t obtained is');
disp(value(t));

A simple QP with inequalities constraints

Prove that x ∗ = ( 1 , 1 / 2 , − 1 ) x^*=(1, 1/2, -1) x∗=(1,1/2,−1) is optimal for the optimization problem
min ⁡ ( 1 / 2 ) x T P x + q T x + r s . t . − 1 ≤ x i ≤ 1 , i = 1 , 2 , 3 \min (1/2)x^TPx+q^Tx+r\\ s.t.\quad -1\leq x_i\leq 1, i=1,2,3 min(1/2)xTPx+qTx+rs.t.−1≤xi​≤1,i=1,2,3
where
P = [ 13 12 − 2 12 17 6 − 2 6 12 ] q = [ − 22.0 − 14.5 13.0 ] r = 1 P=\left[ \begin{matrix} 13 & 12 & -2\\ 12 & 17 & 6\\ -2 & 6 & 12 \end{matrix} \right]\quad q=\left[ \begin{matrix} -22.0\\ -14.5\\ 13.0 \end{matrix} \right]\quad r=1 P=⎣⎡​1312−2​12176​−2612​⎦⎤​q=⎣⎡​−22.0−14.513.0​⎦⎤​r=1

cvx code

%% cvx: QP
cvx_begin
    variable x(n)
    minimize ((1/2)*quad_form(x, P)+q'*x+r);
    x>=-1;
    x<=1;
cvx_end

yalmip code

%% yalmip
x = sdpvar(n, 1);
F = [-1<=x<=1];
obj = (1/2)*x'*P*x+q'*x+r
optimize(F, obj);

Reference

Convex Optimiztion S.Boyd Page 203, 215