The tag has no wiki summary.

learn more… | top users | synonyms (1)

1
vote
1answer
91 views

Optimization over vector spaces. Generalized KKT.

I am looking for the extension of the theorem I found in the book by Luenberger called "Optimization by vector space methods." Here is the statement of that theorem from Luenberger: Generalized ...
1
vote
0answers
57 views

Utility maximization of n goods

I have a question that involves finding the optimal demand of n goods for a consumer. However, I haven't anything like this before and I'm not sure how to proceed. The consumer has a utility ...
2
votes
1answer
37 views

Would I use KKT conditions to solve this optimiztion problem?

my problem (P) is: $$(P) \space \space \text{min} \space x_1x_2$$ $$\text{s.t.} \space x_1-x_2-2 \leq 0$$ $$x_2 \leq 0$$ Prove that $x^* = (1,-1)$ is a strict local minimizer. ...
2
votes
0answers
18 views

Determining active constraints in KKT

Suppose there is a constrained optimization problem having inequality constraints. We can solve it using Karush-Kuhn-Tucker conditions. My question is how do we determine which constraints are active ...
2
votes
1answer
62 views

Formulation of convex constrained optimization problem (SVR)

I'm trying to figure out where I'm going wrong with my formulation of a certain problem, as all other instances of it were formulated slightly differently. The problem (SVR problem, If you're ...
1
vote
1answer
25 views

KKT for not convex problems

In my optimization course we learned something about KKT for not konvex problems: $$min \; f(x)$$ $$s.t. \; c(x)=0$$ $$d(x)\geq 0$$ $$f(x): \mathbb{R}^n\rightarrow \mathbb{R}$$ $$c(x): ...
0
votes
0answers
51 views

How does this optimization problem satisfy Karush-Kuhn-Tucker Conditions?

I am following Andrew Ng's course notes on Support Vector Machines at: http://cs229.stanford.edu/notes/cs229-notes3.pdf There is something in these notes which I do not understand. SVM's basic ...
1
vote
2answers
59 views

Local optimality of a KKT point.

Consider the problem \begin{equation} \min_x f(x)~~~{\rm s.t.}~~~ g_i(x)\leq 0,~~i=1,\dots,I, \end{equation} where $x$ is the optimization parameter vector, $f(x)$ is the objective function and ...
1
vote
1answer
37 views

Optimization using Karush-Kuhn-Tucker conditions

min $y^Tx$ subject to $\|x\|^2 \le 1$ where y is a nonzero vector in $\mathbb R^n$ I rearrange the constraints so that the RHS is $0$. New constraint: $x_1^2 + \cdots + x_n^2 - 1 = \|x\|^2 - 1 \le ...
0
votes
0answers
24 views

Linear independence of equality constraint gradients in constraint qualifications

I'm, trying to get an intuitive feel for the various constraint qualifications for KKT points. Most of them seem to rely on the linear independence of $\nabla g_i(x^*)$ where $g_i$ are the equality ...
2
votes
1answer
94 views

Is there a nice representation for KKT conditions for matrix constraints?

I have a convex programming problem: $\min \left\lVert J - R \right\rVert _F$ $J,R$ are matrices. $J$ is given for the problem. One of the constraints is: $R = KQ$ Here, $R,K,Q$ are matrices. $K$ ...
0
votes
0answers
47 views

Bordered Hessian for Kuhn-Tucker

With Lagragian problems, you are often asked to solve for a stationary point and use the bordered Hessian to determine whether it is a maximum or minimum. I have noticed with Karush-Kuhn-Tucker ...
1
vote
0answers
31 views

Explain KKT conditions without reference to duality.

Is it possible to explain (not derive) KKT necessary conditions without reference to the concept of Lagrangian duality?
0
votes
1answer
52 views

Optimization: KKT conditions statement

I'm currently following this material http://www.math.uh.edu/~rohop/fall_06/Chapter2.pdf And I can't understand why the following statement is true, between the equations (2.9) and (2.10): "The ...
1
vote
0answers
64 views

Kuhn-Tucker constraint qualification, overdetermined?

I have a question about the constraint qualification for KKT. As I've seen the theorem stated if $G(x^*)=(g_1(x^*),\dots,g_n(x^*))$ are the binding constraints at a local max $x^*$ then the jacobian ...
1
vote
1answer
34 views

Quadratic Problen with 2 constraints

Could someone help me to solve the following: $\min x^Tx$ s.t. $x^T a=1$ $x^T b=0$ where $x$,$a$ and $b$ are $(N\times1)$ vectors and $1$ and $0$ scalars. Thank you!
0
votes
0answers
24 views

Threshold in a maximisation problem (with KKT conditions)

I'm looking to maximise with respect to $x_i$ $$L = \sum_{i= 1}^n y_i \frac {x_i^{1 - \epsilon}}{1 - \epsilon}$$ subject to $ \sum_{i= 1}^n x_i = B $ and $x_i \ge 0$ for all $i$, where $y_i$, $B$ ...
0
votes
0answers
81 views

KKT Conditions and Convexity

min $x^2 -xy +y^2 -5x+6y$ subject to $1 \leq y$, $y^3 \leq 2x$, and $x \leq 8$ Write out the KKT conditions for this problem. Show that $(x,y) = (4,2)$ is a KKT point, and is therefore a global ...
0
votes
0answers
97 views

Lagrange dual method and KKT condition

Consider the following optimization problem \begin{equation}\notag \begin{split} \max & x^2+y^2 \\ \mathrm{s.t.} & x^2 \leq 1 \\ & 0\leq y\leq 2 \end{split} \end{equation} Obviously, the ...
0
votes
1answer
79 views

Lagrange condition and second-order conditions

Given a function to minimize or maximize with equality and/or inequality constraints, I can use Lagrange multiplier and/or KKT to solve such problems. So I understand how it works. My problem is ...
0
votes
0answers
116 views

Are box constraints problematic when using KKT conditions to solve quadratic programming problems?

I've dealt with quadratic programming before, but I've never seen something of this sort: $$\min \frac12 \|v\|^2 + \sum_ip_i$$ $$\text{s.t. }f(v,p)\ge0 $$ $$0\le p_i\le a$$ for some constant a ...
2
votes
1answer
212 views

Optimization Problem: Karush-Kuhn-Tucker Condition

I am working on the question displayed below. I know that the method of Lagrange Multipliers is used to find the solution for optimization problems constrained to one or more equalities and when our ...
0
votes
1answer
181 views

KKT maximization problem

$x^2y \rightarrow$ max, such that $x^2 + 4xy \leq 1, x \geq 0$ and $y \geq 0$. I think I need to use the KKT conditions here. I did however not yet succeed in solving it, so could someone ...
0
votes
1answer
178 views

KKT conditions on minimization problem

I am trying to get an explicit solution to the following problem with the help of KKT conditions. But I am stuck. The problem: $ min_x 1/2 ||y-x||^2_2 + \lambda||x||_1 $ This is what I have done ...
0
votes
1answer
57 views

Kuhn-Tucker conditions: why does $\lambda$ $\dfrac{\partial L}{\partial \lambda}=0$?

Satifying Kuhn-Tucker conditions. Given $\lambda$ is a row, and $\dfrac{\partial L}{\partial \lambda}$ is a column, why does $\lambda$ $\dfrac{\partial L}{\partial \lambda}=0$ ?
1
vote
1answer
31 views

Non linear programming please HELP

Hey guys, I never do that but just found out that I have an assignment due in a few hours..thought it was for later, any help/solutions for this one?
0
votes
1answer
175 views

KKT Conditions for Minmax Problem

Let $\mathbf{x}\in\mathbb{R}^n$ and $\mathbf{y}\in\mathbb{R}^m$. Now $$f\left(\mathbf{x}, \mathbf{y}\right):\mathbb{R}^n\times\mathbb{R}^m\rightarrow\mathbb{R}$$ is convex in $\mathbf{x}$ and concave ...
6
votes
1answer
679 views

Help me organize these concepts — KKT conditions and dual problem

This is a long question in which I explain my current understanding of certain ideas. If anyone is interested in reading this and would like to provide any commentary/feedback that may help me ...
4
votes
2answers
2k views

Simple explanation of lagrange multipliers with multiple constraints

I'm studying support vector machines and in the process I've bumped into lagrange multipliers with multiple constraints and Karush–Kuhn–Tucker conditions. I've been trying to study the subject, but ...
1
vote
2answers
123 views

Determine the points where $f$ is has a local minimum/maximum. Multivariable calculus question.

This is not homework, but it is in my book and I find it hard to solve: Determine the points where $f$ is has a local minimum/maximum. Determine if it strong/weak and absolute/relative and ...
0
votes
1answer
64 views

KKT formulation

How to reformulate the following problem $$min \frac{1}{2} (x_1-a_1)^2+ \frac{1}{2} (x_2-a_2)^2$$ $$s.t. \mathbf{1}^Tx=1$$ $$ ||x||_2\leq2$$ as the following system of KKT conditions: $$(1 + ...
1
vote
1answer
198 views

Check Kuhn-Tucker conditions

How to check if $(0,1)$ point is the solution of this optimization problem using Kuhn-Tucker Theorem. Find the min of $e^{x_1-x_2}-x_1-x_2$ where $x_1+x_2\le1,\ x_1\ge 0,\ x_2\ge0$ I am thinking ...
1
vote
0answers
79 views

KKT: Explain visually the optimality condition $F_0\cap G_0\cap H_0=\emptyset$

I am trying to understand visually what this condition actually mean. It is the optimality condition in KKT. It means something like that constraint -set, objective -set and hyperplane -set has no ...
1
vote
1answer
898 views

Linear least squares with non-negativity constraint

I am interested in the linear least squares problem: $$\min_x \|Ax-b\|^2$$ Without constraint, the problem can be directly solved. With an additional linear equality constraint, the problem can be ...
1
vote
2answers
243 views

How can I infer a result using primal feasibility, dual feasibility, and complementary slackness?

I am trying to find the minimum of $-x_1$ with restrictions $\bar g\leq\bar 0$ so that $$\bar g=\begin{pmatrix} (x_1+2)^2+(x_2-4)^2-20\\ (x_1+2)^2+x_2^2-20\\ -x_1\end{pmatrix}\leq ...
1
vote
2answers
203 views

What does the statement “Optimality condition for convex problem” mean? KKT or other condition?

I am stuck to the problem 4 here, course Mat-2.3139, the due day was yesterday. The hint is "Optimality-condition for a convex-problem". I have asked this now from 3 assistants and everyone with ...