23

KKT and duality are indeed closely related. To demonstrate this, I will look at a convex minimization problem in which all functions are convex and smooth. I will make use of Lagrange duality. Linear programming duality is just a special case of Lagrange duality applied to linear programs. Consider the following convex minimization problem \begin{align} p^* =...


11

No, the KKT conditions aren't applicable to mixed-integer programming problems with integer variables. The theory behind the KKT conditions depends on the objective and constraint functions being differentiable but functions of integer variables aren't differentiable. It's certainly possible to enforce integrality constraints using continuous variables. ...


10

If you want to use the KKT conditions for the solution, you need to test all possible combinations. This is why in most cases, we use the KKT's to validate that something is an optimal solution, since the KKT's are the first-order necessary conditions for optimality. For convex nonlinear optimization, you are better off using sequential quadratic ...


9

You do not have $3$ constraints, you have $T$ constraints. For example, if $T=5$, then we have \begin{align}e(1)&=e(0)-d(1)+\eta\cdot c(0)\tag{1}\\e(2)&=e(1)-d(2)+\eta\cdot c(1)\tag{2}\\e(3)&=e(2)-d(3)+\eta\cdot c(2)\tag{3}\\e(4)&=e(3)-d(4)+\eta\cdot c(3)\tag{4}\\e(4)&=0.5\cdot E\tag{5}\end{align} You might like to use the same ...


8

Consider the following minimization problem \begin{eqnarray} \min &&\quad f(x) ~&= -x &\\ \text{s.t.} &&\quad g_1(x) & =x &\le 0\\ &&\quad g_2(x) & = 2x &\le 0 \end{eqnarray} which attains the unique global minimum for $x^* = 0$. Note that both constraints are active in this point. By definition, $\nabla g_1(...


6

You should use the KKT conditions (turning the sign restrictions on $x$ into constraints), but it turns out they will not affect the results. First, let me point out that $\partial L/\partial x_1$ is undefined when $x_1=0$, so you need to deal with the case $x_1=0$ (and the case $x_2=0$) separately. Given the monotonicity of $L$, you can easily show that if $...


6

You have shown that KKT is necessary for a local minimum. Also that it is necessary for a local maximum. But you have not shown that a local minimum or local maximum exists. Indeed, there is no local maximum. So is the KKT point you found a local minimum? That is what 2nd order conditions can assess. The 2nd order (KKT) sufficiency conditions (whose ...


5

Use CVX's entr function. $\sum_{i=1}^ 4x_i\ln(x_i)$ can be entered as -sum(entr(x)) entr Scalar entropy. entr(X) returns an array of the same size as X with the unnormalized entropy function applied to each element: { -X.*LOG(X) if X > 0, entr(X) = { 0 if X == 0, { -Inf otherwise. If X ...


3

The gradient and Hessian of $f$ at $x=x_0$ are constants (vector and matrix respectively), so $f_0(x)$ is a quadratic function of $x$. If it helps, write it as $f_0(x) = c_0 + c^Tx + x^T D x$. Hopefully you know the gradient of that. Then figure out what $c_0$, $c$ and $D$ are in terms of $x_0$, $f(x_0)$, $\nabla f(x_0)$ and $Hf(x_0)$, substitute and maybe ...


3

Note that by assumption, there must be some $i \in I(x^*) \cup \{0\}$ with $y_i \ne 0$. Let $\mathcal I = \{i \in I(x^*) \cup \{0\} \mid y_i \ne 0\}$ be the set of such indices. Let $u$ be any unit vector of the same dimension as $x^*$. We wish to show that $x^* + tu$ is either not feasible or has weakly worse objective for any positive scalar $t$. To show ...


2

Binary (Boolean) values are integer values. Therefore, optimization problems with boolean constraints are either integer programming or mixed integer programing (MIP). Generally, there is no easy algorithm that is guaranteed to find the optimal solution of MIP problems quickly. My reason to believe that is: I can implement a boolean satisfiability (b-sat) ...


1

This sounds like parametric programming to me. In short, you can calculate a set of regions, typically called "critical regions", within which the same set of constraints is active. This in return enables you to calculate $x$, $\lambda$ and $\mu$ as an explicit function of your parameter $a$. There are MATLAB tools to do this, most prominently the ...


1

Minimize $x^2$ where $1 \le x \le 2$. \begin{aligned} \min_{x} \quad & f(x)\\ \textrm{s.t.} \quad & h_{1}(x) \le 0\\ &h_{2}(x) \le 0 \\ \end{aligned} where \begin{align} f(x) &= x^2 \\ h_{1}(x) &= 1 - x \\ h_{2}(x) &= x - 2 \end{align} KKT conditions: \begin{align} 0 &= \nabla f(x) + \mu_{1}\nabla h_{1}(x) + \mu_{2} \nabla h_{...


Only top voted, non community-wiki answers of a minimum length are eligible