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

learn more… | top users | synonyms

0
votes
0answers
5 views

Optimization problem: minimize $\theta {w}^H_{{p}}{R_{nn}}{w_p} + (1-\theta){c}^T \text{diag}({p}){c}$

I have an optimization problem \begin{equation}\label{eq:optimi_joint2} \begin{aligned} \operatorname*{minimize}_{\mathbf{w_p}\in \mathbb{C}^M,\mathbf{p}\in \{0,1\}^M} \ \ &\theta \mathbf{w}^H_{...
0
votes
0answers
8 views

Could anyone explains the solution for constrained optimization in a paper “Embedding a semantic network in a word space”?

I'm reading a paper "embedding a semantic network in a word space". In the paper, a problem for embedding word sense is formalized as bellow. $$ \text{minimize}_{E,p}\sum_{ijk}w_{ijk}∆(E(s_{ij}),E(n_{...
0
votes
0answers
21 views

Lagrangian fuction for optimization problem

I have an optimization problem \begin{equation}\label{eq:optimi_joint1} \begin{aligned} \text{minimize}_{\mathbf{w_p}\in \mathbb{R}^M,\mathbf{\Lambda_p}\in \mathbb{R}^{M\times M}} \ \ &\kappa \...
0
votes
1answer
45 views

Is this proof correct? Lagrange multipliers

Suppose that $f,g : \mathbb{R}^n \to \mathbb{R}$ are $C^1$ functions and $c$ is a regular value of $g$. If $a \in g^{-1}(c)$ is a minimum for $f$ restricted to $g^{-1}(c)$ then there is $\lambda \in ...
1
vote
1answer
13 views

nonlinear KKT analysis with bounded variables

By the help of lagrangian multipliers, I am solving a nonlinear problem with 6 variables using KKT analysis. At the beginning, I do not consider any upper-bound for the variables to see whether the ...
0
votes
1answer
31 views

Confusion of a formula about Lagrangian

Recently, I am reading a paper about eigenvalue problems. Consider the following problem, which occurs at the first page of the paper. \begin{align} \text{minimize}\quad &x^TAx \\ \text{subject ...
0
votes
0answers
26 views

Equivalence between standard optimization problem and Langragian form

Given a problem: $$\min_x f(x)$$ subject to $$g(x) \le C$$ In general, when it is equivalent to the problem $$\min_x f(x) + \lambda g(x)$$ for certain $\lambda$? Here my equivalence means : the ...
1
vote
2answers
46 views

Use lagrange multipliers to calculate the maximum and minimum

$f(x,y,z)=x^2y^2z^2$ constrained by $x^2+y^2+z^2=1$ $\nabla f_x$ $=$ $2xy^{2}z^{2}$, $\nabla f_y$ $=$ $2yx^{2}z^{2}$, $\nabla f_z$ $=$ $2zx^{2}y^{2}$ $\nabla g_x$ $=$ $2x$, $\nabla g_y$ $=$ $2y$, ...
0
votes
0answers
22 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 ...
2
votes
3answers
50 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
42 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
29 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
41 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
51 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
69 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
200 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
42 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
50 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
27 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
37 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
44 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
52 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 ...