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
30 views
Linear inequality constraint - in KKT optimisation
I have a query regarding whether KKT is optimal with some linear inequality constraint and non-linear inequality constraint. For KKT to be optimal the inequality constraints must be convex.
We know ...
0
votes
0answers
31 views
Non-convex QCQP with embedded variable
I have the following problem whose optimal solution (if possible), I would like to find.
$\min_{\mathbf{f}} \left\| \mathbf{L}_1 \mathbf{f} \right\|^2_2 + \left\| \mathbf{L}_2 \mathbf{f} \right\|^2_2 ...
0
votes
1answer
26 views
how to use KKT conditions for an exponential function
our teacher gave us a problem in the exam that I failed to answer it even after passing it, and I ask for an explanation from people here please...
this is the problem :
let K be a subset of $\Bbb R^...
0
votes
0answers
16 views
Equivalent Convex programs with different solutions
Let $R_\kappa \in \mathbb{R}^{d \times d}_{sym}$, $S_\kappa \in \mathbb{R}^{d \times d}_{sym}$, $\eta_\kappa \in \mathbb{R}^+$, for a set $\{ \kappa \}$. Define a optimization problem $(1)$ as
\begin{...
0
votes
0answers
25 views
The operation of KKT condition in lagrange function
Does kkt condition do the partial differential to the lagrange multiplier i wanted,and set the equation become zero? i mean,
$L=P_E+\alpha [P_T-\sum\limits _{k=1}^{K}p_k]+\gamma [\sum\limits _{j=1}^{...
0
votes
0answers
35 views
How to correctly use KKT conditions?
Let $A\in \mathbb{R}^{n\times n}$ be a positive definite matrix. Then find
\begin{equation}
\max_{|x_i|\leq1}x^TAx
\end{equation}
Here I want to use KKT conditions to show that $|x_i|=1$ is an ...
1
vote
0answers
25 views
KKT conditions - Equality constraints
I have an equality constraints as
$\qquad \qquad \min_x f(x) \\ \qquad \qquad s.t. \quad Ax \leq b \\\qquad \qquad \qquad x = h(x)$.
The KKT conditions of the minimization without the equality ...
2
votes
1answer
55 views
KKT condition with equality and inequality constraints
find the KKT point of the following problem:
$$\min\quad f(x_1,x_2)=(x_1-3)^{2}+(x_2-2)^{2}\\
subject\quad to\qquad \qquad \qquad \qquad \qquad\qquad\\
x_1^{2}+x_2^{2}\le5\\
x_1+2x_2=4\\
x_1\ge0,x_2\...
1
vote
1answer
43 views
How to handle optimization problems when optimization variable is matrix?
Suppose we have the following optimization problem
$$
\min_{0\preceq M \preceq I} y^TMy
$$
where $y \in \mathbb{R}^n$ and $M \in \mathbb{R}^{n \times n}$ is a positive semi-definite matrix. Notice ...
0
votes
0answers
17 views
Minimize $\left\|BA\right\|_2 $ under these constrain
Minimize $\left\|BA\right\|_2$
while B is a given $m*n$ matrix with rank n and A is an $n*t$ matrix which is not given.
Such that $B'*u_{1}*v_{1}' = a*u*v$;
$\left\|A\right\|_2 = b$.
While
...
0
votes
1answer
28 views
Lagrange duality compared with Lagrange multiplier method
As we all know, Lagrange multiplier method says:
in order to find the extremum of $f(x)$ over $x$, s.t. $g(x)=0$,
one instead finds the extremum of $f(x)+\lambda g(x)$ over $x$ and $\lambda$. Note ...
1
vote
1answer
44 views
Find KKT point of $\min_{x \in \mathbb{R}^4} x^Tx$ subject to $x^TAx \geq 1$.
onsider the following problem:
$$\min_{x \in \mathbb{R}^4} x^Tx$$
over $C=\{x \in \mathbb{R}^4 \mid x^TAx \geq 1\}$ where $A \in \mathbb{R}^{4 \times 4}$ is a symmetric matrix with two distinct ...
0
votes
1answer
47 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
32 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
14 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
19 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
1answer
39 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 ...
1
vote
0answers
28 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{...
-1
votes
1answer
35 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
45 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
63 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
26 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
15 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
55 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
47 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
18 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
14 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
125 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
30 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
19 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
55 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
40 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
58 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
72 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
32 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
31 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
93 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
42 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
56 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
118 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
124 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
114 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
55 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
114 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
110 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 (-...
