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
1answer
85 views

Dual of this primal optimization problem?

How would one find the dual of the following problem? $min_x 1/2 ||y-x||_2^2 + \lambda||x||_1 $ Can someone please explain to me how to do this since there are no specific constraints?
0
votes
1answer
70 views

Proof that a ball is convex when $p =\infty$

I want to prove that a ball for infinity norm is convex: $$ B_\infty=\{x\in\mathbb R^n : \|x\|_\infty\le1\} $$ I came up with this proof and appreciate it if someone can help to verify if this is ...
0
votes
1answer
69 views

Is this function convex or concave?

I have a function, $f(x_{0},x_{1},......x_{n})=\sum^{n-1}_{i=0}A_{i}r^{-(x_{i}+x_{i+1})}-B$ $A_{i} >0$ for all $i$ and $B>0$ and $1 \leq r \leq 2$ so above function is convex or concave? ...
2
votes
0answers
102 views

Uniqueness of the solution

We know that 1) Minimise of a convex function the unique solution exists 2) Maximise of a concave function the unique solution exists How about 1) Minimise of a strictly convex function? 2) ...
5
votes
1answer
458 views

Dual to the dual norm is the original norm (?)

I have the following questions about dual norms : How do you prove that the dual of the dual norm is in fact the original norm? This is what I have so far: If I have $\|y\|_* $ as the norm dual of ...
1
vote
1answer
46 views

Does a discrete set of points in $\mathbb{R}^{n}$ define a locally finite collection of hyperplanes?

Let $v_{1},v_{2},...$ be a discrete set of non-zero vectors in $\mathbb{R}^{n}$. By discrete, I mean that any $v_{i}$ is surrounded by an $\epsilon$-ball not containing any other point $v_{j}$. ...
2
votes
0answers
139 views

Infimum over area of certain convex polygons

Let us identify the Euclidean plane with the complex plane $\Bbb C$. For every $n\ge 1$, consider the following collection of finite sets in $\Bbb C^{n+1}$: $$S_n:=\{(z_0,z_1,\dots,z_n)\in\Bbb ...
3
votes
1answer
75 views

What type of convex constraint is defined by SQRT?

Let $A$ be an $n \times n$ positive semidefinite matrix and $\forall k, x_k \in \mathbb{R}^n$. The distance with respect to this matrix is defined as $ \|x_i -x_j\|_A := ...
4
votes
2answers
111 views

Showing a quotient $\mathbb{Z}$ module is free

In Fulton's "Introduction to Toric Varieties" he repeatedly uses the following fact. Let $\sigma$ be a strongly convex rational polyhedral cone in a lattice $N$ and let $N_{\sigma}$ be the subgroup ...
1
vote
1answer
93 views

Prove that $f$ is a convex function if $f=d(x,C)$ and $C$ is convex.

Question: Suppose $V$ is a normed space and $f:V \rightarrow \mathbb R$ defined as $f(x)=d(x,C)=\inf_{c \in C}||x-c||_V$ where $C$ is a convex subset of $V$. Prove $f$ is a convex function. Attempt ...
2
votes
2answers
526 views

Show that $f(x)=||x||^p, p\ge 1$ is convex function on $\mathbb{R}^n$

Show that $f(x)=||x||^p, p\ge 1$ is convex function on $\mathbb{R}^n$. I have tried to use Holder's inequality, but I still cannot solve this problem. Could you help me with this problem? Thank you ...
7
votes
1answer
190 views

$\max\min$ problem

Suppose there is a real valued function $f(x,y)$ where $x,y$ are vector variables $x\in\mathbb{R}^n$ $y\in\mathbb{R}^m$. Moreover $f$ is strictly/concave in $x$ and strictly/convex in $y$. $f$ is also ...
4
votes
2answers
155 views

Product / GM of numbers, with fixed mean, increase as numbers get closer to mean.

I am trying to prove a statement which goes like this. Let $a_i$ and $b_i$ be positive real numbers where $i = 1,2,3,\ldots,n$; where $n$ is a positive integer greater than or equal to $2$, such ...
1
vote
0answers
58 views

Is the following problem convex , quasiconvex, or nonconvex?

I want to get the optimal matrix $W$. But I am not sure whether it can be resolved. Note that $W,\mu,\lambda_{1},\ldots,\lambda_{K} $ are variables, others are fixed. Is it convex or quasiconvex or ...
1
vote
1answer
87 views

Excercise of Convex Analysis

Let be $ K \subset \mathbb{R}^n $ a convex and closed cone, $ x \in \mathbb{R}^n $. Show that the following asserts are equivalent: $x_1$ is the projection of $x$ to $ K $ and $x_2$ is the ...
0
votes
1answer
26 views

Convex Set Property

I have a question regarding Convex Sets. It seems that if a convex set S contains the vertices $A_1, A_2, ..., A_k$ of a polygon P = $A_1A_2...A_k$, it contains all points of the polygon P. But how ...
4
votes
2answers
114 views

Convex sets: a hint on how to solve a problem

Could anyone give me a hint on how to solve the following problem? Let $X_1, \dots, X_{d+1}$ be some finite sets in $\mathbb{R}^d$, such that the origin lies in ${\rm conv}(X_i)$ for all $i \in \{1, ...
0
votes
1answer
36 views

Effect of Moving within the Feasible Region

$f:\mathbb{R}^n\rightarrow\mathbb{R}$ is a concave function with local maximum at $\mathbf{x}^*$ in a convex, closed feasible set $\mathcal{F}\subset\mathbb{R}^n$. Now consider a suboptimal point ...
0
votes
1answer
196 views

When does infinite intersection preserve a closed property?

There are two statements well known in Math and Computer Science: Intersection of infinite number of regular languages is not regular. Intersection of infinite number of convex sets is convex. ...
1
vote
2answers
98 views

$f, g$ are convex and positive $\Rightarrow f(x)g(y)$ is convex?

Prove or provide a counterexample: if $f$ and $g$ are real convex positive functions on some intervals, then $f(x)g(y)$ is convex.
3
votes
1answer
131 views

Every face of compact convex set is closed?

Well, this is my doubt: Let $\vec{E}$ be a n.v.s. and $K\subset \vec{E}$ a compact convex set. Then every face of $K$ is closed. Any hint in order to prove it is welcome. Thanks in advance!
0
votes
1answer
385 views

How do I prove that the composition of an affine function preserves convexity?

What would be the formal proof that $ f(Ax + b) $ given $ f(x) $ is a convex function ? I got to the point where I expanded $$ f(\lambda(Ax+b) + (1- \lambda)(Ay+b)) = f(A(\lambda x + (1 - \lambda)y) + ...
0
votes
1answer
63 views

Convexity of a sum of functions

I need to check whether a functions is convex. The function is sum over fractions $ S(c, \sigma, r) = \sum_n \frac{\mu_n}{c(\mu_n^2 + \omega^2)}$ where $\mu_n = \frac{r\lambda_n + \sigma}{c}$ with ...
1
vote
1answer
405 views

proximal operator of infinity norm

What is the proximal operator of $||x||_\infty $? I know we have to take the subgradient and compute it but I am a bit stuck. Can anyone show me steps?
1
vote
3answers
51 views

Why is $ \left( \frac1n \sum_{i=1}^n x_i^{p+1} \right) \geq \left( \frac1n \sum_{i=1}^n x_i \right)^{p+1} $ true?

Let us suppose that $0 \leq p \leq 1$. All variables are assumed to be non-negative. The function $x \mapsto x^{p+1}$ is strictly convex upwards, so $$ \left( \frac1n \sum_{i=1}^n x_i^{p+1} ...
2
votes
0answers
67 views

Maximizing the smallest eigenvalue of a linear combination of matrices

I have an engineering back ground. Due to work, I came across this problem \begin{align} &\max_{\lambda,y_i\in \mathbb{R}}~\lambda \\\ ...
1
vote
1answer
58 views

Real analysis, convexity problem

The course is an elementary course on Rudin so we don't have much material on convexity. We have this problem concerning a convex subset, $C$, of $R^k$. a) show that the closure $cl(C)$ is convex. ...
1
vote
2answers
23 views

Linear program dual

We are trying to find the dual of the following linear program. $$ \max_x \ 2x_1 \ + x_2 \ \ \ \ -- (1) $$ such that, $$ x_1 + x_2 \leq 2 \ \ \ \ -- (2)\\ -x_1 - x_2 \leq -4 \ \ \ ...
0
votes
1answer
107 views

Proximal functions

I am a little bit new to proximal functions and I am currently stuck with the following problems How would I derive the prox function for the regularizer (h(x) function) : $\alpha\sum_{k+} $ and for ...
1
vote
1answer
98 views

Proximal operator

What is a proximal operator and how would one derive it in general for a function? In particular, if I had a function: $ f(x) = x^TQx + b^Tx + c $ How would I get the proximal operator for this if Q ...
0
votes
0answers
85 views

Problem in the Hermite - Hadamard inequality.

Hermite - Hadamard inequality Let $f$ be a convex function on $[a, b]$. Then $$f \left( \frac{a+b}{2} \right) \leq \frac{1}{b-a} \int_{a}^{b} f(x) \, \mathrm{d}x \leq \frac{f(a)+f(b)}{2}.$$ Why is ...
0
votes
1answer
44 views

Subtle question concerning intersection of convex sets

I am attempting to convince myself that if $$\{S_{\alpha}: \alpha \in \mathcal{A}\}$$ is any collection of convex sets, then $$\cap_{\alpha \in \mathcal{A}}S_{\alpha}$$ is convex. This is my proof so ...
0
votes
1answer
28 views

Conjugate vectors

What are conjugate vectors? Can I have an example of it? [ This question is in respect to finding the roots of equations with conjugate direction methods]
1
vote
1answer
48 views

Existence of a supporting hyperplane

In $\mathbb R^n$, let $C$ be a closed convex set not equal to $\mathbb R^n$ itself. I'd like to prove that the boundary of C: $\delta C$ is the set of all supporting points of $C$. For the first ...
2
votes
0answers
47 views

Problem proving link between convexity and first derivative being monotonic

I'm having trouble completing a proof of a well-known theorem: suppose a real-valued function $f$ is differentiable in $I$; if $f$ is strictly convex in $I$ then $f'$ is strictly increasing in $I$. (I ...
0
votes
1answer
81 views

homework about convex set

Let $C$ be a nonempty convex subset of $\mathbb R^k$. Let $x\in\mathbb R^k$. Assume that $x$ is not an interior point of $C$. Show that there exists a vector $a$ not equal to $0$ such that a'x ...
2
votes
1answer
57 views

Find the real vector $x$ which satisfies all this?

I got this after applying KKT conditions to an optimization problem. Let $\mathbf{h}$ be a given $N\times 1$ real vector. Let $\alpha$ be a real constant. We need to find $\lambda$ and the $N\times ...
0
votes
1answer
140 views

When is the support function of a set strictly subbaditive?

Let $C\subset \mathbb{R}^n$ be a closed, convex set. The support function of $C$ is the function $\delta^*(\cdot|C):\mathbb{R}^n\rightarrow \mathbb{R}$ given by $$\delta^*(y|C)=\max_{x\in C}\sum ...
2
votes
0answers
54 views

Convex, closed, symmetric sets as open balls

So we recently saw the way that we can, given a convex symmetric body in $\Bbb R^n$, construct a norm such the closed unit ball is the convex set. We're wondering whether this holds for infinite ...
0
votes
1answer
626 views

Convex conjugate of $\ell_1$ and $\ell_2$ norm

Given a function $f$, we can define a function $f^{*}$, called the convex conjugate (also known as the Fenchel conjugate) of $f$ as follows: $$ f^*(\vec{z})= \sup_{\vec x \in \mathbb ...
2
votes
1answer
903 views

Unit Ball with p-norm

I am having trouble understanding the definition of p-norm unit ball. What I know is that for infinity (maximum norm), then it will shape as a square. I need a "click" to understand this, can someone ...
5
votes
1answer
113 views

Distance from point to vertices of convex hull

let $P = \{p_1, \ldots, p_k\}$ be any $k$ points on the unit $n$-sphere in $\mathbb{R}^{n+1}$ and $p_0 = 0$ the origin. Furthermore, let $CH(P\cup \{p_0\})$ denote the (possibly degenerate) convex ...
4
votes
1answer
344 views

Strictly convex function: how often can its second derivative be zero?

It's a basic fact that a twice-differentiable function from $\mathbb{R}$ to $\mathbb{R}$ is strictly convex if its derivative is positive everywhere. The converse is not true: consider, e.g., $f(x) = ...
1
vote
0answers
36 views

Is the optimizer of a strongly-convex cost function bounded?

Let f(x) be strongly-convex. Can its minimizer be unbounded? I suspect not. Can we obtain a bound on it in relation to the strong-convexity constant? I believe an equivalent formulation of this ...
0
votes
1answer
78 views

show that function is convex

Let $f:\mathbb{R}\to\overline{\mathbb{R}}$. Show that $$f\left(x\right)=\begin{cases} +\infty & \mbox{ if }x\in\left(0,\infty\right)\\ 0 & \mbox{ if }x=0\\ -\infty & \mbox{ if ...
0
votes
1answer
54 views

Measure of a set

Let $A \subset R$ such that for all open interval I, $m^* (A \cap I) < 1/2 L(I)$, where L is the length of a interval and $m^*$ is measure, prove that $m^*(A)=0$. I appreciate any hint to solve ...
0
votes
0answers
29 views

Finding Borel measures on a closed convex hull

Let $M=C(I)^{\ast}$, the space of complex Borel measures on the unit interval $I$. Suppose we give $M$ the weak*-topology induced by the Banach space $C(I)$. Now $\forall$ $t \in I$, let $e_t \in M$ ...
3
votes
2answers
2k views

Second derivative positive $\implies$ convex

In proof of the following theorem; If $f$ has a second derivative that is non-negative (positive) over an interval then $f$ is convex (strictly convex). $f$ is in real number space., the book I ...
3
votes
0answers
141 views

Polytopes inside polytopes

I would like to share some facts about polytopes and how to check whether a polytope is a subset of some other polytope. I will provide some methods and I would like to know whether there exist other ...
0
votes
0answers
174 views

Subsets of R2 that are convex, closed, and have non-empty interiors?

Can someone give me some guidance with this problem? Thanks. Suppose that $A, B \subset \mathbb{R}$ are convex, closed, and have non-empty interiors. Prove that $A, B$ are the closure of their ...