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

2024-01-09 01:28

本文主要是介绍最优化理论分析复习--最优性条件(一),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

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

上一篇

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

无约束问题的极值条件

由于是拓展到向量空间 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

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

下一篇

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

这篇关于最优化理论分析复习--最优性条件(一)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/585491

相关文章

Spring 中 BeanFactoryPostProcessor 的作用和示例源码分析

《Spring中BeanFactoryPostProcessor的作用和示例源码分析》Spring的BeanFactoryPostProcessor是容器初始化的扩展接口,允许在Bean实例化前... 目录一、概览1. 核心定位2. 核心功能详解3. 关键特性二、Spring 内置的 BeanFactory

MyBatis-Plus中Service接口的lambdaUpdate用法及实例分析

《MyBatis-Plus中Service接口的lambdaUpdate用法及实例分析》本文将详细讲解MyBatis-Plus中的lambdaUpdate用法,并提供丰富的案例来帮助读者更好地理解和应... 目录深入探索MyBATis-Plus中Service接口的lambdaUpdate用法及示例案例背景

MyBatis-Plus中静态工具Db的多种用法及实例分析

《MyBatis-Plus中静态工具Db的多种用法及实例分析》本文将详细讲解MyBatis-Plus中静态工具Db的各种用法,并结合具体案例进行演示和说明,具有很好的参考价值,希望对大家有所帮助,如有... 目录MyBATis-Plus中静态工具Db的多种用法及实例案例背景使用静态工具Db进行数据库操作插入

Nginx中location实现多条件匹配的方法详解

《Nginx中location实现多条件匹配的方法详解》在Nginx中,location指令用于匹配请求的URI,虽然location本身是基于单一匹配规则的,但可以通过多种方式实现多个条件的匹配逻辑... 目录1. 概述2. 实现多条件匹配的方式2.1 使用多个 location 块2.2 使用正则表达式

Go使用pprof进行CPU,内存和阻塞情况分析

《Go使用pprof进行CPU,内存和阻塞情况分析》Go语言提供了强大的pprof工具,用于分析CPU、内存、Goroutine阻塞等性能问题,帮助开发者优化程序,提高运行效率,下面我们就来深入了解下... 目录1. pprof 介绍2. 快速上手:启用 pprof3. CPU Profiling:分析 C

MySQL表锁、页面锁和行锁的作用及其优缺点对比分析

《MySQL表锁、页面锁和行锁的作用及其优缺点对比分析》MySQL中的表锁、页面锁和行锁各有特点,适用于不同的场景,表锁锁定整个表,适用于批量操作和MyISAM存储引擎,页面锁锁定数据页,适用于旧版本... 目录1. 表锁(Table Lock)2. 页面锁(Page Lock)3. 行锁(Row Lock

Springboot中分析SQL性能的两种方式详解

《Springboot中分析SQL性能的两种方式详解》文章介绍了SQL性能分析的两种方式:MyBatis-Plus性能分析插件和p6spy框架,MyBatis-Plus插件配置简单,适用于开发和测试环... 目录SQL性能分析的两种方式:功能介绍实现方式:实现步骤:SQL性能分析的两种方式:功能介绍记录

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列(LCS)问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动

C#使用DeepSeek API实现自然语言处理,文本分类和情感分析

《C#使用DeepSeekAPI实现自然语言处理,文本分类和情感分析》在C#中使用DeepSeekAPI可以实现多种功能,例如自然语言处理、文本分类、情感分析等,本文主要为大家介绍了具体实现步骤,... 目录准备工作文本生成文本分类问答系统代码生成翻译功能文本摘要文本校对图像描述生成总结在C#中使用Deep

详解如何在React中执行条件渲染

《详解如何在React中执行条件渲染》在现代Web开发中,React作为一种流行的JavaScript库,为开发者提供了一种高效构建用户界面的方式,条件渲染是React中的一个关键概念,本文将深入探讨... 目录引言什么是条件渲染?基础示例使用逻辑与运算符(&&)使用条件语句列表中的条件渲染总结引言在现代