CODEWITHSUNDEEP
pythonmatlabmathematical-optimizationcvxpynon-convex
anirudhc1229
anirudhc1229

Reputation: 65

Solving optimization with norm constraints (non-convex QCQP)

Given a set of points in 3D space S and a set of vectors V where each point s_i can translate along vector v_i, I want to find the minimum total displacement of the points required to guarantee that no two points are within a distance r of each other. Denote the new locations of the points as X.

I'm very new to optimization, but this is my attempt to formulate this problem in Python using cvxpy:

def optimize(S, V):

    # new coordinates of each point
    X = cp.Variable(S.shape)

    # objective function: minimize total displacement of all points
    obj = cp.Minimize(sum(cp.norm(x_i - s_i) for x_i, s_i in zip(X, S)))

    constraints = []

    # constraint 1: all pairs of points must have distance of at least r between them
    constraints += [cp.norm(x_i - x_j) >= r for i, x_i in enumerate(X) for x_j in X[i+1:]]

    # constraint 2: magnitude of translation of a point is at most the magnitude of its vector
    constraints += [cp.norm(x_i - s_i) <= cp.norm(v_i) for x_i, s_i, v_i in zip(X, S, V)]
 
    # constraint 3: direction of translation of a point is same as direction of its vector
    constraints += [v_i.T @ (x_i - s_i) == 1 for x_i, s_i, v_i in zip(X, S, V)]

    prob = cp.Problem(obj, constraints)
    prob.solve()

    return X

Constraint 1 causes a DCP error:

cvxpy.error.DCPError: Problem does not follow DCP rules.

Is this an issue with the problem itself or am I just formulating it incorrectly? Can the problem be reformulated as a convex QCQP, or as some other form (e.g. NLP, SOCP)? If necessary, I can switch to a different solver in either Python or Matlab. Any advice would be appreciated.

Also, I tried using the QCQP package for cvxpy (https://github.com/cvxgrp/qcqp), but it's only compatible with cvxpy 0.4, which has a bunch of other deprecated dependencies.

Upvotes: 0

Views: 569

Answers (0)

Related Questions