Skip to main content

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.

Filter by
Sorted by
Tagged with
4 votes
0 answers
33 views

Existence and Uniqueness of Equilibrium points for Concave N-Person Games

I am reading a paper. I have a problems with understanding their lemma Lemma: The nonzero elements of every vector $u \in U(x)$ are given by a vector $\bar{u} \in E^k, \bar{k} \leqslant k$, where $\...
Pipnap's user avatar
  • 431
2 votes
0 answers
33 views

Wrong sign in co-state of optimal control problem

Consider the following deterministic optimisation problem \begin{align} J(t) = \min_{c(t)} \ & \frac{1}{2} \int_0^\infty e^{-\delta u} \left( x(u)^2 + \lambda y(u)^2 \right) du \\ s.t. \ &c(t) ...
NC520's user avatar
  • 341
0 votes
0 answers
8 views

Lagrange mutilplier and KKT theorem problem(maybe) with some probabilities

Suppose we want to maximise a expected utility function: $$E_1(u(C_1,C_2,C_3)) $$ subject to following constraints. There are two possible situations each with probability $\frac{1}{2}$. $$C_1 + S_1 = ...
Chang Henry's user avatar
1 vote
0 answers
50 views

analytical solution to a toy-sized but interesting optimization problem

My question follows after the initial context. My research includes solving a subproblem many many times - maximizing the Euclidean distance between a pair of convex neighborhoods, e.g. between an ...
William M.'s user avatar
1 vote
0 answers
33 views

Sufficency of the KKT condition

This is a beginner question so I apologize. The problem is to minimize $f(x,y) = 5x-3y$ subject to $x^2+y^2 = 136$. Let the Langarian be $L(x,y,u) = 5x-3y+u(x^2+y^2-136)$ The KKT condition gives that ...
Phil's user avatar
  • 1,710
0 votes
0 answers
27 views

Prove that the feasible set is non-empty.

Consider the following optimization problem: $$ \begin{alignat}{3} & \underset{{\bf x}}{minimize} \quad & f({\bf x}) &= x_{0,0} & & \\ & subject~to \quad & h({\bf x}) &...
Wojtek's user avatar
  • 1
0 votes
0 answers
29 views

Prove that the inequality constraints are active at the optimal solution.

Consider the following optimization problem: $$ \begin{alignat}{3} & \underset{{\bf x}}{minimize} \quad & f({\bf x}) &= x_{0,0} & & \\ & subject~to \quad & h({\bf x}) &...
Wojtek's user avatar
  • 1
1 vote
0 answers
22 views

constrainted optimisation proof using $Ax\leq b$

I am trying to prove the following, let $x^*$ be a local minimum of the constrained optimisation problem- minimise $f(x)$ subject to $Ax\leq b$. I have tried using the KKT 1st order conditions and ...
peely458's user avatar
1 vote
0 answers
21 views

Efficient Method for Solving KKT problems

In the attached inequality, constrained, optimisation, problem. Looking at the specific case where $\lambda_1 = 0, \lambda_2 > 0$ that I am trying to solve, you can see that I have managed to find ...
CormJack's user avatar
  • 452
2 votes
3 answers
111 views

Checking KKT Constraint Qualifications

When checking whether the CQ are satisfied in KKT, i.e. checking for Linear Independence amongst all combinations of the constraints. Is it true to say we only need to check combinations that could be ...
CormJack's user avatar
  • 452
1 vote
1 answer
40 views

Maximize this function subject to "too general" conditions?

I'm facing a problem I cannot understand how to solve. I have to find the max of $f(x, y) = 2x + y$ over the set $V = \{(x, y) \in\mathbb{R}^2:\ \sqrt{x} + a\sqrt{y} \leq 2, x\geq 0, y \geq 0\}$ with $...
Heidegger's user avatar
  • 3,482
0 votes
0 answers
43 views

Are KKT necessary optimality conditions in general non-convex problems? (with non-zero duality gap)

I have seen similar questions here, but have not been able to clarify mine. KKT are necessary conditions for optimality if strong duality holds (Boyd and Vandenberghe, section 5.5.3). However, strong ...
joselo's user avatar
  • 1
1 vote
0 answers
36 views

Determining Optimal Policy Probabilities in Off-Policy PPO Using KKT Conditions

I'm working through a paper on Proximal Policy Optimization (PPO) and am trying to understand the derivation of the optimal policy probabilities for the off-policy case as expressed in Equation 16. &...
Amantuer Rewuhan's user avatar
1 vote
0 answers
107 views

Optimisation problem in two variables

I have to understand a thing about this exercise: find the minimum of $f(x, y) = (x-2)^2 + y$ subject to $y-x^3 \geq 0$, $y+x^3 \leq 0$ and $y \geq 0$. Now, I solved the problem quite easily in a ...
Enrico M.'s user avatar
  • 26.3k
0 votes
1 answer
29 views

How to solve $\min(x^2+y^2)$, $x\ge1, y\ge-2$, using the KKT conditions?

I'm trying to understand better optimisation problems and in particular the KKT conditions. To this end, consider the minimisation problem $\min(x^2+y^2)$ subject to $x\ge1$ and $y\ge -2$. It's clear ...
glS's user avatar
  • 7,095
0 votes
1 answer
44 views

Why am I getting a constant for alpha when I take the derivative of my objective function?

I am trying to solve this simple optimization problem: Minimize $f(x,y)=x^2+y^2$ over $\frac{1}{4}x^2+\frac{1}{9}y^2-1=0$ I get $L = x^2+y^2+\alpha(\frac{1}{4}x^2+\frac{1}{9}y^2-1)$ then $0=\frac{\...
Beans's user avatar
  • 149
0 votes
0 answers
18 views

General questions on optimisation problems

Sorry to bother you again, hopefully someone will answer again... I have some questions about optimisation problems, related to KT conditions (but maybe not only). My questions are rather theoretical, ...
Heidegger's user avatar
  • 3,482
0 votes
1 answer
52 views

Is this SDP analytically solvable?

I am studying the following semi-definite problem: $$\begin{array}{rl} \textrm{Given:} & W \in \mathbb{R}^{n \times n} \\ \textrm{Minimize:} & u_1 + u_2 + \ldots + u_n \\ \textrm{Subject to:} &...
ConMan's user avatar
  • 25.6k
0 votes
1 answer
46 views

How do I know when a point is a max or a min (multivariable optimisation problem)?

I am stuck in understanding how I can deduce if the solution I found is a max or a min. The exercise reads: $$\max \quad f(x, y) = 2x - y \qquad \text{subject to} \qquad \begin{cases} x^2+y = 2 \\ x+y ...
Heidegger's user avatar
  • 3,482
1 vote
0 answers
22 views

LCP of KKT from a QP without non-negativity constraint and semidefinite Q matrix

Most formulations of the LCP derived from the KKT conditions of a QP tackle problems with non-negativity constraints $x\ge 0$. Wikipedia presents an alternative without the non-negative constraints ...
Bruno's user avatar
  • 19
0 votes
1 answer
41 views

Do Karush Kuhn Tucker $\mu$ conditions have to be unique?

In KKT, we have some optimal point $x^*$ with associated $\mu^*$ value for inequality constraints. Are these $\mu^*$ values unique for a given $x^*$ (for the primal problem)? It seems that when these ...
Andrew Wang's user avatar
0 votes
0 answers
73 views

Simultaneous Zero Values in Complementary Slackness

The complementary slackness condition within the KKT optimality conditions states that $\lambda_i^* f_i(x^*) = 0$ for all inequality constraints $f_i(x) \leq 0$ and for optimal primal variable $x^*$ ...
Inquisitive's user avatar
0 votes
1 answer
48 views

Ref Request: Infinite Dimensional Lagrange Multipliers, KKT Conditions, and Control

I'm looking for a more up-to-date book covering similar material as the second half of Luenberger's Optimization by Vectors Space Methods. That book covers Lagrange multiplier necessary conditions in ...
Smithey's user avatar
  • 705
0 votes
1 answer
71 views

Application of KKT-Theorem Does Not Give Expected Result

I've got this exercise for uni that I've been absolutely racking my brain over for the past couple hours, the problem goes as follows: Let $\theta_1, \cdots, \theta_d \in (0, \infty)$. Consider the ...
Jord van Eldik's user avatar
0 votes
0 answers
10 views

Proofing Slater's condtion iterative?

If I have a convex optimisation problem for an engineering application of the standard form: $$ \begin{equation*} \begin{aligned} \min_{x} \quad & f(x)\\ \textrm{s.t.} \quad & g_i(x) \leq 0 \\ ...
Michael's user avatar
  • 53
0 votes
0 answers
31 views

KKT necessary conditions - applied to linear sum function

I'm having issues interpreting the KKT conditions. Consider a very simple problem (from e.g. Economics) $$ \max_{(x_1, x_2) \in \mathbb{R}^2_+} x_1 + x_2 \quad \text{s.t.} \quad p_1 x_1 + p_2 x_2 = w $...
mwaddoups's user avatar
0 votes
0 answers
26 views

How to use KKT to solve the problem with multiple sets of constraints

I have two sets: $I=\{1,2,\dots,n\}$ and $J=\{1,2,\dots,m\}$ and a set of subsets as $P=\{p_1, p_2, \dots, p_d\}$ that each member of $P$ is a subset of $I$, for example, $p_d=\{3,4\}$. This is my ...
Hami's user avatar
  • 3
0 votes
2 answers
82 views

Prove optimality of constrained convex optimization problem analitically (using KKT conditions)

I'm trying to prove that the constrained convex minimization problem with decision variable $\boldsymbol{x} \in \mathbb{R}^{n}$ given by $$ \min_{\boldsymbol{x}} \Vert \boldsymbol{x} \Vert_{2} \text{ ...
Bart Wolleswinkel's user avatar
0 votes
1 answer
42 views

Solving the problem through KKT condition

This is my optimization problem where $n$ is the only decision variable of the problem: \begin{align} \min_{n} \quad &c n \\ \text{subject to:}\quad &\sum_{i \in I} D_{i}x_i \lambda_i &...
Hami's user avatar
  • 3
1 vote
1 answer
57 views

Lagrange multipliers problem, finding the absolute max

I have to find the absolute maximum of $f(x, y, z) = 2xy + 3yz$ over the set $V = \{ (x, y, z) \in \mathbb{R}^3:\ x+y+z \leq 1, x \geq 0, y \geq 0, z \geq 0\}$. I proved the set is both bounded and ...
Heidegger's user avatar
  • 3,482
1 vote
1 answer
83 views

Find solution of optimisation problem $\min_{x} \; x^TAx$ with constraint $\Vert x \Vert^2 \leq 1$

I have to find the solution of the following problem : $A \in R^{n\times n}$ is a symetric positive define matrix $$ \begin{cases} \min_{x} & x^TAx \newline s.c & \Vert x \Vert^2 \leq 1 \end{...
Ippotis TheKing's user avatar
2 votes
0 answers
47 views

Can I use KKT to analytically solve this min-max problem? [closed]

I am new to optimization and I to solve the following optimization problem: $$ \min_{g_i(x) \leq 0, h_i(x) = 0} \max_{ \{p_1, \dots,p_n \} \in \Delta} \sum p_i - p_i x_i $$ where the constraints ...
ABIM's user avatar
  • 6,779
0 votes
0 answers
51 views

Minimizing quadratic cost function over an Euclidean ball

Let $f : \mathbb{R}^d \to \mathbb{R}$ be defined by $$f(\theta) := \| \theta - z \|^2_\Delta := (\theta-z)^t \Delta (\theta-z)$$ where $\Delta = \operatorname{diag}(s_1, \ldots, s_d)$, where $s_i > ...
deque's user avatar
  • 551
0 votes
0 answers
24 views

Help solving Exponential Sum problem using KKT conditions

I am trying to solve the following convex optimization problem where $a_i, b_i >0$ for $i=1,2,3$. I am wondering if it is possible to get a general formula for the optimal solution without checking ...
Zona's user avatar
  • 57
1 vote
0 answers
212 views

Is there a closed form to this quadratic program?

Problem : I am currently trying to solve some optimization problem to get some information about a matrix. In the following, when we have a matrix $A\in\mathbb R^{m\times n}$, $0\leq A$ means that $0\...
P. Quinton's user avatar
  • 6,076
0 votes
1 answer
116 views

Are KKT conditions still necessary and sufficient for optimality in a nonlinear max problem with pseudo-concave objective?

We all know that KKT conditions are necessary and sufficient conditions for optimality in a convex minimization problem (or a concave maximization problem). Recently, I found that the convexity/...
Rex Lee's user avatar
  • 41
0 votes
1 answer
50 views

KKT unconstrained optimization of duals

I've been working through parts of "KKT Conditions, First-Order and Second-Order Optimization, and Distributed Optimization: Tutorial and Survey" and can't fully comprehend it. The problem ...
artems's user avatar
  • 1
0 votes
0 answers
42 views

Irregular points for KKT theorem; $\min(x-4)^2+y^2$ for $x^2+y^2-9\le0,-x-3\le0,x-3\le0$ and $-y-2\le0$

I am solving this optimization problem: \begin{equation} \min (x-4)^2+y^2 \end{equation} subject to \begin{cases} x^2+y^2-9\le0 \\ -x-3\le0\\ x-3\le0\\ -y-2\le0 \end{cases} In the point (0,3) the ...
userF's user avatar
  • 1
0 votes
0 answers
29 views

Karush-Kuhn-Tucker conditions

I am solving this exercise: min $x^2+(y-8)^2$ \begin{cases} y-x^2+2=0 \\ y-7\le0 \end{cases} The solutions are (3,7) and (-3,7) as minima points and (0,-2) as maximum point. For ...
userF's user avatar
  • 1
0 votes
0 answers
79 views

Optimisation Problem Setup and KKT conditions

I am trying to setup an optimization problem with equality and inequality constraints. I want to estimate a specific variable call $\chi$ subject to a minimisation problem -- guidance on the setup and ...
user862800's user avatar
0 votes
1 answer
123 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) =...
Dave299's user avatar
  • 31
1 vote
1 answer
108 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$ ...
user35083's user avatar
0 votes
1 answer
237 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 ...
Confused_intense_thoughts's user avatar
2 votes
0 answers
52 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 ...
Beerus's user avatar
  • 2,493
1 vote
2 answers
231 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 ...
Przemo's user avatar
  • 11.5k
2 votes
0 answers
70 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 ...
user278486's user avatar
1 vote
1 answer
106 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 ...
Waseem Bughio's user avatar
2 votes
1 answer
276 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 ...
cc88's user avatar
  • 81
1 vote
0 answers
267 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 ...
Dylan Dijk's user avatar
1 vote
0 answers
53 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\...
drearien's user avatar

1
2 3 4 5
11