The optimization problem is shown below

$$ \min_{\boldsymbol{w}}\boldsymbol{w}^T\boldsymbol{Sw}\\ s.t. |\boldsymbol{w}^T\boldsymbol{a}_i|>1, i=1,2,\cdots, n $$ , where $\boldsymbol{w}, \boldsymbol{a}_i$ are vectors and $\boldsymbol{S}$ is a positive-definite matrix.

The objective function is convex, but the feasible region defined by constraints is non-convex. Would any one provide some methods or insights in solving this optimization problem? Thanks.


All $\boldsymbol{a}_i$s are known. Also $\boldsymbol{S}_w$ is available.

I tried to convert the absolute inequality constraint $|\boldsymbol{w}^T\boldsymbol{a}_i|>1$ to two constraints as follows:

$\boldsymbol{w}^T\boldsymbol{a}_i>1$ and $\boldsymbol{w}^T\boldsymbol{a}_i<-1$.

Unfortunately, we could not use these two constraints simultaneously, because these two constraints contradict to each other. We can only pick one of them. In this case, we need to pick one constraint from each absolute constraint, either $\boldsymbol{w}^T\boldsymbol{a}_i>1$ or $\boldsymbol{w}^T\boldsymbol{a}_i<-1$. This is a combination problem, where there are $2^n$ cases, which is not practical.

  • 3
    $\begingroup$ To get access to a greater pool of experts on optimization, consider posting this on some other site (one where optimization is more central a topic) of the Stack Exchange network instead. $\endgroup$ Commented Dec 17, 2021 at 12:01
  • 2
    $\begingroup$ Hi: Assuming the $a_i$ are known, you can convert that to $w^{T} a_{i} > 1$ and $w^{T} a_{i} < -1$ $\endgroup$
    – mark leeds
    Commented Dec 17, 2021 at 13:18
  • $\begingroup$ @markleeds Depending on how $a_{i}$ is set, that might lead to discontinuities. Would that be an issue? The typical way that I have handled absolute value constraints is by adding in supplemental variables $w_{+}$ and $w_{-}$ with the property that if you subtract them you get $w$ and are both greater than zero individually. The only thing to be aware of is when $w_{+,i}$ and $w_{-,i}$ are both larger than zero. Adjusting the way the optimization is set up can help reduce the likelihood that happens. $\endgroup$
    – John
    Commented Dec 17, 2021 at 18:29
  • $\begingroup$ @John: It's been a loooong time, as in multiple decades, since I took a class in optimization. You could be right but I'm not familiar with discontinuities in constraints causing a problem. Or it's possible that I just don't remember !!!! Also, maybe your idea of using $w_{-}$ and $w_{+}$ can help but, if I was andy, I would try seperating the constraint into the two constraints and then see if the result respects the constraints. Apologies for not being able to reply with a more useful response. $\endgroup$
    – mark leeds
    Commented Dec 18, 2021 at 3:47
  • $\begingroup$ @RichardHardy thanks for your advice. Is there website that recommend? Thanks again. $\endgroup$
    – Andy
    Commented Dec 18, 2021 at 6:00


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.