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)

0
votes
1answer
31 views

Why does convexity of a function required the following

What is the significance of the following condition $$\forall x_1, x_2 \in dom(f) , \forall \theta \in [0, 1], f(\theta x - (1-\theta)y) \leq \theta f(x) + (1-\theta)f(y)$$ and why isn't the ...
0
votes
2answers
207 views

Dual of a Semi Definite Programming Problem

How do I write the dual of the following semi definite programming problem? \begin{align} \max_{\lambda,y_i}~&\lambda \\ &\sum_{i=1}^{L}y_i\mathbf{C}_i-\lambda\mathbf{I}\geq 0 \\ ...
2
votes
1answer
51 views

Let $f: [a,b] \rightarrow R$ be convex. If f is not constant, then the supremum of $f$ is not inside of [a,b].

I could use some help with this proof. Let $a,b \in \mathbb{R}, \ a<b \ \ f: [a,b] \rightarrow \mathbb{R}$ be convex. Prove: If f is not constant, then the point, where the supremum of ...
2
votes
2answers
164 views

Convexity / Concavity --> Formal Definition

How do I show that $f(x, y)=(x + y)^2$ is convex/concave using the formal definition of convexity/concavity?
0
votes
0answers
55 views

Is continuity preserved under Max operator and Euclidean norm?

Suppose that the functions $f_i: \mathbb{R}^k \rightarrow \mathbb{R}$ are all continuous over $\mathbb{R}^k$ for $i=1,...,k$. Is the function $$ g(x)=\|\max\{0,f_1(x)\},...,\max\{0,f_k(x)\}\|^2 $$ ...
2
votes
0answers
37 views

Complexity of finding extremal rays

Suppose that $\{L_i\}$ is a collection of $k$ linear forms on $\mathbf R^n$. Let $$C=\{x \in \mathbf R^n : L_i \cdot x \geq 0 \text { for all } i \}$$ be the closed convex cone defined by the ...
1
vote
1answer
70 views

Convex Sets and extreme supports

Let the set $S$ in $R^n$ consists of the origin $0$ and $n$ lineary independent vectors $T_1, \ldots, T_n$. Show that $C(S)$, the convex hull of of $S$, is the intersection of its extreme supports, ...
1
vote
1answer
93 views

Tangent cone of graph and epigraph sets.

Let us first recall the definition of tangent cone $\; T(\bar x; \Omega)$ of a subset $\Omega$ at $\bar x \in \Omega$, where $X$ is a Banach space: $$T(\bar x; \Omega)=\{v\in X:\; \; \exists ...
0
votes
0answers
158 views

Exact Line Search in Projected Gradient Descent

How is exact line search adapted for projected gradient descent in convex optimization? One way I think of is that unconstrained exact line search is run, and the new point is projected into the ...
0
votes
2answers
36 views

Relation between sum of a max and max of a sum?

Consider $\frac{1}{T}\sum_{t=1}^{T}\max\{ 0,a_t\}$. Can we say whether this is greater or equal then $\max\{ 0,\frac{1}{T}\sum_{t=1}^{T}a_t\}$?
1
vote
1answer
97 views

The closednees in Moreau - Rockafellar Theorem.

One says that $x\mapsto \langle x^*,x\rangle +\alpha\;$ is an affine minorant of $f: \; X\to \overline{\mathbb R}\;$ if $\;\langle x^*,x\rangle +\alpha \leq f(x)\;$ for all $x\in X$. The Moreau - ...
2
votes
2answers
221 views

straightforward way to determine if this set is convex?

straightforward way to determine if this set is convex? $Z=\left\{x\in\mathbb{R}^2:3x_1^4-x_1x_2+x_2^4\le x_2,x_1>2,x_2>2\right\}$ I know I can try by manipulation of linear combination of two ...
2
votes
0answers
131 views

Show that the graph of a convex function is above any tangent plane

In proving jensen inequality one use that the graph of a convex function is above any tangent plane. I've been reading Property of convex functions and Tangent line of a convex function. But what ...
0
votes
1answer
59 views

Volume of unit n-dimensional ball, definite integal

As a part of an assignment to calculate the volume of unit n-dimensional ball I got to the following expression, which I believe is true: ...
0
votes
1answer
143 views

Computing subgradients, a basic example.

A vector $v \in \mathbb{R}^n$ is a subgradient of a convex function at $x$ if $$f(y) \geq f(x) + <v, y - x>$$ for all $y \in dom(f).$ The set of all sub gradients is known as the sub ...
0
votes
0answers
109 views

Linear transformation preserving strict convexity

Consider the functions $f:\mathbb{R}^n\to\mathbb{R}$, $g:\mathbb{R}^m\to\mathbb{R}$ and the non-square matrix $A \in \mathbb{R}^{m\times n}$ with $m>n$. Let $x\in\mathbb{R}^n$ and consider the ...
2
votes
1answer
101 views

Sums of convex functions strictly convex in one variable

Let $f_i:\mathbb{R}^n\to\mathbb{R}$, $i=1,2,\ldots,n$ be twice continuously differentiable, convex functions in $x = (x_1,x_2,\ldots,x_n)$. Let each $f_i$ be strictly convex in $x_i$. Is the function ...
0
votes
1answer
100 views

A Simple Algorithm for Imposing Semi-definite Constraints

What is the simplest algorithm to implement, to impose semi-definite constraints? $\min_{X\succeq 0} f(X) $, where $X$ is an $n \times n$ symmetric matrix, and $f$ is a general smooth convex ...
0
votes
1answer
143 views

L1 ball contained in convex hull of L0 ball

Consider the set $S$: the set of vectors whose $L^0$ pseudo-norm is upper bounded by $s$. Also, consider the $L^1$ ball of radius $\sqrt{s}$. It is apparently a well known fact that the $L^1$ ball is ...
2
votes
1answer
63 views

Distance of convex combination of pairs of points in $\mathbb{R}^n$

Given 4 points $w,x,y,z \in \mathbb{R}^n$ define for $t\in [0,1]$ $f(t)=d(wt + (1-t)x, yt + (1-t)z)$. Is this function convex? I have found a proof by differentiating twice and calculating a lot but ...
0
votes
1answer
459 views

Convexity definition confusion

When one writes $$f(\lambda x + (1-\lambda)y) \le \lambda f(x) + (1-\lambda)f(y)$$ for $x,y\in \mathbb{R}^n$, $\lambda\in(0,1)$ what does this mean? 1) Does it mean that the function is jointly ...
0
votes
0answers
90 views

Creating a $C^2$ smooth convex curve which joins circular arcs

Suppose that I have many points $p_1$,..., $p_n$, all very close to origin 0. For R very, very large, I have circular arcs of radius R, $\alpha_i$, about $p_i$. I do not speak about their ...
1
vote
1answer
47 views

Impact of constraints on convex optimization

Let me start by saying I know almost nothing about optimization so please bear with me. Basically, I am wondering whether it is possible to solve a problem with two constraints by solving the problem ...
0
votes
1answer
145 views

Is this function strictly convex?

I think this function is strictly convex in the vector ${\bf x} = (x_1,x_2,x_3,x_4)$ but the fact that some terms are zero when variables take on the same values leaves me uncertain, i.e. when ...
0
votes
2answers
62 views

Question on convexity

If I have a function $f:\mathbb{R}^n\to\mathbb{R}$ that is convex in ${\bf x} = (x_1,x_2,\ldots,x_n)$ and strictly convex in one of the variables, say $x_1$, then is $f({\bf x})$ strictly convex in ...
0
votes
1answer
23 views

Continuity of convex functions at point out of domain

I have been studying the continuity of a convex function and having a trouble below: In some books, the authors defined the the continuity of a convex function $f$ even $f$ is not in $\mbox{dom }f$, ...
1
vote
1answer
25 views

Properties that guarantee quasiconvexity in $\mathbb{R}^n$

I have an open bounded connected domain $\Omega \subseteq \mathbb{R}^n$ and I would like to say that for every two $x,y \in \Omega$ there is a path $\gamma$ from $x$ to $y$ of length at most $C|x-y|$ ...
7
votes
7answers
6k views

Operations research book to start with

for somebody having a quite strong background in Mathematics, which are some good books for the domain of Operations research? I guess there are textbooks covering topics like linear and nonlinear ...
0
votes
1answer
25 views

A Q about convex optimality criterion

Hope to ask about p. 139 of S. Boyd's cvx book: x is optimal iff x is in X (feasible set) and And the book use the following pic to illustrate: My Q is: why there is a negative sign '-' in ...
0
votes
1answer
142 views

Integral of increasing continuous function is convex

Suppose $g$ is increasing and continuous. Does it follow that $G(x) = \int_0^xg(y)dy$ is convex? Clearly $G'$ is increasing and continuous, and $G''\geq 0$ exists a.e., but I don't see how this ...
0
votes
1answer
34 views

Partial Ordering of proper cone K

$K$ in $\mathbb{R}^n$, and $K$ is a proper cone. Partial Ordering of $K$ : $x \leq_K y$ iff $y-x\in K$ (S. Boyd p. 43) My questions are: Does it require $x,y\in K$? If $x,y\in K$, it seems ...
0
votes
1answer
54 views

A Q about S.Boyd's CVX book p. 107

A Q about the following: (Come from S.Boyd's note) Note 1: y is a r.v with log-concave pdf "p(y)". My Qs are: What is the f(x) in the proof? It is marginal pdf or cdf or expected value? It ...
2
votes
2answers
1k views

Prove Convex Hull of Minkowski sum

I want to prove that the following holds, where the $+$ means Minkowski sum: $$ conv(A+B)=conv(A)+conv(B) $$ Let the convex hull of $A+B$ be $$ conv(A+B)=\sum_{j,k}\lambda_j\mu_k(a_j+b_k) $$ I ...
0
votes
1answer
71 views

Convex function that has a finite limit at infinity

Can someone give me an example for a convex function that has a finit limit at infinity ?
5
votes
1answer
163 views

A bounded subset in $\mathbb R^2$ which is “nowhere convex”?

Let $F : \mathbb S^1 \to \mathbb R^2$ represents a simple closed curve $C$ in $\mathbb R^2$. The Jordan curve theorem says that the curves bounds a interior domain $\Omega$ and $\partial \Omega= C$. ...
1
vote
0answers
60 views

Convexity of $\int f(\frac{dP}{dQ})dQ$ for some convex $f$

I want to prove the convexity of $\int f(\frac{dP}{dQ})dQ$ for some convex $f$ and here is what I've done so far: Since $f$ is convex, $f(\frac{dP}{dQ})$ is also convex w.r.t. $dP$ because $dQ$ ...
1
vote
2answers
47 views

A statement for convex sets

The following statement is true or false? Given a convex set $S$ then for any $y \in S$ and $\theta\in[0,1], \theta \in \mathbb R$ there exist $y_1,y_2 \in S, y_1 \ne y, y_2 \ne y$ such that ...
5
votes
4answers
147 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 ...
0
votes
1answer
59 views

Convex function almost surely differentiable.

If f: $\mathbb{R}^n \rightarrow \mathbb{R}$ is a convex function, i heard that f is almost everywhere differentiable. Is it true? I can't find a proof (n-dimentional). Thank you for any help
0
votes
1answer
152 views

Show homeomorphism between convex hull and unit ball?

In the proof of Schauder fixed point theorem in Evans' PDE book, he uses a claim that the convex hull $K$ of $N$ points $x_1,\dots,x_N$ in a convex compact subset $A$ of a Banach space $X$ is ...
4
votes
2answers
414 views

Volume of the projection of the unit cube on a hyperplane

Let $C_n\subset\mathbb{R}^n$ be the $n$-dimensional cube with side $1$, and let $P_k$ be any $k$-dimensional plane, $k\leq n$. What is the maximal $k$-volume $V_{n,k}$ of the projection of $C_n$ on ...
1
vote
1answer
52 views

Is $f(H)=H^TH$ convex? $H$ is a $m\times n$ matrix

I tried to prove $f(H)=H^TH$ convex, where $H$ is a matrix. We know when $h$ is a vector, then $f(h)=h^Th$ is convex. Can I prove it using the following equation? $[\theta H_1 + (1-\theta) ...
0
votes
2answers
31 views

Does one of these conditions for norms follow from the other?

The two conditions are: For all unit vectors $\mathbf{x}$ and $\mathbf{y}\hspace{-0.02 in}$, $\:$ if $\; \left|\left|\hspace{.03 in}\mathbf{x}\hspace{-0.05 in}+\hspace{-0.04 ...
1
vote
2answers
148 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 ...
1
vote
0answers
26 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
63 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
143 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 ...
0
votes
1answer
48 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
81 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
64 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 ...