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
33 views

is $R^N_{ ++}$ a convex set?

Is $R^N_{ ++}$ a convex set? I'm working on some optimization hw problems that have some functions of the type: $f:\mathbb{R}^2_{++} \rightarrow \mathbb{R}$ And it seems like in general whenever ...
0
votes
0answers
68 views

when does the Minkowski inequality for infinity norm become equality

I have two vectors $x, y \in \mathbb{R}^d$, it is well known as Minkowski inequality that: $|x+y|_\infty \leq |x|_\infty + |y|_\infty$, where $|x|_\infty= \underset{i=1..d}{\max} |x_i|$ with $x = ...
1
vote
1answer
215 views

Show convex combination

If I have a bounded set $F$ in $N$ dimensional space and another set $G$ where every element $g$ in $G$ has $h'g=c$ and also must exist in $F$. $H$ is a vector in the $N$ dimensional space and $c$ is ...
0
votes
1answer
40 views

$C^2$ approximation of a convex set with a “flat part”

Suppose we have a closed, bounded, convex set $K \subset \mathbb{R}^n$ with non-empty interior. It's well-known that we can approximate $K$ either from the inside or from the outside in the Hausdorff ...
0
votes
2answers
38 views

When is the difference of two convex functions convex?

Assume that $X$ is a finite dimensional Banach space. I know that in general if two functions $f:X \mapsto \mathbb{R}$, $g:X \mapsto \mathbb{R}$ are convex then the function $(f-g):X \mapsto ...
0
votes
1answer
64 views

Prove that convex function on $[a,b]$ is absolutely continuous

In the book Roberts, Varberg, Convex functions, on pp.9-10 is proved that If $f:(a,b)\rightarrow \mathbb R$ is continuous and convex then $f$ is absolutely continuous on each $[c,d]\subset ...
1
vote
1answer
25 views

Why should the points that define a simplex be affinely independent?

I have a question regarding the definition of a simplex. I am quoting the definition of a simplex from Wikipedia, which is similar to the definition in my textbook too "Specifically, a $k$-simplex is ...
0
votes
1answer
43 views

The definition of convex body and the Hilbert cube

I currently have a question about the definition of convex body. The formal definition is: a convex body is a convex set which has non-empty interior. By non-empty interior, we meant for a set ...
0
votes
1answer
45 views

Algorithm - the longest chord whose supporting line contains a given point, in a convex polygon

"Let $P$ be a convex $n$-gon and $q$ a point in the plane. Find an algorithm to compute the longest chord whose supporting line contains q." When $q$ is external to $P$, I think I can prove the ...
2
votes
1answer
66 views

Compact set and its extreme points

I am reading Chapter 3: Convexity of Rudin's "Functional Analysis". Here is the problem I'm having trouble solving (number 18): Let $K$ be the smallest convex set in $\mathbb{ R}^3$ that contains ...
3
votes
1answer
52 views

algorithm to find closest point in a convex polygon from an external point

Given a convex polygon $P$, and a point $q$ of the plane, external to $P$, what is the fastest algorithm to compute the closest point in $P$ to $q$. A linear algorithm of course works, computing the ...
1
vote
2answers
38 views

algorthm to find a farthest point in a convex polygon to an external point

Given a point $q$ external to a convex polygon $P$, propose an algorithm to compute a farthest point in $P$ to $q$. One can always have at least one vertex of $P$ in the set of farthest points of $P$ ...
2
votes
0answers
41 views

Isometric isomorphism maps extreme points to extreme points

I am trying to prove that $\mathcal{c}$ and $\mathcal{c_0}$ are isomorphic but not isometrically isomorphic. I've read on this forum that isometric isomorphism preserves extreme points, but I don't ...
0
votes
0answers
27 views

Book/Papers for properties of convex/ uniformly convex Banach Spaces

I am looking for reference books and research articles which cover analysis of uniformly convex and strictly convex Banach spaces.
0
votes
0answers
23 views

Prove a complex function to be convex

I have a function and want to prove that it is convex when $0 \leq x \leq 1$: \begin{equation} f(x)=\frac{b1g'(x) f_1(x)^{n-2}+g'(1) \gamma}{g'(1) ( \gamma+b1) } \end{equation} and \begin{equation} ...
1
vote
0answers
65 views

Minimum distance from a subspace in a Banach space

$X,Y,Z$ are disjoint sets of vectors in a Banach space M. $S_X,S_Y,S_Z$ denotes the subspace formed by the vectors in $X, Y$ and $Z$ respectively. $S_{YZ}$ and $S_{XZ}$ denote the subspaces formed by ...
0
votes
1answer
44 views

Question about the structure of a convex optimization problem

I am reading a tutorial about Convex Optimization and it defines the general Convex Optimization problem as: $$ minimize_x f(x)$$ where $g_1(x) \leq 0, ... , g_m(x) \leq 0$ and $Ax=b$ and $x \in ...
2
votes
2answers
56 views

Is $[u_1,u_2]$ an edge of the polytope $conv(F)$?

Here's the problem. I have a finite set of vectors $F \subset \mathbb{Z}_{\geq 0}^d$. I define $P$ to be the convex polytope $conv(F)$ i.e. the convex hull of $F$. Given $u_1, u_2 \in F$, is the ...
1
vote
3answers
49 views

How to check the function is convex or not?

How one can check the function whether it is convex or not. I know one method by using Hessian Matrix but I think it did not fit for the following example. I think Hessian matrix method cannot be ...
0
votes
0answers
39 views

Cyclical monotonicity

I am deeply troubled by a question for the homework. Either prove or a give a conter-example to the following claim: A continuously differentiable function $f:\mathbb{R}^l\to\mathbb{R}^l$ is ...
1
vote
1answer
61 views

Onion-peeling in O(n^2) time

I am working on the Onion-peeling problem, which is: given a number of points, return the amount of onion peels. For example, the one below has 5 onion peels. At a high level pseudo-code, it is ...
3
votes
1answer
97 views
0
votes
0answers
17 views

Convex hypograph implies convex level sets. Is this proof complete and correct?

I want to show that when the hypograph of a function is convex, then the upper level sets are convex too. By definition, a pair $(x, a)$ belongs to the hypograph $H$ if $f(x)\geq a$. Let's suppose ...
0
votes
0answers
24 views

Hyperplane optimization for Support Vector Machines

I am trying to learn about the theory behind the Support Vector Machines, by reading the tutorial at: http://research.microsoft.com/pubs/67119/svmtutorial.pdf In its most basic form, SVMs is a binary ...
5
votes
2answers
243 views

What is the smallest possible angle of this polygon?

A convex polygon contains a square with side-length 1 and is contained in a parallel square with side-length 2 (which is its smallest containing square). What is the smallest possible angle of the ...
3
votes
1answer
397 views

Differentiability of Moreau-Yosida approximation.

I want to show that if $X$ is a reflexive Banach space with norm of class $\mathcal{C}^1$ and $f\colon X\to\mathbb{R}\cup \{+\infty\}$ is convex and lower semicontinuous, then $f_{\lambda}$ is ...
0
votes
1answer
47 views

Sufficient condition for global maximum of strictly quasi-concave functions (unconstrained)?

Suppose $f(x)$ is a function from $\mathbb{R}$ to $\mathbb{R}$ and $f$ is strictly quasi-concave. If $x^*$ is a point such that $f'(x^*)=0$, then can we say that $x^*$ is a global maximum of this ...
4
votes
1answer
62 views

A convex function is differentiable at all but countably many points

Let $f:\Bbb R\to\Bbb R$ be a convex function. Then $f$ is differentiable at all but countably many points. It is clear that a convex function can be non-differentiable at countably many points, ...
0
votes
0answers
20 views

Differentiability of Moreau-Yosida Regularization? [duplicate]

I'm looking for a proof of the differentiability of the Moreau-Yosida regularization of a proper closed convex function $f(y)$ defined on an n-dimensional Banach space $Y$. namely the function is ...
0
votes
1answer
34 views

Is the closure of a geodesically convex set convex?

My question is Is the closure of a geodesically convex set convex? If so, is there a simple proof for it? In $ R^n $ there is a simple proof for it through convergent sequences. How should I apply ...
0
votes
1answer
66 views

What are the formulas for the number of vertices, edges, faces, cells, 4-faces, …, $n$-faces, of convex regular polytopes in $n \geq 5$ dimensions?

I know that in dimension $n \geq 5$ there are only 3 kind of convex regular polytopes in each dimension: the $n$-simplex, the $n$-cube and the $n$-orthoplex. I would like to know if there are ...
2
votes
2answers
56 views

Quasiconcavity of incomplete gaussian integral

From visual experiments , it appears that the set $$ S_r = \left\{ (x,y) \text{ s.t. } \int_x^y e^{-t^2} dt \geq r \right\} $$ is convex for $r \geq 0$. Or equivalently, the function $$ f(x,y) = ...
0
votes
1answer
24 views

Convexity of an exponential function

I failed the following question in a quiz: For which values of $a$ the function $e^{-a\sqrt(x)}$ with $dom = \mathbb{R}^+$ is convex? Check all that apply: $a\leq0$ $a\geq0$ $-1 \leq a\leq1$ ...
0
votes
1answer
33 views

Convex Sets Pre-image

I am struggling with the following question: Let $a \in \mathbb{R}^n $ and $ b \in \mathbb{R}$ and define $ f: \mathbb{R}^n \rightarrow$ $\mathbb{R} $ by $f(x) = \langle x,a \rangle + b, x \in ...
0
votes
1answer
26 views

what does full- dimensional means when speaking about covex cones

I want to know the exact definition of full-dimensional. And what does "dimension" refer to, is that in the sense of algebraic variety? I have read several writing announcing that the cone of ...
0
votes
1answer
32 views

Proofing set to be convex

I am struggling solving the following exercise: Let $a \in \mathbb{R}^n$ and $ b \in \mathbb{R}$ and define $f : \mathbb{R}^n \rightarrow \mathbb{R}$ by $f (x)=\langle x,a \rangle + b, x\in ...
1
vote
1answer
48 views

Example of a convex set whose closure is not convex?

An enumeration $ν\colon ℕ → A$ of the rationals $A$ in $(0..1)$ yields an open set $U_ν = \bigcup_{k ∈ ℕ} B_{1/4^k}(ν(k))$, containing all of $A$. You can choose $ν$ such that $U_ν ⊂ (0..1)$ (by using ...
1
vote
1answer
30 views

Compactness, Convexity, Convex Hull of Sets including sequences

Is the following set compact, is it convex and what is the convex hull? $V = \{(x_1, x_2,...,x_n) \in \mathbb{R}^n :\frac{1}{1 + i} \leq x_i \leq \frac{1}{i}, i=1,2,...,n\}$ My thoughts: I was ...
1
vote
1answer
47 views

Consider the problem minimize $f(x_1,x_2) = (x_2 −x_1^2)(x_2 −2x_1^2)$

(i) Show that the first- and second-order necessary conditions for optimality are satisfied at $(0,0)^T$. (ii) Show that the origin is a local minimizer of f along any line passing through the origin ...
1
vote
2answers
136 views

Is every convex function on an open interval continuous?

Let $f:(a,b)\rightarrow \mathbb{R}$. $f$ satisfied the following property: If $\forall x_{1},x_{0},x_{2}\in(a,b)$ and $x_{1}<x_{0}<x_{2};$then$\frac{f(x_{0})-f(x_{1})}{x_{0}-x_{1}}\geq ...
2
votes
3answers
168 views

Why doesn't the definition of the interior of a set depend on the dimension of the set

I have just started with a course on convex optimization and have been introduced to the concept of the interior of a set. I have a fairly basic question. I am still trying to understand this topic, ...
1
vote
1answer
43 views

Dual of concave function is convex

If $U(x)$ is strictly increasing and strictly concave and $lim_{x \rightarrow \infty}$ U'(x) = 0, prove that its dual: $$U^{*}(y) = max_x \{U(x) - xy\}$$ is convex. Does anyone know how to prove ...
0
votes
1answer
290 views

Convex n- sided polygon proof writing (homework question)

Would anyone be able to help me with the following problem or give me a push in the right direction? I am not entirely sure where to start and I have been looking at this problem for hours... Any help ...
1
vote
0answers
19 views

On Convex Interpolation and distances

Let $C$ denote the class of all real-valued convex functions on $[0, 1]^2$. Fix $n \geq 2$ and points $x_1, \dots, x_n$ in $[0, 1]^2$. Let $S \subset R^n$ be defined by \begin{equation*} S := ...
0
votes
0answers
22 views

A Difficult combinatorial optimization problem

Let $\mathcal{J}$ be a closed, bounded, compact, convex set in $\mathbb{R}^L$. (Notations: vector $\mathbf{x}$ is denoted in bold letters and its $i^{th}$ co-ordinate is denoted as $x_i$. ...
0
votes
0answers
86 views

weights go to infinity in logistic regression with linearly separable data

I have the loss function of logistic regression $L(W)$ = - $\sum_{i=1}^n {y_i}.log[\sigma(w^Tx)] + {(1-y_i)}.log[1- \sigma(w^Tx)]$ I have derived the Hessian and proven it's positive semi-definite ...
0
votes
0answers
16 views

Eliminating variables in convex program

This is a basic convex optimisation question. I have the following problem: $$\max_{\substack{t\le e\\ At\le b}} e^\top t$$ How do I find the optimum $t^*$? I write the KKT conditions, get ...
2
votes
1answer
24 views

Showing the multivariate normal is log-concave?

I'm trying to show that $\log p(x) = -\frac{1}{2}(x-\mu)^{T} \Sigma^{-1}(x-\mu)$ is concave. How would I go about this in $\mathbb{R}^n$? I've tried taking derivatives but I'm getting stuck once I get ...
0
votes
1answer
62 views

Show that this function is convex?

So I'm supposed to show that this function is convex, but I have no idea how to go about it...I've been told to use Cauchy Schwarz in order to show that the Hessian is non-negative definite, but I'm ...
0
votes
0answers
7 views

Verification of the Approach to a given non-convex integer programming problem

I need to verify my approach to a non-convex integer programming problem. It would be interesting to see other approaches as well. Let $\mathbf{C}_1,\dots,\mathbf{C}_R$ be $N\times N$ hermitian ...