I've been studying optimization theory for a while and I'm interested in finding out the solution to the following problem. Suppose we have a regression problem in the form of:

$$\quad y^k = \beta_0 + \beta_1 x + \beta_2 x^2 - u^k, \quad k=1,...K$$

With the following constraints:

\begin{equation} \label{eq5} \begin{split} min \sum_{k=1}^{K} u_k^2\\ s.t.\qquad u^k &\geq 0, \quad k=1,...K\\ \beta_0& \leq 0\\ \beta_1,\beta_2 & \geq 0 \end{split} \end{equation}

How do we translate such an optimization problem in a standard quadratic form?

\begin{equation} \begin{split} min(\frac{1}{2}x^TQx+c^Tx)\\ s.t.\quad A^Tx\leq b \\ \end{split} \end{equation}

Thank you in advance


I assume your regression problem is $$y_k = \beta_0 + \beta_1x_k + \beta_2x_k^2-u_k.$$

Let column vectors $\beta = (\beta_0, \beta_1, \beta_2)'$ and $v_k = (1, x_k, x_k^2)'$, we can rewrite the objective for this regression model as \begin{align*} & \sum_{k=1}^K u_k^2 = \sum_{k=1}^K \left(\beta_0 + \beta_1x_k + \beta_2x_k^2-y_k\right)^2 \\ = & \sum_{k=1}^K\left(v_k^\prime\beta - y_k\right)^2 = \sum_{k=1}^K\left(v_k^\prime\beta\right)^2-2y_kv_k^\prime\beta + y_k^2 \\ = & \sum_{k=1}^K\beta'v_kv_k^\prime\beta - \sum_{k=1}^K2y_kv_k^\prime\beta + \sum_{k=1}^Ky_k^2 \end{align*} Note $\sum y_k^2$ is a constant and can be dropped freely in the objective function. Let $Q = 2\sum_{k=1}^Kv_kv_k^\prime$, $c = -2\sum_{k=1}^Ky_kv_k$, there is the standard quadratic program form $$\min_{\beta} \frac12\beta^\prime Q\beta + c'\beta.$$ Now let's look at the constraints, $\beta_0 \le 0$, $\beta_1 \ge 0$, and $\beta_2\ge 0$ can be written as $A_0^\prime\beta \le b_0$ where matrix $A_0$ is $$A_0 = \left(\begin{matrix}1 & 0 & 0\\ 0 & -1 & 0 \\ 0 & 0 & -1\end{matrix}\right)$$ and $b_0^\prime = (0,0,0)$. Each of $u_k \ge 0$ can be written as $-v_k^\prime\beta \le -y_k$. Combining all constraints together, we have $A^\prime\beta \le b$ where \begin{matrix} A & = & (A_0 &-v_1 &-v_2 & \cdots &-v_K) \\ b^\prime & = & (b_0^\prime & -y_1& -y_2 & \cdots & -y_K) \end{matrix}

In fact, the constraint $u_k\ge0$ is quite unusual. Usually, the estimation error is centered at 0, in your case, it is certainly not centered at 0. Also, with that set of constraints, you may run into feasibility problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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