Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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
1answer
17 views

KKT condition for the proximal algorithm

This slide shows that the KKT condition for the proximal gradient descent is this inequality. I don't know where this comes from. Using KKT , we can only get equality for the stationary condition, ...
1
vote
0answers
30 views

Dual of linear function with convex and non-convex constraints

I would like to compute the dual of the following problem by using the KKT conditions. However, due to form of the first constraint I am not able to obtain the dual. The problem is the following \...
0
votes
0answers
40 views

Optimizing a function under strictly positive constraint

Find x and y that optimise \begin{align} f(x,y) &= (-a-y)(\Psi(y)-\Psi(x+y)) + (b-x)(\Psi(x)-\Psi(x+y)) \\ &-\log \Gamma(x+y) + \log\Gamma(x) + \log\Gamma(y) \end{align} where a, b are ...
0
votes
1answer
51 views

KKT optimisation - condition of inequality constraint being zero

For example, given the following: Minimise $$ f(x_1, x_2) $$ Subject to $$ h(x_1, x_2) = 0 $$ $$ g(x_1, x_2) \leq 0 $$ The KKT conditions are written out as $$ l(x, \lambda, \mu) = f(x_1, x_2) +...
1
vote
0answers
37 views

Derive the KKT conditions for the following problem. [closed]

\begin{align} \min &\ \text{tr}(CX) - \log \det X \\ \text{s.t} &\ \text{tr}(AX) = b \\ &\ Xs = y, X \in S^n_+ \end{align} with $b \in \mathbb{R}, y \in \mathbb{R}^n, s \in \mathbb{R}^n$ ...
4
votes
1answer
26 views

How to project a vector on a set defined by linear inequality constraints through KKT conditions?

I need to find the projection $x \in \mathbb{R}^{k}$ of a vector $z \in \mathbb{R}^{k}$ on the set defined by $Y \cdot x \geq 0$ where $Y$ is a (given but no specific property) matrix of size $m \cdot ...
1
vote
1answer
48 views

General solution to linear program?

Source of the Problem The problem comes from an application in economics concerning trade between agents to maximize aggregate "wealth". More exactly, there are $m$ agents and $n$ groups and we ...
0
votes
1answer
32 views

How to convert constrained optimization problem to non-constrained using lagrangian and kkt

I have a nonlinear objective function with a nonlinear set of inequality constraints and I am trying to reformulate the problem using the Lagrangian function. My goal is to transform a constrained ...
1
vote
2answers
58 views

Solve KKT conditions of the following problem

I'm having problems solving the following $\min f(X) = −3x^2 +y^2 +2z^2 +2(x+y+z) $ subject to $c(X):=x^2+y^2+z^2−1=0$ Now, I get the KKT: $-6x +2 -2\lambda x = 0 $ $2y +2 -2\lambda y = 0 $ $4z +...
0
votes
0answers
7 views

Quadratic problem with non-negativity constraints: substantiate the hardness of analytical solution

I have a quadratic program $$ \underset{V\mathbf{x}=\mathbf{d}, \mathbf{x} \geq \mathbf{0} }{\min} f_{\mu}(\mathbf x)= \sum_{i=1}^{n} \text{Var}\left(R_{i}\right)-\sum_{i=1}^{n}\mu\text{E}(R_i), $$ ...
0
votes
0answers
13 views

KKT conditions and weak duality

KKT conditions are always necessary for optimality and are sufficient under strong duality. Why is strong duality needed for sufficiency? Why is weak duality not sufficient?
0
votes
0answers
25 views

How can we check the convexity of the two variables function?

I am working on the problem of KKT conditions with inequality constraints and at the last stage, it needs to check if the point in question satisfies Slater's constraint qualification. According to ...
1
vote
1answer
16 views

For a Bi-level Mixed Integer Linear Program with integer variables in the lower, can I use KKT conditions to reduce the problem to a single level?

For example, my optimization formulation looks something like this: max $-10y-x$ s.t. $y=$ arg {min $20y-25x\leq 30;2y+x\leq 10;-y+2x\leq 15;10y+2x\geq15$} $y$ integer In order to convert this to ...
2
votes
2answers
63 views

Where am I wrong in my understanding about the activeness of the constraints?

I have following convex optimization problem $$\text{min. }~~ x~\\ \text{s.t.}~~~\frac{y^2}{x}\leq z\\ y+z\leq c$$ where $\{x,y,z\}$ are the non-negative variables and $c$ is some positive ...
0
votes
0answers
37 views

Optimization of $\min{ c^{T}x+b^{T}y}$

I am new to optimization, and whenever we get an LP of the sort: $\min{ c^{T}x+b^{T}y}$ s.t. $Ax\leq b$ $A^{T}y=-c$ $y \geq 0$ Assume that there is a valid point that fulfills the restrictions. ...
1
vote
1answer
48 views

How to handle the case when KKT condition is always false for this toy case?

For the following simple problem: $$\begin{aligned} \min_x & (x-2)^2\\ s.t. \ \ & x^2=0\\ &x^2 \le 0 \end{aligned}$$ Since there is only one feasible point $x=0$, the answer is obvious. ...
1
vote
0answers
28 views

Find minimizer with active constrains

I am trying to find a minimizer for a function $ f : \mathbb R^2 \rightarrow \mathbb R $ with constrains $ c(x) \geq 0, c : \mathbb R^2 \rightarrow \mathbb R^4 $. I also need to find out the correct ...
0
votes
1answer
56 views

Using the KKT Conditions in the Non Convex Case (Quasi Convex)

It is know that if the problem is convex then we can use the KKT conditions to find the solution. However, is it still possible to use the KKT conditions in the same way if the objective function is ...
0
votes
0answers
40 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
36 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
38 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
17 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
54 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
48 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
68 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
147 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
67 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
19 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
34 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
52 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
156 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
39 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
18 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
25 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
48 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
76 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
44 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
67 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
64 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
31 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
16 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
60 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
29 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
43 views

Operation Research penalty function and KKT

I have a problem as this. Wish someone could help me! Thanks a lot!
0
votes
0answers
21 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
138 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
22 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
59 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 ...