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)

0
votes
0answers
69 views

Help prove a lemma similar to Fredholm alternative (linear algebra / convex optimization)

I was asked to help with a proof of a lemma similar to Fredholm alternative. It looks too similar so I think it may be wrong - could you please advise whether it is true and hint how to prove it? The ...
0
votes
2answers
69 views

If two convex sets have the same closure then their relative interiors are the same

I am having trouble seeing this. I have read and understood the proofs that cl(ri(C))=cl(C) and ri(cl(C))=ri(C). But to conclude that cl(C1)=cl(C2) iff ri(C1)=ri(C2) from the above two equalities? Do ...
1
vote
1answer
34 views

Problem in convex analysis

I found this problem in one of the old exams for convex analysis: Let $A \subseteq \mathbb{R}^n$ be a convex set and $f:A \rightarrow \mathbb{R}$ a convex function. a) Show that $f^{-1}(-\infty,a)$ ...
1
vote
1answer
118 views

Relative interior of the sum of two convex sets

I'd like to show ri(C1-C2)=ri(C1)-ri(C2) without using the fact that relative interior is preserved under linear transformations. I.e. Is there a way to show this by showing both inclusions?
2
votes
1answer
61 views

Affine hull of the intersection of two convex sets

Is it true that the affine hull of the intersection of two convex sets is the intersection of the affine hulls of these sets? Where the intersection of the two convex sets is non empty? Many thanks!
1
vote
1answer
22 views

Matrix convexity of -log

Is $-\log$ a matrix convex function? That is, taking the function $\log:(0,\infty)\rightarrow \mathbb{R}$ is the matrix inequality $$ \log\left((1-t)A+tB \right)\geq (1-t)\log A+ t \log B $$ satisfied ...
2
votes
0answers
42 views

Convex hull of the set of piecewise constant vectors

A piece-wise constant or blocky signal can be defined as follows Definition: Let $p,b\in\mathbb{N}$ such that $b\leq \left(p-1\right)$. Define the set of normalized blocky vectors as the following ...
0
votes
1answer
64 views

Show $f$ concave, $C^2$ implies $f''\leq 0$

Suppose I wanted to show that a concave function $f:(a,b) \to \mathbb{R}$ which is $C^2$ must have negative second derivative at each $x\in (a,b)$. I might try this by finite difference, noting that ...
0
votes
0answers
37 views

convexity in oriented matroid theory

I would like to try to solve the following problems. If someone knows how to prove at least part (a), could you show me the proof? I am having a LOT of trouble understanding oriented matroid theory. ...
0
votes
1answer
23 views

Proportion of domain in which convex function is small

Let $K \subseteq \mathbb R^n$ be a compact convex set with volume $V$, and let $f: K \to [0,1]$ be a convex function with domain $K$. Assume that $\min_{x \in K} f(x) = 0$. I claim that, for every ...
0
votes
1answer
76 views

Convex hull of the union of two nonempty sets

I was reading about convex hulls on Wikipedia (Convex hull) and I read : $ Conv(A \cup B)= Conv(Conv(A) \cup Conv (B))$ where $A$ and $B$ are nonempty sets. I can see intuitively that this equality ...
0
votes
1answer
84 views

Does a convex function with a Lipschitz continuous gradient always have a strong convex conjugate?

I got the answer is 'Yes' from a scribe. But I am confused because: Suppose there is a convex function $f(x)=x^THx$, where $x\in\mathbb{R}^N$ and $H\in\mathbb{R}^{M\times N}$ is positive ...
3
votes
0answers
59 views

On convex functions being continuous

Every convex function is continuous. It usually says "draw this and it will become obvious that the epigraph is not convex. However, when I draw the epigraph of $f: [0,3] \to \mathbb{R}, f(x) = x^2$ ...
0
votes
2answers
33 views

Proving that a certain set is convex

I'm trying to prove that the set $W = \{x \in \mathbb{R}^2 : 2x_{1}^{2} + 3x_{2}^{2} \leq 4\}$ is convex. I've been trying to do this using the definition of W being convex when for all $x, y \in W $ ...
1
vote
0answers
29 views

Issues with quasi Newton method convergence

I have this issue with the convergence of the quasi newton method. I have a convex objective function which I need to minimize wrt some parameters. I generated some synthetic data using a defined ...
1
vote
1answer
44 views

average of a bounded convex set

Suppose $X$ is a bounded convex set. We know that the average of any $n$ points of $X$, belongs to it, i.e. if $x_1, x_2, . . . , x_n \in X$ then $\frac{x_1+x_2+\cdots +x_n}{n}\in X$. How can we ...
0
votes
1answer
101 views

Finite optimal value for a linear program with unbounded feasible region.

I read this problem in CLRST : Show that a linear program can have finite optimal objective value even if the feasible region is not bounded. Now all the cases I could think of where such a thing ...
0
votes
1answer
219 views

Prove convexity of squared Euclidean norm

I need to prove that the square of the Euclidean norm is convex, so: $||\theta x+(1-\theta)y||^2\leq\theta||x||^2+(1-\theta)||y||^2$. Can I use the triangular inequality (if yes, how?) or should I ...
0
votes
1answer
52 views

A concept for measuring convexity of a set

I was wondering if there is such a concept for measuring the convexity of a set $S\subset \mathbb{R}^2$ (and similarly for $S\subset \mathbb{R}^n)$ with, say, $C^1$ boundary: For now let's assume ...
1
vote
1answer
82 views

Prove that $ri (epi f)=\{(x, y): x\in ri (dom f), y >f(x)\}$

$f: R^n \to (-\infty, \infty]$ is a convex function. Prove that $ri (epi f)=\{(x, y): x\in ri (dom f), y >f(x)\}$ I have used definition of convex functions to prove that the right-side is ...
5
votes
1answer
235 views

Mean value staying in a convex or a subspace

Let $f : \mathbb{R}^n \to \mathbb{R}^m$ such that $\forall x\in \mathbb{R}^n$, $f(x)\in C$ where $C$ is a convex set of $\mathbb{R}^m$ (respectively $f(x)\in F$ where $F$ is a linear subspace of ...
0
votes
2answers
29 views

convexity and the interior sphere condition

Consider $\Omega $ a open, convex bounded subset of $R^n$. Let $x_0 \in \partial \Omega$. I believe that exists a open ball $B \subset \Omega$ such that $\partial B \cap \partial \Omega = \{ x_0 \}$. ...
2
votes
1answer
41 views

Proof inequality using convexity

I struggling with proofing an inequality. We have to show that $x - y \le (1-\theta)^{-1} x^\theta (x^{1-\theta} - y^{1-\theta})$ holds for all $x, y > 0, \theta \in [0, 1)$. Further we know that ...
0
votes
1answer
51 views

convex function and convex set

Let $f$ be a convex function from $R_{++}^n$ to $R$. If $f(x_i)\geq f(y_i)$, where $x_i,y_i$ in $R_{++}^n$, $i=1,2,...,n$. The question is: is the following inequality true: $$f(\sum_{i=1}^n a_i ...
1
vote
1answer
56 views

Question about relative interior of subsets in $\Bbb R^n$

I would love to get some hint or direction regarding this : If $S\subseteq T$, when $S,T$ are convex, and ${\rm ri}(S) \cap {\rm ri}(T) \neq \emptyset$ then ${\rm ri}(S) \subseteq {\rm ri}(T)$. ...
0
votes
1answer
41 views

(pseudo-/quasi-)convexitiy of ratio between quadratic and affine function

Let $X\subseteq\mathbb{R}^n$. I have the following function $f:X\rightarrow\mathbb{R}$: $$ f({\bf x})= \frac{c_1 + \sum_{i=1}^n a_ix_i +\sum_{i=1}^n b_ix_i^2}{c_2+\sum_{i=1}^n d_i x_i}\enspace.$$ All ...
1
vote
1answer
19 views

Formula for extracting bounding points from a given set of points

I have a set of geographic locations, i.e. points defined by latitude and longitude. Given this set of points, I need to select only those of them that belong to the surface bounds. The simplest ...
0
votes
1answer
124 views

KKT conditions on minimization problem

I am trying to get an explicit solution to the following problem with the help of KKT conditions. But I am stuck. The problem: $ min_x 1/2 ||y-x||^2_2 + \lambda||x||_1 $ This is what I have done ...
1
vote
1answer
57 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
46 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
48 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
61 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
208 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
41 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
129 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
60 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
103 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
83 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
256 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 ...
0
votes
0answers
151 views

Is a linear-fractional function convex?

For example a simple linear-fractional function $f(x) = \frac{a^Tx+b}{c^Tx+d}$ with the domain of $f$ being $\lbrace x|c^Tx+d > 0\rbrace$, where $a, c, x \in \mathbf{R}^n$ and $b,d \in \mathbf{R}$. ...
7
votes
1answer
144 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
152 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
45 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
80 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
18 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
104 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
32 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
0answers
80 views

Proof of corollary of Farkas' lemma

I tried to prove the following lemma of Farkas' lemma: Given the system $Ax<b$, $A\in \mathbb{R}^{m\times n}$, $b\in \mathbb{R}^m$, the system is infeasible iff there exists $\lambda\in ...
0
votes
1answer
96 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
93 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.