Topic
  • 1 reply
  • Latest Post - ‏2018-12-09T01:24:31Z by EdKlotz
Mahzad
Mahzad
12 Posts

Pinned topic Projection of a vector on a convex set using CPLEX

‏2018-12-08T23:36:24Z | convex cplex projection set

I want to find the projection of a vector called "a" on a closed and convex set with linear constraints. The set is in the following form:

 

Ax=b

Bx<=d

x>=0

I know I need to solve the following problem to get the projection:

minimize ||x-a||^2

Ax=b

Bx<=d

x>=0

However, it takes a long time when I optimize it using CPLEX since it is a large scale problem with millions of variables and I need to optimize it thousands of times for convergence. I was wondering if there is an efficient way to solve this problem using CPLEX. 

Thanks for your time and help.

  • EdKlotz
    EdKlotz
    393 Posts

    Re: Projection of a vector on a convex set using CPLEX

    ‏2018-12-09T01:24:31Z  

    Well, if A or B have some special structure, you could try CPLEX;s automated Benders decomposition feature if you were willing to replace the quadratic two norm objective with the corresponding one norm objective involving the sum of absolute values of xi - ai.  As all your variables are continuous, you would need to annotate the variables to communicate the separation between master and subproblem.

     

    But before looking into that,

    • Have you tried the both simplex algorithms and the barrier algorithm on the model?   If so, and you want further assistance, upload these logs to these thread; maybe that will shed light on a bottleneck that can be removed.
    • Replacing the quadratic two norm with the linear one norm not only could enable you to easily use Benders, it might also speed up the performance solving the model directly.   You will remove the Q matrix from the linear systems the Barrier and simplex methods currently have to deal with in your QP formulation, so you might get faster results.  
    • Exactly how big is your model?    How many variables and constraints does it have?