Questions tagged [lagrange-multipliers]

The method of Lagrange multipliers finds critical points (including maxima and minima) of a differentiable function subject to differentiable constraints.

Filter by
Sorted by
Tagged with
0 votes
0 answers
15 views

Trying to understand lagrange multiplier and lads

I’m trying to do the lagrange multiplier test manually accordig to the below text provided by my supervisor. I do not fully understand what he means. Could anyone maybe describe it in R syntax? He ...
user avatar
  • 1
0 votes
1 answer
34 views

deriving the optimal distribution

Let the input variable $X \in \mathcal{X}$ and the target variable $Y \in \mathcal{Y}$. For a fixed hypothesis $h \in \mathcal{H}$ I want to solve \begin{equation} \min_{p(X,Y)} \int_{\mathcal{X}}\...
user avatar
  • 27
1 vote
1 answer
37 views

incorporating a distribution constraint in a minimisation objective

For a given (convex) hypothesis $h \in \mathcal{H}$, and the variables $X \in \mathcal{X}$ and $Y \in \mathcal{Y}$ I have the following optimisation problem: \begin{equation} \min_{p(X,Y)} \int_{\...
user avatar
  • 27
1 vote
0 answers
28 views

Derivation of the SVM regression problem

EDIT: The terms at the end will not get cancelled as they involve different variables: $\alpha$ and $\alpha^*$, etc. Now the post is corrected. I will leave this question here in case someone is as ...
user avatar
  • 259
0 votes
0 answers
19 views

What's a Heterogenous time series and how does Lagrange multiplier test statistic relate to it?

I have two time series with me. Running analysis with fb KATS time series Analysis module, I get below values for heterogeneity. ...
user avatar
0 votes
0 answers
37 views

SVM: How to derive the KKT condition with soft margin term is quadratic?

I was reading the Introdunction to Data Mining (2013) when I came across this in section 5.5: $$ f(\textbf{w})=\frac{||\textbf{w}||^2}{2}+C\left(\sum^N_{i=1}\xi_i \right)^k $$ I found similar ...
user avatar
0 votes
0 answers
43 views

Why $\gamma$ in regularization term of XGBoost is defined as minimum loss reduction (not minimum squared loss reduction) and not substracted?

From the source https://xgboost.readthedocs.io/en/stable/tutorials/model.html I guess that the mean-squared error is optimized subjected to a constraint of minimum loss reduction. It appears like ...
user avatar
  • 11
0 votes
0 answers
30 views

Primal Problem of SVM

The primal problem of SVM is denoted as below. $$min_{w,b}\left(\phi \:\left(w\right)\right)=min_{w,b}\left(\frac{1}{2}w^Tw\right)$$ Subject to $$y_n\left(w^Tx_n+b\right)\ge 1,\:n=1,2,3,...,l$$ And If ...
user avatar
2 votes
1 answer
39 views

KKT Conditions for thresholds?

My main question is that when I use Lagrange Multipliers/KKT conditions to perform optimization with threshold constraints, I seem to get contradictory FOC. Here is a characteristic example: take an ...
user avatar
  • 23
0 votes
0 answers
23 views

Doubt about Lagrange Multiplier Statistics for q exclusions restrictions

For obtaining the Lagrange Multiplier Statistics I follow this steps (Wooldridge 2019, Introductory Econometrics): Regress $y$ on the restricted set of independent variables and consider the ...
user avatar
  • 69
0 votes
0 answers
23 views

Lagrangian multiplier with an equality constraint and an inequality constraint

I want to compute the maximum of a function $f(x)$ with an equality constraint, $g(x) = 0$ and an inequality constraint, $h(x)\geq 0 $. I would know what to do with only an equality constraint, or ...
user avatar
1 vote
0 answers
137 views

How to proof that the square of the half-margin of maximum-margin SVM is equal to the summation of lagrange multipliers given by SVM dual?

Can be show that the square of the half-margin of maximum-margin SVM is equal to the summation of Lagrange multipliers given by SVM dual? i.e, Let $ \rho = \dfrac{1}{w}\\ $ Show that: $$ \dfrac{1}{\...
user avatar
0 votes
1 answer
19 views

RSM and steepest ascent for new $x'$ coordinates

In Myers, Montgomery, & Anderson-Cook, C. M. (2016)$^1$ the authors provide (p. 235) a general methodology to find new $x'$ coordinates in the path of steepest ascent based on constrained ...
user avatar
2 votes
0 answers
53 views

Gradient descent finds local minima for a problem that can be formulated as a convex problem

I am trying to find $$ \min_W \|Y-XW \|_F^2$$ $$s.t. \exists ij, W_{ij}\geq0 $$ where X is input data and Y is the output data we try to fit to. This is a convex optimization problem that can be ...
user avatar
  • 271
2 votes
0 answers
53 views

Rewriting Lagrange Multiplier with non-linear optimization

NOTE: if you have access to the book mentioned below , please skip to the part of this post marked with (*), as I will now provide a short summary of the relevant background information for my ...
user avatar
  • 129
2 votes
0 answers
31 views

convex optimisation formulation of SVM

I am currently learning about Support Vector Machine's (SVM) from the CS229 Stanford Class. In page 16 of the notes, they transformed $$max_{\hat{\gamma}, w, b} \frac{\hat{\gamma}}{||w||} \\ s.t \,\,\,...
user avatar
  • 996
1 vote
1 answer
440 views

How to derive the $\ nR^2 $ form of the LM test statistic?

Several lagrange multiplier (LM) test statistics =$\ nR^2 $~$ \chi^2 $, where the LM test statistic is generated from regressing the square of residuals on some function in an auxiliary equation. The ...
user avatar
  • 63
0 votes
0 answers
35 views

Lagrange multiplier test statistic math

I'm trying to understand the how the Lagrange multiplier test statistic written like this: $$LM = \hat{d'}_1 (\hat{\phi}_{11}-\hat{\phi}_{12}\hat{\phi}_{22}^{-1}\hat{\phi}_{21})^{-1}\hat{d}_1 \...
user avatar
  • 63
1 vote
0 answers
22 views

Optimization problem for SVM with hard margin

I am trying to implement the SVM with hard margin from scratch. I have reduced the problem to finding the solution from the following optimisation problem $$ \operatorname{max}\limits_{\alpha}L(\alpha)...
user avatar
1 vote
0 answers
14 views

Score test using restricted mle

I am doing a study on Rao score test and still confused about the score vector. How am I supposed to calculate the score vector? Can I just use (ˆθn - θn) for the score vector? As I understood that ...
user avatar
  • 11
1 vote
1 answer
32 views

Rewrite $\frac{1}{2}||x-u||_2^2$ subject to $||x||_1\le c$ to lagrangian form with multiplier $\lambda \ge 0$

Rewrite $\frac{1}{2}||x-u||_2^2$ subject to $||x||_1\le c$ to lagrangian form with multiplier $\lambda \ge 0$ So I'm pretty new to converting constraint functions to Lagrangian form, but I read that ...
user avatar
0 votes
1 answer
46 views

Non-negative Constraints in Soft-Margin SVM Lagrange Equation

I was reading the A Tutorial on Support Vector Machines for Pattern Recognition as a supplemental for my Intro to ML class and I wasn't sure why $ a_i \geq 0 $ and $ \lambda_i \geq 0 $ cannot be ...
user avatar
  • 1
0 votes
1 answer
95 views

Finding the MLEs for pi in a contingency table proof

Reference: https://data.princeton.edu/wws509/notes/c5.pdf In a two-dimensional table, (the multinomial model - section 5.1.2 in the link above), I was wondering how they get $$\hat\pi_{i.} = \frac{y_{...
user avatar
2 votes
1 answer
94 views

Logarithms in Karush-Kuhn-Tucker conditions

I have the following optimization (and standarised) problem: $$minimize\ -(x\ ln(x)\ +\ y\ ln(y))$$ $$subject\ to\ \ \ \ \ \ \ \ \ \ \ \ \ x+y-1<=0$$ $$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ...
user avatar
2 votes
1 answer
189 views

Maximum Entropy Discrete Distribution

In Pattern Recognition and Machine Learning the author uses Lagrange multipliers to find the discrete distribution with maximum entropy. Entropy is defined by; $$H=-\sum_i p(x_i)\ln(p(x_i))$$ and the ...
user avatar
1 vote
0 answers
38 views

What is $\alpha$ in SVM Lagrangian fucntions

Is it a column matrix or a row matrix? I saw on a CMU slide that $\alpha$ is defined as $\alpha=(\alpha_1, \alpha_2, ..., \alpha_n)^T>=0$? I dont see much of a formal definition for the exact form ...
user avatar
1 vote
1 answer
43 views

Convert the following expression w.r.t to the whole dataset instead of element of the dataset?

I am in the process of expressing the w in LSSVM with data points and constants. After I resolve the KKT conditions for the LSSVM I got $$w = \sum ^N _{i=1} \alpha_i x_i$$ Is it possible to convert ...
user avatar
1 vote
1 answer
166 views

Minimize $f(A,B)$ s.t. $\text{exp}(A)^T \text{exp}(B)=J_K$

I have a function $f(A,B)$ that maps a pair of two (tall) matrices, $A$ and $B$, to a scalar cost that I want to minimize. $A$ and $B$ both have $K$ columns. I also want to impose a set of equality ...
user avatar
1 vote
0 answers
19 views

Lagrange Multiplier Test (Score Test) reliability at low likelihood

The Lagrange Multiplier Test (Score Test) in the multivariate case has the following formula: $$ LM = [\underline{s}(\underline{\theta_0})]^T*[Var(\underline{\theta_0})]^{-1}*\underline{s}(\underline{\...
user avatar
  • 31
0 votes
0 answers
111 views

What is the maximum entropy distribution with a mean of 0, stdev of 1, skew of 1 (instead of zero), and kurtosis of 1 (instead of 3)?

As we know, there are an infinite number of distributions with mean of zero and variance of one. One of the special things about the normal distribution is that is has the maximum entropy. (https://...
user avatar
  • 181
2 votes
2 answers
106 views

How to solve MNP (minimum norm) problem in SVM?

I'm reading an article, which says that MNP (minimum norm problem) can be solved as SVM. In the minimum norm problem, we're given a set of points in $R^d$ and need to find a point in convex hull of ...
user avatar
  • 201
0 votes
0 answers
282 views

Minimizing Mean Square Error

Suppose we have a random sample $\textbf{X}=(X_1,...,X_n)$ from a shifted exponential distribution with common density $f(x|\theta)=\left\{\begin{matrix} e^{-(x-\theta)} & x\geq \theta\\ 0 & ...
user avatar
2 votes
0 answers
63 views

What are Lagrange multiplier and Dual decomposition methods?

What are the Lagrange multiplier and Dual decomposition methods? How are these methods used in Machine Learning(ML) for Optimization?
user avatar
  • 2,461
1 vote
1 answer
305 views

Are Lagrange multipliers of regularization terms learned or set?

Background knowledge I knew about regularization in machine learning: A regularization term is added to the objective function to prevent overfitting. Usually, one would like to restrict the variance ...
user avatar
  • 135
4 votes
0 answers
195 views

How to prove the equivalence between constrained form and Lagrange form for lasso and ridge regression?

How to prove the equivalence between constrained form and Lagrange form for lasso and ridge regression? Given lasso (constrained form): $$\underset{\beta}{\min}{(\frac{1}{2N}||y-x\beta||_2^2)} \...
user avatar
1 vote
2 answers
3k views

Calculating the value of $b^{*}$ in an SVM

In Andrew Ng's notes on SVMs, he claims that once we solve the dual problem and get $\alpha^*$ we can calculate $w^*$ and consequently calculate $b^*$ from the primal to get equation (11) (see notes) ...
user avatar
  • 63
0 votes
0 answers
28 views

If the Lagrangian formulation also has constraints, what is then the simplification?

Consider the following constrained optimization problem. $$\begin{array}{ll} \text{minimize} & f(w)\\ \text{subject to} & g_{i}(w) \leq 0\\ & h_{j}(w) = 0\end{array}$$ The equivalent ...
user avatar
  • 141
1 vote
0 answers
74 views

Optimal proposal for the Metropolis-Hastings algorithm using Tierney's theorem

Let $(E,\mathcal E,\lambda)$ be a measure space $p:E\to[0,\infty)$ be $\mathcal E$-measurable with $$c:=\lambda p\in(0,\infty)$$ and $$\mu:=\underbrace{\frac1cp}_{=:\:\tilde p}\lambda$$ $q:E^2\to[0,\...
user avatar
  • 539
2 votes
0 answers
758 views

Solving constrained optimization problems with Adam

The adam algorithm has been very successful for solving non-convex optimization problems that appear in deep learning. Are there ways to extend adam to solve constrained optimization problems? Among ...
user avatar
  • 245
1 vote
1 answer
40 views

why in SVM we have different indices for dot product?

I am confused by Lagrangian method in SVM, I can not understand why we use different indices in dot product. Suppose with using Lagrangian W is : $ W_{i}=\sum_{i}L_{i}y_{i}x_{i} $ In SVM ...
user avatar
1 vote
0 answers
103 views

why we use Lagrangian method in SVM?

I am wondering why we are using Lagrangian method in SVM? if we have just 3 features and 1000 rows, then objective function would be $w_{1}^{2}+w_{2}^{2}+w_{3}^{2}$ but if we use Lagrangian then we ...
user avatar
  • 137
1 vote
0 answers
22 views

how we can constraints in dual of lagrangian?

I am confused about the general rule of Lagrangian multiplier. (which usully use for SVM). I could not find a good book or paper that explain it completely and clearly. Suppose we have $$minimize: ...
user avatar
  • 137
3 votes
0 answers
83 views

Maximum entropy probability distribution over non-negative support and finite mean?

I'm trying to derive which univariate probability distribution maximizes entropy, assuming finite mean $\mu$ and non-negative support $[0, \infty)$. I know that the answer is the exponential ...
user avatar
4 votes
1 answer
2k views

How to choose between dual gradient descent and the method of Lagrangian multipliers?

For an optimization problem $$ \max f(x)\\\ s.t. g(x)\le 0 $$ The Lagrangian is $$ \mathcal L(x, \lambda)=f(x)-\lambda g(x) $$ Dual gradient descent solves it by (according to Page 43 of this lecture,...
user avatar
  • 985
1 vote
0 answers
35 views

Wide variety of results in Breusch-Pagan Tests on simulated data?

I wanted to see how the results of the BP-test would come out. This stemmed from a debate with someone who claimed that the BP-test would start rejecting the null hypothesis of homoskedasticity even ...
user avatar
  • 851
1 vote
0 answers
647 views

How do we know we're maximizing the Lagrangian objective function in PCA?

In Principal Component Analysis, we start with $m$ observations $x_1,\dots,x_m$, each of which is an $n$-dimensional vector. Assume we have centered the data; that is, we have subtracted the variable ...
user avatar
0 votes
1 answer
93 views

What would happen to the solution of primal SVM problem we had 0 in constraint instead of 1

That is, what if the constraint was $y^i(w^Tx^i + b) ≥ 0$
user avatar
1 vote
0 answers
26 views

Finding three coefficients (weight/ratio) by minimising variance

I am finding the value of a,b and c for minimising the variance of the following equation (four variables are correlated): $$ Var(\Delta V)=V ar[\Delta S-a\Delta F_1 - b\Delta F_2 -c\Delta F_3] $$ ...
user avatar
4 votes
1 answer
1k views

Gradient descent in SVM

I am studying about SVM now. Then I came across the problem. The dual optimization problem is as follows: \begin{align*} &\max_\alpha~~~~~ W(\alpha) = \sum_{i=1}^{n} \alpha_i -\frac{1}{2}\...
user avatar
  • 1,089
3 votes
0 answers
296 views

Support Vector Machines: a beginner's question about the underlying math

I'm new to Support Vector Machines and I've been trying to get into the underlying math (instead of just using Scikit Learn or something like that). I understand the math behind it up to the point ...
user avatar
  • 139