问题标签 [convex-optimization]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
1 回答
442 浏览

python - CVXOPT GLPK 返回错误的解决方案

我正在使用 GLPK 的 python 接口。我正在寻找一个解决方案 X:

  • 最小化 c
  • G * X <= H
  • A * X = b

我正在使用以下语句

那是我的 G 矩阵:

那是我的 h 矩阵

那是我的A矩阵

那是我的B矩阵

然而,通过执行以下操作:

我得到以下解决方案:

这显然是错误的。

因为 A * X != b

我没有任何线索来解决这个问题。文档很少。

0 投票
1 回答
2128 浏览

python - 在 python 中使用 scikit 包在 SVM 中获取负 alpha 值

我在 python 中使用 scikit 包实现 SVM。我在解释plot_separating_hyperplane.py中的“alpha i”值时遇到了困难

样本输出

Dual_coef_ 为我们提供了“alpha i * y i”值。我们可以确认“alpha i * y i”的总和 = 0 (0.04825885 + 0.56891844 - 0.61717729 = 0)

我想找出“alpha i”值。这应该很容易,因为我们有“alpha i * y i”值。但我让所有的“阿尔法我”都是负面的。例如,点 (0.95144703, 0.57998206) 位于直线上方(参见链接)。所以 y = +1。如果 y = +1,则 alpha 将为 -0.61717729。同样,点 (-1.02126202, 0.2408932) 位于该线下方。所以 y = -1,因此 alpha = -0.04825885。

为什么我的 alpha 值为负数? 我的解释错了吗?任何帮助将不胜感激。


供你参考,

对于支持向量分类器 (SVC),

给定训练向量 , i=1,..., n, 在两个类别中,以及一个向量使得 ,SVC 解决了以下原始问题:

在此处输入图像描述

它的对偶是

在此处输入图像描述

其中'e'是全1的向量,C > 0是上界,Q是n乘n半正定矩阵,在此处输入图像描述在此处输入图像描述核。在这里,训练向量被函数映射到更高的(可能是无限的)维空间。

0 投票
2 回答
1573 浏览

python - 基于cvxopt的python半定嵌入

我正在尝试基于cvxopt包在 python 中实现半定嵌入算法(参见此处),以解决半定编程。我在将半定程序的定义映射到 cvxopt 的接口时遇到了一些问题(请参阅this)。

这是我目前的实现:

执行程序会抛出ValueError(Rank(A) < p 或 Rank([G; A]) < n)。任何提示这里出了什么问题?

0 投票
1 回答
1031 浏览

matlab - 最小化 L1-Regularized 系统,收敛于非最小位置?

这是我在 stackoverflow 上的第一篇文章,所以如果这不是正确的区域,我深表歉意。我正在努力最小化 L1 正则化系统。

这个周末是我第一次深入优化,我有一个基本的线性系统 Y = X*B,X 是一个 n×p 矩阵,B 是一个 p×1 模型系数向量,Y 是一个 n× -1 输出向量。

我试图找到模型系数,我已经实现了梯度下降和坐标下降算法来最小化 L1 正则化系统。为了找到我正在使用回溯算法的步长,我通过查看梯度的 norm-2 并终止算法,如果它“足够接近”为零(现在我使用的是 0.001)。

我试图最小化的函数是以下 (0.5)*(norm((Y - X*B),2)^2) + lambda*norm(B,1)。(注意:通过 norm(Y,2) 我的意思是向量 Y 的 norm-2 值)我的 X 矩阵是 150×5 并且不是稀疏的。

如果我将正则化参数 lambda 设置为零,我应该收敛于最小二乘解,我可以验证我的两种算法都做得很好而且相当快。

如果我开始增加 lambda,我的模型系数都趋向于零,这就是我所期望的,但我的算法永远不会终止,因为梯度的 norm-2 始终是正数。例如,1000 的 lambda 将给我 10^(-19) 范围内的系数,但我的梯度的 norm2 约为 1.5,这是经过数千次迭代后,而我的梯度值都收敛到 0 到 1 的某个值范围,我的步长变得非常小(10 ^(-37)范围)。如果我让算法运行更长时间,情况并没有改善,它似乎已经以某种方式卡住了。

我的梯度和坐标下降算法都收敛于同一点,并为终止条件给出相同的 norm2(梯度)数。它们也适用于 0 的 lambda。如果我使用非常小的 lambda(比如 0.001)我会收敛,如果我运行一两个小时,0.1 的 lambda 看起来会收敛,一个更大的 lambda 并且收敛速度太小没用。

我有几个问题,我认为可能与问题有关?

在计算梯度时,我使用有限差分法 (f(x+h) - f(xh))/(2h)),h 为 10^(-5)。对 h 的这个值有什么想法吗?

另一个想法是,在这些非常小的步骤中,它在几乎与最小值正交的方向上来回移动,这使得收敛速度如此缓慢以至于毫无用处。

我最后的想法是,也许我应该使用不同的终止方法,也许看看收敛速度,如果收敛速度非常慢,则终止。这是一种常见的终止方法吗?

0 投票
2 回答
1482 浏览

python - 将 cvxopt 用于仅具有 Aeq=beq 的 LP 问题(没有 A*x<=b 的约束)

我正在尝试解决以下形式的线性规划问题

对于交通问题。

但是,使用 CVXOPT 需要为 lp(G,h,A,b) 求解器定义变量 Gx <= h。

我尝试创建我的 A 和 b 矩阵,对于 G 和 h 矩阵,我使用 G 的单位矩阵(乘以 -1)和 h 的零向量,以便施加 x>=0 约束。

但是,当我运行我的代码时,它会返回一个“奇异 KKT 矩阵”。

谁能帮我解决问题,或者我如何在没有 G 和 h 变量的情况下运行 CVXOPT 求解器。

0 投票
3 回答
2581 浏览

r - R中的CVX-esque凸优化?

我需要解决(很多时候,对于大量数据,以及一堆其他事情)我认为归结为二阶锥程序的问题。它可以在CVX中简洁地表达如下:

显示的数据长度和等式约束模式只是来自某些测试数据的任意值,但一般形式将大致相同,具有两个客观术语 - 一个最小化错误,另一个鼓励稀疏性 - 以及大量的等式约束在优化变量的变换版本的元素上(本身被限制为非负数)。

这似乎工作得非常好,比我以前的方法要好得多,它使约束变得腐烂。问题在于,这方面的所有其他事情都发生在 R 中,将它移植到 Matlab 会很麻烦。那么在 R 中这样做是否可行,如果可行,怎么做?

这实际上归结为两个独立的问题:

1)这有什么好的R资源吗?据我从CRAN 任务页面中可以看出,SOCP 包选项是CLSCOPDWD,其中包括一个 SOCP 求解器作为其分类器的附件。两者都有相似但相当不透明的界面,并且文档和示例有点薄,这使我们能够:

2)在这些包使用的约束块格式中表示上述问题的最佳方式是什么?上面的 CVX 语法隐藏了很多繁琐的额外变量等问题,我可以看到自己花了数周时间试图做到这一点,所以任何提示或指示将我推向正确的方向都会非常受欢迎......

0 投票
1 回答
252 浏览

machine-learning - Nesterovs第三种方法-python中的实现

我正在考虑为我用 python 编写的算法实现 Nesterov 的方法。任何人都可以请我指向可以帮助我开始实施此方法的文档吗?我是一名职业程序员,因此关注非理论版本。

我尝试通过这个http://www.ee.ucla.edu/~vandenbe/236C/lectures/fgrad.pdf但是当他们提到代理运营商时我感到震惊。什么是代理运算符,是否有任何实现代理运算符的指针?

非常感谢您的时间。

0 投票
1 回答
119 浏览

matlab - Matlab 凸优化工具箱。未显示优化变量

我在 matlab 中使用凸优化工具箱,目标函数被最小化并显示值。但是我找不到达到最小值的优化变量。有人会告诉我如何找到它吗?

0 投票
1 回答
134 浏览

matlab - 凸优化 - matlab - 4D优化变量

在 matlab 优化工具箱中,优化变量是否可以是 4D 矩阵,如果可以,如何指定起点?我可以把它全部归零吗?通过 4D 矩阵,我的意思是矩阵的矩阵。因此需要 4 个索引来确定一个值。

0 投票
1 回答
2576 浏览

python - 检查约束在 cvxpy 中可以使用实际值

在 cvxpy 中解决优化问题时,是否有一种很好的方法可以通过用实际值替换优化变量来检查约束是否有效?

我有一个复杂的优化问题(100 多个约束),但我知道最佳解决方案应该是什么。但是,cvxpy 失败并显示错误消息ValueError: Rank(A) < p or Rank([G; A]) < n 我认为这是因为我在其中一个约束中有错字,使它们不一致。有没有一种很好的方法来替换变量的实际值,以查看违反了哪些约束(因为它们可能有拼写错误)?

我的实际问题很复杂,所以我做了一个简单的例子:

in-4约束c3应该是. +4这失败并显示错误消息:Certificate of primal infeasibility found. 如果我输入p.show()我得到:

是否有一个值可以替换正确的解决方案 ( x == 3., y == 1.) 以便看到违反了第三个约束?我试过搞乱x.value等,但还没有找到办法