Convex Optimization is a special case of mathematical optimization. It includes Linear Programming and least-squares.

learn more… | top users | synonyms

0
votes
1answer
44 views

Coerciveness of a function - help

I'm trying to show that $$f(x_1,x_2,x_3) = e^{x_1^2 + x_2^2} + (x_1^2 + x_2^2 + 3x_2)^{500}$$ is not coercive, but am struggling to see anything. Any help is appreciated!
1
vote
0answers
23 views

Convexity over a line given a convex interval [duplicate]

Let $f : \mathbb{R}^n \to \mathbb{R}_∞$ be a function. I want to prove that $f$ is convex over the line $L_{v,x_0}$ iff $\psi : \mathbb{R} \to \mathbb{R}_∞$ $\psi(t) := f (x_0 + tv)$, is convex ...
0
votes
0answers
11 views

Subsets being cones

I am trying to self-study convex optimization and still trying to get into the gist of it. There is a question in my text as follows: Let $V$ be the set of sequences whose terms are contained in ...
0
votes
1answer
22 views

Subdifferential is closed, convex and bounded

If $f: \mathbb{R}^n \to \mathbb{R} \cup \{+\infty\}$ is convex, how can I show that $\partial f(x_0)$ (sub differential) is closed and convex, and also bounded (bounded when f over the entire domain)
1
vote
2answers
40 views

Is the support function always unique for a convex set?

Given an arbitrary set $A ⊂ \mathbb{R}^n$ , the support function associated with the set $A$ $ σ_A : \mathbb{R}^n \to \mathbb{R} ∪ \{+\infty\}$ is defined as $\sigma_A(x):= \sup_{z \in A} \langle ...
1
vote
2answers
30 views

Showing coercivity of a function

I am well attuned to the definition for a function to be coerce, which is that $\lim_{\|x\| \to \infty}f(x) = \infty$ ie the values of $f$ go to infinity as the norm goes to infinity. So Ex.1 ...
1
vote
0answers
33 views

How to find a hyperplane

Let $A, B ⊂ \mathbb{R}^n$ be two nonempty sets such that $A ∩ B = ∅$. $H(A, B) := \{(w, d) ∈ \mathbb{R}^{n+1} : \sup_{x\in A} \langle w,x\rangle ≤ d ≤ \inf_{y \in B} \langle w, y\rangle \}$ How do I ...
1
vote
2answers
23 views

How to find ellipsoid bounding the intersection of an ellipsoid and half-space?

How does one prove that the bounding ellipsoid $E(A', a')$ of the intersection of an ellipsoid $E(A,a) = [ x | (x-a)^TA^{-1}(x-a) ]$ and half-space $H = [x | c^Tx \le c^Ta ]$ is given by the ...
2
votes
0answers
42 views

does this convex set have a specific name?

Let $x_1,\dots,x_N$ be points of $\mathbb{R}^n$. Define the following set: $\mathcal{A} = \left\{\sum_{j=1}^N a_j x_j : -1 \le a_j \le 1, \, \, \forall j=1,...,N\right\}$. It is an easy exercise to ...
0
votes
2answers
44 views

Uniqueness of constrained maximum

I have the following constrained maximisation problem $$\begin{array}{ll} \text{maximize}_{x,y,c,d} & q f(c) +(1-q) f(d) \\ \text{subject to} & x+y\leq 1 \\ & cq\leq y \\ & d ...
1
vote
1answer
18 views

Convexity of a subset is convex?

Let $V$ be the set of sequences whose terms are contained in $\mathbb{R}^n . V$ is the set of functions $x(·) : N → \mathbb{R}^n $ which we denote as $\{x_n\}_n \subset \mathbb{R}^n$. $V$ is a vector ...
1
vote
1answer
34 views

Support function of a set is convex

Given an arbitrary set $A ⊂ \mathbb{R}^n$ , the support function associated with the set $A$ $ σ_A : \mathbb{R}^n \to \mathbb{R} ∪ \{+\infty\}$ is defined as $\sigma_A(x):= \sup_{z \in A} \langle ...
1
vote
1answer
50 views

The set of separating hyperplanes is a convex cone

Let $A, B ⊂ \mathbb{R}^n$ be two nonempty sets such that $A ∩ B = ∅$. $H(A, B) := \{(w, d) ∈ \mathbb{R}^{n+1} : \sup_{x\in A} \langle w,x\rangle ≤ d ≤ \inf_{y \in B} \langle w, y\rangle \}$ I can't ...
0
votes
1answer
79 views

Show both relaxations of boolean LP give equal lower bounds

Given the boolean LP: $$\text{Minimize}\;\; c^Tx$$ $$\text{Subject to}\;\; Ax \leq b$$ $$\hspace{57mm} x_i(1-x_i)=0\;\; i=1,...,n$$ Show that the LP relaxation: $$\text{Minimize}\;\; c^Tx$$ ...
4
votes
1answer
48 views

When the closure of a convex set contains a ball

Suppose $C$ is a convex set in $\mathbb{R}^n$ whose closure contains the open ball $B(x,r)$. Is it true that $C$ contains $B(x,r)$? Motivation: I am asking this because something like this seems to ...
0
votes
0answers
21 views

Eliminating variables from an SOCP

Given an SOCP problem $$ \begin{array}{ll} \text{minimize}&w^Tx\\ \text{subject to} &\|A_i x + b_i\|_2 \le c_i^T x + d_i ~~~~~~~ 1 \le i < N\\ \end{array} $$ where $x$ is partitioned into ...
1
vote
1answer
34 views

Showing affinity of a function - proof help

Let $V$ be the set of sequences whose terms are contained in $\mathbb{R}^n . V$ is the set of functions $x(·) : N → \mathbb{R}^n $ which we denote as $\{x_n\}_n \subset \mathbb{R}^n$. $V$ is a vector ...
0
votes
0answers
35 views

Positive semidefiniteness of a matrix -to examine convexity- What mistake have I made?

$f(x) = \begin{cases} e^{x_1x_2} & x_1, x_2 \geq 0 \\ +\infty & otherwise \\ \end{cases}$ The Hessian of this matrix is: $H = \begin{pmatrix} x_2^2e^{x_1x_2} & ...
0
votes
1answer
30 views

strong convexity of loss function in multi-dimensional (high-dimensional) space

My question is based on this paper (see the last 10 rows in page 7). It seems this is a general claim: In machine learning or statistic, the loss function $l(W^TX, y)$ (a linear predictor) can never ...
1
vote
1answer
45 views

Help with this convex set proof

Take $C ⊂ \mathbb{R}^n$ a convex set. Fix $x_0 ∈ C$ and a nonzero vector $v ∈ \mathbb{R}^n$ . Define the set $I(x_0,v) := \{t ∈ R : x_0 + tv ∈ C \}$. Prove that $I_(x_0,v)$ is a convex subset of ...
1
vote
0answers
71 views

Showing convexity of a function with the restriction over an arbitrary line proof

Let $f : \mathbb{R}^n → \mathbb{R}_∞$ be a function and let $C ⊂ dom f$ be a convex set. $$**Part I**$$ Prove that $f$ is a convex function if and only if $f$ is convex over every line $L_{v,x_0}$ ...
2
votes
0answers
23 views

What decides the structure of the dual variables taken in designing min-max type combinatorial optimization algorithms?

There are a bunch of combinatorial optimization problems like min cost flows and min weight perfect matchings that invoke duality and complimentary slackness to improve the primal feasible solution. ...
0
votes
1answer
27 views

under what conditions the following matrix optimization has a unique solution?

So the problem is simple: Consider the following matrix optimization problem on matrix D. What conditions on the matrix dimensions should apply so that the solution to the minimum is unique. please ...
1
vote
1answer
66 views

infimum and supremum notation

I have stumbled across this blob of text when reading my textbook, and would like to know how to interpret it more intuitively. I understand the definitions of inf and sup, however not so much what ...
1
vote
0answers
66 views

Any example of strongly convex functions whose gradients are Lipschitz continuous in $\mathbb{R}^N$

Let $f:\mathbb{R}^N\to\mathbb{R}$ be strongly convex and its gradient is Lipschitz continuous, i.e., for some $l>0$ and $L>0$ we have $$f(y)\geq f(x)+\nabla f(x)^T(y-x)+\frac{l}{2}||y-x||^2,$$ ...
2
votes
1answer
60 views

Hessian Related convex optimization question

My precise question is from an exercise; Let $f : \mathbb{R}^2 → \mathbb{R}$ be a twice differentiable function. Prove that there exists a $λ ∈ R$ such that $g : \mathbb{R}^2 → \mathbb{R}$ defined as ...
0
votes
0answers
24 views

MD (Mirror Descent) over l_1 simplex lower bound proof

I'm looking for a proof of a lower bound of the Mirror Descent optimization algorithm over l_1 simplex. I am not asking to reproduce a proof here, but rather for a reference. I did go over the ...
0
votes
0answers
12 views

Showing that every extreme point of the set of solutions of the standard form of constraints of any L.p.p. is a basic feasible solution

Let $\vec y$ be an extreme point of the convex set of solutions of $A \vec x=\vec b $ where only the solutions of $\vec x(\in \mathbb R^n)$ with all components non-negative are taken ; then I want ...
2
votes
1answer
36 views

How to set up Lagrangian optimization with matrix constrains

Suppose we have a function $f: \mathbb{R} \to \mathbb{R} $ which we want to optimize subject to some constraint $g(x) \le c$ where $g:\mathbb{R} \to \mathbb{R} $ What we do is that we can set up a ...
1
vote
1answer
39 views

Showing the intersection/union of a cone is a cone

Defining a set $C \subset \mathbb{R}^n$ as a cone if for ever $x \in C$ and $\alpha \geq 0$ we have $\alpha x \in C$. ie they are closed under scalar multiplication. How can I show that the ...
1
vote
1answer
40 views

How can I show the following statements are equivalent?

Let $C ⊂ \mathbb{R}^n$ Prove that the following statements are equivalent. (i) $C$ is an affine set (ii) For every $x_0 ∈ C$ , the set $C − x_0 := \{ z − x_0: z ∈ C \}$ is a subspace. (iii) There ...
0
votes
1answer
20 views

Does optimal solution always occur at a vertex?

Is it true that if LP $ \text{max} \{c^Tx \ | \ Ax \leq b \}$ has an optimal solution, then $\exists$ a vertex which is simultaneously an optimal solution for LP? I know this works for LP of a ...
2
votes
0answers
33 views

Dual Decomposition with multiple coupling constraints

This is probably a a simple question, but have been stuck on this for a while and unable to figure out my issue from the standard Boyd/Vandhenbergen decomposition references. I am interested in dual ...
2
votes
2answers
48 views

Interpreting norm definition

Book: Convex Optimization (Author: Stephen Boyd), Appendix A, Topic: A.1.2 Norm,distance, and unit ball Can anyone please help me in understanding the following definition of "norm" $$ \| x \| ...
0
votes
0answers
34 views

LP in standard form

I don't know how to properly named this question but here it goes: Let $x, c \in \Bbb{R}^n$, $b \in\Bbb{R}^m$, $A \in \Bbb{R}^{m \times n}$. Consider LP in the form: min $\{c^tx : Ax = b, x \ge 0\}$ ...
0
votes
1answer
23 views

Proximal operators on Balls (Projection)

I was following this tutorial, In section 21 it is given Proximal operator over a ball $B_\epsilon$ of radius $\epsilon$ as $$\text{Proj}_{B_\epsilon(y)}(u) = y + (u-y) \max({1 , ...
1
vote
1answer
54 views

Showing convexity proof

Let $F: \mathbb{R}^n \rightarrow \mathbb{R}^m$ be an affine function, i.e., $F (x) = L(x) + b$, with $L : \mathbb{R}^n \rightarrow \mathbb{R}^m$ linear and $b \in \mathbb{R}^m$ Then for every convex ...
1
vote
0answers
14 views

Is epi(max(f,g)) the intersection of epi(f) and epi(g)?

On an exam, I found the question "is max($f(x),g(x))$" convex if $f,g$ are convex? This lead me to the question in the topic. Is the intersection of epi$(f)$ and epi$(g)$ = epi($\max(f,g)$)? If so, ...
0
votes
2answers
52 views

How to solve the function $\max \sum_{i=1}^n \log(x_i \cdot \mu)$ with $\sum _{j=1}^b \mu_j = 1$

$$ \max_{\mu} \sum_{i=1}^n \log(x_i \cdot \mu)\qquad\text{with}\qquad \sum _{j=1}^b \mu_j = 1,\qquad \mu_i \ge 0,\qquad x_{ij} \ge 0 $$ The function is shown as above, where $x_i$ and $\mu$ are ...
1
vote
0answers
49 views
+50

Is optimal solution to dual not unique if optimal solution to the primal is degenerate?

If optimal solution to the primal is degenerate, does it necessarily follow that optimal solution to dual not unique? That is, is uniqueness an unnecessary assumption? Spin-off from here. In my ...
0
votes
1answer
28 views

Dual part of complementary slackness

The proof of the complementary slackness of P: min $c^Tx $ @ $Ax = b, x \geq 0$ D: max $b^Ty $ @ $A^Ty \leq c$ Goes something like $c^Tx = b^T y = y^TAx \Leftrightarrow c^Tx-y^TAx = 0 ...
3
votes
0answers
40 views

Online stochastic convex optimization.

I need to find/approximate the argument that minimizes a stochastic convex function $F(\theta, Z)$: $$ {\arg\min_{\theta}} E_{Z}[ F(\theta, Z) ]$$ Where $Z$ is some random variable (we could assume ...
1
vote
0answers
37 views

saddle point versus local extermum

Suppose a function $f$ from $\mathbb{R}^n \to \mathbb{R}$, is differentiable. We know that $c$ is a critical point of $f$, i.e. $\nabla f(c) = 0$. Our goal is to find out if $c$ is a local extremum, ...
0
votes
1answer
32 views

Model logical constraints without binary variables?

Is it possible to express "either $f(x) \leq 0$ or $g(x) \leq 0$" where $f,g$ are linear constraints by using a finite number of continuous constraints/new variables, WITHOUT breaking convexity or ...
0
votes
1answer
39 views

Optimization problem with an added quadratic inequality constraint

Consider the following (non-convex) optimization problem on the real variables $\lambda_\ell^\pm$ with $\ell=1,\ldots,n$ \begin{align} \mbox{maximize}&\quad ...
2
votes
1answer
55 views

What is the motivation behind the, convex and concave closures of submodular functions?

What is the motivation behind the , convex and concave closures of submodular functions? Also, my understanding is that the submodularity condition is somewhat like concavity which makes it counter ...
1
vote
1answer
112 views

Scale ellipsoid maximally within polyhedron

Given an ellipsoid around the origin with scaling parameter $e$ in the form $x^T E x \leq e$ and a polyhedron $P$ given by $A x \leq b$, how can we define an optimization problem that maximizes e such ...
1
vote
0answers
18 views

How to interpolate a function with a reproducing kernel

I am trying to interpolate a function that is noisy, but I know with a high amount of certainty about a third of the points in the series. I am trying to estimate the smooth mean of the signal via a ...
2
votes
1answer
51 views

Minimum Distance between a Triangle and a Distance Field 3D

I am looking for (possibly numerical) solution to this geometric problem: Given a filled 3D triangle $T = \text{conv}(p_1, p_2, p_3) \subseteq R^3$, and a distance field $D(x) : R^3 \to R$, what ...
3
votes
1answer
78 views

Closest point on a 3D triangle, is this algorithm correct?

Given a point $P$ and three triangle vertices $U$, $V$, $W$, all in $\mathbb{R}^3$, I need to find the point in the triangle $UVW$closest to $P$. Does the following algorithm work, or have I missed ...