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

learn more… | top users | synonyms

0
votes
2answers
51 views

Minimum quadratic form value within a line?

If I have $x\in R^n , C\in R^{m\times n}, d\in R^m$, $m<n$, then $Cx=d$ is a linear manifold. And $P\in R^{n\times n}$, $P>0$, the quadratic form is $y=x^TPx$ Is there an analytical expression ...
0
votes
1answer
112 views

How do I prove that objective function is not convex

Here is my objective function. \begin{equation} \begin{array}{c} \underset{\mathbf{x},\mathbf{y}}{\text{minimize}}\hspace{4mm} \big(\lambda_1\left( \mathbf{y}^T V^{(1)}\mathbf{x} \right)^2 + \...
0
votes
0answers
23 views

Convex signal reconstruction for convex generator function?

Let $f : \mathbb{R} \mapsto \mathbb{R}$ be a convex (not affine) function and suppose that $y = f(x)$. We want to reconstruct the input $x$ for a given $y$, and the standard approach would be to ...
0
votes
1answer
86 views

The Legendre-Fenchel transform of $BV$ semi-norm

I am reading a numerical paper in which it calls some "easy" facts from convex analysis but I can't justify it... Let $\Omega\subset \mathbb R^2$ be open. Define for a function $u\in L^1(\Omega)$ and ...
0
votes
0answers
54 views

Convex envelopes of bivariate functions

In order to convexify my nonlinear non-convex program I need convex envelopes for the function $(x/y)^2$, both x,y are positive. I am only aware of the convex envelopes of the type $xy$ from here ...
0
votes
0answers
26 views

Rewriting a strictly convex quadratic equality constraint

I have the following constraint $$ x^TAx+b^Tx=c $$ where $A$ is a positive definite matrix. Is there any way to take advantage of the strict convexity of this expression to reformulate the constraint ...
3
votes
1answer
293 views

Regarding Nesterov's smooth minimization

I am currently studying this Nesterov's paper for project purposes, and I am trying to figure out how the smoothing and the minimization algorithm works I have tried looking at the example ...
0
votes
0answers
15 views

Find the nearest point of $y$ from a probability simplex. [duplicate]

I need to compute the nearest point of $x$ from a probability simplex. Formally, I want to ask if there is a close form for the solution to the following optimization problem: for $y\in \mathbb{R}^k$, ...
1
vote
1answer
59 views

Functional Lifting in Optimisation - Reference Request

I'm looking to learn about the use of (functional) lifting applied to a non-convex optimisation problem to give a (larger) convex problem. Unfortunately, I'm having a great deal of trouble finding ...
1
vote
0answers
68 views

Minimizing the max function

Suppose we have the single-variable function $$f(x) = \max_k \{f_k(x)\}$$ where each $f_k$ is convex and smooth (and known beforehand). We want to minimize it over some bounded interval. We can, in $\...
1
vote
0answers
68 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
151 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
49 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
30 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
49 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
29 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
94 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
96 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
33 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
112 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
78 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
43 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), f_1(...
0
votes
0answers
43 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
101 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
49 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
3answers
80 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 $\nabla^...
0
votes
1answer
35 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
37 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
36 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
41 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 $\sigma_1\in\...
0
votes
1answer
33 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
44 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
39 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
76 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 ...
1
vote
1answer
88 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
35 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
120 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
49 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
55 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
108 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
88 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
43 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 ...
1
vote
0answers
57 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
78 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 ...
1
vote
1answer
133 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
43 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 ...
5
votes
3answers
620 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 ...
-2
votes
2answers
98 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, $f'...
1
vote
0answers
25 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
115 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)$ ...