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
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 (-...