In mathematical optimization, the Karush–Kuhn–Tucker (KKT) conditions are first order necessary conditions for a solution in nonlinear programming to be optimal, provided that some regularity conditions are satisfied.

learn more… | top users | synonyms (1)

0
votes
0answers
14 views

Minimizing convex functions without compatible gradients

I've been working on a minimization problem for a while, involving "simple" conditions, but haven't been able to figure it out. I've tried using Lagrange Multipliers and KKT, but the presence of ...
0
votes
1answer
20 views

Minimization problem with infinite variables and linear constraints

How can this minimization problem be solved? $$ \left\{\begin{matrix} \begin {aligned} &\sum_{i=1}^{\infty}P_i^3 \rightarrow min \\&\sum_{i=1}^{\infty}P_i=1 \\ &P_i\geqslant 0 \:for\: ...
0
votes
0answers
27 views

Proving equivalent optimization problems

Consider the problems $\min f(x) , x \in X$ and $\min g(x), x \in X$. two optimization problems are said to be equivalent if an optimal solution to one, is also optimal to another. I would like to ...
0
votes
0answers
30 views

Functional analysis with KKT conditions

I want to solve an optimization problem min $F(x_{ik}) $ subject to $x \in X$. $F$ here is a function or functional that I wish to determine. I want my optimal ...
0
votes
0answers
19 views

Strong Duality for Euclidean distance

i have an optimization problem in the form: $min ||x - y||$ sbj to: $A.x = 0$ $A.y = 0$ $l_x \leq x \leq u_x, l_y \leq y \leq u_y$ I'm trying to find the dual form of this optimization problem, ...
2
votes
0answers
25 views

Theoretically understanding the algorithmic solution to this Quadratically Constrained Quadratic Optimization Problem

I have a simple QCQP problem to solve: $\min_{t} x(t)^{T}Ax(t)$ subject to constraints $x(t)^{T}Ax(t) > 1 $ where A is a positive definite matrix and $x(t) \in \mathbb{R}^2$ is some time ...
1
vote
1answer
29 views

Quadratic programing problem and MATLAB

I have a little problem with quadratic programing problem: ${\bf v}^T \Sigma {\bf v} \rightarrow min $, and constrains are $ {\bf v}^T \mu = \mu_*, {\bf v}^T {\bf 1 }= 1, 0 \leq {\bf v}. $ Where ...
0
votes
0answers
25 views

Minimize $\|\mathbf{x-y}\|^2 $ subject to $x \in $ set $S=\{\mathbf{x} \in \mathbb{R}^n \;\;\;\mid \;\;\; \|\mathbf{x-x_c}\|^2\leq r^2 \}$

We are given the set $S=\{\mathbf{x} \in \mathbb{R}^n \;\;\;\mid \;\;\; \|\mathbf{x-x_c}\|^2\leq r^2 \}$ and a point $\mathbf{y} \in \mathbb{R}^n$. Our goal is to find point $\mathbf{\hat{x}}$ ...
0
votes
0answers
22 views

Connection between method of Lagrange multipliers and KKT conditions?

I understand that in general, the KKT conditions are not sufficient for optimality. However, if the primal problem is a convex optimization problem, then the KKT conditions are sufficient for ...
0
votes
0answers
27 views

KKT conditions for nonlinear problem

I need to state the KKT conditions for the following problem: Minimise $x_1^2 + 2x_2^2$ subject to $(x_1-1)^2 + x_2^2 \le 1$ and $x_2 = 1$. I have that these conditions are: $f(x^*) \le 0$ ...
0
votes
1answer
22 views

Can lagrange multiplier(Kuhn tucker multipliers?) change in corner solution?

If we want to maximize $f(x)$ subject to two constraints, one which says that $x< c$ $c>0$, and another that says that $x\geq 0 $. Assume there are no problems with either $x=0, x>0$ or $\mu ...
1
vote
0answers
33 views

KKT conditions for a convex optimization (optimal crowdsourcing with budget constraint)

I am having some troubles deriving the optimal solution of the following convex optimization problem, $w_j$, $c_{ij}$, and $B$ are fixed and non negative. \begin{align} & ...
0
votes
2answers
25 views

Kuhn-Tucker's Conditions for optimization problem with non linear inequalities constraints

My problem is to minimize the function \begin{align*} f(x,y,z,t)=& 3 t \left(2 x^2+4 x z\right) \left(2 t x y+t x z-2 t y^2-2 x z+4 y z\right) \\ &+\left(-t x^2+4 t x y+4 t y z+4 x z-8 y ...
0
votes
0answers
60 views

KKT conditions (equations) for Generalized Assignment Problem or Binary integer programming problem

I have this formulated Generalized Assignment Problem (GAP) or it can also be considered as Binary integer programming problem. Solving this problem can be achieved through Branch and Bound Technique. ...
0
votes
0answers
28 views

Optimization by KKT-method

I need to solve the following problem by KKT method. $$ \text{min} \ \ 2xy + 2yz + 2zx \\ \text{subject to} \ x^2 + y^2 ≤ 2, \ 2x + 2y + z = 0 $$ I have gotten as far as setting up the system of ...
4
votes
0answers
60 views

How to use the Karush–Kuhn–Tucker conditions?

From what I read, the Karush-Kuhn-Tucker conditions are a generalization of the Lagrange Multiplier Method. For the Lagrange Multiplier Method I have been able to find a serie of steps I must do to ...
0
votes
0answers
20 views

General KKT problem

Consider the following problem, where $a_j,b$ and $c_j$ are positive constants: Minimize 􏰀$\sum_{j=1}^n \frac{c_j}{x_j}$, subject to $\sum_{j=1}^n a_j x_j = b, x_j ≥ 0$ for $j= 1,...,n$. Write ...
0
votes
1answer
30 views

Linear programming with kernel

Can anyone please help me with solving the constrained minimization problem below? $$\mathbf{x}^* = \arg\min \sum_{i=1}^m q_i e^{-2x_i} $$ $$s.t.$$ $$\sum_{i=1}^m x_i = c$$ $$x_i\geq0, i = ...
0
votes
0answers
15 views

Kuhn Tucker condition sufficient for global optimum

LL is the variable and s,rs,r are parameters. The question asks to solve maxL≥0rf(L)−wLmaxL≥0rf(L)−wL where f(L)f(L) is twice continuously differentiable, strictly increasing and strictly concave. ...
1
vote
0answers
36 views

Kuhn Tucker condition is sufficient for a global optimum?

$L$ is the variable and $s,r$ are parameters. The question asks to solve $max_{L\geq0}rf(L)-wL$ where $f(L)$ is twice continuously differentiable, strictly increasing and strictly concave. Then how ...
2
votes
1answer
41 views

How to solve this KKT problem?

Given an optimization as follows: \begin{align} \text{minimize}\quad &c^Tx \\ \text{subject to}\quad &Ax = 0 \\ & \|x\|_2^2 \leq 1 \end{align} where $A \in \Re^{m\times n}$ is of ...
2
votes
1answer
45 views

BigPicture Lagrangian, KKT, Duality

I have a question regarding the big-picture in the field: Lagrangian, Duality, KKT, sufficient, necessary conditions. 1) Duality is a concept: “The solution to the dual problem provides a lower ...
2
votes
0answers
26 views

What is the logic behind the given optimization problem?

I am following a book which has a part on numerical optimization techniques. In order to elaborate Karush-Kuhn-Tucker theorem, they gave the following example: When the unconstrained solution $x=A^+ ...
0
votes
0answers
40 views

KKT Conditions for Euclidean Distances

Suppose that we have an undirected and edge weighted graph $G = (V,E)$. The weight $w_{ij}$ of an edge $\{i,j\} \in E$ determines the Euclidean distance between the vertices $i$ and $j$ s.t. $i,j \in ...
0
votes
0answers
17 views

Validity of nonlinear optimization with exponential type inequality constraint as KKT / Lagrange multipliers?

Given positive coefficients $h_i, \beta_i$ and $k$ we have the minimization problem $$\displaystyle \min\sum_{i = 1}^n h_{i}s_i\\ \text{subject to} \displaystyle\sum_{i = 1}^n \alpha^{s_i}\beta_i \leq ...
2
votes
2answers
57 views

Minimize $x^2+y^2$, subject to… (optimal points, KKT conditions, dual theories)

I am new to this. I am self learning to get ahead of my next years course and came across this question. I thought it would be a good question to look at due to it touching an many different aspects ...
0
votes
0answers
39 views

dual feasibility of Kuhn-Tucker condition?

minimize $f(x)$ subject to \begin{align} f_i(x) & \le 0, \quad i \in \left\{ 1,\ldots,m \right\} \\ h_i(x) & = 0, \quad i \in \left\{ 1,\ldots,p \right\} \end{align} Then the Lagrange ...
2
votes
1answer
42 views

Some True or False questions on Nonlinear Optimisation (Exam Preparation)

I am currently preparing for a Nonlinear Optimisation exam and am working through some old question papers and came across these True or False questions: When minimizing a convex function over ...
0
votes
0answers
31 views

Solve system with complex fractional equations

I need to maximize a function with equality constraint, so I made the Lagrangian function and I found the partial derivatives, which are these: $$ \frac{|h_1|^2}{\sigma^2(\frac{x ...
0
votes
0answers
29 views

KKT condition and linear program

Since all linear program all convex, and the Slater's condition always hold for linear programs. Is it always possible to solve the linear programs with KKT conditions? because it will convert the ...
0
votes
0answers
16 views

Maximize using KKT conditions.

Let $T\ge1$ be some finite integer. Maximize $\sum_{t=1}^{T} (\frac{1}{2})^t \sqrt(x_t)$ Subject to $\sum_{t=1}^{T} x_t \le 1 $ and $ x_t \ge 0, t = 1,...,T$. I believe that constraints $ x_t ...
1
vote
1answer
31 views

Karush-Kuhn-Tucker NLP

Consider the nonlinear program Minimize: \begin{align}f(x,y) = \frac{1}{2}x^2 - 10xy + 10y^2\end{align} Subject to: \begin{align}2x +y^2 &\le 5 \implies g_1(x,y)=2x + y^2 -5 \le0 \\ ...
2
votes
1answer
60 views

KKT condition - minimization problem

$y^2-8 \ln(x+4)\rightarrow$ min, such that $-x^2 -y^2+9 \geq 0, y \geq 0$ *I have to find all possible optimal points.* Lagragian function is: $L(x,y,γ_1,γ_2) = y^2 - ...
0
votes
1answer
49 views

optimisation with inequality constraints

I'm struggling with this question: $ \max \{ \ln(y) - (x-1)^2 \} $ s.t. $x + y \leq t$ and $y > 0$ I'm trying to use the Lagrange/Kuhn-Tucker method but don't know how to progress after getting ...
1
vote
1answer
50 views

applying KKT to non-convex optimization

I am trying to find a solution for following \begin{eqnarray} \text{minimize }~~ -\sum_{i=1}^K \frac{1}{a_i+b_i2^{(-2x_i)}} \\ \text{s.t.} ~~~ \sum_{i=1}^Kx_i=C \end{eqnarray} where ...
0
votes
0answers
34 views

Solving the Lagrange dual problem

If we have a convex constraint problem $$ \text{min}\quad f_0(x)\\ f_i(x)\le0\\ h_i(x)=0, $$ where $f_1,\ldots,f_n$ are convex and $h_1,\ldots,h_r$ are affine. Assuming Slater's conditions we know ...
3
votes
1answer
68 views

KKT conditions for a maximization problem

I have an optimization problem \begin{equation} \mathbf{w}^*= \text{argmax} ...
0
votes
0answers
41 views

Sufficiency of KKT problem

I have a continuous, twice differentiable function $f:\mathbb{R}^2\rightarrow \mathbb{R}$. My objective is to maximise the function $f$ subject to quasiconcave function $g_i(x,y)\le 0,\, i\in\{1,2\}\, ...
3
votes
1answer
76 views

Kuhn Tucker conditions, and the sign of the Lagrangian multiplier

I was under the impression that under the Kuhn-Tucker conditions for a constrained optimisation, with inequality constraints the multipliers must follow a non-negativity condition. i.e. $$\lambda ...
1
vote
0answers
12 views

Regularity for the Feasible region

I have this problem $min -x +y $ $x-y^2\leq0 $ $\frac {(x-1)^2}{4} +y^2 \leq 1$ $y \geq -1/2$ Say if the feasible region is regular or not, analitically. I know that to check the KKT ...
0
votes
1answer
59 views

Finding KKT conditions for nonlinear optimization problem.

I have an optimization like below: $\text{ minimize } \sum_k - \log_2 x_k $ $\text{subject to: } x_k \leq q , k =1,2, \cdots, N .$ I can form the Lagrange of the problem as below: $L(x, ...
0
votes
0answers
39 views

KKT system with rank-deficient constraints

I have an optimization problem of the following form: $$ \begin{aligned} \operatorname*{minimize}_x & \quad \frac{1}{2}||x - a||^2 \\ \operatorname{subject~to} & \quad ...
4
votes
1answer
98 views

Is this a known result?

I heard the following result and I am wondering if anyone can verify its correctness and also provide a source to cite. If the Lagrangian $L(x,\lambda)$ is convex in $x$ at the optimal Lagrange ...
0
votes
0answers
34 views

optimization of a function with inequality constraint

I have a function to be maximized subject to constraints. I can write the primal Lagrange function as the following: (objective function WITH two constraints in the last two terms) $$L_P = ...
1
vote
0answers
27 views

projection KKT optimal condition

Using the KKT optimality condition find the orthogonal projection of an arbitrary point $c \in$ to the closed convex set $C$ (non empty) defined by: (a) $C=\{x \in R^n : Ax\leq a\}$ where $A\in ...
1
vote
0answers
36 views

KKT Optimality Conditions

I am working with the following optimization problem: $$ \min_{\Delta} \boldsymbol{\theta}^T\boldsymbol{\Delta} \\ \text{Such that:} ~~~0 \leq \mu_i + \Delta_i \leq 1 ~~\forall~~ i\in\{1,2,\ldots, n\} ...
1
vote
2answers
108 views

Do we really need the constraint qualification?

I can't keep my fingers off Nocedal/Wright's Numerical Optimization (1999,1E) and I apologize. But maybe YOU can shed light on the question: Why does a point $x \in \mathbb{R}^n$ need to satisfy the ...
0
votes
1answer
40 views

Eliminate cases before calculting all KKT conditions

I have the following non linear programming to solve: $$\left\{\begin{matrix} \min & (x-3)^2 + (y-2)^2 \\ s.t. & x^2 +y^2 \leq 5 \\ & x+y\leq 3 \\ & x \geq 0\\ & y\geq 0 ...
0
votes
0answers
15 views

For which values of $c_1, c_2$ and $c_3$ is (1, 2, -2) a local minimum

Consider the problem $$\left\{\begin{matrix} \min & x^2 -2xy + 2xz +y^2 + 4yz + z^2 + c_1x + c_2y + c_3z \\ s.t & g(x,y,z)=-x^2 -4xy - 4xz -2y^2 -4yz - 2z^2 + x -y+z+4 =0 \\ \; & ...
0
votes
1answer
20 views

Constrained Optimization: $\min x_1$

Consider the problem $$\left\{\begin{matrix}\min & x_1 \\ s.t & x_2 \geq 0 \\ \; & x_2 \leq x_1^3 \end{matrix}\right.$$ It is asked to find the minimum and show why this does not satisfy ...