Convex analysis is the study of properties of convex sets and convex functions. For questions about optimization of convex functions over convex sets, please use the (convex-optimization) tag.

learn more… | top users | synonyms (3)

1
vote
1answer
17 views

Can a compact set of $\mathbb{R}$ have some properties and not being convex

The question is related to this one On a condition when bounded sets in R n is convex ?. Suppose that $n > 1 $ and that $C \subset \mathbb{R}^n$ is a compact (closed and bounded) set having a ...
0
votes
1answer
293 views

Convex function and its epigraph PROOF

Can someone help prove this statement. Consider a function $f:R^{n} \to R$ and epi $f$ = {$(x,t) \in R^{n+1}$: $x \in R^{n}$, $t \geq f(x)$} A function is convex if and only if its epigraph is a ...
4
votes
2answers
29 views

On a condition when bounded sets in $\mathbb R^n$ is convex ?

Is it true that a bounded set in $\mathbb R^n$ , $n>1$ , is convex iff every straight line through an arbitrary interior point of the set intersects the boundary of the set in exactly two points ? ...
0
votes
0answers
19 views

Intersection between a hyperplane and a convex polytope

We work over $\mathbb{R}^N_+$, where $N \ge 2$. We are facing a situation in which we need to find the intersection between a hyperplane and a convex polytope. I tried to search on the internet, but ...
1
vote
2answers
59 views

Theorem 6.4.1 Auslender Asymptotic cones and functions in optimization and variational inequalities

In proof of Theorem 6.4.1, the author assumes that $\text{rge}\,A\subset\text{aff}\,C$ and for $\epsilon>0$ claims that $\epsilon^{-1}(C-\text{rge}\,A)\subset\text{aff}\,(C-C)$, that I can't verify ...
0
votes
1answer
24 views

If the boundary of a convex set in $\mathbb R^n$ ($n>1$) is connected , is it necessarily also path-connected ?

If the boundary of a convex set in $\mathbb R^n$ ( where $n>1$) is connected , is it necessarily also path-connected ?
2
votes
1answer
16 views

Connected-ness of the boundary of convex sets in $\mathbb R^n$ , $n>1$ , under additional assumptions of the convex set being compact or bounded

Is the boundary of every compact convex set in $\mathbb R^n$ , ($n>1 $ ) connected ? is it path connected ? What if we assume only that the convex set is bounded , is the boundary connected ( and ...
0
votes
0answers
16 views

Half space representation of a convex polytope

We know that the half space representation of a polytope is given by: $Ax<b$. Consider a convex polytope in $\mathbb{R}^3_+$ with vertices given by the following set of points: ...
0
votes
1answer
147 views
+50

Proving that $\text{ri rge}\,A=\text{ri conv rge}\,A$

"If $A:\mathbb R^n\rightrightarrows\mathbb R^n$ is maximal monotone,then $\text{ri rge}\,A$ is convex". This is a proposition in auslender's book about the asymptotic cones. We can prove that ...
0
votes
0answers
23 views

Dividing given rectangle into regions with certain finite points being given

The problem I am facing is as follows. Suppose we have a unit square and we have been given certain no. of finite points, n (For eg n=5) which are randomly spread in the square. Now, we want to ...
-1
votes
0answers
19 views

Exactly one supporting line for a $C^1$ Jordan curve [on hold]

Let $\gamma :[a,b]\to\mathbb{R}^2$ be a convex Jordan curve (closed, simple, continuous) that has $C^1$ regularity, with $\gamma '(t)\neq 0,\ \forall t\in [a,b]$. Prove that there is exactly one ...
0
votes
1answer
16 views

Let $A$ be a convex set in $\mathbb R^n $ , where $n>1$ ; then is it true that $\bar A \setminus A^{\circ}$ i.e. the boundary of $A$ is connected ?

Let $A$ be a convex set in $\mathbb R^n $ , where $n>1$ ; then is it true that $\bar A \setminus A^{\circ}$ i.e. the boundary of $A$ is connected ? if yes , then is it also path connected ?
1
vote
0answers
25 views

References for the following functional

In many of the types of problems Ive looked at the following quantity keeps arising and I was wondering if anyone knew any references I could look at to learn some its properties. Take any function ...
0
votes
1answer
13 views

$A$ be a non-empty closed convex subset of a Hilbert space $H$ , is the distance from $A$ always attained at a unique point in $A$ ?

Let $A$ be a non-empty closed convex subset of a Hilbert space $H$ , then is it true that for every $b \in H$ , $\exists$ unique $x_b \in A$ such that $||x_b-b||=d(b,A)=\inf \{||b-x||:x \in A\}$ ?
1
vote
0answers
22 views

Why is this function, related to SVM derivation, non-convex?

I'm working through a support vector machines tutorial. In eventually deriving the solvable objective function, the following objective function (to be maximized) was proposed, but dismissed as ...
0
votes
0answers
32 views
+50

Characterizing affine subspaces order-theoretically

Let $V$ denote a real vectorspace and $\mathrm{Con}(V)$ denote the poset of convex subsets of $V$. The goal is to identify those elements of $\mathrm{Con}(V)$ that happen to be affine subspaces of $V$ ...
-1
votes
0answers
31 views

How to prove that the following function is convex

I have a following function that I would like to show it is convex in $x$, however the function is not a sum of convex functions so I think I need to specify some conditions. However I don't know how ...
0
votes
0answers
27 views

Is convex or non convex function?$J(u,c)=\int K(x).u.(f(x)-c)^2dx$

I have a function such as $$J(u,c)=\int K(x).u.(f(x)-c)^2dx$$ where $f(x):\Omega \to R$; c is constant; $0 \le u \le 1$; and K(.) is gaussian kernel. My question is that : Is J convex or non-convex ...
1
vote
1answer
53 views

Is there any way to make the following function convex?

I need to find optimal lagrangian multiplier vectors for a quadratic programming problem subject to three quadratic equality constraints and several other linear inequality constraints. I would like ...
1
vote
1answer
33 views

Difference of support functions and its minimum points

Let $A$ and $B$ are convex, compact sets in $\mathbb{R}^n$. We have known that $$\max_{a\in A}\min_{b \in B} \|a-b\|=\sup_{\|g\|\le1}(\sigma_A(g)-\sigma_B(g)),$$ where $\sigma_M(x)=\sup_{u\in ...
1
vote
0answers
28 views

How to understand a proposition of subgradient

The question is from the following: Convex Optimization Algorithm (p.512)----- Prof. Bertsekas Let $f: R^n \rightarrow (-\infty, \infty]$ be a proper convex function. For every $x \in ...
4
votes
1answer
27 views

Visualizing Euclidean Algorithm in $\mathbb{Q}(\sqrt{-7})$ and $\mathbb{Q}(\sqrt{-11})$ with Convex Geometry

In an attempt to answer one of the bounty questions, I have started picturing Euclidean division in quadratic fields. In theory we would like the equation: $$ a = b\,q + r ...
0
votes
0answers
20 views

Find parameters of a quadratic surface given 3 points

I have 3 points in the space each defined as a vector with its two coordinates $\eta_k=(x~~ y)^T$. Given $\eta_1,~ \eta_2$ and $\eta_3$ I would like to find the parameters $Q,~ P$ and $b$ of the ...
2
votes
1answer
50 views

Calculating the distance function and projection

Let $\Omega=\{x\in\mathbb R^n\mid\langle a,x\rangle=b\}$. We define the distance function and projection as follows $$d(x;\Omega)=\inf\{||x-\omega||\mid\omega\in\Omega\}$$ ...
0
votes
1answer
50 views

Lower semi-continuity of particular function

Let $F : \mathbb{R}^n \rightrightarrows \mathbb{R}^n$ be a set-valued map, locally bounded, upper semi-continuous, and taking nonempty, convex and compact values. Let $f : \mathbb{R}^n \to \mathbb{R}$ ...
0
votes
1answer
21 views

Supporting lines of closed Jordan curve

Given a simple closed Jordan (i.e. continuous) curve $\gamma:[a,b]\to\mathbb{R}^2,\ \gamma([a,b])=C_\gamma$, how can I prove that $D_\gamma$ (the set of all interior points of $\gamma$ toghether with ...
3
votes
1answer
18 views

Volume of Convex Polytope with rational Entries

I have the following question: In this article Polytope volume computation it is stated that when considering a bounded convex polytope $P=\{x \mid Ax\le b\}$ with the matrix $A$ and the vector $b$ ...
1
vote
0answers
66 views

Find the intersection between two convex hulls, in this specific case

We work over $\mathbb{R}^K$. Let $V$ the set of vectors whose coordinates take values $0$ or $1$, or equivalently the corners of the unit cube $[0,1]^K$, . Let $d:\{0, \ldots, K\} \to \mathbb{R}_+$ ...
2
votes
4answers
91 views

Sufficient condition for convexity

Let f:$ [a,b] \rightarrow \mathbb{R} $ a continous function such that $ \forall (x,y) \in [a,b]^{2}, \exists t \in ]0,1[, f(tx+(1-t)y) \le tf(x) + (1-t)f(y) $ show that f is convex
1
vote
1answer
27 views

Strongly convex, bounded from below by a quadratic function.

A strongly convex function $V: \mathbb{R}^d \rightarrow \mathbb{R}$ with negative parameter is given, i.e. $$ V(tx + (1-t)y) \leq tV(x) + (1-t) V(y) - \lambda t(1-t) | x -y |^2 , $$ with ...
1
vote
1answer
53 views

Convex function inequality for Euclidean norm: $\|(f(x_1),\cdots,f(x_n))\|_2\leq f(\|x\|_2)$

Let $f:\mathbb{R}\rightarrow\mathbb{R}$ be a positive, convex, continuous function such that $f(0)=0$. (If you wish you can also suppose $f$ to be monotone increasing.) I would like to prove or to ...
0
votes
0answers
55 views

Is $C(B^c)$ an open set?

Assume that $B$ is an open set, if \begin{equation*} C:=\{x=\sum_{i=1}^{n}\lambda_{i}x_{i},\lambda_{i} \geq 0,\sum_{i=1}^{n}\lambda_{i}=1,x_i \in B\} \end{equation*} is a convex that contains $B$, ...
-2
votes
2answers
29 views

Simple question on convexity [closed]

If $\epsilon,\lambda\in(0,1)$, $a,b\in(1-\epsilon,1+\epsilon)$, then is $$\lambda a+(1-\lambda)b\in(1-\epsilon,1+\epsilon)?$$
3
votes
1answer
2k views

Relation between Positive definite matrix and strictly convex function

I have a problem. From wikipedia http://en.wikipedia.org/wiki/Positive-definite_matrix any function can be written as $$z^TMz$$ where z is a column vector and M is a symmetric real matrix. However ...
3
votes
2answers
45 views

Proving $x\ln(\frac{x}{a})+y\ln(\frac{y}{b})\geq (x+y)\ln(\frac{x+y}{a+b})$

Let a,b,x,y be positive reals. Prove $x\ln(\frac{x}{a})+y\ln(\frac{y}{b})\geq (x+y)\ln(\frac{x+y}{a+b})$ I don't have any olympic background, so I may be missing some standard trick. The ...
0
votes
1answer
19 views

Interior of difference of two convex sets

Let $A, B$ be two nonempty convex set in normed space $X$. We always have $$ \text{int}(A)\bigcap B\ne\emptyset\;\Longrightarrow\; 0\in\text{int}(A-B). $$ Indeed, suppose that $\text{int}(A)\bigcap ...
1
vote
2answers
46 views

Is it convex function?

I have a function and I don't know it is whether convex or non-convex: $$J(c,\alpha)=\int_\Omega ( \alpha c-I(x))^2u \, dx+ \|\alpha\|^2$$ where $0 \le u \le 1$, $I(x): \Omega \to R$, $c$ is constant ...
2
votes
2answers
60 views

If $A\subset B$, then $\text{ri}\, A\subset\text{ri}\,B$?

Is it true that If $A\subset B$, then $\text{ri}\, A\subset\text{ri}\,B$? Let $u\in\text{ri}\,A$, then there is $\epsilon>0$ such that $$\mathbb B(u;\epsilon)\cap\text{aff}\,A\subset A\subset B$$ ...
4
votes
2answers
38 views

Supporting hyperplane of a convex set

Let $\Omega$ be a bounded convex set in $\mathbb{R}^n$, and let $\partial \Omega$ denote its boundary. Fix a point $p$ in $\Omega$, and let $c$ denote the point on $\partial \Omega$ that is closest ...
0
votes
0answers
18 views

Curvature of strictly concave function: scaling of derivative

I am looking at a strictly concave function $f: R_+ \to {R}$ with $f' >0$ and $f'' < 0$. I require the following property which I don't fully understand: $$ k f'(kx) \geq f'(x) \quad \forall ...
1
vote
1answer
28 views

any good way to approximate this non-convex function with convex function?

There is a non-convex constraint in my optimization problem, which is given by $\displaystyle -xy\log\left(1+\frac{z}{xy}\right)$. Obviously, it is neither convex or concave. Is there any good convex ...
3
votes
2answers
354 views

Are convex hulls of closed sets also closed?

If $X$ is a compact set in $\mathbb R^n$, how can we show that $\operatorname{conv} X$ is compact as well? Can we say something similar without assuming boundedness, i.e., are convex hulls of closed ...
2
votes
1answer
38 views

convexity proof of a function including ln and sums

$$f(x_1,\dots,x_n)=\sum\limits_{i=1}^nx_i\ln x_i-\left(\sum\limits_{i=1}^nx_i\right)\ln\left(\sum\limits_{i=1}^nx_i\right)\rightarrow R_{++}^n$$ How can I prove this is convex on $R_{++}^n$? I tried ...
0
votes
0answers
18 views

Equivalence of two properties [closed]

Let $f:\mathbb{R}^n\rightarrow\mathbb{R}$ and $\alpha>0$. Prove that the two following properties are equivalent: (1) For all $|\delta|\leq\alpha$, $\lambda\in (0,1)$, and $x_0,x_1\in\mathbb{R}^n$ ...
0
votes
0answers
27 views

Existence of a continuously differentiable function from the projection of a convex set

Let $V$ be an open convex set of $\mathbb{R}^{n+1}$ and let $U$ be the projection of $V$ onto $\mathbb{R}^n$ - i.e. the set of $x \in \mathbb{R}^n$ such that there is some $y \in \mathbb{R}$ with ...
1
vote
1answer
17 views

$x=argmin_{x\in A}||y-x||_2$ iff $\langle y-x,z-x\rangle \leq0$ for all $z\in A$

Consider $x\in A\subset\mathbb{R^n}$ with A closed and convex. How can you see that $$x=argmin_{x\in A}||y-x||_2$$ iff $$\langle y-x,z-x\rangle \leq0$$ for all $z\in A$. I tried using ...
0
votes
2answers
39 views

$f$ convex: exists linear map $g$ s.t. $f\geq g$?

Let $f:\mathbb R\to\mathbb R$ be convex. Does there exist a linear map $g(y)=ay+b$ such that $f(y)\geq g(y)$ and $f(x)=g(x)$? Clearly, if f is differentiable we can argue with the tangent line, but ...
0
votes
0answers
42 views
5
votes
2answers
78 views

Proving $x^4$ is strictly convex

I'm not sure how to prove $f(x) = x^4$ is strictly convex using just the definition of strict convexity: $$f((1-t)x+ty) < (1-t)f(x)+tf(y)$$ for $0<t<1$. Is this just an algebra slog? If so, I ...
0
votes
1answer
25 views

Interpreting a condition about CDF

Let F(X) be a strictly increasing CDF which admits a positive density f(x). Is the condition x/F(x) being non-increasing (aka, weakly decreasing) equivalent to saying that F(x) is convex? If not, what ...