Hot answers tagged

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


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


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


2

A possible (non linear) model for this problem: Define the following variables : $a$ is the $x$-coordinate of the circle $b$ is the $y$-coordinate of the circle $r\ge0\;$ is the radius of the circle $\omega_i$ is a binary variable that equals $1$ if and only if point $(x_i,y_i)$ lies on the circle. The objective function is then to maximize $$ ...


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


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


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


2

There is a neat geometric way to see why this should be so, but I've forgotten some of the details. Some papers of Daubeches, Dohono, etc. contain these details. Unfortunately, I've forgotten these refs too. So, I'll give you the somewhat lazy solution (you probably already figured out that I'm a very lazy person), based on proximal operators and the Mureau ...


2

Since there is only a single variable in your reduced problem, you can find the best choice of $x_i$ just using techniques from precalculus. (Consider separately the cases $x_i \geq 0$ and $x_i \leq 0$, and visualize the graph of a quadratic function in each case.) Here's a different viewpoint (summarized very briefly). Let $f(x) = \|x\|$, where $\| \cdot ...


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.


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


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


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


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


1

The method of choosing all sets of 3 points, finding the circle that passes through that set, and seeing which other points lie on that circle has one big problem: roundoff error. If you try to use any method that involves taking square roots, roundoff can cause problems. Here is a method, based on some previous work of mine, that allows this to be done ...


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


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



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