New answers tagged

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_B$ are 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 variables $y_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