0
$\begingroup$

I have a quadratic optimization problem with inequality and equality constraints. In problem formulation, the one constraint that is giving me difficulties is a an equality constraint with a max function. I've simplified my problem as to just focus on this one constraint. For now, assume other linear constraints exist and the objective function has both quadratic and linear coefficients that are perfectly convex on their own. I've also elaborated for other people's sake.

My objective is to achieve the form

$$ \min_{x} \qquad (1/2)x^THx+c^T x \\ \mathrm{s.t.} \quad g_i(x) \leq 0 \\ \qquad h_j(x)=0 \\ $$

Note that function g(x) must be convex and h(x) must be affine. The goal is to make both h(x) and g(x) affine so that I can use a general QP solver without introducing integer variables.

My problematic equality constraint is in the form

$$ a = Max(b,c) \\ $$

where a,b are decision variables, and c is a constant. We can assume that a will always be a>0 as c will be chosen c>0. I've attempted to linearize the max function.

If we assume c=0, we can reformulate the constraint with the following

$$ a = (1/2)b+(1/2)|b| \\ $$

Playing around with a way to introduce c, I achieved

$$ a = (1/2)b+(1/2)|b-c|+(1/2)c \\ $$

Which seems to work for all cases. The problematic term in this equality is (1/2)|b-c|. We can introduce a new variable, t, via epigraph trick, that equals |b-c|.

$$ a = (1/2)b+(1/2)t+(1/2)c \\ t=|b-c| $$

I believe I can do the following by putting a penalty on t in the objective.

$$ a = (1/2)b+(1/2)t+(1/2)c \\ t \geq |b-c| $$

Equivalent to

$$ a = (1/2)b+(1/2)t+(1/2)c \\ t \geq b-c \\ t \geq -b+c $$

I'm afraid that putting it as formulated in the objective will affect the optimum. Will the optimum possibly be affected? How should I go about choosing the penalty for t if this is ok? Have I made any mistakes? Is there a better way to go about doing this? Thanks! :)

Edit: I'm thinking I may need to suck it up and reformulate my problem as a MIQP. I don't imediatly see how to start that however.

$\endgroup$
2
  • $\begingroup$ Instead of introducing $t$, you can directly replace $x_1=\max(x_2,0)$ with $x_1 \geq x_2$, $x_1 \geq 0$. If this is not equivalent, your original problem is not convex, and a QP solver will not be able to solve it. $\endgroup$ Commented Apr 19, 2018 at 12:07
  • $\begingroup$ Those inequalities are true for the most part, 0 is not the lower bound, but that bound is still a constant. However, the way my objective is set up (not represented here), setting the problem up in that way will push x1 (as represented in your example) to +inf. x1 and x2 are part of a time series. This is why I tried bounding the function by adding a t. $\endgroup$ Commented Apr 19, 2018 at 15:18

1 Answer 1

Reset to default
3
$\begingroup$

Unless you have that the equality holds at optimality even though you relax the equality to $\max(b,c) \leq a$, you have to, as you say, suck it up and go for a MILP representation.

The representation you are looking for is a disjunction of the two cases $a = b, b\geq c$ and $a = c, c \geq b$. A simple big-M model for that would be to introduce two binaries $\delta_1$ and $\delta_2$ and

$$-M(1-\delta_1) \leq a-b \leq M(1-\delta_1), c\leq b + M(1-\delta_1),\\ -M(1-\delta_2) \leq a-c \leq M(1-\delta_2), b\leq c + M(1-\delta_2), \\\delta_1+\delta_2 =1$$

with carefully selected as-small-as-possible constants $M$ (different on all the constraints)

$\endgroup$
2
  • $\begingroup$ "Unless you have that the equality holds at optimality..." Does this phrase somehow suggest that a non-MIQP/LP is still possible? Because this is the desired goal. If however, you mean that this happens by accident on not specifically designed, then nevermind. $\endgroup$ Commented Apr 19, 2018 at 15:15
  • 1
    $\begingroup$ Yes, if the equality holds at optimality, then you effectively solved the equality constrined problem even if you just used the inequality version $a\geq b, a\geq c$. That depends on the model of course. Maximize performance of car subject to cost equal to 100000 dollars would typically have the same solution as Maximize performance of car subject to less than to 100000 dollars, since you always would use the full budget. $\endgroup$ Commented Apr 19, 2018 at 16:40

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.