Need help in formulating a optimization problem

(Bodhibrata Mukhopadhyay) #1

I need to find a point (any point will do) located inside a convex set Z. Z is the intersection of N convex set that is defined by Z_i ().

Z_i ={x | ||x-a_i||^2 <= k_i}, i=1,…,N
x (belongs to R^2)
a_i (belongs to R^2) and k_i (belongs to R) are given.

I have formulated the following SDP to solve it. Is there any other way to solve the problem.

cvx_begin sdp
variable x(2,1)
subject to
for i=1:N
[k(i) (x-a(:,i))’;(x-a(:,i)) eye(2) ] >= 0
end
cvx_end

(Mark L. Stone) #2

This can be formulated as an SOCP. norm(x-a(:,i)) <= sqrt(k(i)) . But CVX will convert the SDP into an SOCP (but maybe with norrm squared), so it might be a little better to directly enter it as an SOCP.

(Bodhibrata Mukhopadhyay) #3

Thank you. I have tried using SOCP format. However, SDP format takes less time to execute than the SOCP format. Other than SDP/SOCP can it be solved by any other technique that is fast enough?