将最小化绝对值加权和改为线性优化

Question

例如，我们有一个优化问题

分钟 $$\Sum_{i=1}^{i=n} |w_{i} - a_{i}| * b_{i}$$ 英石。 \sum_{i=1}^{n} ci * wi = 0

并给出 ai、bi、ci。如何将其转换为线性程序？

我知道如果我们想要最小化 |x - a|，我们应该让 b 最小化，其中 b > x-a 且 b > -(x-a)。然而，在这种情况下，我们想要最小化绝对值的加权和并且不知道bi的符号。有谁知道怎么办吗

Answer 1

仅当 ${b}_{i} \geq 0$ 时，问题才是凸的，否则问题不是凸的。
为了看到它，假设问题是一维的，所有都是标量。
设置 $a = 0, b = -1$ 的输出函数 $- \left| w ight|$ 不是凸的（它是凹的）。

假设 ${b}_{i}$ 为非负值，则：

import numpy as np
import scipy as sp

# %%
numElements = 10
vA = np.random.randn(numElements)
vB = np.random.randn(numElements)
vC = np.random.randn(numElements)

hObjFun = lambda vW: np.dot(np.abs(vW - vA), np.maximum(vB, 0))

# %%
# Solution in the given formulation

vW1 = cp.Variable(numElements)

oObjFun = cp.Minimize( cp.abs(vW1 - vA).T @ cp.pos(vB) )
oCvxPrb = cp.Problem(oObjFun, [(vW1.T @ vC) == 0])
oCvxPrb.solve(solver = cp.CLARABEL)

# %% 
# Solution in Linear Programming form

vW2 = cp.Variable(numElements)
vT = cp.Variable(numElements)

oObjFun = cp.Minimize( vT.T @ cp.pos(vB) )
oCvxPrb = cp.Problem(oObjFun, [(vW2.T @ vC) == 0, vW2 - vA <= vT, -vT <= vW2 - vA])
oCvxPrb.solve(solver = cp.CLARABEL)

# %%
# Verify solution

np.isclose(hObjFun(vW1.value), hObjFun(vW2.value)) #<! Should print `True