最优化理论分析复习--最优性条件(一)

文章目录

  • 上一篇
  • 无约束问题的极值条件
  • 约束极值问题的最优性条件
  • 基本概念
    • 只有不等式约束时
  • 下一篇

上一篇

最优化理论复习–对偶单纯形方法及灵敏度分析

无约束问题的极值条件

由于是拓展到向量空间 R n R^n Rn, 所以可由高数中的极值条件进行类比

  1. 一阶必要条件
    设函数 f ( x ) f(x) f(x) 在点 x ˉ \bar{x} xˉ 处可微, 若 x ˉ \bar{x} xˉ 是局部极小点,则 ▽ f ( x ˉ ) = 0 \bigtriangledown f(\bar{x}) = 0 f(xˉ)=0
    类比于若 x ˉ \bar{x} xˉ 是极小值点则 f ′ ( x ˉ ) = 0 f'(\bar{x}) = 0 f(xˉ)=0

  2. 二阶必要条件
    f ( x ) f(x) f(x) x ˉ \bar{x} xˉ 处二阶可微,若 x ˉ \bar{x} xˉ 是局部极小点, 则 ▽ f ( x ˉ ) = 0 \bigtriangledown f(\bar{x}) = 0 f(xˉ)=0, 且 H e s s i a n Hessian Hessian 矩阵 ▽ 2 f ( x ˉ ) \bigtriangledown^2f(\bar{x}) 2f(xˉ) 是半正定的。
    类比于 若 x ˉ \bar{x} xˉ是极小值点则 f ′ ( x ˉ ) = 0 , 且 f ′ ′ ( x ˉ ) ≥ 0 f'(\bar{x}) = 0, 且 f''(\bar{x}) \geq 0 f(xˉ)=0,f(xˉ)0

  3. 二阶充分条件
    设函数 f ( x ) f(x) f(x) 在点 x ˉ \bar{x} xˉ 处二次可微,若梯度 ▽ f ( x ˉ ) = 0 \bigtriangledown f(\bar{x}) = 0 f(xˉ)=0, 且 H e s s i a n Hessian Hessian 矩阵 ▽ 2 f ( x ˉ ) 正 定 \bigtriangledown^2f(\bar{x})正定 2f(xˉ), 则 x ˉ \bar{x} xˉ是严格局部极小点。
    类比于 f ′ ( x ˉ ) = 0 , f ′ ′ ( x ˉ ) > 0 f'(\bar{x}) = 0, f''(\bar{x}) > 0 f(xˉ)=0,f(xˉ)>0 x ˉ \bar{x} xˉ 是极小值点

  4. 充要条件
    f ( x ) f(x) f(x) 是定义在 R n R^n Rn 上的可微凸函数 x ˉ ∈ R n \bar{x} \in R^n xˉRn, 则 x ˉ \bar{x} xˉ 为整体极小点的充要条件是 ▽ f ( x ˉ ) = 0 \bigtriangledown f(\bar{x}) = 0 f(xˉ)=0
    注:如果 f ( x ) f(x) f(x) 是严格凸的,则全局极小点是唯一的。

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

约束极值问题的最优性条件

基本概念

定义: 对 m i n f ( x ) min f(x) minf(x), 设 x ˉ ∈ R n \bar{x} \in R^n xˉRn 是任给一点, d ≠ 0 d \not = 0 d=0, 若存在 δ > 0 \delta > 0 δ>0, 使得对任意的 λ ∈ ( 0 , δ ) \lambda \in (0, \delta) λ(0,δ), 有 f ( x ˉ + λ d ) < f ( x ˉ ) f (\bar{x} + \lambda d) < f(\bar{x}) f(xˉ+λd)<f(xˉ), 则称 d d d f ( x ) f(x) f(x) 在点 x ˉ \bar{x} xˉ 处的下降方向。

  1. 引理: 设函数 f ( x ) f(x) f(x) 在点 x ˉ \bar{x} xˉ 可微, 若存在 d ≠ 0 d \not = 0 d=0, 使得 ▽ f ( x ˉ ) T d < 0 \bigtriangledown f(\bar{x})^T d < 0 f(xˉ)Td<0, 则存在 δ > 0 \delta > 0 δ>0, 是使得对 ∀ λ ∈ ( 0 , δ ) \forall \lambda \in (0, \delta) λ(0,δ), 有 f ( x ˉ + λ d ) < f ( x ˉ ) f(\bar{x} + \lambda d)<f(\bar{x}) f(xˉ+λd)<f(xˉ)
    与梯度方向成钝角的方向是下降方向
    表示为
    F 0 = { d ∣ ▽ f ( x ˉ ) T d < 0 } F_0 = \{ d | \bigtriangledown f(\bar{x})^T d < 0\} F0={df(xˉ)Td<0}

  2. 定义: 设集合 S ⊂ R n , x ˉ ∈ c l S . S \subset R^n, \bar{x} \in clS. SRn,xˉclS., d d d 为非零向量, 若存在数 δ > 0 \delta > 0 δ>0, 使得对任意 λ ∈ ( 0 , δ ) , \lambda \in (0, \delta), λ(0,δ), 都有 x ˉ + λ d ∈ S \bar{x} + \lambda d \in S xˉ+λdS 则称 d d d 为集合 S S S x ˉ \bar{x} xˉ 的可行方向。
    就是移动方向在可行域内
    表示为 D = { d ∣ d ≠ 0 , x ˉ ∈ c l S , ∃ δ > 0 , ∀ λ ∈ ( 0 , δ ) , 有 x ˉ + λ d ∈ S } D = \{ d | d \not = 0, \bar{x} \in clS, \exists \delta > 0, \forall \lambda \in (0, \delta), 有 \bar{x} + \lambda d \in S \} D={dd=0,xˉclS,δ>0,λ(0,δ),xˉ+λdS}
    x ˉ 处 的 可 行 方 向 锥 \bar{x} 处的可行方向锥 xˉ

  3. 定义: 若问题的可行点 x ˉ \bar{x} xˉ 是某个不等式约束 g i ( x ) ≥ 0 g_i(x) \geq 0 gi(x)0 变成等式, 则该不等式约束称为关于可行点 x ˉ \bar{x} xˉ 的起作用约束; 否则称为不起作用约束。
    表示为
    I = { i ∣ g i ( x ˉ = 0 , x ˉ ∈ S ) } I = \{ i| g_i(\bar{x} = 0, \bar{x} \in S) \} I={igi(xˉ=0,xˉS)}

  4. 定义:在起作用约束作对应切线,获得对应梯度,与这两个梯度同时呈锐角的方向为积极约束的可行方向。
    表示为 G 0 = { d ∣ ▽ g i ( x ˉ ) T d > 0 , i ∈ I ( x ) } G_0 = \{d | \bigtriangledown g_i(\bar{x})^T d > 0, i \in I(x) \} G0={dgi(xˉ)Td>0,iI(x)}
    即由约束条件求出的可行方向
    G 0 ⊂ D G_0 \subset D G0D
    问题标准形式:
             m i n f ( x ) \ \ \ \ \ \ \ \ min f(x)         minf(x)

s . t . { g i ( x ) ≥ 0 , 不 等 式 约 束 h j ( x ) = 0 , 等 式 约 束 x ∈ R n s.t.\left \{\begin{matrix} g_i (x) \geq 0,不等式约束 \\ \\h_j(x) = 0,等式约束 \\ \\ x \in R^n \end {matrix} \right. s.t.gi(x)0hj(x)=0xRn

几何最优性条件:设 S S S R n R^n Rn 的非空集合, x ˉ ∈ S , f ( x ) \bar{x} \in S, f(x) xˉS,f(x) x ˉ \bar{x} xˉ 处可微, 若 x ˉ \bar{x} xˉ 是局部最优解, 则 F 0 ∩ D = ∅ F_0 \cap D = \emptyset F0D=
即所有的可行方向都是上升方向

只有不等式约束时

由于 G 0 ⊂ D G_0 \subset D G0D 所以也有 F 0 ∩ G 0 = ∅ F_0 \cap G_0 = \emptyset F0G0=,可行域之内不能有空洞

  • (F-J条件) 设 x ˉ ∈ S , I = { i ∣ g i ( x ˉ ) = 0 } , f ( x ) , g i ( x ) ( i ∈ I ) \bar{x} \in S, I = \{ i | g_i(\bar{x}) = 0\}, f(x), g_i(x) (i \in I) xˉS,I={igi(xˉ)=0},f(x),gi(x)(iI) x ˉ \bar{x} xˉ 处可微, g i ( x ) ( i ∉ I ) g_i(x) (i \notin I) gi(x)(i/I) x ˉ \bar{x} xˉ 处连续, 若 x ˉ \bar{x} xˉ 是问题的最优解,则存在不全为零的数 w 0 , w i ( i ∈ I ) w_0, w_i (i \in I) w0,wi(iI) 使得
    w 0 ▽ f ( x ˉ ) − ∑ i ∈ I w i ▽ g i ( x ˉ ) = 0 w_0 \bigtriangledown f(\bar{x}) - \sum\limits_{i \in I} w_i \bigtriangledown g_i(\bar{x}) = 0 w0f(xˉ)iIwigi(xˉ)=0
    x ˉ \bar{x} xˉ F − J F-J FJ
    为必要条件,极小值点一定是 F-J点, 但 F-J点不一定为极小值点

在这里插入图片描述

在这里插入图片描述
w 0 = 0 w_0 = 0 w0=0 是另外另个约束条件的梯度必须能相互抵消,这种情况才有最优解,因此更多的是关注 w 0 ≠ 0 w_0 \not = 0 w0=0的情况

  • (KKT条件) 设 x ˉ ∈ S \bar{x} \in S xˉS , f , g i ( i ∈ I ) 在 x ˉ 处 可 微 , g i ( i ∉ I ) 在 x ˉ 连 续 f, g_i(i \in I)在\bar{x} 处可微, g_i(i \notin I) 在\bar{x}连续 f,gi(iI)xˉ,gi(i/I)xˉ(保证无空洞), { ▽ g i ( x ˉ ) ∣ i ∈ I } 线 性 无 关 \{ \bigtriangledown g_i(\bar{x}) | i \in I\} 线性无关 {gi(xˉ)iI}线, 若 x ˉ \bar{x} xˉ 是局部最优解, 则存在非负数 w i , i ∈ I , w_i, i \in I, wi,iI, 使得
    ▽ f ( x ˉ ) − ∑ i ∈ I w i ▽ g i ( x ˉ ) = 0 \bigtriangledown f(\bar{x}) - \sum\limits_{i \in I} w_i \bigtriangledown g_i(\bar{x}) = 0 f(xˉ)iIwigi(xˉ)=0

在这里插入图片描述
凸规划的判别方法:

  1. 可行域是凸集, 目标函数是凸函数
  2. 可行域是 ≥ \geq 的凹函数, 目标函数是凸函数

求KKT点

  • KKT条件的另一种表述
    x ˉ ∈ S \bar{x} \in S xˉS , f , g i ( i ∈ I ) 在 x ˉ f, g_i(i \in I)在\bar{x} f,gi(iI)xˉ 处可微, { ▽ g i ( x ˉ ) ∣ i ∈ I } 线 性 无 关 \{ \bigtriangledown g_i(\bar{x}) | i \in I\}线性无关 {gi(xˉ)iI}线, 若 x ˉ \bar{x} xˉ 是局部最优解, 则存在非负数 w i , i = 1 , 2... m w_i, i =1,2...m wi,i=1,2...m 使得
    { ▽ f ( x ˉ ) − ∑ i = 1 m w i ▽ g i ( x ˉ ) = 0 ( 没 要 求 对 应 的 g i ( x ) 为 约 束 条 件 ) w i g i ( x ˉ ) = 0 , i = 1 , 2... m ( 互 补 松 弛 条 件 ) w i ≥ 0 i = 1 , 2... m \left \{\begin{matrix} \bigtriangledown f(\bar{x}) - \sum\limits_{i = 1}^{m} w_i \bigtriangledown g_i(\bar{x}) = 0(没要求对应的g_i(x)为约束条件) \\ \\w_ig_i(\bar{x}) = 0, i = 1, 2...m (互补松弛条件) \\ \\ w_i \geq 0 i = 1,2...m \end {matrix} \right. f(xˉ)i=1mwigi(xˉ)=0(gi(x))wigi(xˉ)=0,i=1,2...mwi0i=1,2...m

通过这个表述方式,加上原来的约束然后将所有的方程列出来求解
在这里插入图片描述
在这里插入图片描述
有人会算的话请留言,感谢

下一篇

最优化理论复习–最优性条件(二)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/302761.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

小程序如何设置客服

​小程序客服功能可以帮助企业与用户建立更紧密的联系&#xff0c;提供更好的服务体验。本文将介绍如何在小程序中设置客服功能&#xff0c;以及一些提高客服效率和用户满意度的最佳实践。 1. 登录mp.weixin.qq.com&#xff0c;在侧边栏找到功能->客服&#xff0c;支持设置…

基于Java SSM框架实现校园网络维修系统项目【项目源码】

基于java的SSM框架实现校园网络维修系统演示 java简介 Java主要采用CORBA技术和安全模型&#xff0c;可以在互联网应用的数据保护。它还提供了对EJB&#xff08;Enterprise JavaBeans&#xff09;的全面支持&#xff0c;java servlet API&#xff0c;JSP&#xff08;java serve…

docker部署awvs

docker部署awvs cantos部署docker点这里 下载镜像 docker pull xiaomimi8/awvs14-log4j-2022 docker images 查看本地所有镜像启动镜像 docker run -it -d&#xff08;后台运行&#xff09; -p&#xff08;端口映射&#xff09; 13443&#xff08;主机端口&#xff09;:3443&…

第一个Java网络爬虫程序

目录 前言第一个Java网络爬虫程序总结 前言 网络爬虫是一种获取互联网信息的技术&#xff0c;它可以模拟浏览器行为&#xff0c;访问网站并提取所需的数据。在这个小Demo中&#xff0c;我们使用Java语言结合HttpClient库实现了一个简单的爬虫程序&#xff0c;用于抓取汽车之家…

【陈老板赠书活动 - 21期】- Python树莓派编程从零开始(第3版)

陈老老老板&#x1f9d9;‍♂️ &#x1f46e;‍♂️本文专栏&#xff1a;赠书活动专栏&#xff08;为大家争取的福利&#xff0c;免费送书&#xff09; &#x1f934;本文简述&#xff1a;活就像海洋,只有意志坚强的人,才能到达彼岸。 &#x1f473;‍♂️上一篇文章&#xff…

鸿蒙设备-开发板基础学习(BearPi-HM Micro)

theme: minimalism 每当学习一门新的编程语言或者上手一款新的开发板&#xff0c;在学习鸿蒙设备开发过程中&#xff0c;带大家写的第一个程序&#xff0c;通过这个程序&#xff0c;我们可以对鸿蒙设备开发的整个流程有一个初步的体验。BearPi-HM Micro开发板为例&#xff1a;…

数据结构-测试4

一、判断题 1.队列结构的顺序存储会产生假溢出现象。 &#xff08;T&#xff09; 2.度为二的树就是二叉树。(F) 二叉树的度可以小于等于2 3. 栈是插入和删除只能在一端进行的线性表&#xff1b;队列是插入在一端进行&#xff0c;删除在另一端进行的线性表。&#xff08;T&…

代码随想录算法训练营第二十四天 | 回溯算法

理论基础 代码随想录原文 什么是回溯法 回溯也可以叫做回溯搜索法&#xff0c;它是一种搜索的方式。 回溯是递归的副产品&#xff0c;只要有递归就会有回溯。 回溯法的效率 虽然回溯法很难&#xff0c;不好理解&#xff0c;但是回溯法并不是什么高效的算法。因为回溯的本…

对接讯飞聊天机器人接口--复盘

1、准备工作 1&#xff09;、进入以下平台进行注册&#xff0c;登录后&#xff0c;点击红框处 2&#xff09;、点击个人免费包&#xff08;会弹出实名认证&#xff0c;先进行实名认证&#xff09; 3&#xff09;、认证后&#xff0c;会进入以下界面&#xff0c;先添加应用 4&am…

栈的经典算法问题(算法村第四关白银挑战)

括号匹配问题 有效的括号 20. 有效的括号 - 力扣&#xff08;LeetCode&#xff09; 给定一个只包括 (&#xff0c;)&#xff0c;{&#xff0c;}&#xff0c;[&#xff0c;] 的字符串 s &#xff0c;判断字符串是否有效。 有效字符串需满足&#xff1a; 左括号必须用相同类…

滴水逆向1

八进制加法乘法表 EF11101111 j记住其映射关系 十进制的定义&#xff1a;由十个符号组成&#xff0c;分别是0 1 2 3 4 5 6 7 8 9 逢十进一。九进制的定义&#xff1a;由九个符号组成&#xff0c;分别是0 1 2 3 4 5 6 7 8 逢九进一。十六进制的定义&#xff1a;由十六个符号组成…

鸿蒙开发解决agconnect sdk not initialized. please call initialize()

文章目录 项目场景:问题描述原因分析:解决方案:总结:项目场景: 鸿蒙开发报错: agconnect sdk not initialized. please call initialize() 问题描述 报错内容为: 10-25 11:41:01.152 6076-16676 E A0c0d0/JSApp: app Log: 数据查询失败: {“code”:1100001,“messag…

在Kubernetes中优雅地导出和清理Ingress资源

引言 Kubernetes的Ingress资源是定义外部访问集群服务的规则。随着微服务架构和容器化技术的普及&#xff0c;Ingress作为路由流量的关键组件变得愈发重要。当我们需要在环境之间迁移Ingress资源或者备份当前的配置时&#xff0c;就会用到导出功能。然而&#xff0c;直接使用k…

听GPT 讲Rust源代码--compiler(29)

File: rust/compiler/rustc_const_eval/src/util/check_validity_requirement.rs 在Rust编译器的源代码中&#xff0c;rust/compiler/rustc_const_eval/src/util/check_validity_requirement.rs文件的作用是进行验证要求的检查。具体而言&#xff0c;该文件定义了函数check_val…

一文讲透使用Python绘制双纵轴线图

双纵轴线图主要用来展示两个因变量和一个自变量的关系&#xff0c;并且两个因变量的数值单位不同。具体来说&#xff0c;双纵轴线图是指在一幅图上有一个横轴和两个纵轴&#xff0c;适用于三个变量。两个纵轴分别表示一个变量&#xff0c;横轴变量同时适用于两个纵轴上的变量&a…

C++力扣题目--94,144,145二叉树非递归(迭代)遍历

为什么可以用迭代法&#xff08;非递归的方式&#xff09;来实现二叉树的前后中序遍历呢&#xff1f; 我们在栈与队列&#xff1a;匹配问题都是栈的强项 (opens new window)中提到了&#xff0c;递归的实现就是&#xff1a;每一次递归调用都会把函数的局部变量、参数值和返回地…

Azure Machine Learning - 人脸识别任务概述与技术实战

Azure AI 人脸服务提供了可检测、识别和分析图像中的人脸的 AI 算法。 人脸识别软件在许多不同情形中都十分重要&#xff0c;例如识别、无接触访问控制和实现隐私的人脸模糊。你可以通过客户端库 SDK&#xff0c;或者直接调用 REST API 使用人脸服务。 目录 一、人脸识别服务场…

Python print()函数高级用法和 len()函数详解:获取字符串长度或字节数

Python print()函数高级用法 我们使用 print() 函数时&#xff0c;都只输出了一个变量&#xff0c;但实际上 print() 函数完全可以同时输出多个变量&#xff0c;而且它具有更多丰富的功能。 print() 函数的详细语法格式如下&#xff1a; print (value,...,sep,end\n,filesys.s…

词嵌入位置编码的实现(基于pytorch)

背景介绍 在transformers架构当中&#xff0c;对于词向量的输入需要加上原本词对应的位置信息&#xff0c;作为输入到模型中训练的input&#xff0c;那具体的位置编码如何实现呢&#xff1f;本篇博客就跟大家一起分享一下对应的步骤 位置编码的公式 对于词向量的位置编码的方…

LaTex引用字体变色

使用下面这条语句进行修改。 ‘citecolor’改变参考文献颜色&#xff0c; ‘linkcolor’改变图标公式引用的颜色&#xff0c; ‘urlcolor’ 文本网站超链接颜色。 \usepackage[colorlinks,bookmarksopen,bookmarksnumbered,citecolorblue, linkcolorblue, urlcolorblue]{hyper…