# BFGS Constrained Optimization Failure Due to Precision Loss

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)

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):

# 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.

• 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. Commented Jan 30 at 21:05
• The objective is nondifferentiable at any point where explained_KPI equals total_KPI. The BFGS method is designed to work with smooth objective functions. Commented Jan 31 at 1:31
• 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. Commented Feb 4 at 3:13
• 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. Commented Feb 4 at 10:50

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*}
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.