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.
331
questions
0
votes
1answer
18 views
Slaters conditions for a convex optimisation problem
I have the following convex optimisation problem which is assumed to give an optimal solution:
$max: f(x)$
$ a_{i}\leq x \leq b_{i}$ for $i=1,...,n$ and $a_{i}< b_{i}$ where $a_{i}, b_{i} \in \...
0
votes
1answer
29 views
How to use the KKT-conditions for a not-differentiable function using subdifferentials.
First some notation. Let $\dfrac{\partial}{\partial \textbf{x}} f(\textbf{x})$ determine the gradient for a funcion $f:\textbf{R}^n \rightarrow \textbf{R}$, and let the subdifferential be determined ...
0
votes
0answers
16 views
Show that if this nonbinding constraint is deleted, it is possible that $\bar{x}$ is not even a local minimum
Hello guys I am looking for some help for this nonlinear problem
Let $\bar{x}$ be an optimal solution to the problem of minimizing $f(x)$ subject to $g_{i}(x)\leq0, i=1,...,m$ and $h_{i}(x)=0, i=1,.....
1
vote
0answers
15 views
Analytical derivation of linear optimization problem with KKT conditions possible at all?
I would like to find an analytical solution to a linear optimization problem optimizinig over multiple time steps. Following a reduced version of the LP with variables denoted in capital letters and ...
0
votes
0answers
95 views
Tucker Nearness Problem
I'm still not very confident with tensor calculus and I came across a paper that was solving an optimization problem based on Tucker decomposition; I don't understand how, from the initial formulation,...
0
votes
0answers
27 views
Which decision variables to consider in the KKT transformation of a bilevel optimization problem into a single-level one when collocation is used?
I am currently dealing with a dynamic bilevel optimization problem, that is, the variables are changing in time as described here: general problem formulation.
To address the dynamics of the system, ...
0
votes
1answer
34 views
How to minimize $ x $ subject to $ y \le x^3$ and $y \ge 0 $
I have been getting into NLP, the Karush Kuhn Tucker theorem and the Linear Independence Constraint Qualification and I came across this problem.
My first attempt was to solve graphically and I ...
1
vote
1answer
34 views
One dimensional constrained optimization: KKT conditions versus irregular points
In a constrained optimization problem, we search local solutions in the regular points that satisfy the KKT solutions as well as the irregular points. All the local solutions are included in these ...
0
votes
0answers
7 views
Necessity of non negativity conditions of slack variable in KKT
I have the following question:
$\min \frac{1}{2}w\cdot w + \frac{C}{2}\sum_i\xi_i^2$ subject to $y_i(w\cdot x_i + b)\ge1-\xi_i \; \; \forall i $
Where $\xi_i$ are slack variables.
Show that the ...
0
votes
0answers
47 views
KKT after epigraph
$\mathbf{P1}:$ $\max_{\mathbf{x}} \sum_{i}\textrm{min}(~f_i^1(\mathbf{x}),~f_i^2(\mathbf{x}))$
s.t $\sum_i x_i \leq a ~\forall ~i$
Applying epigraph the equivalent problem
$\mathbf{P2}:$$\max_{\...
0
votes
0answers
22 views
Frizt John and KKT with optimization problem
I am trying to find all candidates for a local minimizer in $min\{ -x_1| x_2-(1-x_1)^3\leq 0 , -x_2\leq 0\}$.
Denote $g_1(x)= x_2-(1-x_1)^3$, $g_2(x)= -x_2$, and $I(\bar x)=\{ i|g_i(\bar x)=0\}$
I ...
0
votes
1answer
46 views
Minimize function subject to inequality constraints using KKT conditions
Task:
$$f(x)=x_1^2-2x_2+x_3^2\to \min$$
$$x_1+x_3=1$$
$$2x_1+x_2-x_3\le 2$$
$$x_1\ge0$$
Wolfram Mathematica result: $x_1=0, x_2=3, x_3=1, F(x)=-5$.
GNU Octave result: $x_1=0, x_2=3, x_3=1, F(x)=-5$.
...
0
votes
0answers
35 views
Minimizing quadratic form with quadratic and linear constraints
I am trying to solve the following optimization problem
$$\begin{array}{ll} \text{minimize} & \mathbf{x}^T \mathbf{A} \mathbf{x}\\ \text{subject to} & \left(\mathbf{x}-m\mathbf{1}\right)^T \...
3
votes
1answer
86 views
Question about KKT conditions and strong duality
I am confused about the KKT conditions. I have seen similar questions asked here, but I think none of the questions/answers cleared up my confusion.
In Boyd and Vandenberghe's Convex Optimization [...
0
votes
1answer
28 views
Quadratic programming: KKT Optimality conditions
I am struggling with an exercice with the following quadratic program:
$$min:x_{1}x_{2} + x^{2}_{1} + \frac{3}{2}x^{2}_{2} + 2x^{2}_{3} + 2x_{1} + x_{2} + 3x_{3}$$
subject to
$$x_{1} + x_{2} + x_{3} ...
0
votes
1answer
83 views
Optimization using KKT of a 3 variable function
I want to maximize the function :
$$\sum_{i=0}^n x_i*ln(1+ \frac{ c*y_i*z_i }{x_i})$$
subject to : $$\sum_{i=0}^n x_i \le X_0 \;\;\;\;\;\;\; and \;\;\;\;\;\;\; \sum_{i=0}^n y_i \le Y_0 $$
$$ x_i \;...
1
vote
1answer
32 views
Karush Kuhn Tucker and Optimal Minimum
I am a little not clear on the solutions of KKT Conditions. Suppose we have a convex function $f(x)$ and at a specific $x$ are our KKT conditions fulfilled. Does this make this point a global minimum ...
0
votes
1answer
28 views
Why use Primal-dual Methods for Linear Programs
We know we can solve an LP directly using KKT matrix method, even for QPs this works, for an example problem
$$
\min_{x_1,x_2} x_1^2 + x_2^2 \quad \textrm{s.t.}
$$
$$
x_1 + x_2 = 5
$$
KKT matrix is
...
1
vote
1answer
28 views
Minimize $\sum_{i=1}^p (y_i-x_i)^2 $ such that $\sum_{i=1}^{p'} y_i^2 - R^{2} \le 0$
I'm solving the following optimization problem. Could you please verify if my proof is correct or contains logical mistake? Thank you so much!
Let $x = (x_1,\ldots,x_p) \in \mathbb R^p$, $p' \le p$,...
1
vote
0answers
52 views
Minimize $\frac{1}{2}\sum_{i=1}^p (y_i-x_i)^2$ such that $\sum_{i=1}^p y_i - 1=0$ and $\forall i \in [\![ p ]\!]: -y_i \le 0$ by KKT method [duplicate]
I asked how to solve this optimization here. I found this approach by combining @Royi's idea in his answer with KKT's conditions. Personally, I feel my formulation is clearer and easier to understand.
...
1
vote
1answer
73 views
How to minimize $\sum_{i=1}^p (y_i-x_i)^2$ with constraints $\sum_{i=1}^p y_i - 1 =0$ and $\forall i=\overline{1,p}:-y_i \le 0$?
Let $x = (x_1,\ldots,x_p) \in \mathbb R^p$. I'm solving the constrained optimization problem
$$\begin{align*}
\text{min} &\quad \sum_{i=1}^p (y_i-x_i)^2 \\
\text{s.t} &\quad \sum_{i=1}^p ...
2
votes
0answers
44 views
How to solve this maximization problem | KKT conditions
Maximize the objective function $f(x)=\sum_{i=1}^n (1-e^{-k_ix_i})$, where $(k_i >0) \in \mathbb{R}, (0\leq x_i \leq 1) \in \mathbb{R} $ .
$\max\sum_{i=1}^n (1-e^{-k_ix_i})$
Subject to
i) $\...
3
votes
0answers
35 views
Question about Lagrange multipliers, optimization problems and KKT-points.
I am having some difficulties with optimization problems with inequality constraints. In general the problems I am given will look something like this:
$$\min f(x,y,z) \\ \text{s.t.} \space \space \...
0
votes
0answers
29 views
Question about KKT-conditions and inequality constraints.
I have two questions regarding the application of KKT conditions. Let's say I am given the following optimization problem:
$$\min f(x,y,z) \\ \text{s.t.} \space h(x,y,z)=0 \\ g_1(x,y,z) \color{red}{\...
0
votes
0answers
39 views
First order Karush-Kuhn-Tucker optimality conditions: non-differentiable points in feasibility set
Background:
Consider the optimization problem \begin{align}&\min_{\mathbf x\in \mathbb X} f(\mathbf x)\\ &\text{ subject to } g_i(\mathbf x)\leq 0, i=1,2\ldots,I,\end{align}
where $f(\mathbf ...
2
votes
0answers
36 views
KKT-Conditions in a functional setting
Let $F:L^2([0,1])\rightarrow \mathbb{R}$ be a convex functional.
Consider the minimization problem
\begin{align}
\underset{f(\cdot) \in L^2([0,1])}{\min} F(f)\,\,\text{ subject to }
\|f(\cdot)...
2
votes
3answers
53 views
How to prove the harmonic-geometric mean inequality by solving an optimization?
The harmonic-geometric mean inequality is defined as follows
$$
\frac{n}{\sum_{i=1}^n \frac{1}{x_i}} \leq (\Pi_{i=1}^{n}x_i)^{\frac{1}{n}}\tag{1}
$$
Given the following linear programming problem
$$
...
1
vote
1answer
38 views
How to solve linear program $\min \langle c, x \rangle$ using Lagrangian?
Given the following linear programming problem
$$
\min \langle c, x \rangle\\
\begin{align}
\text{s.t} \,\,\,\,\,\,\,& \sum_{i=1}^{n}x_i=1\\
&x\geq0
\end{align}
$$
where $x \in \mathbb{R}^n$.
...
1
vote
1answer
162 views
KKT multipliers and “active” and “inactive” constraints on the generalized Lagrangian $L$
The textbook Deep Learning by Goodfellow, Bengio, and Courville, says the following in a section on constrained optimization:
The inequality constraints are particularly interesting. We say that a ...
0
votes
0answers
20 views
Identity of particular KKT points
$\renewcommand{\vec}{\mathbf}$
Consider a non-linear minimization problem $\mathcal{P}$ and suppose to have found a point $\vec{x}$ satisfying the first order KKT conditions.
Suppose further that ...
1
vote
0answers
46 views
Constraint qualification in actual algorithm: are they ever checked?
I have a hard time to understand the interest of constraint qualification in actual algorithm for optimization. I know that there are many questions already about constraint qualification but they ...
1
vote
0answers
24 views
Motivation non-negativity constraint KKT conditions
I am having problems understanding the non-negativity constraint on the Lagrange multiplier in the KKT conditions. Why does the sign matter?
See this link for statement of the KKT conditions.
I do ...
0
votes
1answer
36 views
Using KKT to minimize projection $f(x_1, x_2,…, x_n) = x_n$
For fixed, finite $n$, let $x \in \mathbb{R}^n$. I am trying to solve a problem of the form:
Minimize: $$f(x) = x_n$$
such that
$$g_j(x) \leq 0; \ j \in \{1,...,m\}$$
$$h_\ell(x)=0; \ \ell \in \{1,......
3
votes
1answer
41 views
KKT condition with infinite gradient at the boundary
Let $P\subseteq \mathbb{R}^n$ be a convex polytope (cut out by finitely many linear inequalities) and $O\subseteq \mathbb R^n$ be an open set such that $O\cap P$ contains the (relative) interior of $P$...
0
votes
0answers
43 views
Can I use KKT condition to solve this optimization problem? why?
We all learn about KKT condition in the optimization ,but I don't know when can we use the KKT condition?
Or why can we use the KKT to solve the optimization?
Why can't we use the KKT to solve the ...
0
votes
1answer
26 views
Sufficient condition for always binding constraint in maximization problem
I was thinking whether there is some sufficient conditions to have always binding constraint for the following types of optimization problem:
$ \max_{x, y \in [0,1]x[0,1]} f(x,y; \alpha) \qquad \text{...
0
votes
0answers
66 views
Find an upper bound on distance between perturbed solutions for quadratic constrained least squares (like) problem (KKT pairs approximation)
Let $A \in \mathbb{R}^{n \times n}$ a symmetric matrix and $b \in \mathbb{R}^n$.
Given $(\bar{\lambda} , \bar{x}) \in \mathbb{R} \times \mathbb{S}^{n-1}$ - an approximate solution for the problem: $\...
0
votes
0answers
42 views
Maximizing objective function with non-concave constraint
I have a maximization problem in the form
$$\max_{x} ~f(x)= \max_{x}~a ~\log(1+x) - b ~x \\
y ~x - c ~z ~ \log(1+x) \leq 0\\
a,b,c,x,y,z >0
$$
I computed the Hessian of the function $z ~ \log(1+x)...
0
votes
1answer
34 views
Finding Fritz-John multipliers
We have the optimization problem:
Minimize $f(x,y) = (x+1)^2 + y^2$ subject to $g(x,y) = -x^3 + y^2 \leq 0$.
We would like to find multipliers $\lambda_0, \lambda_1$ satisfying the Fritz-John ...
0
votes
0answers
20 views
Using KKT conditions when there is more constraints than variables
I am having difficulty solving the problem below. Specifically, I am curious about what happens when I cannot find the lambda values. Do we consider a solution does not exist? There is only one ...
0
votes
0answers
26 views
$\max \sum_{k = 1}^\infty k^2x_k^2, s.t \sum_{k =1}^\infty x_k^2 \leqslant \delta^2, ~\sum_{k = 1}^\infty k^4x_k^2 \leqslant 1$
$$\left\{\begin{aligned}
&\max \sum_{k = 1}^\infty k^2x_k^2
\\
&\text{s.t. } \sum_{k =1}^\infty x_k^2 \leqslant \delta^2, ~\sum_{k = 1}^{\infty} k^4x_k^2 \leqslant 1
\end{aligned}\right.$$
I ...
0
votes
0answers
24 views
How to get $\boldsymbol{x*}$ for a system of linear algebra equations using Lagrange and Karun-Kuhn-Tucker multipliers?
The optimisation problem I am trying to solve involves the following cost function:
$$f=\frac{1}{2}\boldsymbol{x}^{T} \boldsymbol{C} \boldsymbol{x} - \boldsymbol{x}^{T} \boldsymbol{m}$$
subject to:
$$...
2
votes
0answers
50 views
Proof KKT points are inside a ball and find the Lagrange multipliers
I am trying to learn continuous optimization and I need to solve the following exercise. Despite the fact that I solved some exercises about KKT conditions and Lagrange multipliers, I can't solve this ...
0
votes
0answers
51 views
The example of convex program for KKT
Is the example of convex programming problem (convex program) for which $\exists \lambda = (\lambda_0, ... ,\lambda_m)$ s.t. Karush-Kuhn-Tucker conditions are met but $\dot{x}$ isn't minimum?
X - ...
0
votes
1answer
51 views
The example for KKT-conditions
Is the example for convex programming problem (convex program) where Karush-Kuhn-Tucker conditions are met for every $\lambda = (\lambda_0, ... ,\lambda_m)$, but the $\lambda_0 = 0$?
X - linear space....
0
votes
0answers
30 views
Optimization Using KKT Conditions
I need to maximize the profit function Ļ=50x+10y subject to the constraints x,yā„0 and x-yā¤3 and 5x+2yā¤20 using KKT conditions.
0
votes
1answer
52 views
Solve Using KKT Conditions
I need to minimize the function $c = 5x^2-80x+y^2-32y$, subject to the
constraints $x,yā„0$ and $x+yā„20$ using KKT Conditions.
0
votes
0answers
27 views
Dual for minimizing quasiconcave function?
I am trying to characterize the solution of an optimization problem, where the objective function involves minimizing a quasi-concave function subject to linear constraints. I wanted to know is there ...
1
vote
0answers
29 views
Is this hint for an exercise about KKT's theorem correct?
My professor gave us this problem
$$\begin{align*}
\text{min} & \quad x + 2y + 3z \\
\text{s.t} & \quad x^2 + y^2 + z^2 && = 1 \\
& \quad x + y + z && \le 0
\...
1
vote
1answer
53 views
Minimize $x + 2y + 3z$ subject to $x^2 + y^2 + z^2 = 1$ and $x + y + z \le 0$
I'm trying to solve this problem by KKT's condition:
$$\begin{align*}
\text{min} & \quad x + 2y + 3z \\
\text{s.t} & \quad x^2 + y^2 + z^2 && = 1 \\
& \quad x + y + z ...
