Machine Learning
  • Introduction
  • man
  • Linear model
    • Linear Regression
    • Generalized Linear Models
    • Nonlinear regression
  • bayes
    • bayesian network
    • Variational Bayesian inference
    • Gaussian Process Regression
  • Logistic Regression
    • L1 regularization
    • L2 regularization
    • softmax
    • Overflow and Underflow
  • SVM
    • C-SVM
    • C-SVM求解
  • EM
    • GMM
  • Maximum Entropy
    • IIS
  • HMM
    • viterbi algorithm
  • CRF
  • Random Forest
    • bagging
    • random forest
  • boosting
    • catboost
    • gradient boosting
    • Newton Boosting
    • online boosting
    • gcForest
    • Mixture models
    • XGBoost
    • lightGBM
    • SecureBoost
  • LDA
  • rank
    • RankNet
    • LambdaRank
    • SimRank
  • Factorization Machine
    • Field-aware Factorization Machine
    • xdeepFM
  • Clustering
    • BIRCH
    • Deep Embedding Clustering
  • Kalman filtering
  • word2vec
  • 关联规则挖掘
  • MATH-Mathematical Analysis
    • measure
  • MATH-probability
    • Variational Inference
    • Dirichlet分布
    • Gibbs Sampling
    • Maximum entropy probability distribution
    • Conjugate prior
    • Gaussian Process
    • Markov process
    • Poisson process
    • measure
    • Gumbel
  • MATH-Linear Algebra
    • SVD
    • SVD-推荐
    • PCA
    • Linear Discriminant Analysis
    • Nonnegative Matrix Factorization
  • MATH-Convex optimization
    • 梯度下降
    • 随机梯度下降
    • 牛顿法
    • L-BFGS
    • 最速下降法
    • 坐标下降法
    • OWL-QN
    • 对偶问题
    • 障碍函数法
    • 原对偶内点法
    • ISTA
    • ADMM
    • SAG
  • MATH-碎碎念
    • cost function
    • Learning Theory
    • sampling
    • Entropy
    • variational inference
    • basis function
    • Diffie–Hellman key exchange
    • wavelet transform
    • 图
    • Portfolio
    • 凯利公式
  • ML碎碎念
    • 特征
    • test
    • TF-IDF
    • population stability index
    • Shapley Values
  • 课件
    • xgboost算法演进
  • Time Series
  • PID
  • graph
    • SimRank
    • community detection
    • FRAUDAR
    • Anti-Trust Rank
    • Struc2Vec
    • graph theory
    • GNN
  • Anomaly Detection
    • Isolation Forest
    • Time Series
  • Dimensionality Reduction
    • Deep Embedded Clustering
  • Federated Learning
  • automl
  • Look-alike
  • KNN
  • causal inference
Powered by GitBook
On this page

Was this helpful?

  1. MATH-Convex optimization

对偶问题

PreviousOWL-QNNext障碍函数法

Last updated 5 years ago

Was this helpful?

绿线标出的是约束g(x,y)=cg(x,y)=cg(x,y)=c的点的轨迹。蓝线是f(x,y)f(x,y)f(x,y)的等高线。箭头表示斜率,和等高线的法线平行。从梯度的方向上来看,显然有d1>d2d1 \gt d2d1>d2。绿色的线是约束,也就是说,只要正好落在这条绿线上的点才可能是满足要求的点。如果没有这条约束,f(x,y)f(x,y)f(x,y)的最小值应该会落在最小那圈等高线内部的某一点上。而现在加上了约束,最小值点应该在哪里呢?显然应该是在f(x,y)的等高线正好和约束线相切的位置,因为如果只是相交意味着肯定还存在其它的等高线在该条等高线的内部或者外部,使得新的等高线与目标函数的交点的值更大或者更小,只有到等高线与目标函数的曲线相切的时候,可能取得最优值。

如果我们对约束也求梯度∇g(x,y)\nabla g(x,y)∇g(x,y),则其梯度如图中绿色箭头所示。很容易看出来,要想让目标函数f(x,y)f(x,y)f(x,y)的等高线和约束相切,则他们切点的梯度一定在一条直线上(f和g的斜率平行)。

也即在最优化解的时候:∇f(x,y)=λ(∇g(x,y)−C)\nabla f(x,y) = \lambda (\nabla g(x,y) - C)∇f(x,y)=λ(∇g(x,y)−C) , 即:∇[f(x,y)+λg(x,y)−C]=0,λ≠0\nabla [f(x,y) + \lambda g(x,y) - C] = 0, \lambda \neq 0∇[f(x,y)+λg(x,y)−C]=0,λ=0

关于拉格朗日乘子法与KKT条件
Lagrange 是怎么想出来Lagrange乘子法的