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

learn more… | top users | synonyms

2
votes
3answers
48 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
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,...
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 ...
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
37 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 ...
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 \...
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. ...
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.
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
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
1answer
46 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) $ $$ ...
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
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\...
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
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
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
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 ...
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
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 ...
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: ...
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
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 $${(\...
0
votes
1answer
43 views

Why are most Lagrange multipliers zero in the SVM solution?

I read everywhere that a non-zero Lagrange multiplier $\lambda_i$ signifies that the corresponding point $x_i$ is a support vector, but I can't see how a support vector and a non-support vector have a ...
1
vote
3answers
51 views

Find points that give the shortest distance between $y = x^2$ and $y-x+2=0$ using Lagrange multipliers

I am asked to find, using Lagrange multipliers, the points on $y = x^2$ and $y-x+2=0$ that give the shortest distance between the curves. Obviously, $d(x,y) = \sqrt{(x-x_0)^2 + (y-y_0)^2}$, but I am ...
0
votes
1answer
22 views

Position of vertices of right triangle inscribed on $x^2+4y^2=1$ with maximum area using Lagrange Multipliers

I am asked to find, using Lagrange multipliers, the position of the vertices of a right triangle inscribed on $x^2+4y^2=1$ that has the maximum area. The two legs of the triangle (which are not the ...
0
votes
0answers
7 views

Conditional extremes, solving $xa+yb < (x^p+y^p)^{\frac{1}{p}}(x^q+y^q)^{\frac{1}{q}}$ if.

Conditional extremes, solving $$xa+yb \leq (x^p+y^p)^{\frac{1}{p}}(x^q+y^q)^{\frac{1}{q}}$$ using lagrange multipliers.. If $\frac{1}{q}+\frac{1}{p}=1$ and $p,q>1$. This reminds me of Holders ...
1
vote
3answers
90 views

Hottest and coldest points on a heated circular plate (use Lagrange multipliers)

A circular plate given by the relationship $x^2 + y^2 \leq 1$ is heated according to the spatial temperature function $T(x,y) = 2x^2 + y^2-y$. Find the hottest and coldest point on the plate using ...
1
vote
0answers
16 views

Is convexity of the objective function sufficient for a local maxima to be a global maximum?

In my problem, I have to maximize a convex function $f(x_1,x_2,\cdots,x_n)$ subject to two equality constraints $g_1=0$ and $g_2=0$. As usual, I constructed the Lagrangian $L=f+\lambda_1g_1+\...
0
votes
1answer
33 views

Word Problem Lagrange Method

I am studying for my exams and got very very stuck at a word problem on the Lagrange Methods, my biggest difficulty is to properly identify the function to be maximized (in this case) and so its ...
1
vote
0answers
65 views

Find the maximum distance from origin to the surface?

I am having trouble with this problem... I need to find the maximum distance from the origin to the surface $$f:=\frac{x^4}{2^4}+\frac{y^4}{3^4}+\frac{z^4}{(\sqrt2)^4}-1$$ I think I have to use ...
1
vote
2answers
41 views

How is f(4,4,4)=48 a local minimum? Can it be inferred that it is either a maxima or minima & only one extreme value within the constraint?

Disclaimer: In the definition (Stewart Calculus, 7E): "Method of Lagrange Multipliers" part (b)- Evaluate $f$ at all extreme points $(x,y,z)$ from step a. The largest of these values is the maximum ...
2
votes
1answer
33 views

Solving a quadratic convex optimization problem

There's this convex optimization problem which I got stuck after writing the Lagrange equation. I simply couldn't find a way to eliminate the Lagrange multiplier. $$\begin{array}{ll} \text{minimize} &...
1
vote
0answers
42 views

Finding the Maximum and Minimum values w/constraint [duplicate]

I apologize I have asked this question before but it died and I just got around to working it out based on the suggestions so here it is. Let the function $f$ be defined as $f$($x$,$y$,$z$) $=$ $x$$...