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

learn more… | top users | synonyms

0
votes
1answer
41 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
19 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
23 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
37 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
10 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
29 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
29 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
29 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
43 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
40 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
37 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
22 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
42 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
31 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
37 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
24 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
52 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
59 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
313 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
39 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
53 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
95 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
62 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
24 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
76 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
27 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
71 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
52 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
57 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
49 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
30 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
163 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
38 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
41 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
17 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
21 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
42 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 ...