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

learn more… | top users | synonyms

0
votes
0answers
23 views

strengths and weaknesses of analytical method

I was wondering if anyone could suggest any books or paper that explain/discuss the advantages and drawbacks of analytical methods for optimization. Also, if we have a convex objective function ...
1
vote
0answers
20 views

How to define the nuclear norm of a tensor

As we know,the nuclear norm of a matrix $X$ is defined as this: $$||X||_{*}=\sum{\sigma_{i}}$$ where $\sigma_{i}$ is the singular value of $X$. But how to define the nuclear norm of a tensor ...
0
votes
2answers
118 views

Prove a closed ball in $\mathbb R^3$ has an infinite number of extreme points.

How do I show that a closed ball in $\mathbb R^3$ has an infinite number of extreme points ? (Closed ball is written as $S = \{(x,y,z) \in \mathbb R^3 | \sqrt {x^2 + y^2 + z^2} \le R \}$) I know ...
0
votes
1answer
48 views

Let $S = \{ (x,y,z) \in \mathbb R^3 : x^2 + y^2 + z^2 \le 1\}$. Prove $(1-\lambda)x + \lambda y \in S$ for $x=\lambda'y$, $\lambda' < 0$.

Let $S = \{ (x,y,z) \in \mathbb R^3 : x^2 + y^2 + z^2 \le 1\}$. I've verified that $x,y \in S$ implies $(1-\lambda)x + \lambda y \in S$ when $x,y$ are linearly independent using Pythagoras and when ...
0
votes
1answer
18 views

Compute the extreme points of a polyhedron $P$ and write $(1/2,1/2,1/2)$ as a linear combination of these.

Compute the extreme points of a polyhedron $P$ and write $(1/2,1/2,1/2)$ as a linear combination of these. I want to compute all the extreme points of the set $P$ (polyhedron) in $\mathbb R^3$ ...
3
votes
2answers
46 views

Can $\text{conv} \{ e_1,e_2,e_3, (1/2, 1/2, 1) , (1/2, 1, 1/2) , (1, 1/2, 1/2) \}$ be reduced to a convex hull of a subset of these?

How do I see whether $$\text{conv} \{ e_1,e_2,e_3, (1/2, 1/2, 1) , (1/2, 1, 1/2) , (1, 1/2, 1/2) \}$$ can be reduced to a convex hull of a subset of these vectors? That is, if $D = \{ e_1,e_2,e_3, ...
0
votes
1answer
26 views

How do I show that the set $S$ in $\mathbb R^3$ defined by linear inequalities is a $3$-simplex?

Consider the set $S$ in $\mathbb R^3$ defined by the inequalities: $x+y+z \ge 1$ $-x+y+z \le 1$ $x-y+z \le 1$ $x+y-z \le 1$ How can I show that $S$ is a $3$-simplex ? (Convex hull of $3 + 1$ ...
0
votes
1answer
27 views

How to introduce auxiliary variables to make the objective function separable?

$$\min_{X}\|X_{(1)}\|_{*}+\|X_{(2)}\|_{*}+\|X_{(3)}\|_{*}+\lambda\|Ax-b\|_2^2$$ where $X$ is a three order tensor, $X_{(i)}$ is a matrix whose column are the mode-$i$ fibers of $X$(i=1,2,3),$x$ is ...
0
votes
5answers
86 views

Let $B=\{ (x,y,z) \in \mathbb R^3 : x^2 + y^2 + z^2 \le 1\}$. Prove existence of a unique point $v_0 \in B$ that is closest to $v \notin B$?

Suppose $B=\{ (x,y,z) \in \mathbb R^3 : x^2 + y^2 + z^2 \le 1\}$. Consider a point $v \notin B$. How do I prove that there exist a unique point $v_0 \in B$ that is closest to $v$. Also, how do I ...
1
vote
1answer
28 views

what does separable convex program mean?

In literature,a separable program is formulated like this: $$\min_{x_{1},...x_{n}}\sum_{i=1}^{n}f_{i}(x_{i})$$ where $f_{i}$ is a closed proper convex function. My question is what does 'closed' ...
0
votes
1answer
20 views

MLE of an increasing nonegative signal from convex optimization book

I need help solving this problem from Stephen Boyd's Convex Optimization additional exercise. Its question 6.6 from additional exercise. Maximum likelihood estimation of an increasing nonnegative ...
0
votes
1answer
39 views

Iterative method to compute only the positive eigenvalue's and corresponding eignevectors of a very large matrix?

I have a very large dense matrix (~10000 X ~10000) which is not full rank . I want to compute only the positive eigenvalues and corresponding eigenvectors instead of computing all of them. I have ...
1
vote
1answer
38 views

Simple question on maximizing a family of concave functions

Given $x \in [0,1]$, let $f_k(x)$ be concave function in $x$ for all $k= 0,1,...,N$. Is the following two maximization formulations equivalent? $$ \max_{0 \le k \le N} f_k(x) =?= \max \{f_0(x), ...
0
votes
0answers
41 views

Can I perform Maximum likelihood via optimization?

I have two $3 \times 3$ matrices $\mathbf{a}$ and $\mathbf{f}$. $\mathbf {f}$ is completely known to me. Also $a_{ij} \in [+1,-1]$ \begin{equation} \mathbf{f} = \left( \begin{array}{ccc} f_{11} ...
0
votes
1answer
15 views

Can a Convex QCQP Problem with an additional linear constraint be converted to a SOCP?

I have a quadratically constrained quadratic programming problem that I massaged into the form $$ \begin{aligned} & \underset{x}{\text{minimize}} & & x^T Q x \\ & \text{subject to} ...
0
votes
1answer
21 views

Optimization: maximizing nonconvex sum of product of constraints

I'm wondering if there is any way to convexify, approximate, and/or simplify the following problem. $\max. \sum_{k \in K} \prod_{i \in I} (a_{ik} x_{ik} + b_{ik})$ s.t. $x_{ik} \in [0,1]$ where ...
0
votes
2answers
32 views

Derivative of a function of trace

Suppose $X$ is a diagonal matrix, $X \in \mathbb{R}^{m \times m}$. Let $f\colon\mathbb{R} \to \mathbb{R}$ be a twice differentiable function. Find the following $$\nabla^2_X f(tr(X))$$ where ...
0
votes
0answers
9 views

How to generate feasible $H$-conjugate descent search directions in convex subset

If we want to minimize a quadratic function $f(x)=c^Tx+\frac12x^THx$ (where $H$ is a symmetric positive-semidefinite matrix) in a convex subset $C\subset\mathbb{R}^n$, then is it possible to generate ...
0
votes
1answer
28 views

chain rule with scalars, vectors, and matrices

Consider two differentiable functions, $f : \mathbb{R}^{n \times n} \to \mathbb{R}$ and $g : \mathbb{R}^2 \to \mathbb{R}^{n \times n}.$ In general, for some $x \in \mathbb{R}^2$, what is the gradient ...
1
vote
0answers
28 views

Is there any software to solve this large scale convex optimization problem?

I want to solve the following large scale convex problem: $min\ \ ||A$u-b$||_2^{2}+ ||$U$_{(1)}||_*+||$U$_{(2)}||_*+||$U$_{(3)}||_*$ where U is a three order tensor, U$_{(i)}$ is a matrix whose ...
0
votes
0answers
28 views

Optimising a piecewise convex function

I have a function $f(x)$ defined for $x\in \mathbb{R}^+$ that is decreasing, piecewise convex and continuous. The 'pieces' of $f$ are exponential and the rate of decrease for each piece reduces as we ...
0
votes
0answers
18 views

Properties of a proper cone

Let $K$ be a proper cone. I need to prove following properties: if $x \preceq_K y$ and $u \preceq_K v$, then $x+u \preceq_K y+v$ if $x \preceq_K y$ and $y \preceq_K z$, then $x \preceq_K z$ if $x ...
0
votes
1answer
37 views

Homework on matrix and convex set [closed]

Suppose that $A,B\in\mathbb{R}^{n\times n}$ and both symmetric. Define $$ H=\{\sigma\in\mathbb{R} \mid A+\sigma B \text{ is semi-positive definite}\} $$ Assume that there exist ...
0
votes
1answer
28 views

a quadratic function with a solution

I am studying Convex Optimization and my book says that if I have the function $y=x^TAx+2b^Tx$ and the solution $x^*=-A^\dagger b$, then $y$ can be reduced to $y^*=-b^TA^\dagger b$ $\quad$ ($\dagger$ ...
-3
votes
1answer
32 views

Prove a convex function

I have to prove that if $f:A \to \mathbb{R}$ is convex and $c \ge 0$ then $c \cdot f:A \to \mathbb{R}$ is convex. I know that function $f:A \to \mathbb{R}$ is convex if for $\forall x,y \in A$ and ...
0
votes
2answers
28 views

Optimization problem: smallest euclidean distance with positive entries constraints

Suppose there is the simple function: \begin{align} f(x,y,z) &= (x-a)^2 + (y-b)^2 + (z-c)^2 + (x+y-S-z - d)^2 \end{align} where $a,b,c,d$ are nonnegative constants, and $S$ is an integer. I ...
0
votes
0answers
41 views

how to prove convexity of the function below?

For a graph $G$ consider the following function, $$f=\sum_{(i,j) \in G ,(i,k) \notin G } \max(0,c+ \left\|e_i-e_j\right\|_2^2-\left\|e_i-e_k\right\|_2^2)$$ where $e_i \in\mathbb R^n$ ($n$ dimension ...
2
votes
1answer
38 views

How to solve the convex optimization problem [closed]

$$\min (\|X_{(1)}\|_{*}+\|X_{(2)}\|_{*}+\|X_{(3)}\|_{*})+u\|Ax-b\|_2^2+v\|Cx\|_2^2$$ where $X$ is a three order tensor, $X_{(i)}$ is a matrix whose column are the mode-$i$ fibers of $X$(i=1,2,3),$x$ ...
0
votes
1answer
21 views

Is the following function concave? (or log of it)

I have a function $f(x_1, x_2, ..., x_M) = \displaystyle \prod_{i = 1}^N \frac{(\sum_{j = 1}^{M} a_jx_jI_{ij})^2}{\sum_{j = 1}^{M} a_jx_j}$ in domain $\{{\bf x} \in {\bf R}^m \setminus {\bf 0} \ ...
3
votes
1answer
44 views

Projection of $z$ onto $\{x\mid Ax = b\}$

Suppose $A$ is fat(number of columns > number of rows) and full row rank. The projection of $z$ onto $\{x\mid Ax = b\}$ is (affine) $$P(z) = z - A^T(AA^T)^{-1}(Az-b)$$ How to show this? ...
0
votes
2answers
36 views

Convergence of a sequence of projections

Let $C \subset \mathbb{R}^n$ be a compact, convex set, and $P \in \mathbb{R}^{n \times n}$ be a positive definite matrix ($P \succ 0$). Consider the projection $\Pi_P: \mathbb{R}^n \rightarrow C$ ...
0
votes
1answer
20 views

Minimizing nonsmooth single variable functions?

What options is available if one wants to minimize a nonsmooth convex function of one variable? Subgradients would work, but there has to be some nice way of utilizing that we're only searching in 1d. ...
0
votes
1answer
39 views

KKT conditions for a convex optimization problem with a L1-penalty and box constraints

I am having some trouble deriving / understanding optimality conditions for a convex optimization problem of the form: $$\begin{align} \min_{x\in\mathbb{R}^d}~ & f(x) + C.\|x\|_1 &\\ &x_i ...
0
votes
3answers
30 views

How to show the optimal condition of $f(\alpha) = \frac{R^2+G^2\sum_{i=1}^k \alpha_i^2}{2\sum_{i=1}^k \alpha_i}$

Consider the following function: ($\alpha>0$) $$f(\alpha) = \frac{R^2+G^2\sum_{i=1}^k \alpha_i^2}{2\sum_{i=1}^k \alpha_i}$$ It is a quadratic (in $\alpha$) over linear (in $\alpha$); therefore, ...
0
votes
1answer
36 views

Two duality theorems

Suppose $X$ is a Hilbert space with norm $||.||$ and $K$ is a weak compact and convex subset of $X$. The supporting functional: $$h(x^*)=\sup_{x\in K} \langle x^*, x \rangle$$ The indicator ...
0
votes
0answers
17 views

Intuition on primal convergence in dual subgradient method

It is well known that the subgradient method applied to the Lagrange dual of a convex problem may produce a sequence converging to the dual optimum, but the primal iterates produced by this sequence ...
1
vote
0answers
49 views

Quadratic optimization problem (inner products) with stochastic constraints

Let the set of feasible solution be the set of all row-stochastic $n \times k$ matrices $P = [p_{ij}]$, that is $\mathcal{P} := \{P \in \mathbb{R}^{n \times k} \ | \ P \mathbf{1} = \mathbf{1}, P \geq ...
0
votes
1answer
51 views

SDP relaxation of a non-convex quadratically constrained quadratic program.

I am very new to SDP and SDP solvers. I have a semi definite program of the following form $$\min_{x,X}\ Q\bullet X+c^Tx$$ $$\text{s.t. } Q^k \bullet X + (c^k)^T x =b^k , \ k=1,2, \dots,m \\ \quad ...
0
votes
1answer
34 views

How to solve the following non-convex optimization problem?

$$\min \|X\|_{*}+u\|Ax-b\|_2^2+v\|Cx\|_2^2 + wx^THx$$ where $x$ is vec($X$), $u,v$. is constant, H is a symmetric matrix,but it is not semidefinite. Is there any software to do this? Can the ...
2
votes
3answers
284 views

How to solve $\min \limits_{\mathbf{x}} \| \mathbf{Ax}-\mathbf{b} \|^2$?

Let $\mathbf{x}=[x_1,\ldots,x_K]$. I have the following optimization problem: \begin{array}{rl} \min \limits_{\mathbf{x}} & \| \mathbf{Ax}-\mathbf{b} \|^2 \\ \mbox{s.t.} & x_k\ge 0, \forall ...
-1
votes
2answers
37 views

How to prove a function is concave? (Single Variable)

It has been a while after completing the calculus of single variable. Right now I have a function of single variable $f(x)$, and that $f'(x)=-c$ for all $x$. So $f$ is a decreasing function. Bu, ...
1
vote
0answers
23 views

Solution to a nonlinear problem at an extreme point

I have a convex optimization problem of the form: $$ \begin{aligned} \operatorname*{minimize}_{\mathrm{x} = (\mathrm{x}_1, \dots, \mathrm{x}_m) \in \mathbb{R}^{nm}} &\quad f(\mathrm{x}) = ...
0
votes
1answer
49 views

Gradient of a Lagrange dual function

Consider: $$\min_{x \in \mathbb{R}^n} f(x)$$ $$\ \ \ \ \ \ \ \text{s.t. }\ h(x) \leq 0$$ Lagrangian:$\ \ \ L(x,\lambda) = f(x) + \lambda h(x)$ Suppose $x^* = \arg\min_{x} L(x,\lambda)$ ...
4
votes
2answers
94 views

Describing convex hulls in purely metrical terms

Let $X$ denote a Euclidean space; take $X = \mathbb{R}^n$ for concreteness. Now consider $x,y \in X$. Then the line segment joining $x$ and $y,$ hereafter denoted $[x,y]$, can be described in ...
2
votes
0answers
59 views

solving the primal problem via dual

On pp. 248 of Boyd and Vandenberghe: suppose 1) strong duality holds, 2) the dual optimal is attained at $(\lambda^*, \nu^*)$, 3) the dual function $L(x, \lambda^*, \nu^*)$ has the unique minimizer ...
3
votes
1answer
23 views

$\nabla f$ Lipschitz & $f$ Lipschitz

My question is: Which of the following is more restrictive? $\nabla f$ Lipschitz & $f$ Lipschitz I think each one cannot imply the other. For example ($1$D): $$f(x) = \frac {x^2}{3}$$ ...
0
votes
2answers
69 views

Linear optimization with “max” function (convex) constraint

I am working on a linear optimization problem which has a non-linear constraint. Suppose $x = [x_1 x_2]^T$, the problem is $$ \min_{x} \quad c^T x \\ \mathrm{s.t.} \quad Ax \leq b\\ x \geq 0 \\ ...
0
votes
0answers
26 views

Hölder's inequality/Cauchy-Schwarz for Bregman Divergence?

Consider the Bregman divergence. $$ D_F(p, q) = F(p)-F(q)-\langle \nabla F(q), p-q\rangle. $$ And its dual norm: $D_{F*}(p, q) $ where $ F^*(y) = \arg\min_x \left\{ \langle x, y\rangle - F(x) ...
0
votes
0answers
45 views

Prove that $\int_{0 \le u \le 1,\Omega}g^2(x)udx$ in term of $u$ is convex

I am having a cost function and I want to know whether convex or not. Could you explain help me my problem? My problem is that given a cost function such as $$F(u)=\int_{0 \le u(x) \le ...
2
votes
1answer
63 views

Proof of convergence for the proximal point algorithm

I'm trying to come up with a super simple proof of convergence on the proximal point algorithm, which uses the iteration scheme $x^{i+1} = \mathbf{prox}_{tf}(x^i)$ where $f$ is a closed, convex ...