Questions tagged [karush-kuhn-tucker]

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.

Filter by
Sorted by
Tagged with
0 votes
1 answer
28 views

When the Karush-Kuhn-Tucker conditions fail to apply? [closed]

Consider an optimization problem: $\max\limits_{\substack{x_1, x_2}} x_1 + x_2$ s.t. $2 \sqrt x_1 + x_2 \leq y$ $x_1, x_2 \geq 0$ In order to solve it, I set up the Lagrangian: $\mathcal{L}(x_1, x_2) =...
Dave299's user avatar
  • 11
0 votes
0 answers
9 views

KKT Conditions for SVM Problem

I am reading about SVMs and want to confirm that I understand the optimality conditions. Details below: Consider the $n$ points $x_1, x_2, \dots, x_n$, each with $ d$ dimensions, and consider $ n$ ...
user35083's user avatar
0 votes
1 answer
67 views

Kuhn-Tucker conditions for inequality constraints

So, when we solve the optimization problem using Lagrange Multiplier method, I know that lambda can be positive or negative. Lambda is simply the rate of change in the optimal value when the ...
Confused_intense_thoughts's user avatar
0 votes
0 answers
43 views

Geometric Proof About Constrained Minimization Problem

I got the following problem, but I have difficulties understanding part of its solution. I would really appreciate it if someone could explain it for me! Problem Present a geometric proof that in the ...
Beerus's user avatar
  • 261
1 vote
2 answers
76 views

How to use the Karush–Kuhn–Tucker conditions properly?

I want to learn how to use the Karush-Kuhn-Tucker (KKT) conditions to solve a quadratic programming problem with both equality and in-equality constraints. The problem in question is set in finance ...
Przemo's user avatar
  • 10.7k
1 vote
0 answers
25 views

Optimality of a degenerate basic feasible solution in a Linear Program

Consider the linear program $$\max\limits_x c^t x \quad \text{s.t} \quad Ax=b, x\geq 0. $$ I would like to determine whether a specific basis feasible solution (BFS) $x$ is optimal. (I am not ...
user278486's user avatar
1 vote
1 answer
66 views

Max $2x+3y$ subject to $4x+y \leq 5, x\geq0, y\geq0$

Qno: (a) obtain a solution $(x^{*}, y^{*})$ by graphical method. (b) Formulate the Lagrangean. (c) Obtain all the K-T necessary conditions (d) Using values for $(x^{*}, y^{*})$, obtain the values for ...
Waseem Bughio's user avatar
2 votes
1 answer
63 views

Least Squares with Inequality Constraints [closed]

I want to use Least Squares to minimize $Ax-b$ (overdetermined system), subject to $x_1+x_2+x_3=1$ and $\forall x_i, 0 \leq x_i \leq 1$. As per my understanding, I need to set up the Lagrange function ...
cc88's user avatar
  • 81
1 vote
0 answers
74 views

KKT conditions for non-differentiable constraints

So I know that for the problem: $$ \begin{align*} \text{minimize} \quad & f_0(x) \\ \text{subject to} \quad & f_i(x) \leq 0, \quad i = 1, 2, \ldots, m \\ \end{align*} $$ We have the following ...
Dylan Dijk's user avatar
0 votes
0 answers
42 views

Strong duality, primal optimal, satisfies KKT gradient implies dual optimal?

Consider a nonlinear program (specifically not convex): $$ \underset{ x \in \mathbb{R}^{n} }{ \text{min} } f(x) $$ $$ \text{s.t.} g(x) \leq 0 $$ Where $f:\mathbb{R}^{n} \to \mathbb{R}$, $g:\mathbb{R}^...
wsz_fantasy's user avatar
  • 1,076
0 votes
0 answers
20 views

Maximisation problem for a quasi-linear utility function

How do I solve a maximisation problem for a quasi-linear utility function: max $U(x, y) = 2x + \ln (1 + y)$ s.t. $x + y ≤ 5, x ≥ 0, y ≥ 0$ ?
jorge's user avatar
  • 9
0 votes
0 answers
52 views

Second-order-cone programming - Lagrange multiplier and dual cone

In standard nonlinear optimization when we are interested to minimize a given cost function the presence of an inequality constraint g(x)<0 is treated by adding it to the cost function to form the ...
venom's user avatar
  • 233
1 vote
0 answers
49 views

$\nabla f(x)(y-x) \geq 0$ for KKT point x

Let $x\in\mathbb{R}^n$ be a KKT point of the problem $$\min f(x) :\;\text{s.t.}\; h_j(x)\leq0,\;\;\forall j\in\{1,\dots,m\}$$ where $f:\mathbb{R}^n\to\mathbb{R}$ is smooth and all $h_j:\mathbb{R}^n\to\...
drearien's user avatar
1 vote
0 answers
56 views

Solving a constrained optimisation problem where the algebra doesn't make sense

I have the following function to maximise with respect to $x$, $p$, and $\eta$: $\frac{p\eta}{R(x)}[v(x)-\bar\theta R(x)]+(1-\frac{p\eta}{R(x)})p\eta-(1+\lambda)tpx-\lambda R(x) (1)$ subject to the ...
mirrror's user avatar
  • 23
1 vote
1 answer
52 views

Regularized optimization : adding a vanishingly small penalty term does not change the solution set?

Say I am trying to minimize a differentiable function $R: \Theta\to\mathbb R^+$, where $\Theta\subseteq\mathbb R^p $ is a compact subset. Now, for $\lambda\ge0 $, I define the $ \lambda$-regularized ...
Stratos supports the strike's user avatar
0 votes
0 answers
23 views

Hamiltonian and optimality conditions for constrained minimisation problem

Problem: The stochastic optimal control problem is to minimize the discounted value of an expected weighted average of the squared cash flow $x_t$ and the squared cash flow $y_t$ by choosing the ...
NC520's user avatar
  • 217
0 votes
0 answers
76 views

Optimal control problem with Kuhn–Tucker constraint

Problem: The stochastic optimal control problem is to minimize the discounted value of an expected weighted average of the squared cash flow $x_t$ and the squared cash flow $y_t$ by choosing the ...
NC520's user avatar
  • 217
0 votes
0 answers
20 views

Non-Negativity Constraint's on Lagrangians

When we take our Lagrangian and we include non-negativity constraints. If a variable $x = 0$ do we take FOC first or set $x=0$ first? E.g. $Max \; L(x, y, λ) = f(x,y) - λ_1(g(x,y) - k) - λ_x(-x) - λ_y(...
CormJack's user avatar
  • 370
0 votes
1 answer
25 views

Missing Non-Negativity Constraint on Lagrangian

We have the constrained maximisation problem: A perfectly competitive firm produces one output with two inputs, capital $(k)$ and labour $(l)$. The rental cost of capital is equal to $r >0$ and ...
CormJack's user avatar
  • 370
2 votes
0 answers
15 views

Estimating/Tuning a Coefficient from an Objective Function so Optimal Solution Reflects Data

I am working on a problem that is a modified version of a two-knapsack knapsack problem. I am able to find the optimal choices by using Gurobi. However, I would like to estimate a coefficient that is ...
Jack Keefer's user avatar
1 vote
1 answer
36 views

Suppose $x \leq f(x) + f(y), y \leq f(x) + f(y)$, and $f(\cdot)$ concave. Is the solution for $x$ bounded?

I am writing a model which has the following constraints. $$x \leq f(x) + f(y) \\ y \leq f(x) + f(y) \\ x \geq 0 \\ y \geq 0$$ My question is: Does concavity of $f(\cdot)$ guarantee that there is a ...
KarthikSrinivasan's user avatar
0 votes
0 answers
51 views

KKT conditions on optimization problem with inequalities

I have the following optimization problem: \begin{align*} \min_{x} \quad & f(x) = x^2 - 2x + 3 \\ \text{s.t.} \quad & g_1(x) = x - 1 \geq 0 \\ & g_2(x) = -x + 2 \geq 0 \end{align*} Since ...
Homer Jay Simpson's user avatar
0 votes
1 answer
57 views

Solving optimal solution of a NLP using the Kuhn-Tucker condition

Consider the following NLP problem. I have solved it using KTP condition. In case II, I get $\lambda = -\sqrt{\frac{2}{3}}$ , but we know that according to the KTP condition $\lambda$ must be $\geq 0$....
Sann's user avatar
  • 63
1 vote
1 answer
48 views

Continuity of KKT Multipliers

Suppose I have a function $f:X \times \Theta \rightarrow \mathbb{R}$, $n$ choice variables $\bf{x} \in X \subset \mathbb{R}^{n} $ and $m$ parameters $\bf{\theta} \in \Theta \subset \mathbb{R}^{m} $. $...
econ_ugrad's user avatar
2 votes
2 answers
88 views

An optimization problem over the probability simplex

In my lecture notes, it is claimed with no justification that the solution of the optimization problem $$\begin{align} \begin{split} \min_{x_1,\ldots,x_n\in\mathbb R}\ \ &\sum_{i=1}^n x_i^5 \\ \...
Stratos supports the strike's user avatar
0 votes
0 answers
38 views

Support vector machine problem

The support vector machine problem is described below: $$ \begin{aligned} \operatorname{min}_{w,b}&\frac{1}{2}||w||^2\\ \text{s.t. }& v^{(i)}(w^\top u^{(i)}+b)\geq 1,i=1,...,m \end{aligned} ...
Iris's user avatar
  • 1
0 votes
0 answers
17 views

Under which conditions can a Lagrange multiplier of bounded variation (Stieltjes integral) be expressed by a continuous functional (Lebesgue integral)

My question conerns Example 1 in §9.3 of Luenberger's Optimization by Vector Space Methods. There, he considers the problem of finding $x\in D^n(t_o,t_1)$ (n-vector functions possessing continuous ...
Nicki's user avatar
  • 15
0 votes
1 answer
67 views

Lagrange multipliers or KKT problem

Consider the following: find the absolute max and absolute min of $f(x, y, z) = yz + xz$ over $V = \{(x, y, z) \in\mathbb{R}^3; 2x + y + z \leq 1; x \geq 0, y \geq 0, z \geq 0\}$ Attempts So first of ...
Numb3rs's user avatar
  • 2,408
1 vote
0 answers
95 views

QP formulation of the LCP — KKT conditions

I am reading a book on the linear complementarity problem (LCP) that claims that the necessary KKT conditions for the problem \begin{align} \text{minimize} \quad &z^T(q + Mz) \\ \text{subject to} \...
user316720's user avatar
0 votes
1 answer
29 views

In what way KKT are more efficient or "rigorous" than what I did here?

I solved this exercise and I wanted to ask you in what way using KKT conditions, which here I did not use / wrote down, would have made (IF) the solution better / shorter or the procedure more ...
Numb3rs's user avatar
  • 2,408
1 vote
0 answers
32 views

Does there exist a relationship between Lagrangian Duels of Non-Linear Models and Karush-Kuhn-Tucker Optimality Conditions?

To pre-context this question: I am studying the book Non-Linear Programming Theory and Algorithms Third Edition by MOKHTAR S. BAZARAA, et al. for an independent study course, and this book is a lot ...
Miss Mae's user avatar
  • 911
3 votes
0 answers
205 views

Solving a quadratic program with simple linear constraints

This is related to an attempt at solving this problem : Best rank-$1$ approximation of matrix with condition. Let $M\in\mathbb R^{m\times m}$ be PSD symmetric and $a\in \mathbb R^m$ be such that $0\...
P. Quinton's user avatar
  • 5,385
2 votes
0 answers
46 views

Recovering Primal Optimal Solution from Dual Support Vector Machine

This question concerns a subtle issue in the recovery of primal solution for support vector machine from the dual. None of the sources I read addresses it explicitly. In particular, it was missing ...
nowhere's user avatar
  • 1,026
5 votes
2 answers
176 views

Best rank-$1$ approximation of matrix with condition.

Let $A\in\mathbb R^{m\times n}$ be a real matrix. For any $x,y\in\mathbb R^m$, we write $x\leq y$ if $x_i\leq y_i$ for $i=1,\dots,m$. For any matrix $B$, $\| B \|_F$ is the Frobenius norm and is ...
P. Quinton's user avatar
  • 5,385
0 votes
0 answers
41 views

Is there a closed form solution or an efficient solver for this linearly constrained quadratic minimization problem?

Let $A$ be a $m\times n$ matrix and $u\in\mathbb R^m$. Denote by $0\preccurlyeq x$ for some vector $x$ in $\mathbb R^m$ the relation such that $\forall i$, $0\leq x_i$. I am trying to solve the ...
P. Quinton's user avatar
  • 5,385
2 votes
1 answer
95 views

During constrained optimization with inequalities why must the gradient of the objective be in the same direction as the gradient of the constraint?

I have been reading about constrained optimization and understood when there are just equality constraints but am having trouble understanding when there are inequality constraints. I was initially ...
Slade's user avatar
  • 699
0 votes
2 answers
110 views

Solving optimization problem using KKT conditions

Consider the following objective: $$\min_{x,y} 2x +y$$ subject to: $$\sqrt{x^2+y^2} \leq 2$$ $$x\geq 0$$ $$y \geq 0.5x-1$$ The lagrangian is given by: $$ L(x,y,\lambda_1,\lambda_2,\lambda_3)=2x +y + \...
Sarah's user avatar
  • 387
0 votes
0 answers
49 views

Is the sum of KKT multipliers strictly positive?

In a given constrained optimization problem, the objective is convex and the constraints are strictly convex. I know that at least one of the constraints is binding. The Karush-Kuhn-Tucker multipliers ...
Patricio's user avatar
  • 1,509
0 votes
0 answers
13 views

Sign of Main Function and Lagrangian Multipliers in the Lagrangian Function

I am reading a paper in which Lagrangian method (as part of KKT condition) is used to identify the optimal solution. The model is as follows: $$\underset x Max \sum_{i=1}^n S_i \, log(min(\frac{x_i}{\...
Messiah's user avatar
0 votes
0 answers
25 views

Solve the KKT system of knapsack nonseparable quadratic problem in active-set algorithm

I have a convex quadratic nonseparable knapsack problem defined as follows: $$ \min x^TQx+q $$ $$ s.t. \sum_i{a_ix_i}\leq b, $$ $$ l \leq x \leq u $$ I want to optimize the quadratic function using ...
gdrax's user avatar
  • 1
0 votes
1 answer
37 views

Is the global minimum of a nonconvex function over a constrained set the maxmin of the corresponding Lagrangian?

Let a nonconvex differentiable function $f:X\to\mathbb{R}$ and differentiable constraint $g(x)\leq 0$, with $X$ convex. Does the global minimum of $f$, $f(x^\star)$, with $g(x^\star)\leq 0$ coincide ...
shnnnms's user avatar
  • 185
2 votes
3 answers
504 views

Necessary and Sufficient Conditions for Lagrange Optimisation!

I'd be immensely grateful if someone could spell out in black and white: Which conditions are necessary and sufficient, for Lagrange optimisation? Do necessary conditions become sufficient conditions?...
CormJack's user avatar
  • 370
1 vote
1 answer
79 views

Understanding convex optimization

I am reading about Support Vector Machines and there are some steps that I don't understand regarding convex optimization. I won't get into the specific constraints of SVM's. Our minimization problem ...
user599310's user avatar
1 vote
0 answers
33 views

Maximization of a function defined only in a specific region

Let $f(x)$ be: $f(x) = \begin{cases} \dfrac{(1-x) (t-x (t-2))^2}{16 (x (2 e-1)+1)} & in\,\, \mathcal{R} \\[6pt] \text{Indeterminate} & \text{Otherwise} \end{cases} $ Where $$\mathcal{R} = \...
KArrow'sBest's user avatar
0 votes
1 answer
32 views

Are KKT regularity conditions always fulfilled for a single inequality?

When I was studying the KKT regularity conditions it appeared to me that they would always be fulfilled for a single inequality constraint since LICQ only requires the gradients to be independent at ...
Jannis's user avatar
  • 21
1 vote
0 answers
49 views

Constrained optimization: When are the Lagrange multipliers bounded?

In some texts I have seen arguments for the fact that the Lagrange multipliers of a constrained optimization problem remain bounded. Are there general conditions for that fact? In particular, Let a ...
shnnnms's user avatar
  • 185
0 votes
0 answers
27 views

KKT condition and local minima

For finding the minimum values of $f(x,y) = 4{x^2} + 10y{}^2$ on the disk ${x^2} + {y^2} \le 4$ Solution:\ $L(x,y,\lambda ) = f(x,y) + \lambda g(x,y)\,with\,\,g(x,y) = {x^2} + {y^2} - 4$ ${L_x} = 8x +...
Cordoba's user avatar
  • 11
0 votes
1 answer
85 views

Maximizing a quartic polynomial over an interval

Given $c > 0$ and $u > l > 0$, $$ \max_{x \in \Bbb R} \, \left( 1 - 2 c x^2 \right)^2 \quad \text{subject to} \quad l \leq x \leq u $$ Can the maximum value be found in terms of $l$ or $u$? ...
Saeed's user avatar
  • 113
3 votes
0 answers
61 views

How to convert MLCP to LCP

Suppose I have the following mixed linear complementarity problem: $$ \begin{align*} a+Au+Cv&=0\tag{MLCP}\\ b+Du+Bv&\geq0\\ v&\geq0\\ v^\top\left(b+Du+Bv\right)&=0 \end{align*} $$ ...
R.Jackson's user avatar
  • 233
0 votes
0 answers
19 views

KKT Condition and sufficient condition

I have confusion about the KKT condition in a nolinear optimization, in some links we found that KKT method assures only the necessity conditon for local stationary point, however, there are some ...
Cordoba's user avatar
  • 11

1
2 3 4 5
10