1
$\begingroup$

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.

enter image description here

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

1 Answer 1

0
$\begingroup$

Linearization comes with one of two trade-offs, depending on how you do it: maintaining feasibility but perhaps accepting a slightly (?) suboptimal solution; or maintaining optimality (perhaps superoptimality) while perhaps accepting a slightly (?) infeasible solution. I'll assume you prefer the former.

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.

$\endgroup$
1

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.