Questions tagged [lagrange-multipliers]
The method of Lagrange multipliers finds critical points (including maxima and minima) of a differentiable function subject to differentiable constraints.
69
questions
0
votes
0
answers
67
views
Estimating the parameter of a Bernoulli distribution using probabilistic modeling and the MAP estimation
Suppose you tossed a coin multiple times. Sometimes you got heads and other times you got tails. You recorded your experiment in a dataset $ X$. Now you want to estimate the parameter θ (which ...
- 272
1
vote
0
answers
29
views
Why is there only a box constraint on alpha and not on mu when solving the dual problem of soft linear SVM?
I am currently learning about the linear SVM in the non-separable case. In the dual representation, we introduce the Lagrange multipliers μk and αk (see also this source: https://...
1
vote
0
answers
19
views
Are solutions to the Lagrangian multipliers ($\alpha_i$) in a hard-margin SVM unique?
An intermediate step in the derivation of the hard-margin SVM's dual form is as follows:
I also know that $a_i$ for all points not on the margin boundary is 0, which makes sense; they must be zeroed ...
0
votes
0
answers
15
views
The distribution of a score test statistic in a special case
Suppose that we want to test a restriction $\alpha=0$.
Unfortunately, we cannot directly estimate the parameter of interest $\alpha$.
Instead, we can calculate the log-likelihood functions with and ...
- 191
1
vote
0
answers
16
views
Min max formulation conversion to max min formulation. Reason?
Question is based on the screenshot attached. Based on paper here.
I am not being able to understand why min max formulation (eq 4) is first converted to max min formulation (eq 5). Is it something ...
- 11
0
votes
0
answers
21
views
Subspace test for multivariate normal distribution [duplicate]
Subspace test for multivariate normal distribution
Suppose $X_1, X_2,\ldots, X_n$ are i.i.d. observations from a multivariate normal distribution $N(\mu,\Sigma)$ where $\Sigma$ is known. Furthermore, ...
- 1
1
vote
0
answers
53
views
Can we convert the optimization of a loss function with regularization to the Lagrangian, constrained optimization *before* solving the optimization?
It is shown here that the optimization of a loss function with regularization,
$$\text{argmin}_b L(X,b) + c ||b||_p \phantom{aaaaaaaaaaaaaaaaaaaaaaaa} (*)$$
is equivalent to the constrained ...
- 371
0
votes
0
answers
28
views
Cannot understand the bound of Lagrangian parameter in SMO
I'm trying to understand SMO, but stuck to the part of bound for Lagrangian parameters.
In the SMO paper(https://www.microsoft.com/en-us/research/uploads/prod/1998/04/sequential-minimal-optimization....
1
vote
1
answer
173
views
How to maximize the ELBO in coordinate ascent variational inference
In the lecture by D.Blei: https://www.cs.princeton.edu/courses/archive/fall11/cos597C/lectures/variational-inference-i.pdf
Variational inference is explained and he shows how to derive the optimal ...
- 379
0
votes
1
answer
48
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}}\...
- 127
1
vote
1
answer
38
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_{\...
- 127
1
vote
0
answers
102
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 ...
- 269
0
votes
0
answers
212
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 ...
- 11
3
votes
1
answer
88
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 ...
- 75
1
vote
0
answers
229
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}{\...
- 21
0
votes
1
answer
27
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 ...
- 35
2
votes
0
answers
69
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 ...
- 281
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 ...
- 129
2
votes
0
answers
38
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 \,\,\,...
- 1,116
3
votes
1
answer
2k
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 ...
- 83
0
votes
0
answers
69
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
\...
- 83
1
vote
0
answers
30
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)...
- 41
1
vote
0
answers
24
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 ...
- 11
1
vote
1
answer
35
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 ...
- 710
0
votes
1
answer
94
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 ...
- 1
0
votes
1
answer
216
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_{...
- 23
2
votes
1
answer
183
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$$
$$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ...
2
votes
1
answer
320
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 ...
- 259
1
vote
0
answers
77
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 ...
- 55
1
vote
1
answer
46
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 ...
- 55
2
votes
1
answer
176
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 ...
- 7,049
1
vote
0
answers
56
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{\...
- 41
0
votes
0
answers
186
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://...
- 251
3
votes
2
answers
169
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 ...
- 211
0
votes
0
answers
451
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 & ...
2
votes
0
answers
81
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?
- 2,785
1
vote
1
answer
553
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 ...
- 145
4
votes
0
answers
276
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)} \...
- 477
2
votes
2
answers
6k
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)
...
- 73
0
votes
0
answers
31
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 ...
- 141
1
vote
0
answers
86
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,\...
- 141
3
votes
0
answers
1k
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 ...
- 265
1
vote
1
answer
43
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 ...
- 113
1
vote
0
answers
123
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 ...
- 137
1
vote
0
answers
25
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: ...
- 137
3
votes
0
answers
147
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 ...
- 935
6
votes
1
answer
3k
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,...
- 1,065
1
vote
0
answers
45
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 ...
- 891
1
vote
0
answers
784
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 ...
- 145
0
votes
1
answer
102
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$
