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

learn more… | top users | synonyms

0
votes
2answers
60 views

Convex hull of idempotent matrices

What is the convex hull of the set of $n\times n$ (potentially asymmetric) idempotent matrices? Apparently the powers that be want more information: Consider the set $S:=\{A\in\mathbb{R}^{n\times n}:...
0
votes
0answers
36 views

The slope and intercept of piecewise linear functions

If we have a function $f$ in the form: $$f(x)=\sum_{j}^{N}c_j \min_i(a_{ij}x+b_{ij})$$ Question: All of $ a_{ij}$ and $a_{ij}$ are known. How can I find the slopes of $f$ as optimal as possible. $f$...
-1
votes
1answer
18 views

Prove that $C = \{(x_1,x_2,0)\in R^3 | x_1^2+x_2^2 \leq 1\}$ is closed, dim(C)=2 and find ri(C)

Let $C = \{(x_1,x_2,0)\in R^3 | x_1^2+x_2^2 \leq 1\}$. Show that: (1) C is closed $\qquad\qquad$ (2) dim(C)=2 $\qquad\qquad$(3) int(C) = $\varnothing$ (3) $ri(C) = \{(x_1,x_2,0)|x_1^...
0
votes
0answers
34 views

solving Basis pursuit denoising with nuclear norm regularization

$$ \min_{S,L} \quad \left\| S \right\|_{1} + \left\| L \right\|_{*} $$ $$ \text{s.t.}\quad { \left\| D-MS-L \right\| }_{2}^{2}\le \epsilon $$ S,L,D,M are all matrix, $\epsilon$ is scalar, D and M is ...
0
votes
1answer
54 views

how do i show that a function $f(x)$ is convex given that the inequality holds

So i have to prove that the inequality below is true if and only if f is convex and Lipschitz continuous. i have the first part down which is to assume f is convex and show the inequality. But i cant ...
1
vote
1answer
29 views

Minimization problem over convex compact set [duplicate]

Does anybody know a method to solve the following problem numerically (or analytically, if there is a general method, but I doubt it). I am given a matrix $A \in \mathbb{C}^{n \times n}$ and I want ...
0
votes
1answer
37 views

Minimize the product of the traces of PSD matrices

Given two positive semidefinite matrices $X,Y$, I want to minimize their product: $Tr(X)Tr(Y)$. Now as far as I understand the following holds: 1) $Tr(X)Tr(Y)$ is convex since $Tr(X)$ and $Tr(Y)$ ...
0
votes
0answers
18 views

Convex optimization: how to understand epigraphical projection

In Rockafellar's text on convex optimization: Here we can think of the epigraphical projection as if someone shined a light to $f(x,u)$ and the shadow on the $u$ plane is the projection. My ...
0
votes
0answers
43 views

Prove that function is convex.

I have to prove that the function is convex: $$ f(\mathbf{U}) = ||\mathbf{x} - \mathbf{U} \mathbf{U}^T\mathbf{x}||_2^2 $$ Where $\mathbf{U}$ is matrix which columns are eigenvectors. So $\mathbf{U}^...
1
vote
1answer
64 views

applying KKT to non-convex optimization

I am trying to find a solution for following \begin{eqnarray} \text{minimize }~~ -\sum_{i=1}^K \frac{1}{a_i+b_i2^{(-2x_i)}} \\ \text{s.t.} ~~~ \sum_{i=1}^Kx_i=C \end{eqnarray} where $a_i,b_i,x_i\...
2
votes
1answer
26 views

Given $\{x \in \mathbb{R}^2_+: x_1 x_2 \geq 1\}$, find expression of supporting hyperplane

$\{x \in \mathbb{R}^2_+: x_1 x_2 \geq 1\}$ is difficult to sketch because the boundary of this set is the set $x = (t, 1/t)$, $t > 0$ and I don't have a good idea where this supporting hyperplane ...
0
votes
1answer
53 views

Finding a sparse convex combination of basis vectors

Real-world problem: Given $m$ registered 3D geometry meshes with some known consistent measurements (e.g. human bodies with height, hip girth, inseam etc.), I want to produce a new mesh for some ...
0
votes
0answers
29 views

Duality in Langrange Multiplier

The problem is to minimize $$f(x) = x^T.x$$ subject to condition $$Ax = b$$ With the help of Lagrange Multipliers, which gives the equation $$L(x,\lambda) = x^Tx + {\lambda}^T(Ax-b)$$ The solution ...
0
votes
1answer
41 views

Let p ∈ [1,+∞[. Show that f: X → R: x 􏰅→ ∥x∥^p is convex. [duplicate]

I am stuck on this question. Here is what I have so far: Take any $x_1,x_2 \in \mathbb{R}^n$ and $λ \in (0,1)$ $$f(λx_1 + (1- λ)x_2) \leq λf(x_1) + (1- λ)f(x_2)$$ then I would plug the function $|...
2
votes
0answers
22 views

What happens if the segment between two vertices of a polyhedron is the intersection of the polyhedron with a half-space?

I think that given any two vertices, say $x$ and $y$, of a convex polyhedron, if the line segment between $x$ and $y$ is the intersection of the polyhedron with a half-space, then $xy$ forms an edge. ...
0
votes
1answer
66 views

Give example of convex and not convex

I'm looking for a little input on this question. Let $f\colon X\rightarrow (-\infty,+\infty)$ be convex and let $I$ be an interval in $\mathbb{R}$ (bounded or unbounded). Further, recall that $f^{-1}(...
0
votes
0answers
66 views

Quadratic programming over nonnegative orthant?

I'm trying to solve a quadratic optimization over nonnegative orthant as below. \begin{equation} \begin{aligned} \mbox{maximize} \quad & -\frac{1}{2} \lambda^{T} [\frac{\Sigma_{i}}{\alpha_{i}} + ...
0
votes
1answer
34 views

Show the sub level set is convex

I am having a bit of trouble solving the following convexity problem: Let $f:X\rightarrow (-\infty,+\infty)$ be convex and let $\alpha\in\mathbb{R}$. Show that the sub level set $c= {x\in X:f(x)\leq\...
1
vote
1answer
154 views

Linear Transformation of Closed Convex Cone

Given a closed convex cone $C \subset \mathbb{R}^n$ and a matrix $M \in \mathbb{R}^{m\times n}$, is the set $S = \{Mx\mid x \in C\}$ also a closed convex cone? Firstly, $S$ must be a convex cone. ...
1
vote
1answer
34 views

Reference request: convergence property of continuous gradient descent?

Does anyone know of a text that treats the problem of gradient descent from a continuous perspective instead of a discretized perspective? For example, most text investigates the numerical properties ...
1
vote
2answers
65 views

Finding Lagrange multiplier

Suppose I'm looking for $\mathbf{x} \in \mathbb{C^{M\times 1}}$ such that: $$\mathbf{x}=\text{arg}\min_\mathbf{x}\|\mathbf{a+Ax}\|_2^2+\lambda\|\mathbf{x}\|_2^2~,$$ where $\mathbf{a}\in \mathbb{C^{N\...
0
votes
0answers
39 views

Solving the Lagrange dual problem

If we have a convex constraint problem $$ \text{min}\quad f_0(x)\\ f_i(x)\le0\\ h_i(x)=0, $$ where $f_1,\ldots,f_n$ are convex and $h_1,\ldots,h_r$ are affine. Assuming Slater's conditions we know ...
0
votes
1answer
50 views

sparse norm for optimization problem

I want to solve an optimization problem in general form: $$\arg \min f(x) + \lambda *g(x)$$ and i want to choose / define a $g(x)$ in a way to have a sparse solution such that between two possible ...
0
votes
0answers
50 views

how to find the set of feasible optimal solutions?

Consider the following optimization problem; $\min_{M} ~\|a-M*b\|_2$ subject to $\|M\|_2<1$. where $M\in R^{5\times3}$ and a and b are constant vectors. There might be many optimal solutions ...
0
votes
2answers
44 views

Why is an affine set convex?

I wanted to know why do we say that an affine set is convex? From what I understood, if we take two points $x_1$ and $x_2$ $\in \mathbb{R}$, then, the affine set $A$ defined by these two points will ...
1
vote
1answer
151 views

Optimization problem involving, $L_2$, $L_1$ norm and constraints.

Can somebody suggest me how to solve the following optimization problem? \begin{equation*} F(\mathbf{w},\xi)= \begin{aligned} & \underset{\mathbf{w,\xi}}{\text{minimize}} & & \frac{1}{2}\|\...
3
votes
2answers
75 views

construct a function that is not convex

I came across this question as a bonus question and would like some help disecting it. construct a function $ f:\mathbb{R}\times\mathbb{R}\rightarrow\mathbb{R}$ such that $\forall\;y\in\mathbb{R} \;x\...
1
vote
1answer
33 views

Why is this set convex? [duplicate]

Let $C\subset \mathbb{R}^m$ be a convex set, let $A$ be an $m \times n$ matrix and $b \in \mathbb{R}^m$. Show that $S=\{x \in \mathbb{R}^n | Ax+b \in C\}$ is a convex set. I can't understand why ...
2
votes
1answer
167 views

Why the gradient of $\log{\det{X}}$ is $X^{-1}$, and where did trace tr() go??

I'm studying Boyd's "Convex Optimization" and encountered a problem in page 642. According to the definition, the derivative $Df(x)$ has the form: $$f(x)+Df(x)(z-x)$$ And when $f$ is real-valued($i....
0
votes
0answers
34 views

Uniqueness of saddle point solution to zero-sum game

Considering a two player zero-sum game, is a found saddle point solution unique? And if not, are there any conditions under which the saddle point solution is unique?
3
votes
0answers
27 views

Maximum overlap of two convex bodies

Let $\Delta_n=\big\{(x_1,x_2,\ldots,x_n): \sum_i x_i \leq 1, x_i \geq 0\big\}$ denote an n-dimensional simplex. I am trying to find an $y \in \mathbb{R}^n$ such that the $y-$shifted negative simplex ...
0
votes
0answers
11 views

Approximate matrix partition

This problem is similar to the Optimizing sums of log det problem that I had asked earlier, but it is not the same. I have matrix $H$, which has columns $h_1, \ldots, h_n$. I want to partition the ...
2
votes
1answer
92 views

Convergence of gradient descent - derivation help

I am following along some old lectures notes that I found online (source) and I was hoping someone could provide some insight into a bound regarding gradient descent. The goal is to solve $\min_{x\in\...
0
votes
1answer
146 views

How to compute the hessian of the log barrier function

According to note, the log barrier function is given by (page 10): $f(x) = - \sum\limits_{i = 1}^m \log(b_i - a_i^Tx)$ where $b_i$ is a scalar, $a_i, x$ are $n$ dimensional vectors I have ...
0
votes
0answers
41 views

Maximizing a convex function with special structure

We Can prove that $trace(A(P+Q)^{−1}A^T)$ is a jointly convex function of positive variables $[q_1,q_i,...,q_N]$, where $Q=diag(q_1,...,q_N)$, $q_i>0$,∀i, and $P$ is a positive definite matrix. ...
1
vote
0answers
51 views

Newton Raphson convergence: a convex function over a convex cone

Similar to the Newton Raphson algorithm that has a (global) convergence property when we minimize a (strictly) convex function over Euclidean space (based on the second order Taylor serise expansion ...
0
votes
1answer
43 views

Convexity of set

If $C\subset\mathbb{R}^m$ is a convex set, $A$ is an $m\times n$-matrix and $b\in\mathbb{R}^m$, how do I prove that the set $S=\{x\in\mathbb{R}^m|Ax+b\in C\}$ is convex? I know that the definition of ...
0
votes
0answers
38 views

Voronoi sets and polyhedral decomposition.

Let $x_0,\dots,x_K \in \mathbb{R}^n$. Consider the Voronoi region, $V$,around $x_0$ w.r.t. $x_1,\dots,x_k$. $V = \{x\in\mathbb{R}^n | \left\|x-x_0\right\|_2\leq \left\|x-x_i\right\|_2, i=1,\dots,K \}$ ...
0
votes
0answers
21 views

Modification of a proof to work for an LP in inequality form

Suppose an LP is given in the inequality form : $\max\langle c,x\rangle$ subject to $Ax\leq b$. We call $x$ a basic feasible solution to this problem if there are $n$ linearly independent inequalities ...
2
votes
0answers
43 views

Fenchel duality of infinity norm

The minimization problem is $\min\limits_{f_i} \sum^K_{i=1} \|f_i(\mathbf{p})\|_\infty$ Could someone explain how the Fenchel duality is used so the primal-dual formation becomes $$\min_{f_i} \...
3
votes
2answers
62 views

Proving $\{(x_1, x_2) | x_1x_2 \geq 1\}$ is convex

This is so called a hyperbolic set: $\{(x_1, x_2) \in \mathbb{R}^2_{+} | x_1x_2 \geq 1\}$ We proceed to prove that it is convex by showing that a convex combination of points (a line segment) will ...
1
vote
0answers
55 views

Division of linear functions in convex polytope

I am a computer scientist, and find myself needing the following lemma: If f(x)=(g(x))/(h(x)), where g and h are linear and positive with domain the convex polytope d, then extrema of f occur at ...
0
votes
2answers
143 views

Solve for the gradient of $\log \sum\limits_{i = 1}^{m} \exp(a_i^Tx + bi)$

This is a standard problem in convex optimization with well known solution but I cannot seem to follow the procedure given in Boyd's CVX book pg 643 Suppose I am given $f(x) = \log \sum\limits_{i = 1}...
1
vote
1answer
36 views

Is This Constraint Convex?

The variable is $\mathbf{x}=\bigl[x_1,\ldots,x_n\bigr]^T$ and $a_k$ is given number. The constraint is the following: $$\dfrac{|a_k\cdot x_k|^2}{\sum_{j\neq k}^n|a_j\cdot x_j|^2+1}\geqslant \alpha.$$ ...
2
votes
2answers
44 views

Why is the inner product of a quadratic form a quadratic form?

I was going through a derivation of the second derivative of the $\log \det X$ where $X$ is symmetric positive definite, I noticed that despite the second order approximation of log det is written as: ...
1
vote
1answer
239 views

Convex Optimization: Gradient of $\log \det (X)$

In Boyd's CVX book, there is a step by step analysis of the gradient of so called log det function Three confusions: Is the determinant for positive definite matrix exactly equivalent to the sum ...
2
votes
2answers
84 views

Convexity of a trace of matrices with respect to diagonal elements

Can we prove that $\mbox{trace}({\bf A} ({\bf P}+{\bf Q})^{-1} {\bf A}^T)$ is a jointly convex function of positive variables $[q_1,q_i,...,q_N]$, where ${\bf Q}=\mbox{diag}(q_1,...,q_N)$, $q_i&...
5
votes
2answers
62 views

Convex Hull definition and counterexample?

The convex hull of a set $C$ is $$conv(C) = \{\theta_1x_1 + \theta_2x_2 + \cdots + \theta_k x_k: x_i \in C,\theta_i \ge 0, \sum \theta_i = 1, k=1, 2, \ldots \}$$ I am wondering why it is not enough ...
2
votes
1answer
59 views

Submodular First Order Conditions

I have a question about sufficient conditions for a submodular function to be (globally) minimized. Let $f: 2^{\{1,...,n\}} \to \mathbb{R}$ be a submodular function, and let $S^* \subset \{1,...,n\}$ ...
1
vote
0answers
60 views

Definition of a Convex Cone

In the definition of a convex cone, given that x,y belong to the convex cone C,then theta1*x+theta2*y must also belong to C, where theta1 and theta2 are both >=0. What I don't understand is why there ...