Successive Convex Approximation算法的学习笔记
文章目录
- 一、代码debug
- 二、原理
本文主要参考了CSDN上的 另一篇文章,但规范了公式的推导过程和修缮了部分代码
一、代码debug
首先,我们将所有的代码放到MATLAB中,很快在命令行中出现了错误信息
很显然有问题,但是我不知道发生了什么问题。我猜测可能是求解器没有正确安装,因此我正确安装了Gurobi求解器
注意安装Gurobi求解器需要验证license,具体内容可以查询网络上的安装教程。在命令行中输入grbgetkey+licence
就可以完成激活。
但此时还是有问题,我经过查询得知是MEX文件无法指定,是系统路径没有添加gurobi文件的bin,因此我添加到系统路径中
此后文件便可以正确运行了,结果如下。
二、原理
现考虑如下非凸二次规划问题
min f ( x , y ) = [ x , y ] Q [ x , y ] T = x 2 + x y − y 2 s.t. − 1 ≤ x ≤ 1 − 1 ≤ y ≤ 1 \begin{aligned} &\operatorname*{min}f(x,y)&& \left.=\left[\begin{matrix}{x,y}\\\end{matrix}\right.\right]Q\left[\begin{matrix}{x,y}\\\end{matrix}\right]^{T} \\ &&&=x^{2}+xy-y^{2} \\ &\text{s.t.}&& -1\leq x\leq1 \\ &&&-1\leq y\leq1 \end{aligned} minf(x,y)s.t.=[x,y]Q[x,y]T=x2+xy−y2−1≤x≤1−1≤y≤1
其中,
Q = [ 1 0.5 0 5 ] . Q=\begin{bmatrix}1&0.5\\0&5\\\end{bmatrix}. Q=[100.55].
原问题的目标函数可以通过特征值分解转化为凸函数减去凸函数的形式,凸函数减去凸函数未必是凸函数。
Q = V D V T = V ( λ P − λ N ) V T = V λ P V T ⏟ P − V λ N V T ⏟ N \begin{aligned}Q=VDV^T=V\left(\lambda_P-\lambda_N\right)V^T=\underbrace{V\lambda_PV^T}_{P}-\underbrace{V\lambda_NV^T}_{N}\end{aligned} Q=VDVT=V(λP−λN)VT=P VλPVT−N VλNVT
其中,矩阵 P P P 和 N N N 都是半正定矩阵,矩阵 D D D 的表达式如下
D = [ λ 1 λ 2 ⋱ λ k λ k + 1 ⋱ ] = [ λ 1 λ 2 ⋱ λ k 0 ⋱ ] ⏟ λ P − [ 0 0 ⋱ 0 − λ k + 1 ⋱ ] ⏟ λ N D=\left.\left[\begin{array}{cccc}\lambda_{1}& & & & & \\ &\lambda_{2}& & & &\\ & & \ddots & & &\\ & & & \lambda_{k}& &\\ & & & & \lambda_{k+1} &\\ & & & & &\ddots \end{array}\right.\right] =\underbrace{\left.\left[\begin{array}{cccc}\lambda_{1}& & & & & \\ &\lambda_{2}& & & &\\ & & \ddots & & &\\ & & & \lambda_{k}& &\\ & & & & 0 &\\ & & & & &\ddots \end{array}\right.\right]}_{\lambda_P} -\underbrace{\left.\left[\begin{array}{cccc}0& & & & & \\ &0 & & & &\\ & & \ddots & & &\\ & & &0& &\\ & & & & - \lambda_{k+1} &\\ & & & & &\ddots \end{array}\right.\right]}_{\lambda_N} D= λ1λ2⋱λkλk+1⋱ =λP λ1λ2⋱λk0⋱ −λN 00⋱0−λk+1⋱
其中 λ 1 , λ 2 , … , λ k ≥ 0 , λ k + 1 , λ k + 2 , … < 0 \lambda_1,\lambda_2,\ldots,\lambda_k\geq0,\lambda_{k+1},\lambda_{k+2},\ldots<0 λ1,λ2,…,λk≥0,λk+1,λk+2,…<0。
对目标函数的第二项 [ x , y ] N [ x , y ] T \left[x,y\right]N[x,y]^T [x,y]N[x,y]T 在点 ( x ∗ , y ∗ ) (x^{*},y^{*}) (x∗,y∗) 处进行凸近似,即在点 ( x ∗ , y ∗ ) (x^{*},y^{*}) (x∗,y∗) 处进行一阶泰勒展开
− [ x ∗ , y ∗ ] N [ x ∗ , y ∗ ] T − [ ∇ ( [ x , y ] N [ x , y ] T ) ∣ x ∗ , y ∗ ] T ( [ x , y ] − [ x ∗ , y ∗ ] ) T = − [ x ∗ , y ∗ ] N [ x ∗ , y ∗ ] T − ( 2 N [ x ∗ , y ∗ ] T ) T ( [ x , y ] − [ x ∗ , y ∗ ] ) T = − 2 [ x ∗ , y ∗ ] N [ x , y ] T + [ x ∗ , y ∗ ] N [ x ∗ , y ∗ ] T \begin{aligned}&-\left[x^*,y^*\right]N\left[x^*,y^*\right]^T-\left[\nabla\left(\left[x,y\right]N\big[x,y\big]^T\right)\right|_{x^*,y^*}\Big]^T\left(\left[x,y\right]-\left[x^*,y^*\right]\right)^T\\ &=-\left[x^*,y^*\right] N \left[x^*,y^*\right]^T -\left(2N\left[x^*,y^*\right]^T\right)^T\left(\left[x,y\right]-\left[x^*,y^*\right]\right)^T\\ &=-2{\Big[}x^{*},y^{*}{\Big]}N{\Big[}x,y{\Big]}^{T}+{\Big[}x^{*},y^{*}{\Big]}N{\Big[}x^{*},y^{*}{\Big]}^{T} \end{aligned} −[x∗,y∗]N[x∗,y∗]T−[∇([x,y]N[x,y]T) x∗,y∗]T([x,y]−[x∗,y∗])T=−[x∗,y∗]N[x∗,y∗]T−(2N[x∗,y∗]T)T([x,y]−[x∗,y∗])T=−2[x∗,y∗]N[x,y]T+[x∗,y∗]N[x∗,y∗]T
至此,原问题可转化为:
min f ( x , y ) = [ x , y ] P [ x , y ] T − 2 [ x ∗ , y ∗ ] N [ x , y ] T + [ x ∗ , y ∗ ] N [ x ∗ , y ∗ ] T s . t . − 1 ≤ x ≤ 1 − 1 ≤ y ≤ 1 \begin{aligned} &\min & &f\left(x,y\right)=\left[x,y\right]P\left[x,y\right]^{T}-2\left[x^{*},y^{*}\right]N\left[x,y\right]^{T}+\left[x^{*},y^{*}\right]N\left[x^{*},y^{*}\right]^{T} \\ &s.t.& &-1\leq x\leq1 \\ & & &-1\leq y\leq1 \end{aligned} mins.t.f(x,y)=[x,y]P[x,y]T−2[x∗,y∗]N[x,y]T+[x∗,y∗]N[x∗,y∗]T−1≤x≤1−1≤y≤1
clear all
close all
clcQ=[1,0.5;0.5,-1];x=sdpvar(2,1);
xmin=-1;
xmax=1;
Constraints=[];
Constraints=[Constraints,xmin<=x<=xmax];
ops = sdpsettings('solver', 'gurobi', 'verbose', 0);[V,D] = eig(Q);%计算A的特征值对角阵D和特征向量V,使AV=VD成立
lambda_P=D;
lambda_N=-D;
lambda_P(find(D<0))=0;
lambda_N(find(D>0))=0;
P=V*lambda_P*V';
N=V*lambda_N*V';
x0=[0.5;0.5];
x_temp=x0;
while(1)f_k=(x'*P*x-2*x_temp'*N*x+x_temp'*N*x_temp);sol=solvesdp(Constraints,f_k,ops);display([sol.info,' 目标函数值:',num2str(value(x_temp'*Q*x_temp))])x_temp_before=x_temp;x_temp=value(x);if sqrt(sum((x_temp-x_temp_before).^2)/length(x_temp))<1e-10breakend
end
x_result=x_tempX = gridsamp([-1 -1;1 1], 40);
[m,~]=size(X);
YX=zeros(m,1);
for i=1:size(X,1)x=X(i,:);y=x*Q*x';YX(i)=y;
end
X1 = reshape(X(:,1),40,40); X2 = reshape(X(:,2),40,40);
YX = reshape(YX, size(X1));
figure(1), mesh(X1, X2, YX)%绘制预测表面
hold on
scatter3(x_temp(1),x_temp(2),x_temp'*Q*x_temp,200,'r','pentagram','filled')
相关文章:

Successive Convex Approximation算法的学习笔记
文章目录 一、代码debug二、原理 本文主要参考了CSDN上的 另一篇文章,但规范了公式的推导过程和修缮了部分代码 一、代码debug 首先,我们将所有的代码放到MATLAB中,很快在命令行中出现了错误信息 很显然有问题,但是我不知道发生…...
IoT数采平台2:文档
IoT数采平台1:开篇IoT数采平台2:文档IoT数采平台3:功能IoT数采平台4:测试 【平台功能】 基础配置、 实时监控、 规则引擎、 告警列表、 系统配置 消息通知:Websocket 设备上线、设备下线、 数据变化、 告警信息、 实时…...

Vue监听器watch的基本用法
文章目录 1. 作用2. 格式3. 示例3.1 value 值为字符串3.2 value 值为函数3.3 value 值为对象 4. 与计算属性对比 1. 作用 监视数据变化,执行一些业务逻辑或异步操作。 2. 格式 监听器 watch 内部以 key :value 的形式定义,key 是 data 中的…...
MySQL UPDATE JOIN 根据一张表或多表来更新另一张表的数据
当使用MySQL时,经常需要根据一张表或多张表的数据来更新另一张表的数据。这种情况下,我们可以使用UPDATE语句结合JOIN操作来实现这一需求。本文将介绍MySQL中使用UPDATE JOIN的技术。 什么是UPDATE JOIN UPDATE JOIN是MySQL中一种结合UPDATE语句和JOIN…...
JS实现继承的方式ES6版
上一篇:JS实现继承的方式原生版 ES6的继承 主要是依赖extends关键字来实现继承,且继承的效果类似于寄生组合继承。 class Parent() { }class Child extends Parent {constructor(x, y, color) {super(x, y);this.color color;} }子类必须在construct…...

elementui 左侧或水平导航菜单栏与main区域联动
系列文章目录 一、elementui 导航菜单栏和Breadcrumb 面包屑关联 二、elementui 左侧导航菜单栏与main区域联动 三、elementui 中设置图片的高度并支持PC和手机自适应 四、elementui 实现一个固定位置的Pagination(分页)组件 文章目录 系列文章目录…...

YUNBEE云贝-技术分享:PostgreSQL分区表
引言 PostgreSQL作为一款高度可扩展的企业级关系型数据库管理系统,其内置的分区表功能在处理大规模数据场景中扮演着重要角色。本文将深入探讨PostgreSQL分区表的实现逻辑、详细实验过程,并辅以分区表相关的视图查询、分区表维护及优化案例,…...

5.2 通用代码,数组求和,拷贝数组,si配合di翻转数组
5.2 通用代码,数组求和,拷贝数组,si配合di翻转数组 1. 通用代码 通用代码类似于一个用汇编语言写程序的一个框架,也类似于c语言的头文件编写 assume cs:code,ds:data,ss:stack data segmentdata endsstack segmentstack endsco…...
Oracle23免费版简易安装攻略
installation-guide 1 安装 root用户下 wget https://yum.oracle.com/repo/OracleLinux/OL8/developer/x86_64/getPackage/oracle-database-preinstall-23c-1.0-1.el8.x86_64.rpm wget https://download.oracle.com/otn-pub/otn_software/db-free/oracle-database-free-23c-1…...
《论文阅读》一种基于反事实推理的会话情绪检测无训练去偏框架 EMNLP 2023
《论文阅读》一种基于反事实推理的会话情绪检测无训练去偏框架 EMNLP 2023 前言简介相关工作模型构架Basic ClassificationBias ExtractionUnbiased Inference实验结果前言 亲身阅读感受分享,细节画图解释,再也不用担心看不懂论文啦~ 无抄袭,无复制,纯手工敲击键盘~ 今天…...

【编译lombok问题】已解决:编译突然找不到符号问题-get/set找不到符号
一、场景:编译突然找不到符号 报错信息: 找不到符号 符号:方法getName() 二、原因: 没有使用lombok支持的编译器 三、解决方法: 打开File-Settings,按以下步骤进行设置; 修改:-Djp…...

第四篇:3.3 无效流量(Invalid traffic) - IAB/MRC及《增强现实广告效果测量指南1.0》
翻译计划 第一篇概述—IAB与MRC及《增强现实广告效果测量指南》之目录、适用范围及术语第二篇广告效果测量定义和其他矩阵之- 3.1 广告印象(AD Impression)第三篇广告效果测量定义和其他矩阵之- 3.2 可见性 (Viewability)第四篇广…...
PyTorch示例——使用Transformer写古诗
文章目录 PyTorch示例——使用Transformer写古诗1. 前言2. 版本信息3. 导包4. 数据与预处理数据下载先看一下原始数据开始处理数据,过滤掉异常数据定义 词典编码器 Tokenizer定义数据集类 MyDataset测试一下MyDataset、Tokenizer、DataLoader 5. 构建模型位置编码器…...

vue 视频添加水印
1.需求背景 其实腾讯云点播的api也支持视频水印,但是只有单个水印,大概效果是这样子的,不满足我们的需求,我们的需求是需要视频中都是水印。 腾讯云点播水印 项目需求的水印(主要是防录屏,最后的实现效果是这样&…...

Web Animations API 动画
Element.animate() dom.animate动画可以避免污染dom原有的css动画 参考资料 Element.animate() - Web API 接口参考 | MDN Element: getAnimations() method - Web APIs | MDN .tunnel{width:200px;height:200px;background-color:#38f;}<div class"tunnel" …...

【大数据存储】实验五:Mapreduce
实验Mapreduce实例——排序(补充程序) 实验环境 Linux Ubuntu 16.04 jdk-8u191-linux-x64 hadoop-3.0.0 hadoop-eclipse-plugin-2.7.3.jar eclipse-java-juno-SR2-linux-gtk-x86_64 实验内容 在电商网站上,当我们进入某电商页面里浏览…...

日志服务 HarmonyOS NEXT 日志采集最佳实践
作者:高玉龙(元泊) 背景信息 随着数字化新时代的全面展开以及 5G 与物联网(IoT)技术的迅速普及,操作系统正面临前所未有的变革需求。在这个背景下,华为公司自主研发的鸿蒙操作系统(…...
Educational Codeforces Round 133 (Rated for Div. 2) (C dp D前缀和优化倍数关系dp)
A:能用3肯定用三,然后分类讨论即可 #include<bits/stdc.h> using namespace std; const int N 2e510,M2*N,mod998244353; #define int long long typedef long long LL; typedef pair<int, int> PII; typedef unsigned long long ULL; usi…...

【讲解下如何Stable Diffusion本地部署】
🎥博主:程序员不想YY啊 💫CSDN优质创作者,CSDN实力新星,CSDN博客专家 🤗点赞🎈收藏⭐再看💫养成习惯 ✨希望本文对您有所裨益,如有不足之处,欢迎在评论区提出…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查
在对接支付宝API的时候,遇到了一些问题,记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

3.3.1_1 检错编码(奇偶校验码)
从这节课开始,我们会探讨数据链路层的差错控制功能,差错控制功能的主要目标是要发现并且解决一个帧内部的位错误,我们需要使用特殊的编码技术去发现帧内部的位错误,当我们发现位错误之后,通常来说有两种解决方案。第一…...
连锁超市冷库节能解决方案:如何实现超市降本增效
在连锁超市冷库运营中,高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术,实现年省电费15%-60%,且不改动原有装备、安装快捷、…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
【论文笔记】若干矿井粉尘检测算法概述
总的来说,传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度,通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...
Axios请求超时重发机制
Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式: 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!
简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求,并检查收到的响应。它以以下模式之一…...

【分享】推荐一些办公小工具
1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由:大部分的转换软件需要收费,要么功能不齐全,而开会员又用不了几次浪费钱,借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...