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

learn more… | top users | synonyms

1
vote
0answers
42 views

Difficulty in understanding a solution: Constraint minimization of sum of Non-symmetric matrices

I am trying to understand why there is significance difference in the performance of two proposed solutions. Original question (Constraint minimization of sum of Non-symmetric matrices) ...
0
votes
0answers
34 views

convexity of inverse of a matrix

I know that the function $f(X)$ which maps matrix $X$ to $Tr((X)^{-1})$ is convex for symmetric positive definite $X$. This has also been answered in Is the trace of inverse matrix convex? for ...
0
votes
1answer
39 views

Does analytical solution exist for this convex euclidean affine projection problem with non-negativity constraints?

I've come across this convex optimization problem in my research where I need to project a matrix $X_0$ onto a non-negative affine space constraint and box constraints. Concretely, $X \in ...
1
vote
1answer
34 views

how to find the solution of this cost function?

I have the following cost function. $J = \sum_{i=1}^N a\, Trace(W^TX_iW) - b\, Trace(W^TY_iW)$ Where $X_i$ and $Y_i$ are symmetric matrices, $a$ and $b$ are scalars. How can I find W?
0
votes
1answer
30 views

Determining corners of this convex set

Let $N \geq 2$ be an integer. Let $P:= \{ (a_1, \ldots, a_N) \in [0, 1]^N : \sum_n a_n = 2 \}$. Is $P$ the convex hull of $P \cap \{0, 1\}^N$? Edit: This is apparently true, see the beginning of ...
1
vote
0answers
32 views

Fenchel Conjugate of a norm squared

I was wondering if the fenchel conjugate of the $\frac{1}{2}||u||^2$, is the $\frac{1}{2}||u||_*^2$, where $||.||_*$ is the dual norm of $||.||$. This seems to be true for the $\ell_2$ norm. However, ...
0
votes
2answers
96 views

Constraint minimization of sum of Non-symmetric matrices

I am trying to find closed form solution to following problem \begin{equation} \begin{array}{c} \text{min} \hspace{4mm} \big(\lambda_1\left( \mathbf{y}^T V^{(1)}\mathbf{x} \right)^2 + ...
1
vote
1answer
33 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? ...
2
votes
0answers
34 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
1answer
68 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
37 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
36 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
43 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
21 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
43 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
33 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
36 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
25 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
35 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
26 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
1answer
47 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
29 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
42 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
34 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
34 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
26 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 ...
4
votes
2answers
55 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
35 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
56 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
83 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
22 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
36 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
35 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
46 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
80 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
33 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
78 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
90 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
63 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
26 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
13 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
42 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
52 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 ...