For questions on Lagrange multipliers, a strategy to solve constrained optimisation problems.

learn more… | top users | synonyms

0
votes
0answers
16 views

Lagrange's multipliers exercise

Can you help me to understand what to do in the following question? The question is just to choose one alternative, justifying your answer. Which of the following sets of restrictions and points ...
4
votes
3answers
384 views

Augmented Lagrangian

Consider the following equality constraint minimization problem: minimize $\text{ }f(x)$ subject to $Ax=b$ Its Lagrangian is then: $L(x,y) = f(x) + y^T(Ax-b)$ We can use then gradient ascent to ...
0
votes
1answer
633 views

When using the method of Lagrangian multipliers, does it matter whether I subtract or add the lambda term?

As I understand it, the method of Lagrangian multipliers follows the form Minimize $f(x,y)$ subject to constraint $g(x,y)= c$ and involves an equation of the form $L(x,y,\lambda) = f(x,y) + \...
2
votes
3answers
49 views

How can I solve an optimization problem $x^T A x$ with constraint $x^T x = 1$?

Let $A \in \mathbb{R}^{n \times n}$ be a positive definite matrix. \begin{align} &\operatorname*{minimize}_{x \in \mathbb{R}^n} & & x^T A x \\ &\text{subject to} ...
0
votes
1answer
19 views

SVM: How to normalize |WX| > 0 into |WX| = 1

Question What are the reason/basis/rationale and the actual steps and design/mechanism behind to do the normalization to convert |WX| > 0 into |WX| = 1 in the process of getting the optimal W for the ...
3
votes
1answer
56 views

Working with Lagrange multipliers, reducing gradients is okay, right?

I am employing the method of Lagrange multipliers to determine a maximum. As part of this, I arrive at the following equation involving two gradients and the parameter $\lambda$, as is common for ...
0
votes
1answer
23 views

Prove this property of the Hessian

I have been reading about the hessian for a scholar work about optimization and I find this property: Let be $H_{P_0}$ the determinant of the hessian matrix for the Lagrangian function $\mathscr{L}(x,...
2
votes
4answers
67 views

Find the maximum of $U (x,y) = x^\alpha y^\beta$ subject to $I = px + qy$

Let be $U (x,y) = x^\alpha y^\beta$. Find the maximum of the function $U(x,y)$ subject to the equality constraint $I = px + qy$. I have tried to use the Lagrangian function to find the solution for ...
0
votes
1answer
40 views

Find the maximum and minimum values in a range

I'm trying to understand how to find the minimum & maximum values of this function: $$ f(x,y) = xy-y^2 $$ In the following range D: $$ D = \{(x,y) \in R^2 : 0 \leq x \leq 1, |y| \leq x^2 \} $$ ...
1
vote
1answer
28 views

Properties on proximal term

If the equation $x_i$-subproblem showed below is not strictly convex $\arg \min_{x_i}=f_i(x_i)+\frac{\rho}{2}\|A_ix_i+\sum_{j\neq i}A_jx_j^k-c-\frac{\lambda^k}{\rho}\|_2^2$ Why adding the proximal ...
0
votes
1answer
409 views

How can I find the minimum distance between the origin $(0,0)$ and the curve $y=1-x^2$ using Lagrange multipliers?

I used the curve as the constraint and the origin as the point but I am not sure if that is correct.
1
vote
1answer
20 views

Optimization: Via manifolds point of view of Lagrange multipliers method

My basis on differential manifolds calculus and differential geometry being very superficial, I'm trying to understand this section on WP's article. I'm not being able to realize why most of the ...
1
vote
1answer
40 views

Proving inequality using Lagrange multipliers

I have this question. Prove that for all $ x,y\geq 0 $, $$ \dfrac{x^n+y^n}{2}\geq \bigg(\dfrac{x+y}{2}\bigg)^n $$ using the method of Lagrange Multipliers, via $$ \min \dfrac{x^n+y^n}{2}, \text{where $...
0
votes
2answers
45 views

The shortest distance from surface to a point

Many have asked the question about finding the shortest distance from a point to a plane. I have checked those questions and answers and haven't found what I am looking for. Might still have missed ...
1
vote
0answers
25 views

If $p_1 < p_2 < \cdots<p_M $ for some PMF $(p_j)$ then $\sum\limits_{j=1}^{M}(j-1)p_j \geq \frac{(M-1)}{2}$

For any positive integer $M$ and probabilities $p_j$ for $j=1,2,...,M$, which are arranged in ascending order, i.e. $p_1 < p_2 < ...<p_M $, one has $\sum\limits_{j=1}^{M}(j-1)p_j \geq \...
0
votes
1answer
55 views

Messy system with Langrange multipliers

$f(x,y) = (3-x)(3-y)(x+y-3)$ I'm trying to find and classify the critical points of the former function. I have that $$\displaystyle\frac{\partial f}{\partial x} = (3-y)(-x^2-xy+2x+3) \\\...
1
vote
0answers
23 views

Constrained optimization problem using Largange multipliers: ellipsoid collision detection and response

This one is purely for the mathematics so the result is far less important than the method itself. My task is to implement a fast and efficient ellipsoid collision detection and response algorithm. ...
2
votes
1answer
199 views

Least-squares problem with quadratic equality constraint

I want to find the solution of a Lagrange equation whose inputs are matrices. First I have the equation Ax=0. By decomposing $A$ into $A_3$ (columns 9 to 11 of A), $A_9$ (the rest of the columns), ...
0
votes
1answer
35 views

Minima of symmetric polynomials subject to two symmetric constraints

The homogeneous symmetric polynomial of degree $k$ in $n$ variables is $$ f_k(x_1,x_2,\dots,x_n) = \sum_{i_1<i_2<\cdots<i_k}x_{i_1}x_{i_2}\cdots x_{i_k}. $$ Consider the following ...
1
vote
1answer
24 views

Problem about find the extreme of a function (Multipliers of Lagrange)

Good morning, i have a problem with this: Find the maximum and minimum distances from the origin to the curve $g\left(x,y\right)=5x^{2}+6xy+5y^{2}$ I make this: Function to optimize: $f\left(x,y\...
1
vote
2answers
36 views

Maximizing the sum of the squares of numbers whose sum is constant

I wonder how one goes about to find the maximum of $\sum v_i^2$, the $v_i$'s being positive integers whose sum $\sum_i v_i$ is fixed.
1
vote
1answer
40 views

Lagrange multipliers: when is local extremum a global extremum?

Consider the following Olympiad problem from the IMO shortlist: Let the real numbers $a,b,c,d$ satisfy the relations $a+b+c+d=6$ and $a^2+b^2+c^2+d^2=12.$ Prove that: $36 \leq 4 \left(a^3+b^3+c^3+d^...
0
votes
2answers
452 views

Using Lagrange for finding Marshallian Demand

I want to find the marshallian demand function for the user function $u(x_1,x_2) = x_1^ax_2^{1-a}$ where $a \in (0,1)$. This is what I have so far: $$L = x_1^ax_2^{1-a} - \lambda(p_1x_1 + p_2x_2 - y)$...
0
votes
1answer
47 views

maximize 3-variable linear function [version 1.0]

This problem came up when I was trying to solve a bigger, probabilistic problem. So at the end it boils down to this: how can we maximize the function $f(x_2,x_3,x_4) = \frac{18}{100}x_2 + \frac{...
3
votes
3answers
68 views

Find minimum and maximum on range

$f(x,y)=x^{4}-x^{2}+y^{2}$ $B={(x,y)\in \mathbb R, x^{2}+y^{2}\leq 1 }$ I should find minimum and maximum of this function on the range B. I tried it with Lagrange Multiplier and I got these points ...
0
votes
2answers
53 views

Lagrange multipliers with trigonometric functions. Stucked figuring out x and y values.

I want to find the maximum of the function $f(x,y) = \cos^2(x) + \cos^2(y)$ with the constraint $x-y = \pi/4$. Here are my partial derivatives: $$f_x = -2\cos(x)\cdot\sin(x)$$ $$f_y = -2\cos(y)\cdot\...
2
votes
3answers
64 views

Can't find minimum using Lagrange multipliers

I want to find the minimum of the function $f(x,y) = x + y^2$ with the constraint $2x^2 +y^2 = 1$. Here are my partial derivatives: $$f_x = 1$$ $$f_y = 2y$$ $$g_x = 4x$$ $$g_y = 2y$$ I have the ...
1
vote
3answers
81 views

Lagrange Multipliers Method of solving Question

Find the maximum and minimum values of $f(x, y) = x^2 + y^2$ subject to the constraint $x^2 − 2x + y^2 − 4y = 0$ So I have to use lagrange multipliers $ \nabla f(x,y) = \lambda\nabla g(x,y) $ $$ ...
17
votes
3answers
664 views

How to prove Lagrange multiplier theorem in a rigorous but intuitive way?

Following some text books, the Lagrange multiplier theorem can be described as follows. Let $U \subset \mathbb{R}^n$ be an open set and let $f:U\rightarrow \mathbb{R}, g:U\rightarrow \mathbb{R}$ be $...
7
votes
4answers
236 views

Minimize $-\sum\limits_{i=1}^n \ln(\alpha_i +x_i)$

While solving PhD entrance exams I have faced the following problem: Minimize the function $f(x)=- \sum_{i=1}^n \ln(\alpha_i +x_i)$ for fixed $\alpha_i >0$ under the conditions: $\sum_{i=1}^n ...
0
votes
0answers
24 views

Extrema on (compact) vinculum

My textbook ask to find the extrema of $f(x,y) = 2x^2+y^2$ on $x^4-x^2+y^2-5=0$. It uses the lagrangian multipliers to find critic points.. Then it computes the function on these points then says "...
1
vote
0answers
34 views

Lagrange multipliers question with 2 constraints

Let $A=\{x\in \mathbb{R}^n|\sum x_i=n/3, \sum x_i^2=n \}$ $f(x)=\sum x_i^3$ Prove that max of f on A is of the form: $x=(a,a,.....,a,b,b...,b)$ (no need to find a or b). So with Lagrange ...
0
votes
0answers
67 views

How to obtain the optimal Lagrange multiplier vectors if the globally optimal solution for a nonconvex QCQP is found?

I am using a black-box solver to solve the following non-convex QCQP to global optimality. $$ \min_x x^TQ_0x + c^T x \\ s.t. \quad x^TQ_1x+c_1^Tx=b_1 \\ Ax=b \\ l\leq x\leq u $$ where $Q_0$ is ...
0
votes
2answers
44 views

Generalities regarding the Lagrange Multiplier

Apparently the following general statement is true. "Let $\gamma:g(x,y)=0$ be a closed curve that doesn't cross itself. If the maximisation of a function $f(x,y)$ on $g(x,y)$ using Lagrange ...
0
votes
0answers
10 views

Lagrangian Relaxation of quadratically constrained quadratic program

I have the following problem: $$ \min_{w,\theta\ge0}\frac{1}{2}\|w-w_t\|^2+(\theta-\theta_t)^2 \text{ s.t. } w^\top(\hat n\hat z-nz)+\theta w^\top(z-\hat z)+1 \le 0,\theta-1\le 0 $$ Notice that $w$ is ...
1
vote
0answers
49 views

How to solve a binary generalized assignment problem

I have the following generalized assignment problem: Z=max $\sum_{i=1}^{N}\sum_{j=1}^{M} x_{ij}R_{ij}$ such that $\quad 1)\quad \sum_{j=1}^{M} x_{ij}=1 \quad \forall i$ $\quad\quad\...
1
vote
2answers
49 views

Optimizing a problem using Lagrange multipliers

$\newcommand{\norm}[1]{\|#1\|}$ I have the following problem: $$ \min_{w,\theta}\frac{1}{2}\norm{w-w_t}^2+\frac{1}{2}(\theta-\theta_t)^2 \text{ s.t. } w^\top(z(n-\theta)-\hat z(\hat n - \theta)) \ge 1 ...
1
vote
2answers
481 views

Using Lagrange multipliers to find the shortest distance between two straight lines

A problem asks me to use the method of Lagrange multipliers to find the shortest distance between the straight lines $x=y = z$ and $x = -y, z=2$ (It also warns me that using this method is a bit ...
0
votes
0answers
34 views

Find the farthest and nearest point of an ellipsoid

The equation of ellipsoid is $$ax^2+by^2+cz^2+2fyz+2gxz+2hxy+2px+2qy+2rz+d=0$$ The ellipsoid is arbitary rotated and the orientation angle are given and center is at (x',y',z'). The radius of the ...
0
votes
1answer
41 views

Extrema of $f(x)=g(|x-a|^2,|x-b|^2,|x-c|^2):\Bbb{R}^n\to \Bbb{R}$ in $S=\{x: |x|=1\}\subset \Bbb{R}^n$ is a linear combination of $a,b,c$

Since I am getting pretty close to the final exams, I would really yield from having my practice challenged and corrected. Question: Let $a,b,c\in \Bbb{R}^n$ be independent vectors, and $g\in C^{1}(\...
1
vote
1answer
45 views

Is Lagrangian Multiplier Equivalent to Brute Force for binary decision variables

I have a set of variables $x_{i} \in \{1,k\} $ in a non linear optimization problem. As this variable has only two possibilities I have encoded this into a constraint. I assumed having equality ...
2
votes
0answers
41 views

Finding the minimum of $x_1 + \cdots + x_n$ on ellipsoid

Let $A$ be a positive definite matrix $n \times n$ and $u^T = [1 \cdots 1]$. Use Lagrange multipliers to find the minimum of $f(x) = u^Tx$ on $h(x) = \frac{x^TAx}{2} = 2$ This is what I did. $$L(x,...
4
votes
0answers
67 views

I'm walking towards my car - when should I try the remote, in an optimal sense?

I'm interested to learn about how discrete/'event' based elements are incorporated into optimisation problems. Hopefully this is an interesting problem in its own regard, it's inspired by a daily ...
2
votes
2answers
67 views

How do I solve the following equality-constrained quadratic program?

I am trying to minimize: $$(x_1-k_1)^2 + (x_2-k_2)^2 + (x_3-k_3)^2 +\ldots+ (x_n-k_n)^2$$ subject to following equality: $$B = 1 + x_1 + x_2 + x_3 + x_4+\ldots+x_n.$$ Is there a closed form ...
1
vote
2answers
26 views

normalization of constraints $ 0 \leq x \leq 1 $ in Lagrangian KKT

With Lagrangian we have an objective function and a set of equality constraints of form $ g_{i}(x_{j}) = 0 $ . With KKT we can have another set of inequality constraints of the form $ h_{i}(x_{j}) \...
2
votes
1answer
46 views

Directional derivative and lagrange multipliers

Find the points $(x,y)\in \mathbb R^2$ and unit vectors $\vec u$ such that the directional derivative of $f(x,y)=3x^2+y$ has the maximum value if $(x,y)$ is in the circle $x^2+y^2=1$ My attempt: ...
0
votes
2answers
36 views

Using the Lagrange method to find max/min of $f(x,y) = \frac{x^3}3 + y$

Problem Use the Lagrange method to find max/min of $f(x,y) = \frac{x^3}3 + y$ Subject to the constraint $x^2 + y^2 = 1$ My attempt The constraint gives us $g(x,y) = x^2 + y^2 - 1$ $\displaystyle\...
1
vote
1answer
26 views

Alternative solution to a Lagrange Method Optimization Problem

Find extrema of $f(x,y,z)=\frac{1}{x^2}+\frac{1}{y^2}+\frac{1}{z^2}$ subject to $\frac{1}{x}+\frac{1}{y}+\frac{1}{z}=1$ by reducing variables and then using the Single Variable Method or by using ...
0
votes
0answers
14 views

Solving Binary Linear Programming Problem Using KKT

Execuse me, I know that if I searched a lot I could find the answer, However I have already did my research and I am running out of time. I need the detailed solution of the following linear problem (...
0
votes
0answers
30 views

For some $f:\Bbb{R}^n\to \Bbb{R}$, $A\subset \Bbb{R}^n$ and $B\subset A$, show that $\max_{A}(f)=\max_{B}(f)$

Let $A=\{(x_1,...,x_n)|{1\over n}(\sum_{i=1}^n{x_i})={1\over 3},{1\over n}(\sum_{i=1}^{n}{x_i^2}))=1\}\subset \Bbb{R}^n$, and let $B\subset A$ be a subsets of points from $A$ of the form $${(\...