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

1
2 3 4 5
7