New answers tagged

0

The set $A = \{ (x,y) \in \mathbb{R}^2 \ \vert \ (1-x) y \geq 0 \}$ is not a convex set. To see this, observe that $(1, -1), (0, 0) \in A$ but $$\frac{1}{2} \cdot (1, -1) + \frac{1}{2} \cdot \left(0, 0\right) = \left(\frac{1}{2}, -\frac{1}{2}\right) \notin A$$ However, let's work through the other example that you suggested. The set in question is $B = \{ (...


0

You could also use the simplex method to solve the following problem: $$ \min\limits_{x,y,z,e,a}\quad Z= a_1+a_2+a_3 $$ subject to $$-2x+y+z+e_1 =4$$ $$x -e_2+a_1= 1$$ $$y-e_3+a_2=2$$ $$ z-e_4+a_3 = 3 $$ $$x-2y+z +e_5= 1$$ $$ 2x+2y-z +e_6= 5$$ $$ x,y,z,e,a\ge 0 $$ If $\min \{a_1+a_2+a_3\} = 0$, than you have a feasible point (with $a_1=a_2=a_3=0$).


0

Suppose $\mathrm{p,q\in I(S)}.$ Pick $\mathrm{t}\in[0,1]$. $$\mathrm{ \exists x_p,y_p,x_q,y_q:(x_p,y_p,p)^\top,(x_q,y_q,q)^\top\in S }$$ As $\mathrm S$ is convex, $$\mathrm{ t(x_p,y_p,p)^\top+(1-t)(x_q,y_q,q)^\top\in S\\ \implies(\;\underbrace{tx_p+(1-t)x_q}_x,\;\;\underbrace{ty_p+(1-t)y_q}_y,\;tp+(1-t)q\;)^\top\in S }$$ So $$\mathrm{\exists(x,y):(\;x,\;y,\;...


0

Consider $K = B_d(0,1)$ and $y = (1,0,0,\ldots,0)$. We have that $|y| = 1$, so $y \in \partial B_d(0,1) = \partial K$, hence $y \notin$ ext$(K)$. Though, for any $x \in K$, we have $f(x) = |x|^2 < 1 = f(y)$.


1

The cone $C=\{y\colon Ax=y,x\ge 0\}$ is finitely generated (by finitely many columns of $A$) and convex. By Minkowsky-Weyl theorem (en easy proof via Fourier-Motzkin eliminations can be found here, Theorem 1) it is a polyhedral cone, that is, $C=\{y\colon By\le 0\}$. From the last representation it is clear that $C$ is closed as an intersection of closed ...


1

Yes, midpoint quasi-concavity and continuity imply quasi-concavity. Consider an upper level set $E(t) = \{x : f(x)\ge t\}$ of a midpoint quasi-concave and continuous function. For any two points $a,b\in E(t)$, their midpoint $(a+b)/2$ is also in $E(t)$. But then the points at $1/4$ and $3/4$ of the distance from $a$ to $b$ are also in $E(t)$, namely $$ \...


0

The best part about the inequality $$\sum_{n = 1}^{N}x_{i}^{\beta} \leq \left(\sum_{i = 1}^{N}x_{i}\right)^{\beta}\tag{1}$$ is that it is homogeneous in variables $x_{i}$ and hence we can assume without any loss of generality that $\sum x_{i} = 1$. Since each each $x_{i}$ is positive and they sum to $1$ it follows that each $x_{i}$ lies between $0$ and $1$ ...


4

No, of course not. Any finite set with more than one point is compact and not convex.


1

Let $I$ the indices where $x_i < 1$ and $J$ the indices where $x_i \geq 1$ Let $\beta_{{\text{min}}} = \underset{1 \leq i \leq N}\min{\beta_i} > 1$ $\beta_{{\text{max}}} = \underset{1 \leq i \leq N}\max{\beta_i} > 1$ Then $\sum_{i=1}^{N}{x_i^{\beta_i}} = \sum_{i \in I}^{N}{x_i^{\beta_{i}}} + \sum_{i \in J}^{N}{x_i^{\beta_{i}}} \leq \sum_{i \in ...


2

If $0<\beta<1$, then the opposite inequality is true, since the function $x\mapsto x^\beta$ is subadditive in this case. See Prove variant of triangle inequality containing p-th power for 0 < p < 1 and An inequality concerning concave functions. $$\left(\sum_{i=1}^{N}{x_i}\right)^{\beta} \leq \sum_{i=1}^{N}{x_i^{\beta}}.$$ For $\beta=1$ then ...


3

The case $0<\beta<1$ we have re reversed inequality $$\left(\sum_{i=1}^N x_i\right)^\beta\leq \sum_{i=1}^N x_i^\beta$$ Also, this can actually be used to prove the inequality of the present post. Here are some details (for the case $\beta>1$ choose $p=1$ and $q=\beta$).


4

Note that this amounts to showing that $$ \left(\sum_{i=1}^{N}{x_i}^{\beta}\right)^{1/\beta} \leq \sum_{i=1}^N x_i $$ This fact holds for all $\beta \geq 1$, and it is an instance of the Minkowski inequality.


4

If $\beta \ge 1$, this is a consequence of Jensen's inequality applied to the convex function $t \mapsto t^{\beta}$. If $\beta < 1$, this is false with $x_i = 1$.


1

We have $(1)\ \Gamma(x_1,x_2,x_3)=(a x_1+(1-a) x_2, x_3)=(y_1,y_2)\rightarrow y_1=a x_1+(1-a) x_2\ \text{and} \ y_2=x_3.$ $(2)\ a x_1+(1-a) x_2+ x_3\leq 3 \ \rightarrow y_1+y_2\leq 3. $ $(3)\ x_i\geq 1,\ i=1,2,3 \ \rightarrow y_1=a x_1+(1-a) x_2\geq a+(1-a)=1 \ \ \text{and}\ \ y_2=x_3\geq 1 .$ So, according to $(1),\ (2),$ and $(3)$, it is concluded ...


1

For $(x_0, x_3)$ in $Y$, the point $(x_0, x_0, x_3)$ is in X and maps to $(x_0, x_3)$.


0

Let $f(x)= ||x-1|^p-1|$ and $g(x) = M|x|^c$. Assume $p\in (1,2)$, $M>0$, $c \in (0,p]$, $a>0$. 1) If $c>1$ then it will not work: We have $f(0)=g(0)=0$. But the right-derivative of $f$ at $x=0$ is $p>0$, while the right-derivative of $g$ at $x=0$ is $0$. It follows that there is a $\delta>0$ such that $f(x)\geq g(x)$ for all $x \in [0, \...


1

The function $$f(x) = \left|1-\left|1-x\right|^p\right|,\quad p\in(1,2) $$ is non-negative and concave in a right neighbourhood of the origin, non-negative and convex in a left neighbourhood of the origin, hence there are no positive constants $M$ and $c\in(0,p]$ such that $$ f(x)\leq M |x|^c$$ holds over a whole neighbourhood of zero.


1

The property you stated is equivalent to $f$ being strongly monotone and Lipschitz continuous; searching for this combination of terms will bring up a number of papers. It doesn't have a single-word name, since "Lipschitz strongly monotone" is short enough, and self-descriptive. Here's a justification. If $f$ is $L$-Lipschitz and $m$-strongly monotone, ...


3

Rewrite the system of linear inequalities in the following order $$x - 2y + z \leq 1$$ $$2x + 2y - z \leq 5$$ $$-2x + y + z \leq 4$$ $$x \geq 1$$ $$y \geq 2$$ $$z \geq 3$$ Adding the first two inequalities, we get $3 x \leq 6$, or, $x \leq 2$. Adding the 2nd and 3rd inequalities, we get $3 y \leq 9$, or, $y \leq 3$. Hence, $x+y \leq 5$. Adding the 1st ...


3

I tried the graphical method: (Large versions here and here) The affine half spaces with plane orthogonal to the coordinate axes (bound by red planes) are towards the viewer. The other three half spaces (bound by cyan planes) contain the origin. The feasible region seems to be the tetraeder with vertices $$ A = (2,3,5) \\ B = (2,2,3) \\ C = (1,3,3) \\ D ...


1

Label the planes and their intersection points as follows $\begin{array}{llllllll} &\Pi_1:&x=1 & A & B & C & & & W & X\\ &\Pi_2:&y=2 & A & B & & D & & W & & Y\\ &\Pi_3:&z=3 & A & & C & D & & & X & Y & Z\...


0

Clever guessing is ok, random guessing isn't advised. Since $x\geq 1$, $y\geq 2$ and $z\geq 3$. You should try some values that are close to the boundary, since then they are less likely to break the other conditions. So an $x$ value slightly greater than $1$, a $y$ value that is slightly greater than $2$, and a $z$ value slightly greater than $3$. So an ...


1

Let the vector of differences be given by $C x$, where $C \in \mathbb{R}^{m \times n}$ is the oriented incidence matrix of a graph with $n$ nodes and $m$ edges. Hence, $$f (x) := \sqrt{x^T C^T C x} = \sqrt{\|Cx\|_2^2} = \| C x\|_2$$ where $C^T C$ is the Laplacian matrix of the same graph. Thus, $f$ is convex. It is strictly convex if $C$ has full column ...


1

I refer to the wikipedia page of "Caratheodory's Theorem (convex hull)". They assume that $K>d+1$. $$\left| \left\{ x_i-x_1|i=2,\ldots,K\right\}\right|>d$$ If there are more than $d$ vectors in $\mathbb{R}^d$, they cannot be linearly independent.


1

OK, after struggling with elementary tools for a while and in vain, I had to invoke the "Closed Map Lemma", namely that a proper map (i.e one for which pre-images of compact sets are compact) between locally compact Hausdorff spaces (i.e a space in which every point has a compact neighborhood) is closed. For example, see Theorem 2.6 of this paper. In your ...


1

Let $\alpha \in [0,1]$. \begin{align} \varphi(\alpha \lambda_1 + (1-\alpha)\lambda_2)&=f((x+(\alpha \lambda_1 + (1-\alpha)\lambda_2)(y-x)))\\ &=f(\alpha (x+\lambda_1(y-x))+(1-\alpha)(x+\lambda_2(y-x))) \\ &\leq \alpha f(x+\lambda_1(y-x))+(1-\alpha)f(x+\lambda_2(y-x))\\ &=\alpha \varphi(\lambda_1)+(1-\alpha)\varphi(\lambda_2) \end{align}


1

You could check out Boyd's monograph called Proximal Algorithms. Also, Vandenberghe's 236c notes are very helpful. Nesterov's textbook Introductory Lectures on Convex Optimization is another good resource for this material.


1

Pick a point $x_0$ and a nearby point $y_)$ so that the ratio $s = [f(x_0)-f(y_0)]^+/|x_0-y_0|$ is close to $\max_{|x|\le r}|\nabla f(x)|$. Draw the line through $x_0,y_0$ and consider the restriction of $f$ to this line, denoted $g$. Since $g$ is convex, its graph lies above its secant line except between the points where the line meets the graph. So, along ...


1

Consider the linear matrix inequality (LMI) $$X \succeq 0$$ where $X \in \mathbb R^{2 \times 2}$ is symmetric. As $X$ is symmetric, we have $\binom{3}{2} = 3$, rather than $2^2 = 4$, degrees of freedom. Hence, we write $X \succeq 0$ as follows $$\begin{bmatrix} x_{11} & x_{12}\\ x_{12} & x_{22}\end{bmatrix} \succeq 0$$ If $X$ is positive ...


2

We denote by $a_i \in \mathbb R^m$, $i = 1, \ldots, n$ the columns of $A$. By a conic variant of Carathéodory's theorem, each conic combination of $\{a_i\}$ can be written as a conic combination of a linearly independent subset of $\{a_i\}$. Since there are only finitely many linearly independent subsets of $\{a_i\}$, it is sufficient to prove the claim for ...


0

Given a linear matrix polynomial $A : \mathbb{R}^{n} \to \mbox{Sym}_k (\mathbb{R})$ defined by $$A (x) = A_0 + x_1 A_1 + \cdots + x_n A_n$$ where $\mbox{Sym}_k (\mathbb{R})$ is the set of $k \times k$ real symmetric matrices, and matrices $A_0, A_1, \dots, A_n$ are symmetric, we form the following linear matrix inequality (LMI) $$A (x) \succeq O_k$$ ...


1

Let $E$ be a complement of $\ker A$, i.e. $\;\mathbf R^n=\ker A\oplus E$. $E$ is closed in $\;\mathbf R^n$ since we're in a finite dimensional space, and likewise, $\;\operatorname{Im} A$ is a closed subspace of $\;\mathbf R^m$. Now, the restriction of A to $E$ is an isomorphism of $E$ onto $\;\operatorname{Im} A$. On the other hand $\;\{x\in E\mid x\ge 0\...


-1

Let $e_1,...,e_n$ be a basis of $R^n$, you can suppose that $A(e_1),...,A(e_l)$ generate the image of $A$, and $(e_{l+1},...,e_n)$ is a basis of $ker(A)$. if $y$ is an element of the adherence of $C=\{A(x),x\geq 0\}$, $y$ is in the vector subspace generated by $(A(e_1),...,A(e_l)$. You can write $y=y_1A(e_1)+...+y_lA(e_l)$. There exists $(x_m)=A(x_1^me_1+.....


1

Your start is good, if you're going for a proof by contradiction. So, suppose you have an $x$ with $f(x)=0$ such that $B(x,\varepsilon)\subseteq\{f(x)\geq 0\}$. Consider what happens along the line segment connect $x$ to some $v$ such that $f(v)<0$. In particular, for every $\alpha\in (0,1]$ we get that $f(\alpha v + (1-\alpha) x)<0$ by convexity. Now, ...


1

Since the function is convex, let $x$ be an element of the interior $U_0$ of $C_0=\{x\in R^n, f(x)\leq 0\}$.Suppose that $f(x)=0$, there exists an open ball $U\subset U_0$ which contains $x$, $f(U_x)$ is a connected interval since $f$ is continue. Suppose that for every $x\in U_0$ such that $f(x)=0$, $f(U_x)$ is the singleton $\{0\}$, this implies that $D=\{...


1

It seems, everything is a bit simpler. By the definition of the directional derivative we have: $$0>f'(x;v) = \lim_{t\to 0}\frac{f(x+tv)-f(x)}{t} =\inf_{t>0}\frac{f(x+tv)-f(x)}{t},$$ where the latter equality holds due to the convexity of $f$. Now by the definition of $\inf$ we got that for $t$ small enough $$f(x+tv)-f(x)\leq 0,$$ which means that $v$ ...


0

It is not a convex function. For $r=1$ and $x=1$ you get $f(a) = \log(a)$ which is clearly non-convex.


0

Any convex function $f:\mathcal{D}\mapsto\mathbb{R}$ is directionally-differentiable (in any direction) on its relative interior, where $\mathcal{D}\subset\mathbb{R}^n$. Stated symbolically: $$\forall x \in \mathbf{relint}\mathcal{D}, v\in\mathbb{R}^n: f^\prime(x;v) \text{ exists}$$ and $|f^\prime(x;v)| < \infty$. Just as a side note: If $f$ is convex, ...


1

If you have constraints where you turn on/off things by multiplying continuous variables with binary variables, you are typically not going to end up with convex (as in convex relaxations etc) models. Instead, you should model this using big-M strategies. For instance, if you want to model $xy\geq 1$ where $x$ is continuous and $y$ is binary, you introduce ...


0

This is a counterexample in $\mathbb R^2$, where every convex body that does not lie on a line has nonempty interior. First, take a function $g:\mathbb{R}^2\to\mathbb{R}$ that maps every nonempty open set onto all of $\mathbb{R}$. The same construction as in this answer works: take a countable basis of topology, insert a Cantor-type set in each, keeping them ...


1

It is the Hermite-Hadamard inequalities : The mesure $\nu$ defined by $d\nu=\frac{dx}{b-a}$ is a mesure of total mass $1$, its barycenter is $\frac{1}{b-a}\int_a^bxdx=\frac{a+b}{2}$, so the first inequality comes from Jensen inequality. For the second one use the substitution $t=a+x(b-a)$. $\frac1{b-a}\int_a^b f(x)\,dx=\frac1{b-a}\int_0^1 f((1-t)a+tb)dt\le\...


0

Since $f$ is convex on $[a,b]$, one has: $$\forall x\in[a,b],f(x)\leqslant\frac{f(b)-f(a)}{b-a}(x-a)+f(a).$$ Therefore, one gets: $$\int_a^bf(x)\;\mathrm{d}x\leqslant\frac{f(b)-f(a)}{b-a}\frac{(b-a)^2}{2}+f(a)(b-a).$$ Finally, one has: $$\frac{1}{b-a}\int_a^bf(x)\;\mathrm{d}x\leqslant\frac{f(b)+f(a)}{2}.$$


2

The inequality $$ f\Big(\frac{a+b}{2}\Big)\leq \frac{1}{b-a}\int_a^bf(x)\;dx $$ is a special case of Jensen's inequality. And since $f$ is convex, we have $$ f(x)\leq f(a)+\frac{f(b)-f(a)}{b-a}(x-a) $$ for $a\leq x\leq b$, hence $$\int_a^bf(x)\;dx\leq (b-a)f(a)+\frac{f(b)-f(a)}{b-a}\cdot\frac{(b-a)^2}{2}=(b-a)\frac{f(a)+f(b)}{2}$$ which is equivalent to the ...


0

For convenience, we can take $b=1,a=-1$. For the first inequality, use $$f(0) \le \dfrac{f(x) + f(-x)}{2}$$ and integrate both sides from $x=-1$ to $1$. For the second, use $$ f(x) = f\left( \dfrac{1-x}{2} (-1) + \dfrac{1+x}{2}(1)\right) \le \dfrac{1-x}{2} f(-1) + \dfrac{1+x}{2} f(1) $$ and integrate both sides from $x=-1$ to $1$.


1

The first summand $$f(x,y) = \dfrac{a}{bxy + cd} e^{\frac{a}{bxy+cd}} H$$ is not convex. Its Hessian at $(0,0)$ is $$ \left[ \begin {array}{cc} 0&-{\frac {Hab \left( a+{\it cd} \right) }{ {{\it cd}}^{3}}{{\rm e}^{{\frac {a}{{\it cd}}}}}}\\ -{\frac {Hab \left( a+{\it cd} \right) }{{{\it cd}}^{3}}{{\rm e}^{{ \frac {a}{{\it cd}}}}}}&0\end {array} \...


1

No, there are continuous quasiconvex functions that cannot be written as a convex function composed with a diffeomorphis. I give three reasons. Every convex function $g:\mathbb{R}^n\to\mathbb{R}$ is locally Lipschitz. So are diffeomorphisms. Therefore, the composition of a diffeomorphism with a convex function is locally Lipschitz. But, for example, $f(x)=...


0

Suppose we have the following objective function $$f (x) := \frac{1}{2} x^T Q x - r^T x$$ where $Q \in \mathbb R^{n \times n}$ is symmetric and positive definite and $r \in \mathbb R^n$. From the symmetry of $Q$, we conclude that its eigenvalues are real. From the positive definiteness of $Q$, we conclude that its eigenvalues are positive and that $f$ is a ...


0

Let $\mathcal{X}$ and $\mathcal{Y}$ be abstract sets and consider any real-valued function $f:\mathcal{X}\times \mathcal{Y}\rightarrow\mathbb{R}$. For any $(x,y) \in \mathcal{X}\times \mathcal{Y}$ we get: \begin{align} f(x,y) &\geq \inf_{a \in \mathcal{X}} f(a,y) \\ &\geq \inf_{b \in \mathcal{Y}}\left[ \inf_{a \in \mathcal{X}} f(a,b)\right] \end{...


1

Your intuitions are right. Indeed, $g: \alpha \mapsto x + \alpha p_k$ is affine whilst $f$ is convex. Therefore $f \circ g$ is convex.


0

OK, here's a deal: (a) The ray $\{\lambda v | \lambda \ge 0\}$ is closed. This is rather easy. Nothing to do here. (b) In finite dimensions, the convex hull of a compact set is compact. I've proven this for another question here. (c) The Minkowski sum of a compact set and closed set is again closed. This has been neatly shown here. Conclude that your set ...



Top 50 recent answers are included