1
$\begingroup$

I have a quadratically constrained quadratic programming/optimization problem involving kind-of piece-wise quadratic functions $f_n (x_m)=a_{n,m} (x_m-\theta_n)^2$, if $|x_m-\theta_n|<c$; $c^2a_{n.m}$, elsewhere. $a_{n,m}>0$, $x_m$ are the variables.

The objective is to minimize $\sum_m (g_m)$, with respect to $x_m$, subject to $g_m=\sum_n (f_n(x_m)) <= r_m, m=1,..., M, n=1,...,N$. $M=N$ for simplicity.

If $f_n(x_m)$ is just a quadratic function, this problem can be solved straightforwardly. However when it is piece-wise, I am not sure how to solve this.

Anyone that can help to provide a hint will be very appreciated.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ The objective function may not be a strict convex function, when $|\theta_n-\theta_m|>c$. This makes the problem very challenging. $\endgroup$
    – Doodle
    Commented May 17, 2016 at 11:50

1 Answer 1

Reset to default
1
$\begingroup$

I would formulate the problem as follow (please check subscripts...)

$$ \begin{align} &\min \sum_m z_m \\ &s.t. \\ & z_m \geq \sum_n a_{m,n} y^2_{m,n} & m=1,\ldots,M\\ & y_{m,n} \geq 0 & i=1,\ldots,m; j=1,\ldots,N\\ & y_{m,n} \geq x_m - \theta_n & m=1,\ldots,M; n=1,\ldots,N\\ & z_m\leq r_m & m=1,\ldots,M\\ \end{align} $$

Improve this answer
$\endgroup$
4
  • $\begingroup$ thanks a lot for your quick response. It could be a clever idea to introduce another variable $y_{m,n}$. Unfortunately, I just realized that the original function $f_n(x_m)$ is not well formulated when |x_m-\theta_n|>=c. Being zero leads to discontinuous and improper solutions. I have changes the value to $a_{n,m}c^2$. $\endgroup$
    – Doodle
    Commented May 16, 2016 at 1:46
  • $\begingroup$ I tried modifying your approach to the updated problem but was not successful, mainly due to the fact that y needs to be boxed and hence the range of x will be limited too. Any better idea? By the way, if another formulation is possible, such as the one you did above, can interior point type of algorithms be applied to solve it? $\endgroup$
    – Doodle
    Commented May 16, 2016 at 7:13
  • $\begingroup$ OK, I think the new formulation needs a more complex model involving binary variables to model the discontinuity, The one I propose could have been solved by a second-order conic solver based on interior-point. $\endgroup$
    – AndreaCassioli
    Commented May 16, 2016 at 7:30
  • $\begingroup$ Would you be able to provide a reference for the method involving binary variables that you mentioned? thanks. $\endgroup$
    – Doodle
    Commented May 16, 2016 at 9:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .