# Tag Info

1

In all four cases, your $A^{-1}$ should be $A^T$. (Make sure you understand the difference!) Apart from that, $(D1)$ and $(D2)$ are fine. For $(D3)$, since the primal is a minimization problem with the restriction $A \mathbf x \leq \mathbf b$ (as opposed to $A \mathbf x \geq \mathbf b$), then the dual should have its variables constrained by $\mathbf x \leq ... 0 $$x^* \text{ minimizes } f(x) \Longleftrightarrow 0\in\partial f(x^*)$$ is trivial by definition of subgradients: $$f(x) - f(x^*) \ge \partial f(x^*)^T (x-x^*)\quad \forall x.$$ Thanks to Michael Grant for his comments. 0 A convex relaxation of the constraint would give you the convex hull of the feasible region: in this case $$z \le a + b y y_{max}$$ 1 I use the table below to create the dual problem. If you have any question about the table or other aspects of my answer feel free to ask. \begin{cases} \min & 4y_1 &+3y_2&+5y_3&+y_4&\\ &y_1&+4y_2 &+2y_3& +3y_4&\geq 7\\ &3y_1&+2y_2&+4y_3&+y_4&\geq6\\ ... 0 After two weeks, I tried again to solve this problem: First part of the bounded demonstration if: $$(s<0 \mbox{ or } t>0)$$ if$s<0$then$\forall M \le \frac{-1}{s}, x_1=M$is feasible. Yet,$x_1\ge 0$, does it creates a problem? if$t>0 \forall M\ge \frac{1}{t},x_2=M$is feasible. Second part of the bounded demonstration The problem is ... 2 Use binary variables$y_A$and$y_B$that equal$1$if and only if$X_A$and$X_Bare strictly positive (respectively). Then add the following constraints to your LP: \begin{align*} &X_A\le M\,y_A\\ &X_B\le M\,y_B\\ &X_C\le M\,(2-y_A-y_B) \end{align*} M is a large constant. The first two constraints activate the binary variablesy_A$and ... 1 You can think of the problem geometrically. For example, in a 2 dimensional space, each$|a_i^Tx-b_i|$is a line. So$\max_i|a_i^Tx-b_i|is the line that lies above all the other ones, and finally $$\min\left\{ \max_i|a_i^Tx-b_i| \right\}$$ is the set of lines that always lie above the other ones, but at the lowest height: it is the convex hull ... 0 Th function can be reformulated as follows, \begin{align} & \sqrt{2(x_1+x_2)^2+x_2^2+x_3^2+7}+(x_1^2+x_2^2+x_3^2+1)^2 \\ &= \|(\sqrt{2}(x_1+x_2), x_2, x_3, \sqrt{7})^T\| + \|(x_1, x_2, x_3, 1)^T\|^4 \label{pvii:1r} \end{align} where\|.\|$is 2-norm. The above reformulated function is sum of two convex functions. Here,$\|(\sqrt{2}(x_1+x_2), x_2, ...

3

Notice that $\mathrm{x} \mapsto f(\mathrm{x})$ is convex if and only if $y \mapsto f(B\mathrm{y})$ is convex for some invertible matrix $B$. (This is because linear transform preserves lines.) Now using the spectral theorem, choose a symmetric matrix $B$ such that $AB = BA$ and $A^{-1} = B^2$. Then with the transform $\mathrm{x} = B\mathrm{y}$, we see that ...

0

First, let us show that $\{y \mid Ay \leq 0\} \subset \{y \mid x + y \in Q, \forall x \in Q\}$. Consider any $y_0$ for which $Ay_0 \leq 0$. Then $$x \in Q \Rightarrow Ax \leq b \Rightarrow Ax + Ay_0 \leq b + 0 \Rightarrow A(x+y_0) \leq b \Rightarrow x+y_0 \in Q.$$ Next, let us show the reverse inclusion: $\{y \mid x + y \in Q, \forall x \in Q\} \subset ... 1 We wish to show that if a differentiable function$f:\mathbb R^n \to \mathbb R$is strongly convex with parameter$m > 0$then it is strongly monotone with parameter$m$. To say that$f$is strongly convex with parameter$m$means that the function$h(x) = f(x) - \frac{m}{2} \|x\|^2$is convex. (At least, that's my favorite definition of strong ... 1 The function$f(x) = x^4$is strictly convex and the above inequality does not hold for any$m>0$. In particular, if$m>0$and if$y=0$, the left hand side of the above formula is$(f'(x)-f'(0))(x-0) = 4x^4$, and for$0<|x| < {\sqrt{m} \over 2}$, we have$f'(x)-f'(0))(x-0) < m(x-0)^2$. 0 Convex optimization is a very important area in Machine learning as convex functions have very nice properties (local minima is global minima). It is important to identify when a cost function is convex or not. If it isn't convex, we could probably convert it to a convex one. A lot of engineering problems can be written as optimization problems and solved ... -1 No. A cone is not a "polyhedron". A polyhedron, by definition has planar (straight) sides, not curved sides. 1 Yes, or more precisely (as polyhedron may imply three dimensions) a convex polytope. You may readily verify that$C$is convex, and also that its boundary is piecewise a part of a hyperplane. 3 The paper: An accelerated non-Euclidean hybrid proximal extragradient-type algorithm for convex-concave saddle-point problems http://www.optimization-online.org/DB_HTML/2015/09/5113.html Deals with the HPE for Bregmain with epsilon-enlargements. Best regards, Benar F. Svaiter 0 I'm not sure if this is going to generalize to your more complex model, but the scalar case isn't that difficult here. Let's define$\bar{A}(z) = \beta z - \alpha z^2 / 2$, the first "mode" if$A$. Then $$A(x) = \max\{\bar{A}(z) \,|\, z\leq x, ~z \leq \beta/\alpha\}$$ So your original problem transforms from this: $$\begin{array} \text{maximize}_x & ... 2 It's not hard to show (Hint: show that the dual problem is a projection of \frac{1}{\lambda}(Ax_0 + z) onto the polyhedron \mathcal P := \{\theta \text{ s.t }\|A^T\theta\|_\infty \le 1\}, and then use the KKT conditons ...) that if \lambda \ge \lambda_{\text{max}} := \|A^T(Ax_0 + z)\|_\infty, then the solution of your problem is the only zero vector. ... 1 I've no idea what's going on for the feasibility part. If it is feasible, then either s or t must be negative, otherwise s x_1 + t x_2 \ge 0. Conversely, if either s or t is negative, then it is feasible because you just need to make x_1 or x_2 (depending on which of s,t is negative) sufficiently large and it would make s x_1 + t x_2 \le ... 3 From the AM-GM inequality, note that$$x^2y^2z^2\leq\left(\frac{x^2+y^2+z^2}{3}\right)^3<\left(\frac{5}{6}\right)^3<1,$$therefore$$3+2xyz\geq 3-2|xyz|>3-2=1.$$0 I'll do it without having to invert A, so no Newton's method. Also, KKT won't help you because the equality constraint is not convex. When all else fails: do projected gradient descent. Here's some pseudo code for minimizing f(x) = \langle x, Ax + c \rangle s.t. ||x||=1. choose a initial unit vector x \nabla f(x) \leftarrow Ax + c. x ... 0 Besides satisfying the KKT condition, SOSC is also required. Reference: Theorem 1 in http://arxiv.org/pdf/1106.0898.pdf 2 I think I have a counterexample. Define$$K = \Big\{(x,y) \in \big[-\frac12,\frac12\big] \times \big[0, \frac12\big] : y \ge \exp\big(-\frac1{x^2}\big) \Big\}.$$Now, consider the extreme point x_0 = (0,0). The key observation is that all derivatives of x \mapsto f(x) := \exp\big(-\frac1{x^2}\big) vanish at 0, hence, all circles (ellipses) containing ... 1 Try e.g. g(x)=x^2+1, f(x)=(\pi+\arctan(x)) g(x). Then f(x)/g(x) = \pi+\arctan(x) is monotone increasing. f has a minimum near -0.168 while g has a minimum at 0. Moreover, f and g are convex. 1 Observe that d is 2\pi-periodic in every axial direction. The only way that such a periodic function can be convex is if is constant. 2 First, let's define$$Q(x)=P + D(x) = P + \mathop{\textrm{diag}}(x) \otimes I_m$$where \mathop{\textrm{diag}} maps the vector x to the corresponding diagonal matrix, and \otimes denotes the Kronecker product. This makes it a bit simpler to see that$$\frac{\partial Q(x)}{\partial x_i} = \frac{\partial D(x)}{\partial x_i} = e_ie_i^T \otimes I_m = (e_i ... 0 Could it be possible to try the definition of convex sets?$A$is a convex set and$\alpha,\beta\geq 0$, then$(\alpha+\beta)A=\alpha A+\beta A$. As$\alpha A$and$\beta A$in$A$, then according to the definition of convexity$\lambda\alpha A + (1-\lambda)\beta A$equals$(\lambda\alpha + (1-\lambda)\beta)A$. This implies$A$inverse$(\lambda\alpha + ...

Top 50 recent answers are included