# Linearizing a quadratic constraint

I am working on a quadratic conic optimization problem, but I have discovered that it would be preferable if the quadratic constraint is linearly approximated. In other words, I need some way to make the quadratic beta variable linear. Is there any good way to do this? The only decision variable here is the beta, everything else is given as inputs to the problem.

• Are the $\delta_n$ parameters positive?
– prubin
Mar 28 at 15:41
• Yes, they are probabilities so in the range [0,1] Mar 28 at 17:42

We will need upper bounds $$B_n$$ for the $$\beta_n$$ variables. Introduce new variables $$z_n \ge 0$$ to act as surrogates for $$\delta_n \beta_n^2$$ and rewrite the quadratic constraint as $$\sum_n z_n \le A^2.$$ For each $$n$$, let $$f_n(\beta_n) = \delta_n \beta_n^2.$$ Pick breakpoints $$b_{n,0}=0 < b_{n,1} < \dots < b_{n, K_n} = B_n$$ for the domain of $$\beta_n$$ and compute linear secant functions $$f_{n,k}$$ $$(k=0,\dots, K_n - 1),$$ where $$f_{n,k}(\beta_n) = f_n(\beta_n)$$ for $$\beta_n = b_{n,k}$$ and $$\beta_n = b_{n, k+1}.$$ Finally, for each $$n$$ add the constraints $$z_n \ge f_{n,k}(\beta_n)$$ for all $$k.$$
Since $$f_n$$ is strictly convex, $$f_{n,k}(\beta_n) \ge f_n(\beta_n)$$ for $$\beta_n \in [b_{n,k}, b_{n, k+1}],$$ which ensures that $$z_n \ge f_n(\beta_n)$$ for any feasible $$\beta_n.$$ So the resulting LP is guaranteed to produce a solution feasible in the original problem ... but it might miss an optimal solution if the optimal value of any $$\beta_n$$ falls in the gap between $$f_n$$ and the relevant secant. One thing you might consider is solving the approximate LP and then refine the approximation near the optimal solution (add more interpolation points for each $$n$$ near the "optimal" value of $$\beta_n$$), then repeat.
If pictures would help, you might want to refer to this blog post. Figure 2 demonstrates what I am proposing (though only the positive part of the $$x$$ axis is relevant here, where the post's $$x$$ is your $$\beta_n$$). Figure 7 shows how a feasible (potentially optimal) point might be excluded by the approximation.