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)

2
votes
1answer
871 views

$f$ is convex function iff Hessian matrix is nonnegative-definite.

Let $f: \mathbb{R}^2 \rightarrow \mathbb{R}$, $f \in C^2$. Show that $f$ is convex function iff Hessian matrix is nonnegative-definite. $f(x,y)$ is convex if $f( \lambda x + (1-\lambda )y) \le ...
1
vote
0answers
20 views

Checking convexity by looking at 2-dimensional cross-sections

If I have a closed set of n-dimensional points and I want to know if it's convex just by examining some set of 2-dimensional cross-sections (and checking each cross-section for convexity), how small ...
0
votes
0answers
56 views

Online convex programming: Projection followed by normalization

I have the following projected gradient descent online linear programming problem which has been well studied in www.cs.cmu.edu/~maz/publications/techconvex.pdf‎ $\mathbf{y}_{t+1}=\mathbf{w}_t - ...
0
votes
1answer
64 views

How can I prove this problem is quasiconvex?

I'm doing a convex optimization problem. It requires me to fit a rational function to an exponential function. I assumed the original problem would be a quasiconvex optimization problem and based on ...
1
vote
2answers
77 views

Minimizing a convex cost function

I'm reviewing basic techniques in optimization and I'm stuck on the following. We aim to minimize the cost function $$f(x_1,x_2) = \frac{1}{2n} \sum_{k=1}^n \left(\cos\left(\frac{\pi k}{n}\right) x_1 ...
0
votes
1answer
41 views

Strict convexity of the following function

I have a function that is of the form $C({\bf x}) = c_1\left(a_1x_1 + b_1x_1^2\right) + c_2\left(a_2(x_1-x_2) + b_2(x_1-x_2)^2\right) + c_3\left(a_3(x_2-x_3) + b_3(x_2-x_3)^2\right)$ where each ...
0
votes
2answers
79 views

Solution in general for a seemingly simple problem

Let $\mathbb{S}$ be a closed, bounded, convex set in $\mathbb{R}^N$. Let $\mathbb{x}=[x_1,\dots,x_N]$ be any arbitrary vector in $\mathbb{S}$. Then what can we comment on the problem \begin{align} ...
1
vote
0answers
46 views

Proving convexity of the Schatten 1-norm

Is it possible to show that the Schatten 1-norm is convex by the definition of convexity? I can't seem to find any way to derive an expression of the sum or matrix of singular values of a convex ...
0
votes
1answer
146 views

Extreme points of a convex set

How do i find all extreme points of the set: $\displaystyle C=\{x\in\mathbb{R}^n | \sum_{i=1}^n |x_i| \leq 1 \}$? I guess that $x=0$ is an extreme point, but how can i show it and is it the only ...
0
votes
2answers
79 views

Convex function, sets and which of the following are true? (NBHM-$2014$)

Let $f:]a,b[ \to\Bbb R$ be a given function. Which of the following statements are true? a. If $f$ is convex in $]a,b[$, then the set $\tau=\{(x,y) \in\Bbb R^2| x\in ]a,b[, y\ge f(x)\}$ is a convex ...
2
votes
0answers
70 views

Convexity of composition of multi-dimensional functions

I am trying to determine the convexity of a composition of functions, $c$, defined as, $c(x) = f(g(x),h(x))$ where $f:\mathbb{R}^2\to\mathbb{R}$, $g,h:\mathbb{R}^n\to\mathbb{R}$, and ...
2
votes
1answer
100 views

How can the sum of two closed cones be not closed?

Can there be two closed cones $K_1$ and $K_2$ in $\mathbb{R}^3$ such that $K_1+K_2$ need not be closed?
0
votes
1answer
18 views

Conic hull of a proper function

Suppose $f$ is a proper function pn $\mathbb{R}^{n}$with $f(0)>0$.Now consider $$ g(x) = \text{inf}\{t: (t,x) \in \text{cl(cone(epi(}f)))\} $$ Can I always say that $\exists y \in \mathbb{R}^{n} : ...
0
votes
1answer
146 views

Intersection of strictly monotone, convex functions on interval with two given intersections

Given two functions $f,g:[0,1]\rightarrow[0,1]$ that are smooth, strictly convex, strictly monotone s.t. $f(1)=g(1)=0$, $g(0)=f(0)=1$ and $f(x_0)>g(x_0)$ holds for some point $x_0$, does it follow ...
5
votes
4answers
125 views

Why is the projection of a closed polytope closed?

In general, projection of a closed set into a subspace does not result in a closed set. However, I was able to prove that in $\mathbb{R}^n$, the projection of a closed polytope (intersection of ...
3
votes
1answer
245 views

Algebraic Proof that a Disk is Convex

After searching on Google for a while, I cannot seem to find an algebraic proof that a disk is a convex set. Intuitively, this seems obvious: if you take any two points $x, y$ in a disk, then the line ...
0
votes
1answer
21 views

Problem with convex function

In Papadimitriou book I found a problem. If I know that function $f$ is a convex function, and I have values $x_2,...,x_n$, is function $g(x_1) = f(x_1,x_2,...,x_n)$ also a convex function? I know ...
2
votes
1answer
700 views

How to formally prove that f(x,y) is jointly convex if f(x,y)=h(g(x,y))?

I know that this function should be concave, I am working on the Hessian proof but I would rather use this property. I know that h(a) is convex and decreasing in a, and g(x,y) is linear, ...
1
vote
1answer
61 views

Invariant convex subset

Let X be a banach space and $T$ a bounded operator on X with $||T||$ less than or equal to 1. If $T$ is an isometry and $r(T)$<1 show that there is a closed convex non-zero proper subset $C$ of the ...
1
vote
3answers
1k views

How to prove that $e^x$ is convex? [closed]

I need a help with proving of $e^x$ function. We know $e^x$ is a convex function. $$f(c(x')+(1-c)(x'')) ≤ c\cdot f(x')+(1-c)\cdot f(x''), \quad 0 ≤ c ≤ 1$$ Thanks.
1
vote
1answer
163 views

Why the cone generated by a closed convex set containing the origin may not be closed?

I encounter this problem in the proof of Theorem $1.28$, page 21, Skiadas' Asset Pricing Theory. $X$ is a constrained market which is defined to be a closed convex subset of $\Bbb R^{K+1}$, $C = \{kx ...
0
votes
0answers
106 views

KKT conditions for nonsmooth convex problems

What are the KKT conditions for a non-smooth convex function? Is the vanishing gradient of Lagrangian, replaced by $0$ in sub-differential of the Lagrangian, and all other things remain the same? I ...
1
vote
1answer
64 views

Sets defined by distance to a convex set

Let $Y \subset \mathbb R^n$ be a bounded convex set, let $R>0$, and let $$Z := \left\{z \in \mathbb R^n : d(z,Y) > \dfrac12R \right\}$$ where $$ d(z,Y) = \inf_{y\in Y}|y-z|. $$ If you like, ...
0
votes
1answer
41 views

Lipschitz in $\mathbb R^1$ implies Lipschitz along any line in $\mathbb R^k$ (for convex functions)

I'm trying to solve a homework problem (baby rudin course) and realized that Lipschitz continuity really makes the problem easier for me. However, since it is not defined in Rudin I have to prove the ...
13
votes
1answer
317 views

A beautiful inequality for convex functions

Let $f\in \mathcal{C}([0,1],\mathbb R_+)$ increasing. Prove that there exist $g,h\in \mathcal{C}([0,1],\mathbb R)$, convexs, such that $g\leqslant f \leqslant h$ and : $$\displaystyle ...
1
vote
1answer
122 views

Level set of convex functions

Let $f:\mathbb R^n \to\mathbb R \cup\{+\infty\}$ be a proper convex function, assume that there exists $c\in\mathbb R$ such that the $c$-level set $L_{\leq c}=\{x\in R^n: f(x)\leq c\}$ is nonempty and ...
1
vote
0answers
35 views

Generalisation of circumscribed circle for polygones instead of triangles.

Given a triangle, there exists a unique circle passing through its $3$ vertices. I wonder if more generally for any $n\geq3$ we can define a family $\mathcal{C}_n$ of convex closed curves in the ...
0
votes
1answer
92 views

Explain the convexity by looking the hessian matrix of a function

The hessian matrix of a function is given by, $$ H = \begin{bmatrix} a & b & c \\[0.3em] b & b & 0\\[0.3em] c & 0 & c \end{bmatrix} $$ where, ...
4
votes
3answers
233 views

Proving the Obvious

Is it normal that I have the hardest time when I'm trying to prove statements that are blatantly obvious on a visual and/or intuitive level? For instance, how does one go about formally proving the ...
1
vote
1answer
46 views

A characterization of convexity for functions with vectors as domain.

Let $f:\mathbb R^n \rightarrow \mathbb R$ be a continuously differentiable function. By $df(w)$ I denote the Frechet derivative of $f$ at $w$ Prove that $$f \:\text{is convex} \Leftrightarrow ...
1
vote
0answers
69 views

Monotonically increasing maximum eigenvalue

Let a matrix $A \in \mathbb{R}^{n \times n}$ be the convex combination of two matrices as $A = qB + (1-q)C$. Define $B$ as unit anti-diagonal. Define $C_{i,j} = \delta_{i,i+1}$. Consider $A$ for ...
1
vote
1answer
37 views

Computation of convex conjugate

I am learning convex analysis by myself and I need help. How to show that if $X=U=\mathbb{R}$ and $f\left(x\right)=\frac{|x|^{p}}{p}$ then the convex conjugate ...
0
votes
0answers
52 views

How to handle concave-concave constraints?

there. I have an optimization problem, which takes the following form ...
1
vote
1answer
323 views

Proof of the Moreau decomposition property of proximal operators?

Given the prox operator i.e. $ prox_h (x) = arg min_u (h(u) + 1/2 ||u-x||^2_2) $ the Moreau decomposition property says that $ x = prox_h (x) + prox_{h^*} (x) $ where $h^*$ is the conjugate of ...
0
votes
1answer
39 views

Express a function as difference of convex functions (DC)

is there a way to express the function $$1-\exp \Big( \frac{-\max(0,x)^2}{\alpha} \Big)$$ as the difference of two convex functions (DC)? Thanks
3
votes
3answers
958 views

convexity of inverse function

I have a question on the reverse of a convex function. Let $f(x)$ be a convex function. Is the reverse function, say $g(x)=f(x)^{-1}$, is necessarily a concave function ? Considering that such ...
5
votes
1answer
121 views

Inequality related with concave property

Assume that $f>0,f'<0$ and $f$ is logconcave(the log of $f$ is concave) and twice differentiable. Can we prove, or give a counter example to the following claim: there exists $\bar x>0$ such ...
1
vote
0answers
48 views

Does Jensen's inequality become stricter with respect to the right boundary point?

Let $f(x)>0$ for all $t\in %TCIMACRO{\U{211d} }% %BeginExpansion \mathbb{R} %EndExpansion $ be a density. I will truncate the density to the finite interval $[a,b]$ and will eventually be taking ...
1
vote
0answers
27 views

Uniqueness of a convex linear decomposition

Let $X$ be composed of $d$ different vectors of $\mathbb{R}^n$ : $X=\{x_1,\ldots,x_d\}$ and $H$ be the convex hull of $X$. Each vector $y\in H$ can be expressed as $$y=\sum_{i=1}^d a_i x_i,$$ with ...
0
votes
1answer
90 views

Relax equality into inequality in convex problem

Let $\mathbf{x}, \mathbf{z}, \underline{\mathbf{x}}, \overline{\mathbf{x}} \in \mathbb{R}^{I}$, where the first two are variables and the last two are given data. I have the following problem: ...
0
votes
2answers
56 views

Convexity of support function

Let $C$ be a closed non-empty set, but not necessarily convex. The support function of $C$ is given by $$S(z) = \sup_{c \in C} \langle z,c\rangle. $$ Prove that this is a convex function. ...
1
vote
1answer
46 views

Minimizing difference and individual variables in convex problem

Let's say I have the following optimization problem: $$ \begin{align*} \min_{\mathbf{x},\mathbf{y}} & \sum_i x_i-y_i \\ \mathrm{s.t.} & \{\mathbf{x},\mathbf{y}\} \in ...
0
votes
1answer
37 views

Prove that the intersection of convex sets is convex using the following three points…

I want to prove each point, then, use points (1) and (2) to prove (3). $C_{1} = \lbrace x \in \mathbb{R}^{n} \mid h(x) = 0 \rbrace $ is convex iff $h(x)$ is affine in $C_{1}$ $C_{2} = \lbrace x ...
0
votes
1answer
171 views

Matlab - Generate square convex function with positive definite Hessian Matrix

So, I have to generate a square convex function in Matlab and it's Hessian Matrix must be positive definite but I can't find any function that can help me do that. Is there anything I should search ...
1
vote
2answers
362 views

Why is this weighted least squares cost function a function of weights?

Here is a picture from my book regarding weighted least squares: Totally lost here, so I extracted the main nested issues confusing me: First Question: I know that in any LSE we want to minimize ...
0
votes
1answer
125 views

Largest eigenvalue of symmetric matrix

I am trying to understand why the $\lambda_{\max}$ function is convex given an $n\,x\,n$ symmetric matrix, let's call it $A$. I know from elementary property of eigenvalues that all the eigenvalues of ...
1
vote
1answer
37 views

Polytope - Convex Hull

After doing some reading on the V-representation of a convex polytope (finite set of extreme points, also the convex hull?), it's often simply stated that the convex hull is compact. Can anyone show ...
2
votes
1answer
89 views

“Support function of a set” and supremum question.

I have already learned about what a supremum means from wikipedia and from another answer here. However I am not quite sure what 'supremum over a set of functions' means exactly. As an example, my ...
1
vote
1answer
67 views

Caratheodorys lemma proof

I have to proof caratheodorys lemma for my oral exam. The proof is given here. I dont get the last part. "This process can be repeated until x is represented as a convex combination of at most d + 1 ...
0
votes
2answers
70 views

Inequality involving max is confusing me.

I am trying to understand one line in a derivation here. Simply put, the statement is that: $$ max\{\theta \ f_1(x) + (1-\theta) \ f_1(y) \ , \ \theta \ f_2(x) + (1-\theta) \ f_2(y)\} \leq \theta \ ...