Solving Quadratic Optimization with Absolute-Value Constraints

Summary

The document poses a quadratic minimization problem with a positive-definite matrix and constraints requiring each linear form in the decision vector to have magnitude greater than one. Although the objective is convex, the feasible set is non-convex because each absolute-value inequality allows either a positive or negative branch.

It explains that each constraint can be split into two alternative half-space conditions, but choosing a branch for every constraint creates an exponential number of combinations. The text frames this as the central computational challenge, but offers no solution method or numerical evidence. It is therefore useful mainly for recognizing the problem structure and the combinatorial cost of direct enumeration. Strict inequalities also mean the feasible region is open, which can matter for whether a minimum is attained; the document does not discuss this issue or propose relaxations, mixed-integer formulations, or specialized algorithms.

Key ideas

• The quadratic objective is convex when its matrix is positive definite.
• Each absolute-value constraint forms a disjunction between a positive and a negative linear inequality.
• Selecting one branch per constraint produces an exponential enumeration problem.
• The document raises the optimization challenge but does not provide a solution method.

Tags

# How to solve an optimization problem with absolute constraint?


# How to solve an optimization problem with absolute constraint?












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.

Shown in full with attribution under the source's licence. Licence: CC BY-SA 4.0 (Stack Exchange)

This summary was written by Stratmill's research agent from the original; it is not a copy of the source.