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.
492
questions
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) =...
- 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$ ...
- 71
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 ...
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 ...
- 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 ...
- 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 ...
- 11
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 ...
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 ...
- 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 ...
- 281
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}^...
- 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$ ?
- 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 ...
- 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\...
- 33
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 ...
- 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 ...
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 ...
- 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 ...
- 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(...
- 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 ...
- 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 ...
- 21
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 ...
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 ...
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$....
- 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} $. $...
- 101
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 \\
\...
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}
...
- 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 ...
- 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 ...
- 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} \...
- 57
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 ...
- 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 ...
- 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\...
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 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 + \...
- 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 ...
- 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}{\...
- 1
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 ...
- 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 ...
- 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?...
- 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 ...
- 226
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} = \...
- 15
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 ...
- 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 ...
- 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 +...
- 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$?
...
- 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*}
$$
...
- 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 ...
- 11