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 (1)

1
vote
2answers
83 views

computational strategy for solving convex-concave minmax problem

Assume f(x,y) is convex in $x$ and concave in $y$. Then \begin{equation}\min_x \max_y f(x,y)\end{equation} is globally solvable, because f is convex in x (max of convex is convex.) But can we find a ...
2
votes
0answers
257 views

Find a tight upper bound of the following expectation.

I am stuck in finding a tight upper bound (as tight as possible) of the following expectation $$E\left [ (1-a\cdot b^{X})^{m} \right ]$$ where $X\sim B(n-1,p)$ is a binomial random variable.In ...
1
vote
0answers
326 views

What is the relation between convex metric spaces and convex sets?

Here's another question that came to mind when I was reading the article on convex metric spaces in Wikipedia: According to the article, "a circle, with the distance between two points measured along ...
2
votes
1answer
66 views

Convex relaxation for the complement of Lorentz cone

Is it possible to obtain a convex relaxation for $$ \{ (x,t): t \le \|x\|_2\} \in \mathbb{R}^{d+1} $$ where $x \in \mathbb{R}^d$ and $\|x\|_2$ is the usual Euclidean norm, by moving to higher ...
4
votes
1answer
141 views

Convexity of a Given Function

Is the following function convex or concave? $$f(\mathbf{x}) = \frac{1}{N}\sum_{i=1}^N\sqrt{1+\frac{x_i^2}{\left(\frac{1}{N}\sum_{i=1}^{N}x_i\right)^2}},$$ $\mathbf{x} = [x_1,x_2,...,x_N]^T, x_i \ge ...
-3
votes
4answers
324 views

There is a ray from each point of unbounded convex set that is inside the set. [closed]

Let $A$ be a non-empty convex, unbounded set in $\mathbb R^n$. Prove that for each point $a \in A$, there is a non-zero vector $h \in \mathbb R^n$ such that $l = \{x \in \mathbb R^n \mid x=a+th,\ ...
2
votes
1answer
51 views

Is this a linear programming problem

If $x \in R^n$, then $\min \|x\|_{\infty}$ sub to $Ax = b$, $x \geq 0$ where $\|x\|_{\infty}$ is the infinity norm which is $\max\{\|x_1\|,\|x_2\|,\ldots,\|x_n\|\}$. If not then how can ...
1
vote
2answers
136 views

Convexity and minimum of a vector function

Prove that the function $f:\mathbb{R}^n\to \mathbb{R}$ given by $f(x)=x^T \cdot x$ is strictly convex. Use this result to find the absolute minimum by equating the derivative to zero. I am not sure ...
3
votes
1answer
186 views

$(d-1)$-rectifiability of a boundary of compact convex set

Let us have a compact convex set $A\in \mathbb{R}^d$. Then $\delta A$ should be a $(d-1)$-dimensional rectifiable set. I don't seem to be able to show that it can be covered by a countable union of ...
0
votes
1answer
35 views

Is $\{x\in\mathbb{R}^4: x\ge 0, \, x_1x_2+x_3x_4\ge\alpha\}$ convex?

Is $\{x\in\mathbb{R}^4: x\ge 0\, \mbox{ and }\, x_1x_2+x_3x_4\ge\alpha\}$, for $\alpha>0$, a convex set? A related question is this one: Is $f(x_1,x_2)=x_1x_2$, with $x_1,x_2 \in \mathbb{R}_+$, a ...
0
votes
1answer
53 views

non convex optimisation

\begin{eqnarray} {\textbf{maximise}} \hspace{2mm} Ar^{-(a+b)} + Br^{-(a+b+c)}-C \nonumber \end{eqnarray} such that, \begin{eqnarray} c= l(h-m_{0}) \nonumber\\ m_{1} \leq h \leq m_{2} \nonumber\\ ...
0
votes
1answer
308 views

Convex Functions: Property Proof

Let $f\colon S\to \mathbb R$ be a $C^1$ function on a convex domain $S \subseteq \mathbb R^n$. Show that if $f$ is convex then $(\nabla f(x) - \nabla f(y)) \cdot (x-y) \ge 0$ for all $x,y \in S$. ...
1
vote
1answer
42 views

Proving the convexity of a set drawn by a function

I want to prove or disprove the following: For any $x_1,y_1,x_2,y_2\in \mathbb{R}$ such that $$ a \leq x_1 \leq b, \qquad c \leq y_1 \leq d$$ $$ a \leq x_2 \leq b, \qquad c \leq y_2 \leq d$$ when ...
0
votes
1answer
108 views

Fenchel conjugate of a particular function

Consider the function $$f(x,y) = \big(b-x^T A y\big)^2$$ where $x \in \mathbb{R}^{p\times 1}$, $y \in \mathbb{R}^{n\times 1}$, $A \in \mathbb{R}^{p \times n}$ and $b \in \mathbb{R}$. What is the ...
1
vote
0answers
112 views

Characterization of Convex Symmetric Balanced Sets

Let $E$ be a Vector Space over $\mathbb{K}$, where $\mathbb{K}=\mathbb{R}$ or $\mathbb{K}= \mathbb{C}$. We say that $U\subset E$ is balanced if $\alpha U\subset U$ whenever $|\alpha|\leq 1$, where ...
0
votes
1answer
28 views

Directions of decrease for a convex functions

Suppose $f(x,y)$ is a convex function and $$ f(x+\Delta x, y) < f(x,y), ~~~ f (x, y + \Delta y) < f(x,y)$$ Does this imply $$ f(x+\Delta x, y + \Delta y) < f(x,y)$$? I am guessing the ...
0
votes
1answer
94 views

The support function of two sets are equal iff the sets are equal

I am not sure how to approach this question from Boyd. How to show that the support function of two sets $A$ and $B$ are equal iff $A=B$. The support function for a set $A$ is defined as ...
0
votes
2answers
66 views

Is the following function differentiable?

Suppose $ C \subseteq \Bbb R^n $ is bounded, and define $f:\Bbb R^n\to\Bbb R$ by $$f(x) = \sup_{y \in C}\|x-y\|, $$ where the norm is euclidean distance. Is $f$ differentiable?
0
votes
1answer
96 views

Whether this set is convex or not?

Consider the closed disk of radius 1 at the origin. Let it be called set S. Now is the set $S'=S\setminus \{(1,0),(0,1)\}$ convex? I feel like it is convex but I am not sure how to prove. It basically ...
1
vote
0answers
178 views

how to solve the following expectation? closed-form expression or approximation

Suppose there is a binomial random variable $X\sim B(n-1,p)$,how to solve the following expectation $$E[(1- b^{X})^{m}]$$ where $b\in (0,1]$ and $m\in \mathbb{N} $ are all constants.I have tried my ...
2
votes
1answer
198 views

relative interior, convex hull, intersection

For any index set $I$, let $A_\iota\subseteq\mathbb{R}^d$ for $\iota\in I$ be closed sets. Do we have $\bigcap_{\iota\in ...
1
vote
2answers
520 views

A question dealing with the convexity of functions involving the absolute value

Just beginning to learn convex analysis and optimization, I have some inquiries to make with regard to the absolute value function $f(x)= |x|$. This function is clearly convex, but since we know that ...
3
votes
2answers
185 views

How can I prove that a function $f(x,y)= \frac{x^2}{y}$ is convex for $y \gt 0$?

How can I prove that a function $f(x,y)= \frac{x^2}{y}$ is convex for $ y \gt 0$? I take the Hessian matrix of $\displaystyle \frac{x^2}{y}$, and I got: $$H = \displaystyle\pmatrix{\frac{2}{y} & ...
2
votes
2answers
345 views

Convex sets proof

Prove the following theorem: Let $V$ be a linear space and $D$ a convex set. Let $x_1,...,x_k$ be $k$ points in $D$. Let $a_1,...,a_k$ be non-negative scalars such that $\sum\limits_{i=1}^n a_i=1$. ...
3
votes
1answer
159 views

Interior point and Minkowski functional

I want to prove for a convex set that contains zero a point $x$ is interior iff the value of Minkowski functional in that point is strictly less than $1$. is there anyone to help me.
1
vote
1answer
149 views

Submodularity of the product of two non-negative, monotone increasing submodular functions

I'm trying to prove the submodularity of the product of two non-negative, monotone increasing submodular functions Formally, we have $f$ and $g$ are submodular functions, that is, ...
2
votes
1answer
97 views

Continuous and non-decreasing but how?

I am reading a paper and the author shows the continuity and monotonicity of a function. It seems so simple to see but I am sorry that I couldnt see the reason. I will be very happy if you can point ...
1
vote
1answer
131 views

Sum of non convex sets

1) Can the sum of two non convex set be a convex set ? 2) Can the sum of convex set and non convex set be a convex set ?
0
votes
1answer
35 views

Is the set of points in $\mathbb R^n$ for which the sum of all distances from fixed $k$ points is $\le1$, convex?

Is it true that the set of points in $\mathbb R^n$ for which the sum of all distances from fixed $k$ points is $\le1$, is convex?
14
votes
2answers
293 views

Construct an example of set $A$ for which $A+A=A $ but $0∉cl(A)$

How to prove that convexity is necessary condition in this question? Need to construct an example of set $A$ for which $A+A=A$ but $0 \notin cl(A)$. From the linked question follows that $A$ must be ...
1
vote
1answer
180 views

Is this function convex or concave on $(x,y,z)$?

Is this function convex or concave on $(x,y,z)$? $A$, $B$, $a$, $b$, and $c$ are positive constants. $$f(x,y,z) = A\exp\left(\sqrt{(x-a)^2+(y-b)^2+(z-c)^2}\right) + ...
7
votes
3answers
225 views

How to prove that if convex $A \subset \mathbb{R}^n$ and $A+A=A$ then $0 \in cl(A)$?

How to prove that if convex $A \subset \mathbb{R}^n$ and $A + A = A$ then $0 \in cl(A)$? For a example of $A$ which holds a condition but $0 \notin A$ consider $(0,\infty)$.
1
vote
2answers
40 views

If for each $x,y \in A$ , $\frac{x}{2} + \frac{y}{2} \in A$ and $A$ is closed set then $A$ is convex.

If for each $x,y \in A$ , $\frac{x}{2} + \frac{y}{2} \in A$ and $A$ is closed set then $A$ is convex. How to prove? For a example of non convex set which is not closed and holds the condition is ...
1
vote
1answer
121 views

affine set definition equivalence

How to show the following definitions are identical for an affine space: $C = p + W$ where $W$ is a subspace $p$ is a vector in $\mathbb{R}^n$, and $\lambda a + (1-\lambda) b$ is in $C$ for any $a$ ...
2
votes
1answer
121 views

Is the polar set of convex Polytope also Polytope

Let $P$ be a convex polytope. How can I prove that the polar set of $P$ (lets call it $P^*$) is polytope? where $P^*=\{x\in\mathcal R^n:\forall v\in P, |\langle x,v\rangle|\le1\}$ . $Thanks$
0
votes
1answer
73 views

Convexity of a function

Define function $F$ as $F(x,y,x,t)= (xy-zt)^2$ where $x,y,z,t \geq 0$. Question: Is this function Convex? Thanks!
2
votes
3answers
119 views

“Interpolation” of polynomials

I'm dealing with a probability problem and I have to understand the following operation on polynomials: let $F$ and $G$ be any two polynomials of variable $p\in [0,1]$ (to be thought of as a Bernoulli ...
0
votes
2answers
66 views

Banach space Lower semi-continuity (lsc) implying continuity

How to show the following: If the monotone real valued function $f(x)$ whose domain is a subset of $R$ is lower semi continuous on every point of the interior of the domain then it is continuous on ...
3
votes
1answer
80 views

Showing that the set of polynomials is convex

How to show that the set of polynomials of $x^2+bx+c$ having at least one real root, is convex? Let $x^2+b_1x+c_1$ and $x^2+b_2x+c_2$ have at least one real root. Need to show that ...
1
vote
1answer
123 views

directional derivative sublinear of a convex function sublinearity problem to show

How to show the following: If $f:\mathbb R^d \rightarrow \mathbb R$ is convex then its directional derivative is sublinear? Thank you...
3
votes
1answer
168 views

Weak convexity and continuity

For any open interval $(a, b)\subset {\mathbb R}\,$, define a weakly convex function $f:(a, b) \rightarrow {\mathbb R}$ as one for which $$f(q\;x_0 + (1 - q)\;x_1) \leq q\;f(x_0) + (1-q)\;f(x_1)$$ ...
2
votes
1answer
61 views

Possibility of Unboundedness in Least Squares Minimization

Suppose we have the quadratic minimization problem \begin{equation} \min_x \frac{1}{2} x^TPx + q^Tx +r \end{equation} We know that when $P$ is symmetric positive semi-definite, but the optimality ...
3
votes
1answer
47 views

If a vector in a convex set can be extended infinitely to a certain direction, can any vector in that set be extended infinitely to that direction

Assume we have a convex set $U$. Given $x \in U$, assume there exists a vector $y$ such that $\forall t>0, \ \ x+ty \in U$. I wish to prove that $\forall z \in U,\ \ \forall t>0,\ \ z+t y \in U$ ...
0
votes
1answer
143 views

directional derivative of convex function sublinear proving that fact

How can we show that the directional derivative of a proper convex function on $\mathbb{R}^n$ is sublinear? Thank you!
1
vote
0answers
143 views

How to check the convexity of a constrained set

Say that we have the following matrices: $A\in M_{n,n}$ which is unknown, $Y\in M_{n,m}/\{0_{n,m}\}$ and $X\in M_{n,m}/\{0_{n,m}\}$. I want to show that the following set is convex $\Omega=\{S\in ...
0
votes
1answer
77 views

convex conjugate $f^*$ is proper if both $f$ and $f^{**}$ are

If $f$ and $f^{**}$ on $\mathbb R^d$ are proper functions where $f^*$ stands for the convex conjugate of $f$ why does that follow that $f^*$ is proper, too? Thanks a lot...
1
vote
0answers
270 views

Is the composition of trace inverse and convex matrix product convex?

Is the trace of the inverse of the matrix product $B^TB$, i.e. $\mathrm{trace}((B^TB)^{-1})$, convex where $B\in M_{n,m}$. I know that $S\longrightarrow \mathrm{trace}(S^{-1})$ is a convex function ...
1
vote
2answers
314 views

Infimum/Supremum of an intersection of subsets of a vector space.

Consider a collection of subsets $A_i$ of an ordnered vector space or field. I am trying to find out, under what (minimal) conditions the following holds. $\inf \bigcap_{i\in I}A_i \le \sup_{i\in ...
0
votes
1answer
345 views

Convex functions - multi variables

I have $ x_1,x_2,..,x_n\in\left[0,1\right] $. Suppose $ x=(x_1,x_2,..,x_n), F(x,i,j,\epsilon)=g(x_1,...,x_i+\epsilon,...,x_j-\epsilon,..,x_n) $ . We know that $F$ is convex with respect to ...
0
votes
1answer
159 views

Relative interior inclusion of convex sets

Is relative interior(C-D) = relative interior(C) - relative interior(D) where C and D are nonempty convex sets. If so please give the proof If thats not the case could you give a counterexample ...