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
2answers
29 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$ ...
3
votes
1answer
30 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 ...
2
votes
0answers
32 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 ...
2
votes
1answer
43 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 ...
0
votes
0answers
21 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.
1
vote
1answer
17 views

Verifying a production set is a convex cone

This comes from a paper that I am reading: For $i=1,2$, suppose that $F_i(\cdot,\cdot)$ satisfies the assumption: $F_i(K_i,L_i)$ is defined for all $K_i\geq 0$, $L_i\geq 0$. $F_i(0,0)=0$. ...
1
vote
0answers
18 views

Will continuous extension preserve strict convexity?

The problem I am thinking about is like follows. Suppose that $h$ is a strictly convex function on an open convex set $S$. Then, we extend $h$ continuously to the closure of $S$ that is denoted by ...
2
votes
1answer
46 views

Uniqueness of projection in a Banach space

Let $X$ be a Banach space, $M$ be a subspace of $X$ and $x \in X$ be any vector in $X$. Consider $\displaystyle \hat{x}_M=\arg \inf_{m\in M}\|x - m\|$. Under what conditions for $l_p$ norms $p = ...
0
votes
0answers
20 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
53 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
36 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 ...
0
votes
0answers
35 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 ...
2
votes
2answers
53 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
1answer
50 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
82 views

Computing convex hull of a bunch of circles

I am stuck on the following question ...
0
votes
0answers
11 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
17 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 ...
0
votes
1answer
36 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
1answer
29 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 ...
2
votes
1answer
27 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 ...
10
votes
0answers
259 views

Convexity of Matrix Exponential

Consider the function $A: \mathbb{R}^n \rightarrow \mathbb{R}^{n \times n}$ defined as $$ A( x ) := \left[ \begin{matrix} x_1 & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & x_2 & ...
0
votes
1answer
27 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
23 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
17 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
22 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
30 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
41 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
28 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
45 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 ...
0
votes
0answers
11 views

Expressing a convex set as an intersection of halfspaces

The question is as follows: Express the closed convex set {x $\epsilon$ $R^2_+$ | $x_1x_2$ >= 1} as an intersection of halfspaces. Here is what I have: $\bigcap$ {x $\epsilon$ $R^2_+$| $x^2$ >= 1} ...
-1
votes
1answer
29 views

Showing $\ln(1+e^x)$ is convex [closed]

I'd like to show that $\ln(1+e^x)$ is convex. Any help would be greatly appreciated!
2
votes
2answers
53 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) = ...
2
votes
3answers
167 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
2answers
91 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 ...
1
vote
1answer
42 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 ...
1
vote
0answers
17 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
21 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
14 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 ...
0
votes
0answers
67 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 ...
2
votes
1answer
20 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
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 ...
0
votes
1answer
58 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
14 views

Quasiconcave condition for a power function

Let $f(x, y)= (ax^2+by^2)^n$ where $a, b, n$ are positive, $x, y\in \mathbb{R}$. What is the condition of $n$ so that $f(x, y)$ is a quasiconcave, and concave function? My idea is only calculate ...
0
votes
1answer
254 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
2answers
38 views

How to prove that $H(S_1\cap S_2)\subset H(S_1) \cap H(S_2)$ and $H(S_1 \cup S_2) \supset H(S_1) \cup H(S_2)$

I'm studying convex analysis and my task is to prove the following inclusions: $S_1, S_2$ are non-empty sets in $\mathbb{R}^n$, and $H(S) $ defined as the convex hull of set $S$. Show that ...
0
votes
0answers
12 views

extension of semilinear functional in cone.

I'm studying Nigel Kalton's work in extrapolation Banach space theory (paper: Differentials of complex interpolation processes for Kothe function spaces). My question is: Let $T$ be a cone contained ...
0
votes
1answer
26 views

LP with a linear cost function $c^Tx$: Prove optimal value is $-\infty$ or there exist some $v \in P$ such that $c^Tv \le c^Tx$ for all $x \in P$

Suppose I have a LP with a linear cost function $c^Tx$, where $P=\{x \in \mathbb R^n : Ax \ge b\}$ is the polyhedron I want to minimize over. How do I see that either the problem is unbounded, that ...
2
votes
1answer
43 views

normal cone to sublevel set

I came across the following interesting and important result: Let $f$ be a proper convex function and $\bar{x}$ be an interior point of ${\rm dom} f$. Denote the sublevel set $\{x:f(x)\leq ...
0
votes
0answers
28 views

Let $P$ be a polyhedron. Prove, $P$ has at least one extreme point $\iff$ $P$ does not contain a line, by using a lemma.

Let $P$ be a polyhedron. Prove, $P$ has at least one extreme point $\iff$ $P$ does not contain a line, by using a lemma. I've a Lemma saying: Suppose $P=P(V,E)$ where $V,E \in \mathbb R^n$ are ...