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

learn more… | top users | synonyms

0
votes
0answers
17 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
30 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
25 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
37 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
33 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
20 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
37 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
35 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
29 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
28 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
0answers
31 views

Prove a convex function: $F(a,u,c)=\int_{\Omega}u(x)\left (\log(a)+\left(\frac {f(x)-c}a\right)^2 +const\right )dx$

I have a function and I would like to know the function whether convex or non-convex. Let look at my function $$F(a,u,c)=\int_{\Omega}u(x)\left (\log(a)+\left(\frac {f(x)-c}a\right)^2 +const\right ...
-2
votes
0answers
12 views

Subhessians for maximum eigenvalue of a matrix

I am trying to solve a non-linear, non-smooth convex optimization problem using a generic convex optimization solver. This solver requires and (sub)gradients of the objective and the constraints, as ...
0
votes
1answer
33 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
43 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
41 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
32 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 ...
1
vote
3answers
219 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
33 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
41 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)$ ...
2
votes
2answers
59 views

Image restoration in matlab via PDE toolbox

I want to remove a noise for an image using matlab, when the observed image is $$f=u+v$$ where $u$ is the restored image (is the image i want recovered) and $v$ is the gaussian noise. To restore $u$, ...
4
votes
2answers
91 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
58 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
22 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
63 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
23 views

Holder's inequality/Cauchy-Schwartz 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
44 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
52 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 ...
1
vote
2answers
48 views

Why is the constraint $\|w\| = 1$ non-convex?

Related: Why is this function, related to SVM derivation, non-convex? I am studying notes which cover the derivation of SVM. The intuition is the geometric margin should be maximized in order to ...
2
votes
2answers
55 views

What is the interpretation of the following optimization problem?

Suppose we have $N$ variables $x_1,\ldots,x_N$. Let $\mathbf{A}$ a $M \times N$ matrix, and $\mathbf{b}$ a $M \times 1$ vector. I have the following minimization problem: \begin{array}{rl} \min ...
0
votes
1answer
39 views

Express a second-order cone (SOC) inequality as a linear matrix inequality (LMI)

For $y \in \mathbf{R}^n$ and $t \in \mathbf{R}$, show that: $$||y||_2 \leq t ~~\iff~~ F(y) \succeq 0$$ Where $\text{I}$ is the $n \times n$ identity matrix, and $$F(y) = \begin{pmatrix} t ...
1
vote
1answer
28 views

does constant convexity assures global minimum

I have the following question: Consider a function $f:R^n \longrightarrow R$, s.t.: there is a point $x_0 \in R^n$ s.t. $\frac{\partial f}{\partial x^k} =0$ $\forall k$. the hessian matrix ...
0
votes
0answers
151 views

Linear - Quadratic optimization for system of objectives

I have two distinct data sets, $\{x^{\mu},J^{\mu}\}$, $\mu=1,\ldots,n$ and $\{x^{\nu},V^{\nu}\}$, $\nu=1,\ldots,m$ that also include uncertainties $\delta J^{\mu}$ and $\delta V^{\nu}$. In these I fit ...
0
votes
1answer
35 views

Why is one of the KKT conditions the same as one of the constraints?

I'm working through an SVM tutorial (from Andrew Ng Stanford course notes). In the brief coverage of Lagrange duality. The primal optimization problem is stated $$ \min_{w} \theta_{\mathcal{P}}(w) = ...
1
vote
3answers
38 views

Constrainted optimization involving logarithms

The problem is to minimize $ f(x_1, x_2 ,x_3, x_4):= - \Big[ \log ({\frac{1}{4} + x_1}) + \log ({\frac{1}{2} + x_2})+ \log ({\frac{1}{5} + x_3})+ \log ({\frac{3}{4} + x_4}) \big]$ such that ...
0
votes
0answers
14 views

Deriving Dual Averaging from (Sub)gradient Descent

Here the presenter tries to derive a simple Dual Averaging from (sub)gradient descent. I have a little problems understanding the steps. (Sub)gradient descent: Loop through: $$ x_{k+1} = x_k - t_k ...
0
votes
0answers
16 views

Convergence analysis of gradient descent method

From the following: Convex Optimization (S. Boyd) p.467 Content: We will see that the gradient method does in fact require a large number of iterations when the Hessian of $f$, ...
0
votes
1answer
41 views

Is inequality $tr(A^{-1^T} B) tr(A^T B^{-1}) \leq constant$ correct?

I have the following optimization problem \begin{align} \min_{A} &tr(A^{-1^T} B)\cr \text{subject to} &x^T A x > 0 \cr & A_{ii}=1 \end{align} where $A$ and $B$ are some positive ...
1
vote
1answer
40 views

Why is this function, related to SVM derivation, non-convex?

I'm working through a support vector machines tutorial. In eventually deriving the solvable objective function, the following objective function (to be maximized) was proposed, but dismissed as ...
0
votes
0answers
34 views

Is convex or non convex function?$J(u,c)=\int K(x).u.(f(x)-c)^2dx$

I have a function such as $$J(u,c)=\int K(x).u.(f(x)-c)^2dx$$ where $f(x):\Omega \to R$; c is constant; $0 \le u \le 1$; and K(.) is gaussian kernel. My question is that : Is J convex or non-convex ...
-2
votes
1answer
24 views

Inversion of a matrix in a system of linear inequalities

I would like to know if someone knows sufficient conditions on $A\in\mathbb{R}^{n\times n}$ and $b\in\mathbb{R}^{n}$ such that for all $x\in\mathbb{R}^{n}$: $$Ax\leq b \Rightarrow x\leq A^{-1}b \text{ ...
1
vote
0answers
32 views

How to understand a proposition of subgradient

The question is from the following: Convex Optimization Algorithm (p.512)----- Prof. Bertsekas Let $f: R^n \rightarrow (-\infty, \infty]$ be a proper convex function. For every $x \in ...
2
votes
1answer
58 views

Calculating the distance function and projection

Let $\Omega=\{x\in\mathbb R^n\mid\langle a,x\rangle=b\}$. We define the distance function and projection as follows $$d(x;\Omega)=\inf\{||x-\omega||\mid\omega\in\Omega\}$$ ...
3
votes
0answers
22 views

On the solutions of a system of inequalities avoiding Helly's theorem

Let $a_1,b_1,\cdots,a_4,b_4\in\mathbb{R},r_1,\cdots,r_4\in(0,+\infty)$. Show that, if $\not\exists (x,y)\in\mathbb{R}^2$ such that $$ \begin{cases} (x-a_1)^2+(y-b_1)^2\le r_1\\ ...
0
votes
1answer
25 views

Supporting lines of closed Jordan curve

Given a simple closed Jordan (i.e. continuous) curve $\gamma:[a,b]\to\mathbb{R}^2,\ \gamma([a,b])=C_\gamma$, how can I prove that $D_\gamma$ (the set of all interior points of $\gamma$ toghether with ...
0
votes
1answer
22 views

Is this floor function/problem quasiconvex?

I am trying to study an optimisation problem under constraints. The point is that all my constraints are linear as well as all terms of my objective function except one. This guy : $$ \alpha^{\lfloor ...