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

learn more… | top users | synonyms

1
vote
1answer
10 views

How do I set a lower bound to the solution's norm in a QP problem

I know that LASSO-regularization can be used to scale into an $L_1$ upper bound for a solution. But what if I want the norm to be within a specific range $[a,b]$? ie. I also want to set a lower bound? ...
-1
votes
0answers
12 views

How to solve cardinality (number of non-zero elements) problem through convex optimization

So here is the problem: you wanna minimize the number of non-zero elements of a vector x through the following optimization : \begin{array}{ll} \text{minimize} & \mathop{\textrm{Card(x)}} \\ ...
2
votes
0answers
17 views

Log concavity/convexity of a determinant

I was wondering if anyone would be able to help me determine whether the following quantity is log concave or not with respect to $\alpha$? $$\left[\det(\textbf Y^\top \textbf P \textbf G \textbf ...
0
votes
0answers
16 views

Proof - extreme point of a convex set

everybody! I am wondering how to prove the following theorem: Let $S \subset \mathbf{R}^{n}$ be a non-empty closed convex set. Then $S$ has at least one extreme point iff $S$ does not contain any ...
0
votes
1answer
15 views

Equality Constraints in Quadratic Programming

Now I am new to the world of primal-dual algorithms and I want to understand the SOCP-Code of Lobo/Vandenberghe/Boyd (primal dual interior point method). Currently I am working through Goldfarb and ...
3
votes
1answer
29 views

How to show $ \sup \inf g(x,y) \leq \inf \sup g(x,y)$?

Came across this little practice exercise, and I couldn't properly convince myself of this relation: Let $X,Y \subset \mathbb{R}^n$ and $g:X\times Y \rightarrow \mathbb{R}$. Show that $$\sup_{y \in ...
1
vote
3answers
28 views

Questions about coerciveness and convexity

I just have a few yes/no questions, and would really appreciate if you could correct me where I am wrong, and for what fundamental flaw I have. 1. Would the set of coercive functions a linear space? ...
0
votes
2answers
15 views

Coerciveness and Positive definiteness relation?

Let $A ∈ \mathbb{R}^{n×n}$ be a symmetric matrix. How can I demonstrate that A is positive definite iff the function $q(x) := x^TAx$ is coercive . I know the eigenvalues of A have to be positive for ...
1
vote
1answer
23 views

Why does the Weierstrass theorem fail if a set is not compact?

By Weierstrass theorem I mean that if $f:\mathbb{R}^n \to \mathbb{R}$ is continuous and $C \subset \mathbb{R}^n$ is compact, then the theorem asserts that a solution $x^*$ of $$ \text{min} _{x\in ...
0
votes
2answers
25 views

Union of 2 convex sets

Let $f : \mathbb{R}^n→ \mathbb{R}_∞$ be convex over the sets A, B which are also convex. $A ∩ B = ∅$ and $A ∪ B$ is convex. Then is $f$ is convex on $A ∪ B$? Why or why not? I am confused ...
1
vote
1answer
26 views

Proving convexity using the Hessian

Suppose I have $f: \mathbb{R}^n \to \mathbb{R}_\infty$ which is twice continuously differentiable, on some convex set C, which is open. How can I prove that $f$ is convex over C, iff the hessian ...
1
vote
1answer
15 views

Problems with vector vector derivative in optimization

I have a loss function of the followoing form: $L(\mathbf{a}) = \|\mathbf{b} - \mathbf{a}\|_2^2$ Where, $\mathbf{a}$ and $\mathbf{b}$ are vectors of dimension $d\times 1$. I need to calculate ...
2
votes
0answers
26 views

Maximin problem as LP?

Consider the following setting. Let $A\in \mathbb{R}^{3 \times m}$ and $B\in \mathbb{R}^{m\times 3}$ be two matrices such that each of their columns must add up to a given $c\in \mathbb{R}$. Denote by ...
1
vote
2answers
22 views

Is f(x)=-log(x) a closed function?

I am reading Convex optimization written by Stephen Boyd. In page 640, there is an example said \begin{equation} f(x)=-log(x) \end{equation} is a closed function. But this function seems does not ...
0
votes
0answers
24 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
votes
0answers
19 views

Which one(are) true?

My Effort: a,b are true. As f convex means for any 2 points in the curve , curve lies below the line. Thinking geometrically I think c is incorrect as if f negative |f| is positive. I' ll be glad if ...
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
10 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
15 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
28 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
18 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
29 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
17 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
34 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
41 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
16 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
27 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
25 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
0answers
41 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
45 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
19 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 ...
0
votes
1answer
27 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
29 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
25 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 ...
0
votes
1answer
39 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
44 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
20 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
23 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 ...
0
votes
1answer
34 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
39 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
52 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
19 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
8 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
17 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
17 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
26 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
18 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
21 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
42 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
32 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\}$ ...