DoraemonJack Blog

「离开世界之前 一切都是过程」

最优化方法——最速下降法与共轭梯度法

迭代公式、几何直观与中等难度例题

最速下降法(Steepest Descent, SD)和共轭梯度法(Conjugate Gradient, CG)是经典的一阶迭代优化方法。SD以“最陡方向”作为下降方向,配合(一维)线搜索求步长;CG在二次型与对称正定(SPD)情形下能在至多 n 步内精确收敛,且在大规模稀疏问题中极为高效。本文给出两法的迭代公式、收敛要点与中等难度例题推导,并在末尾做对比。 推荐阅读: 共轭梯...

最优化基础——KKT条件

约束优化问题的核心最优性条件

KKT条件(Karush-Kuhn-Tucker条件)是约束优化理论中最重要的最优性条件之一。它提供了在约束条件下判断局部最优解的必要条件,是拉格朗日乘数法的推广。本文将从几何直观出发,深入讲解KKT条件的理论基础、几何意义和实际应用。 一、KKT条件的背景 1.1 从拉格朗日乘数法到KKT条件 在无约束优化问题中,我们通过梯度为零来寻找最优解: \(\nabla f(x^*) = 0...

最优化理论——基础(凸集,凸函数,共轭函数等)

从凸分析到对偶理论的数学基础

最优化理论是现代数学和工程学的重要分支,其核心建立在凸分析和对偶理论的基础之上。本文将从最基础的凸集和凸函数概念出发,逐步深入到共轭函数、拉格朗日对偶等高级理论,为读者构建完整的最优化理论基础。 一、凸集理论 1.1 凸集的定义 定义1.1 设 $C \subseteq \mathbb{R}^n$,如果对于任意 $x_1, x_2 \in C$ 和任意 $\lambda \in [0,...

最优化理论 —— 内点法

在可行域内部寻找最优解的经典方法

内点法(Interior Point Method)是求解约束优化问题的重要方法之一,与惩罚函数外点法不同,内点法要求搜索点始终保持在可行域内部。其基本思想是通过构造障碍函数(Barrier Function)来替代约束条件,将约束优化问题转化为无约束优化问题,同时确保迭代点始终在可行域内部。 一、非线性规划模型 \[\begin{cases} \min & f(\boldsym...

数据结构——树结构

深入理解树结构的基本概念、遍历算法和实际应用

树结构:二叉树、树、二叉排序树等数据结构表示、遍历与实现 树结构是计算机科学中最重要的数据结构之一,广泛应用于文件系统、数据库索引、编译器语法分析等领域。本文将深入探讨树的基本概念、二叉树的表示与遍历、二叉排序树的实现,以及相关的算法应用。 1. 树的基本概念和术语 1.1 树和森林的定义 树(Tree)是由n个节点组成的有限集合,其中: 有且仅有一个根节点 其余节点可分...

数据结构——算法设计方法

用动态图表理解五大算法设计方法

本文通过可视化图表深入讲解五种经典算法设计技术的核心思路和执行流程。 1. 分治法 (Divide and Conquer) 核心思想 将大问题分解为小问题,递归解决小问题,然后合并结果。 分治法流程图 流程图示例 graph LR A --- B B --> C[Happy] B --> D(Sad) graph TD A["大问...

数据结构——经典排序算法归类总结

从原理到实现,对比九种排序算法

排序算法是计算机科学中最基础也是最重要的算法之一。本文基于实际代码实现,深入分析九种经典排序算法的原理、时间复杂度、空间复杂度和稳定性,并提供详细的对比表格。 一、基础排序算法 1.1 插入排序 (Insertion Sort) 算法原理:将数组分为已排序和未排序两部分,每次从未排序部分取出一个元素,插入到已排序部分的正确位置。 1 2 3 4 5 6 7 8 9 10 11 12 ...

最优化理论 —— 惩罚函数-外点法

将约束优化转化为无约束优化的经典方法

惩罚函数法又称乘子法,是将约束优化问题转换为无约束优化问题的方法之一。其基本思想就是通过在原始的目标函数中添加一个障碍函数(也可以理解成惩罚函数)来代替约束条件中的不等式约束。如果当前解不满足约束条件,就在目标项上加上一个正向的惩罚(这里考虑的都是最小化问题),强迫当前解往可行域的方向走。至于正向惩罚的力度,取决于所用的映射函数,即惩罚函数。 一、非线性规划模型 \[\begin{cas...

从零搭建我的博客工作流

Jekyll + GitHub Pages 实战记录

这是一篇用于验证站点构建与首页展示的示例文章,也记录了我本地开发与发布的最小工作流。 目标 用最少的配置跑通本地开发 写一篇能出现在首页的文章 推送到 GitHub Pages 自动发布 本地开发命令 1 2 bundle exec jekyll clean bundle exec jekyll serve 打开浏览器访问:http://localhost...

Hello World

我的第一篇博客模板

写在前面:用这篇模板快速开始你的第一篇文章,替换标题、副标题、时间与标签即可。 前言 这里写文章的背景、动机或摘要等。121313 一、基础表情符号 1.1 常用箭头和指示符号 👉 指向右 👈 指向左 👆 指向上 👇 指向下 ⬅️ 左箭头 ➡️ 右箭头 ⬆️ 上箭头 ⬇️ 下箭头 ↖️ 左上箭头 ↗️ 右上箭头 ↙️ 左下箭头 ↘️ 右下箭头 🔄 循环箭头 ⏪ 快退 ⏩ 快进...