在约束优化中对一组向量的量值和制定约束条件

Question

我正在求解几何约束优化问题。优化中的变量是一组向量的 x-y 分量。 objective 函数在这些变量中是二次函数。

但是，我需要约束向量子集的大小的总和。

具体来说，假设这个子集包含 {v1,v2,...,vn}

我需要解决方案来满足

||v1|| + ||v2|| + .... + ||vn|| <大号

如果它只是一个向量，我可以对两边求平方以获得二次约束并将问题框定为 QCQP

v1.x * v1.x + v1.y * v1.y < L*L

但是，我有多个向量。那么有什么方法可以表达约束，使我可以应用比一般非线性约束优化更具体的技术？或者假设我的 objective 函数可以通过分析最小化，通过

解决问题是否有意义

忽略约束并获得 objective 函数的最佳值 x*
将 x* 以数值方式投影到约束流形上以获得满足约束的最终解？

Answer 1

不确定您的优化问题中还有什么，但仅约束您的范数的任务是非线性的但凸的，可以有效解决。

使用外部库，您可以像这样制作原型。这里使用cvxpy（python）。

有许多遵循相同想法的类似库，例如：cvxopt (python)、picos (python)、yalmip (matlab)、convex.jl (julia)。官方的 solver-APIs 通常更底层，还有更多的工作要做。中间还有 JuMP (julia)。

from cvxpy import *

L = 10.0
V = Variable(3,5)  # 3 vectors

constraints = []
constraints.append(sum_entries(norm(V, axis=1)) <= L)

objective = Maximize(sum_entries(V))
prob = Problem(objective, constraints)
prob.solve()
print("status:", prob.status)
print("optimal value", prob.value)
print("optimal var", V.value)
print('constr: ', sum_entries(norm(V, axis=1).value))

输出：

status: optimal
optimal value 22.36067971461066
optimal var [[ 1.49071198  1.49071198  1.49071198  1.49071198  1.49071198]
 [ 1.49071198  1.49071198  1.49071198  1.49071198  1.49071198]
 [ 1.49071198  1.49071198  1.49071198  1.49071198  1.49071198]]
constr:  sum_entries([[ 3.33333332]
 [ 3.33333332]
 [ 3.33333332]])

以上是自动转换的SOCP-form，可以通过商业求解器或ECOS、SCS等开源求解器求解。

这个转换也向我们证明，这个问题是凸的（通过构造）！该方法称为 Disciplined Convex Programming .

根据您的 library/software 选择，您必须手动进行此转换。当您引入一些辅助变量来收集向量的范数时，应该并不难。在 Gurobi 中，您只需要使用基本的 SOCP-constraint docs.

备注： ||v1|| + ||v2|| + .... + ||vn|| < L 很可怕，因为数值优化通常只关心 <=。其他一切都需要技巧（epsilon-values...）

编辑：

这是一个纯粹的 Gurobi 方法，它可以让您了解如何使用支持与 Gurobi API 类似功能的更多低级库来实现这一点（我正在考虑没有 Mosek 和 CPLEX在那里知道 API 很多；我认为 Mosek 非常不同）。

from gurobipy import *
import numpy as np

L = 10.0

# Model
m = Model("test")

# Vars
v = np.empty((3,5), dtype=object)
for i in range(3):
    for j in range(5):
        v[i, j] = m.addVar()  # by default >= 0; it's just an example

norm_v = np.empty(3, dtype=object)
for i in range(3):
    norm_v[i] = m.addVar()    # aux-vars to collect norms

m.update()  # make vars usable for posting constraints

# Constraints
for i in range(3):
    m.addQConstr(np.dot(v[i, :], v[i, :]),
                 GRB.LESS_EQUAL, norm_v[i] * norm_v[i])  # this is the SOCP-constraint for our norm

m.addConstr(np.sum(norm_v) <= L)  # gurobi-devs would propose using quicksum

# Objective
m.setObjective(np.sum(v), GRB.MAXIMIZE)

# Solve
m.optimize()

def get_val(x):
    return x.X
get_val_func = np.vectorize(get_val)
print('optimal var: ', get_val_func(v))

输出：

Optimal objective 2.23606793e+01

optimal var:  [[ 1.49071195  1.49071195  1.49071195  1.49071195  1.49071195]
 [ 1.49071195  1.49071195  1.49071195  1.49071195  1.49071195]
 [ 1.49071195  1.49071195  1.49071195  1.49071195  1.49071195]]

在约束优化中对一组向量的量值和制定约束条件

Formulating a constraint on the SUM of the magnitudes of a set of vectors in a constrained optimization

optimization

geometry

constraints

vector

mathematical-optimization