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.
0
votes
0answers
14 views
When is LICQ useful in KKT conditions?
KKT establishes a set of criteria for differentiable optimisation problems related to strong duality (i.e. when primal optimal equals dual optimal). In particular, KKT conditions are necessary for ...
1
vote
1answer
26 views
How to imply the vanishing gradient condition in KKT?
In Boyd's Convex Optimisation, the following optimisation problem is considered
$$
\begin{align}
\min\quad & f_0(x)\\
\text{s.t.}\quad & f_i(x)\le 0,\quad i=1:m,\quad m\in\Bbb Z_{\ge 0}\\
&...
0
votes
0answers
11 views
Equivalence of two KKT conditions
The KKT conditions are usually defined as follows
\begin{align}
\nabla_x \cal L(x^*) &= \nabla f(x^*) - \sum_{i\in\cal I}\mu_i g(x^*) - \sum_{i\in\cal E}\lambda_i h(x^*) = 0
\\
g(x^*) &\leq ...
0
votes
0answers
14 views
Linear Program with finite optimal value has strictly complemenetary solution
In my lecture, the following statement was given without any proof:
Given a primal-dual linear problem
(P) $$\{min~ c'x \mid Ax=b, x \geq 0\}$$
(D) $$\{max~ b'y \mid A'y+s=c, s \geq 0\},$$
it ...
0
votes
0answers
27 views
Solve optimization problem using KKT conditions
I'm trying to understand the solution to Boyd and Vandenberghe Problem 5.30:
Boyd and Vandenberghe Problem 5.30
The Lagrangian is $$L(X,\nu)=\text{tr}X-\log\det X+\nu'\left(Xs-y\right),$$ so the ...
0
votes
0answers
14 views
Derive LCP from KKT conditions of a QP
I'm working through this tutorial on LCPs and interior point methods. In it, the authors claim that the following quadratic program
$$
\begin{aligned}
\min \quad& \frac{1}{2}u^TQu - c^Tu\\
\text{...
0
votes
1answer
25 views
Can KKT be used in minimization s.t to constant param
Can KKT be used :
min g(x)
s.t x>=constant
where constant > 0
I have read this
The Kuhn-Tucker method:
here says that
This is an alternative, and ...
0
votes
1answer
32 views
Local optimality of non-convex quadratic minimization with linear constraints
We are interested in minimizing a quadratic function, which is not convex. The feasible set is a polyhedron. We know that the global minimum is at a vertex when the function is concave.
Also, there ...
0
votes
0answers
62 views
How to solve this Non linear optimization problem?
I need to minimize the below-mentioned expression.
$ L = min (a_0-b_0*(p_1+p_2))^2 + (p_1*y1+p_2*y)$ ,with
s.t p_1 >=0 ,p_2 >=0
Here ...
0
votes
0answers
22 views
Explain what happens if you use KKT to solve this problem
Explain what happens if you use KKT to solve this problem:
\begin{equation*}
\begin{aligned}
& \underset{(x,y)\epsilon \mathbb{R}^2}{\text{minimize}}
& & x+y \\
& \text{subject to}
&...
0
votes
0answers
14 views
Optimize a strictly decreasing simple function $f(Ax)$ using KKT condition
$f:\mathbb R^n\to \mathbb R$.
$A$ is a $n\times n$ matrix.
Solve:
$$\min_{x=(x_1,x_2,...x_{n})} f(Ax)$$
s.t. $$x_i>0 \ \forall i$$
$$\sum_{i\in \{1,...n\}} x_i=1$$
$f$ satisfies: if $f(Ax)<...
2
votes
0answers
52 views
Can $f(x) = \sqrt{x_1 x_2} + \sqrt{x_3 x_4}$ be solved by Kuhn–Tucker conditions?
Consider
$\max_{x_1, x_2, x_3, x_4} f(x) = \sqrt{x_1 x_2} + \sqrt{x_3 x_4}$
s.t. $\; p_1x_1 + p_2x_2 + p_3x_3 + p_4x_4 \le w$
I know we can solve the max problem through separately considering ...
1
vote
1answer
43 views
Find the orthogonal projection of $y \in \mathbb{R}^3$ onto the space $\{x: x_1^2 + 2 x_2^2 + 3 x_3^2 \leq 1\}$
Find a formula for the orthogonal projection of $y \in \mathbb{R}^3$ onto the space $\{x: x_1^2 + 2 x_2^2 + 3 x_3^2 \leq 1\}$. The formula should depend on a single parameter that is a root of a ...
0
votes
0answers
16 views
Critical points (Undefined partial derivatives) and KKT condition
I am going through the contents of KKT conditions. But it seems to deal with only cases that partial derivatives of the Lagrangian function $L$ being nonnegative. Is there any case where the local ...
0
votes
0answers
40 views
Operation Research penalty function and KKT
I have a problem as this. Wish someone could help me! Thanks a lot!
0
votes
0answers
13 views
Does any one know how to derive this KKT condition from the lagrangian function?
(1) uplink sum rate maximization
(2) lagrangian function
(3)KKT condition
As the paper said,$24(a)~24(f)$ is derived from the (2) lagrangian function,i know how to derived them from lagrangian ...
1
vote
2answers
115 views
Minimize the weighted sum of reciprocals
Let $\mathbf{a}_{i} \in \mathbb{R}^{M}$ with $\|\mathbf{a}_{i}\|^{2} = 1$, $\forall i = 1, \ldots, N$.
I need to solve the following problem in closed form:
\begin{align}
\displaystyle \mathrm{...
0
votes
0answers
28 views
How to solve this nonlinear optimisation problem?
I have the following optimization problem where $K>0$.
\begin{align*}
\min_{y_1,\ y_2\ge 0} 2k(\exp(-y_1)+\exp(-\min(y_1,y_2)))+2y_1+y_2.
\end{align*}
I divided into two cases:
Case 1: $y_1\...
0
votes
0answers
13 views
Strong Duality in Hilbert Spaces for convex problems?
Setting
I'm looking for a proof of the following fact,
if $f,g$ are lower-semi-continuous and convex function from a Hilbert space $\mathscr{H}$ to $\mathbb{R}$, with $f$ strictly convex continuous.
...
0
votes
1answer
50 views
Silly Quadratic programming
Suppose that I want to minimize the function $x^2$ subject to the contraint
$$
ax\leq b,
$$
for some $b> 0$. I solved the problem if the contraint is an equality but I'm not sure how to go about ...
1
vote
1answer
39 views
Non linear optimization, KKT
max: $10x_1-2x_1^2-x_1^3+8x_2-x_2^2$
s.t.
$x_1+x_2≤2$
$x_1≥0$
$x_2≥0$
I'm supposed to write down the KKT conditions, show that (-1,-1) is not optimal and to find the solution to this problem.
...
0
votes
0answers
45 views
Using kuhn tucker to solve non negativity constraints
George likes breakfast tacos and milk. His utility is given by $u(t, m) = t + 5 \ln(m)$. Suppose tacos
and milk both cost 1 dollar a piece. How should George spend the $\$4$ he has set aside for ...
3
votes
1answer
62 views
Reference Request: KKT in Hilbert Space
Are there analogues of Slater's condition and the KKT conditions in separable Hilbert spaces? Does the infinite dimensionality pose a problem?
1
vote
0answers
22 views
SVD for constrained Optimization
Given the following constrained optimization:
$argmax_{W_1, W_2} W_1^TMW_2 $ subject to $W_1^TW_1 = I$ and $W_2^TW_2 = I$.
The closed form solution $(W_1^*, W_2^*)$ is found through SVD ...
1
vote
0answers
29 views
Applying KKT conditions
This is in relation to this paper
I am looking for ways to optimize Recall @ fixed Precision ($R@P$) for a machine learning problem and i didnt want to use accuracy as a proxy for $R@P$. Upon ...
0
votes
0answers
51 views
Explanation of Karush Kuhn Tucker conditions?
Can somebody please explain how we get the Karush Kuhn Tucker conditions, especially the complementary slackness, without using the crutches of jargons? I am not well versed in what dual problems or ...
0
votes
1answer
34 views
Kuhn-Tucker question with two inequality constraints
I've been asked to solve the following problem.
max $10x-5x^2+2y-y^2+25$
subject to
$1-x-y\ge0$
$1-x^2-y^2\ge0$
Is anyone able to solve this by hand? NB: I've been told that the KT assumptions ...
0
votes
1answer
36 views
When are KKT conditions indeed necessary first order conditions?
Somewhat based on: Reformulation of optimization problem using kkt and lagrange conditions
Say I have the following optimization problem:
$$ \begin{aligned}
\min_{z}\min_{y} \, &\frac{1}{2} y^T \...
0
votes
1answer
64 views
KKT conditions strict inequality constraints
Some people asked questions about KKT conditions with strict inequality constraints, such as
Kuhn Tucker conditions with strict inequality constraints?
Questions about constraints and KKT conditions
...
1
vote
1answer
93 views
Dual problem of unconstrained linear least squares
The following seemingly simple question is confusing the heck out of me:
Take the least squares regression problem (for $X \in \mathbb{R}^{n×p}$ and $y \in \mathbb{R}^n$):
$$\min_{\beta \in \...
1
vote
1answer
83 views
Optimization under constraints - unique solution or not
Say we have a problem such as minimize $f(x)$ such that $h(x)=0$ and $g(x) \leq0$. Let the minimum achieved under these constraints be $f(x^*) = p^*$. My question is:
If $f(x)$ is convex, are $p^*$ ...
-1
votes
2answers
34 views
Langrarian multiplier [closed]
Consider the following function
$$f(x, y)=x^4-y^2$$
And Set $A=\{(x,y)\in R^2: x^2+y^2=1\}$
is required.
find the Lagrangian equation that determines the extreme point of $F$ on $A$ and calculates ...
1
vote
1answer
48 views
Reformulation of optimization problem using kkt and lagrange conditions
Following setup:
$$ \begin{align}
\min_{y} &\frac{1}{2} y^T \bar{H} y \left(=V_k-V_{k+1}\right) \\
\text{s.t. } &x_{k+1}=Ax_k+Bu_k^*\\
&U_k^* = \underset{U_k}{\arg \min} V_k,\...
0
votes
1answer
25 views
Finding global maxima with Kuhn-Tucker conditions (and distinguish them from other critical points)
We want to maximize $(x-1)^2 + (y-1)^2$ restricted to $x + y \le 2$ and $x, y \ge 0$.
I tried the following combinations:
$x \gt 0, y \gt 0$ This led me to no critical point.
$x \gt 0, y = 0$ This ...
1
vote
3answers
110 views
Minimum of the quartic $(x^2-1)^2+y^2$ using KKT conditions
Consider the following optimization problem.
$$\begin{array}{ll} \text{minimize} & (x^2-1)^2+y^2\\ \text{subject to} & x^2 - 4 \le 0\\ & x + y \le 0\end{array}$$
Using KKT ...
1
vote
1answer
75 views
Confusion about definition of KKT conditions
In this link https://www.cs.cmu.edu/~ggordon/10725-F12/slides/16-kkt.pdf you can find this:
And in the Nonlinear programming book by Bazaraa page 207 you can find this:
My question is
Are those ...
0
votes
0answers
22 views
Convert function for KKT
I wanted to ask how can I determine when a function should stay as it is or if I should restate it with changing functions and constraints signs?
e.g.:
$$ f(x) = -(x_1+1)^2 -2(x_2+1)^2 \\ s.t: -x_1-...
0
votes
1answer
39 views
Dual optimization problem, decomposition.
I have the following problem:
$\min x_1 ^ 2 + x_2 ^2$
s.t.
$x_1 + x_2 \ge 1$
$x_1 \ge 0$
$x_2 \ge 0$
I have three inequality constraints, so my lagrangian would be
$L = x_1 ^2 + x_2 ^2 + \lambda_1 (-...
1
vote
2answers
87 views
KKT optimality conditions in optimization exercise
Consider the following problem $$\max \Big(x_1-\frac{9}{4}\Big)^2+\big(x_2-2\big)^2$$ $$s.t.\quad x_2-x_1^2\ge0\\ x_1+x_2\le 6\\x_1,x_2\ge0$$
Write the KKT optimality conditions and verify ...
0
votes
1answer
30 views
How to find if following function is Convex?
I want to optimize the following function $U = ...$ using KKT. I am still learning KKT. However, I cannot understand how I can find if the following function is a convex function?
$$U = \frac{(A-1)B\...
1
vote
1answer
59 views
KKT conditions holds true under Cottles's constraint qualifications?
Exercise
Solution:
Could someone please explain why the reached contradiction solves the exercise?
I can understand the solution but I don't know how does that implies that $\overline x$ is ...
2
votes
2answers
45 views
Does a constrained nonlinear program only have one KKT point?
I am just wondering whether or not a constrained nonlinear program has only one KKT point?
Intuitively, I think this is wrong and the only thing we can conclude is that any KKT in such program is ...
0
votes
1answer
82 views
How to apply KKT conditions (to minimization) to solve maximization problem?
Consider the following problem
$$ \max x_1^2+4x_1x_2+x_2^2 \\ s.t. x_1^2+x_2^2=1 $$
a. Using conditions KKT, find the candidates to be solution.
b. Using second order conditions, stablish the ...
0
votes
0answers
46 views
lagrange multipliers of function log
I am using lagrangian multiplier with KKT conditions for the first time.
I have an equation :
$max \space g(p_f,p_m)= (\frac{h_f p_f}{N})(\frac{h_m p_m}{N})$
subject to :
$h_fp_f-Q<0
\\p_f-p^...
2
votes
1answer
96 views
Minimizing a sum of decaying exponentials subject to constraints
Consider the following problem
\begin{align*}
\min_{x}\quad\sum_i\sum_j&\exp(-a_{ij}x_{ij})\\
\text{subject to}\quad\sum_i\sum_j&x_{ij}=n\\
&x_{ij}\ge0\,\,\forall i,j
\end{align*}
where $x\...
0
votes
0answers
18 views
Two methods for second order sufficient conditions for constrained optimization
There are at least two methods to verify those type of conditions stated in their weaker form:
projected Hessian
bordered Hessian
In these course notes (section 2.6 Projected Hessians - page 19 in ...
0
votes
0answers
46 views
Skills to solve KKT condition equations.
The problem is
$$\begin{aligned}
\min ~&\frac{1}{2}\|x\|_2^2\\
\text{s.t.}~ &a^Tx=b\\
&x\ge 0
\end{aligned}$$
How can we find the optimal solution with KKT condition?
My thinking:
...
0
votes
0answers
20 views
What is the dual function and solution of this function, subject to a restriction?
I woul like to know what is the dual function and then, what is the solution of the dual problem of:
$\begin{align}
{\bf x^*} = \arg \min_{{\bf x}\in{\bf X}}f({\bf x}) = \frac{1}{2} {\bf x^t P x}
\...
2
votes
1answer
52 views
Optimal distribution using KKT condition
I have following problem
\begin{eqnarray}
&\min_{p,t}&\quad \sum_{i =1}^n \frac{a_i^2}{p_i} \\
&s.t.& \sum_{i =1}^n p_i = b \\
&& 0 \leq p_i \leq 1\quad \forall i
\end{...
0
votes
0answers
15 views
First Kuhn-Tucker condition from auxilliary variable
In the optimisationsproblem
minimise $f_0(\textbf{x})$ subject to $f_i(\textbf{x})\leq0 \quad (i=1,2,\ldots,m), \quad \textbf{x}=(x_1,x_2,\ldots,x_n)$
this can be rewritten into
minimise $f_0(\...
