0
$\begingroup$

I am trying to optimize the following objective function according to some constraints. However, the optimization fails at the first iteration with the message that the desired error was not necessarily achieved due to precision loss. Does anyone have any advice as to why this happening so early on? Can you recommend anything I might be doing wrong?

$$ f(\beta_{0}, \beta_{1}, ..., \beta_{n}) = Y_{t} - \beta_{0}x_{0t} - \beta_{1}x_{1t} - ... - \beta_{n}x_{nt} $$

The constraints are: $$ LB_{0} < \beta_{0} < UB_{1} ... LB_{n} < \beta_{n} < UB_{n} $$

Here is my code:

    total_unexplained = 0
    for i in range(len(x)):
        # for i-th month
        explained_KPI = np.sum(x[i] * b)
        total_KPI = np.sum(Y[i])
        total_unexplained += abs(total_KPI - explained_KPI)

    return total_unexplained

bounds = []
# for the coefficient of each channel, set upper and lower bound
for i in range(len(df_b.columns)):
    b_init_val = b_init[i]
    b_init_lower = b_init_val * (1 + b_lower_bound[i])
    b_init_upper = b_init_val * (1 + b_upper_bound[i])
    bounds.append((b_init_lower, b_init_upper))
bounds = tuple(bounds)

# Define the Jacobian function
def jacobian(x):
    gradient = -np.sum(x, axis=0)
    return gradient  

# Without constraint
res = minimize(function_obj, b_init, method='BFGS', bounds=bounds)

This is giving the below error: message: 'Desired error not necessarily achieved due to precision loss.' nfev: 1083 nit: 1 njev: 43 status: 2 success: False

Edit: I have seen the comment that my function is linear, so BFGS would not be a candidate. Does this apply for all scipy minimize algorithms? I have found that other algorithms, such as COBYLA and Nelder-Meal succeeded.

$\endgroup$
4
  • $\begingroup$ Isn't your objective linear? I don't think you can build curvature with a linear objective ;) If I understand your problem correctly, you can simply send each variable to one of its bounds, depending on the sign of its coefficient in the objective. For example, if you have $min~ 3x_1 - 2x_2$ s.t. $x_1 \in [2, 3], x_2 \in [3, 4]$, you want to set $x_1$ to its lower bound (to decrease the objective, you need to minimize $x_1$) and $x_2$ to its upper bound. $\endgroup$ Jan 30 at 21:05
  • $\begingroup$ The objective is nondifferentiable at any point where explained_KPI equals total_KPI. The BFGS method is designed to work with smooth objective functions. $\endgroup$ Jan 31 at 1:31
  • $\begingroup$ Nelder-Mead is a derivative-free optimization approach, so that may explain why it works. BFGS requires derivative information, which might be an issue if your objective is not differentiable everywhere. $\endgroup$
    – spektr
    Feb 4 at 3:13
  • $\begingroup$ OK so the objective function you describe in your message is not correct. Can you please fix it? Your problem can be reformulated as a smooth LP, see spektr's message. $\endgroup$ Feb 4 at 10:50

2 Answers 2

3
$\begingroup$

If you are set on having your objective function be of the form $$\sum_{i=1}^n \lvert y_i - \beta \cdot x_i \rvert$$ subject to the box constraints on the parameters in $\beta$, then you can transform this into a linear programming instance to solve the problem. Specifically, we can obtain a linear program written as follows: $$\begin{align*} &\min_{\epsilon_i, \beta_j} \sum_{i=1}^n \epsilon_i\\ &\text{subject to}\\ &\hspace{1cm} \forall i,\; -\epsilon_i \leq y_i - \beta \cdot x_i \leq \epsilon_i\\ &\hspace{1cm} \forall j,\; L_j \leq \beta_j \leq U_j\\ &\hspace{1cm} \forall i, \epsilon_i \geq 0 \end{align*}$$

This should be easy enough to implement in python using a standard linear programming package.

$\endgroup$
2
$\begingroup$

As was pointed out in the comments, the function you are trying to optimize is of the form $|\beta\cdot x - y|$, which is not differentiable at its minimum. Additionally, the gradient your code is computing is not the correct gradient of the objective, although it seems like that isn't being supplied. This will break most derivative-based optimization algorithms as you get closer to the minimum. However, notice that this optimization problem is equivalent to minimizing the square of the objective, which is smooth everywhere. This modification will make it tractable for most algorithms.

However, your function is linear, so the problem can be simplified to a linear least squares problem with box constraints, which can be solved by more tailored methods, such as SciPy's lsq_linear function, which performs a mixture of linear least squares, trust region, and active set methods modified for quadratic objectives.

$\endgroup$

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.