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

492 questions
Filter by
Sorted by
Tagged with
28 views

20 views

### Maximisation problem for a quasi-linear utility function

How do I solve a maximisation problem for a quasi-linear utility function: max $U(x, y) = 2x + \ln (1 + y)$ s.t. $x + y ≤ 5, x ≥ 0, y ≥ 0$ ?
52 views

### Second-order-cone programming - Lagrange multiplier and dual cone

In standard nonlinear optimization when we are interested to minimize a given cost function the presence of an inequality constraint g(x)<0 is treated by adding it to the cost function to form the ...
1 vote
49 views

25 views

### Missing Non-Negativity Constraint on Lagrangian

We have the constrained maximisation problem: A perfectly competitive firm produces one output with two inputs, capital $(k)$ and labour $(l)$. The rental cost of capital is equal to $r >0$ and ...
15 views

### Estimating/Tuning a Coefficient from an Objective Function so Optimal Solution Reflects Data

I am working on a problem that is a modified version of a two-knapsack knapsack problem. I am able to find the optimal choices by using Gurobi. However, I would like to estimate a coefficient that is ...
1 vote
36 views

### Suppose $x \leq f(x) + f(y), y \leq f(x) + f(y)$, and $f(\cdot)$ concave. Is the solution for $x$ bounded?

I am writing a model which has the following constraints. $$x \leq f(x) + f(y) \\ y \leq f(x) + f(y) \\ x \geq 0 \\ y \geq 0$$ My question is: Does concavity of $f(\cdot)$ guarantee that there is a ...
51 views

### KKT conditions on optimization problem with inequalities

I have the following optimization problem: \begin{align*} \min_{x} \quad & f(x) = x^2 - 2x + 3 \\ \text{s.t.} \quad & g_1(x) = x - 1 \geq 0 \\ & g_2(x) = -x + 2 \geq 0 \end{align*} Since ...
57 views

### Solving optimal solution of a NLP using the Kuhn-Tucker condition

Consider the following NLP problem. I have solved it using KTP condition. In case II, I get $\lambda = -\sqrt{\frac{2}{3}}$ , but we know that according to the KTP condition $\lambda$ must be $\geq 0$....
1 vote
48 views

46 views

### Recovering Primal Optimal Solution from Dual Support Vector Machine

This question concerns a subtle issue in the recovery of primal solution for support vector machine from the dual. None of the sources I read addresses it explicitly. In particular, it was missing ...
176 views

### Best rank-$1$ approximation of matrix with condition.

Let $A\in\mathbb R^{m\times n}$ be a real matrix. For any $x,y\in\mathbb R^m$, we write $x\leq y$ if $x_i\leq y_i$ for $i=1,\dots,m$. For any matrix $B$, $\| B \|_F$ is the Frobenius norm and is ...
41 views

### Is there a closed form solution or an efficient solver for this linearly constrained quadratic minimization problem?

Let $A$ be a $m\times n$ matrix and $u\in\mathbb R^m$. Denote by $0\preccurlyeq x$ for some vector $x$ in $\mathbb R^m$ the relation such that $\forall i$, $0\leq x_i$. I am trying to solve the ...
95 views

### During constrained optimization with inequalities why must the gradient of the objective be in the same direction as the gradient of the constraint?

I have been reading about constrained optimization and understood when there are just equality constraints but am having trouble understanding when there are inequality constraints. I was initially ...
110 views

25 views

### Solve the KKT system of knapsack nonseparable quadratic problem in active-set algorithm

I have a convex quadratic nonseparable knapsack problem defined as follows: $$\min x^TQx+q$$ $$s.t. \sum_i{a_ix_i}\leq b,$$ $$l \leq x \leq u$$ I want to optimize the quadratic function using ...
37 views

### Is the global minimum of a nonconvex function over a constrained set the maxmin of the corresponding Lagrangian?

Let a nonconvex differentiable function $f:X\to\mathbb{R}$ and differentiable constraint $g(x)\leq 0$, with $X$ convex. Does the global minimum of $f$, $f(x^\star)$, with $g(x^\star)\leq 0$ coincide ...
504 views

### Necessary and Sufficient Conditions for Lagrange Optimisation!

I'd be immensely grateful if someone could spell out in black and white: Which conditions are necessary and sufficient, for Lagrange optimisation? Do necessary conditions become sufficient conditions?...
1 vote
79 views

### Understanding convex optimization

I am reading about Support Vector Machines and there are some steps that I don't understand regarding convex optimization. I won't get into the specific constraints of SVM's. Our minimization problem ...
1 vote