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.
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)