# Questions tagged [non-convex-optimization]

The non-convex-optimization tag has no usage guidance.

36
questions

**0**

votes

**0**answers

32 views

### (Iterative?) Solutions to a certain quadratic program with non-convex constraints

Let $y\in\mathbb{R}^m$, $\tau\in\mathbb{R}$ and $X\in\mathbb{R}^{m\times n}$, with $\tau>0$
I would like to efficiently solve the following problem:
Problem 1
Choose $\alpha,z\in\mathbb{R}^m,\beta\...

**0**

votes

**0**answers

68 views

### Convergence of heavy-ball method for non-convex optimization

The heavy-ball method (also called gradient descent with momentum) is commonly used in optimization. The update rule can be written as:
$$x_{t+1}=x_t-\eta\nabla f(x_t)-\beta (x_t-x_{t-1})$$
Suppose $\...

**0**

votes

**0**answers

45 views

### Recovering sparsity from $\ell^1$ relaxation

I've read that $\ell^1$ norm on $\mathbb{R}^n$ is the convex relaxation of the $\ell^0$ "norm":
$$\|x\|_0 \triangleq \sum_{i=1}^n I_{x_i \neq 0}.$$
In the regression setting, under what ...

**0**

votes

**0**answers

21 views

### Approaches and approximations for specific non-convex low-rank optimization problem

I have recently begun looking at an optimization problem in the context of Wiener filtering and lower-dimensional representations. Assume $ X $ is a random vector of length $ n $ and $ Y $ is a random ...

**2**

votes

**1**answer

101 views

### Hardness of concave minimization problem

I have an optimization problem $\underset{x}{\min} ~ c(x) - k \cdot x$ where $c(x)$ is a non-decreasing concave function with $c(0) = 0$, $x \in C \subseteq \mathbb{R}^d_{\geq 0}$. By non-decreasing, ...

**2**

votes

**0**answers

48 views

### Variational forms of non-convex functions

I am trying to understand what kind of variational forms exist for non-convex functions. Alternatively, are there conjugate forms which attain strong duality? For a non-convex function $f$, I am ...

**2**

votes

**0**answers

102 views

### Necessary optimality condition for quadratic programming: a solution of a constrained QAP is a solution of a LP

I have a concern about a result given by Murty in [1] and also written by Floudas and Visweswaran in [2]
They consider a QP:
\begin{array}{ll}{\min _{x} Q(x)} & {=c^{T} x+\frac{1}{2} x^{T} D ...

**0**

votes

**1**answer

127 views

### A quadratic program with non-negativity constraints

Is there any closed form solution for the optimal value of the folowing optimization problem?
$$\begin{array}{ll} \text{minimize} & (\mathbf{x} - \mathbf{y})^{\mathrm{T}}\mathbf{B}(\mathbf{x} - \...

**5**

votes

**1**answer

184 views

### If $\ell_0$ regularization can be done via the proximal operator, why are people still using LASSO?

I have just learned that a general framework in constrained optimization is called "proximal gradient optimization". It is interesting that the $\ell_0$ "norm" is also associated with a proximal ...

**5**

votes

**1**answer

257 views

### Solving a linear program, but over the unit sphere

I want to solve a linear program but with a subset of the variables taken from a unit sphere.
That is, given fixed $\textbf{c} \in \mathbb{R}^{n}$, $\textbf{A} \in \mathbb{R}^{m \times (n+k)}$,
I want ...

**2**

votes

**0**answers

137 views

### Quartic optimization problem over the unit Euclidean sphere

I want to solve following optimization problem in $x \in \mathbb R^n$.
$$\begin{array}{ll} \text{maximize} & \displaystyle\sum_i(x M_i x^T)^2\\ \text{subject to} & \|x\|_2 = 1\end{array}$$
...

**2**

votes

**0**answers

51 views

### Solving Mixed-Integer Non-Linear Optimization Problem

I would like to solve the following optimization problem:
\begin{array}{ll}
\underset{x_{i}\geq0,\, \pi_{i}\in\{0,1\}}{\text{minimize}} & \displaystyle\sum_{i=1}^n x_i\\
\text{subject to} & ...

**3**

votes

**2**answers

117 views

### Program to solve Optimization Problem

I have an optimization problem, this problem has linear constraints and nonlinear constraints. I solved the linear part by MATLAB but the nonlinear constraints I could not solve it. I downloaded ...

**7**

votes

**2**answers

317 views

### Proving an infinite norm minimization problem has finite support (non-convex p-norms)

Consider an optimization problem over infinite variables:
$$
\begin{align}
\min_{x}~& {\left\lVert{x}\right\rVert }_p
\\
\text{s.t}~& \left\langle x, a_n\right\rangle \ge 1~,~\forall n=1,\...

**4**

votes

**1**answer

121 views

### Optimizing a multivariate symmetric (permutation-invariant) function

Let $\ell$ and $d$ be two integers such that $\ell \le d$.
I would like to find the global maxima of the following symmetric function $f\colon (0,1]^n \to \mathbb{R}$,
$$f(x_1, \ldots, x_n) := \sum_{\...

**0**

votes

**2**answers

1k views

### Maximizing a convex function with a convex constraint

Given a convex function $f : \mathbb{R}^n \to [0,\infty)$, the objective is to find the farthest point in the level set $\left\lbrace x \in \mathbb{R}^n \mid f(x) \leq 1\right\rbrace$ (Assuming that ...

**2**

votes

**1**answer

79 views

### Linear optimization with one positive definite quadratic equality condition in P?

I have the following minimization problem in $z \in \mathbb R^n$, which contains $x_1, \dots, x_t, y \in \mathbb R$.
$$\begin{array}{ll} \text{minimize} & y\\ \text{subject to} & xQx'= y\\ &...

**0**

votes

**0**answers

135 views

### non-convex optimization with constraint

I have a special non-convex optimization problem:
$\min / \max \ f(x) + g(x) + h(x)$,
subject to $| g(x) - h(x)| < \varepsilon$,
where $f(x)$ is non-convex, but both $g(x)$ and $h(x)$ are ...

**1**

vote

**1**answer

259 views

### Maximizing quadratic form subject to inequality constraints [closed]

Given a $n \times n$ symmetric matrix $\rm S$, solve the optimization problem in $n \times k$ (where $n \geq k$) matrix $\rm X$
$$\begin{array}{ll} \text{maximize} & \mbox{tr} \left( \mathrm X^\...

**7**

votes

**2**answers

314 views

### Eigenvalue problem with two quadratic constraints

I would like to solve the following problem:
$$\begin{array}{ll} \text{minimize} & \mathbf{x}^T \mathbf{A} \mathbf{x}\\ \text{subject to} & \mathbf{x}^T\mathbf{B}\mathbf{x} = 0\\ & \...

**3**

votes

**1**answer

77 views

### Why to multiply the penalty by $n$ in the penalized least squares and likelihood?

In the SCAD paper by Fan and Li (2001), there exist two forms of penalized least squares as follows:
$$\frac{1}{2}\left \| y-X\beta \right \|^2+\lambda \sum_{j=1}^{d}p_j (\left | \beta _j \right |),$$
...

**1**

vote

**1**answer

242 views

### Are there any solvers to Chance Constrained Programming Problems

I'm trying to solve a chance constrained programming (CCP) problem
$\min_x f_0(x, \xi), \text{ such that } \mathbb{P} ( f_i(x, \xi) \ge \alpha_i ) \le \epsilon_i, \text{ where } i = 1,2,\cdots, m$
...

**5**

votes

**1**answer

284 views

### Maximize the determinant of Boolean combinations of positive definite matrices

I have the following optimization problem.
$$\begin{array}{ll} \text{maximize} & \det \left(\sum^n_{i=1}z_i W_i \right)\\ \text{subject to} & \sum_{i=1}^n z_i = N\\ & z_i
\in \{0,1\}\end{...

**4**

votes

**1**answer

2k views

### Can you give me good examples of non-convex functions that are problematic for optimization?

I want to test my extended gradient descent algorithm, whose aim is to handle non-convex problems better. Can you give me some examples of non-convex functions that are hard to minimize via gradient ...

**1**

vote

**0**answers

237 views

### Is this QCQP convex or nonconvex?

\begin{equation}
\begin{split}
\min_{x\in \mathbb{R}^n}\:f(x)=(1/2)x^{T}Q_0x+c_0^T x
\end{split}
\end{equation}
s.t.
$$
g_i(x)=\frac{1}{2}x^T Q_ix-lmax_i\leq0,i\in\{1,...,m/2\}
$$
$$
g_i(x)=\frac{...

**5**

votes

**2**answers

1k views

### Quadratically constrained linear program (QCLP) over $x$ with the linear constraint $x = Az$

I have a problem that looks very much like a norm-constrained linear program, but with an extra constraint that is unusual for me. The problem is the following. Given a matrix $A$ and a vector $w$,
$$...

**11**

votes

**2**answers

4k views

### Linearly constrained eigenvalue problem

Suppose I'd like to:
\begin{align}
\mathop{\text{min}}_\mathbf{x} && \mathbf{x}^T\mathbf{A}\mathbf{x} \\
\text{subject to:} && \mathbf{x}^T \mathbf{M} \mathbf{x} = 1\\
&& \...

**5**

votes

**1**answer

841 views

### Maximizing quadratic form on the hypercube

I want to maximize a quadratic form $\mathbf x^T\mathbf Q\mathbf x$ and also want to find out which vector $\mathbf x$ maximizes the quadratic form when
$\mathbf Q$ is an $n\times n$ positive ...

**3**

votes

**1**answer

652 views

### Nonconvex optimization problem

I have a nonconvex optimization problem with a linear objective function, a set of linear constraints and a set of nonlinear, non-convex constraints. Is this problem NP-hard? If so, how can I prove ...

**3**

votes

**1**answer

382 views

### Is the feasibility of a system of non-convex quadratic equations and inequations decidable?

I would like to know whether the following problem is decidable.
Given the following system in $x \in [0,1]^n$
$$x^T Q_i x + r_i = 0 \mbox{ for } i = 1, ..., k$$
$$x^T Q_j x + r_j \neq 0 \mbox{ ...

**2**

votes

**1**answer

152 views

### Non-convex quadratic optimization

I would like to optimize the following system:
$$\min_{q,\|q\|=1} \sum_i^n |q^T M_i q|$$
More details:
the size of the unknown vector $q$ is $4 \times 1$,
$M_i$ is a matrix of size $4\times 4$. It ...

**1**

vote

**1**answer

604 views

### A non-convex quadratically constrained quadratic program

$$\begin{array}{ll} \text{minimize} & \beta^{T} A \beta\\ \text{subject to} & \beta^{T} C \beta=1\\ & \beta \geqslant 0\end{array}$$
where $A, C\in \mathbb{R}^{M\times M}$ and $\beta \in ...

**2**

votes

**1**answer

968 views

### Can one maximize the spectral norm of a matrix via semidefinite programming?

Consider the following optimization problem:
Maximize $\|X\|_2$, subject to $X$ being Hermitian (or symmetric) and a bunch of semidefinite constraints on $X$. Here, $\|X\|_2$ is the spectral norm of ...

**1**

vote

**3**answers

2k views

### Solving a non-convex quadratically-constrained quadratic program

I have the following quadratic optimization problem: $\min_{\vec{x}} |\vec{x}|^2$ subject to $\vec{x}^T G_j \vec{x} \geq 1$, $j = 1 \ldots m$, where the $G_j$ are positive semidefinite. $|\vec{x}|$ is ...

**2**

votes

**2**answers

2k views

### Projected gradient descent for non-convex optimization problems

My question is in regards to the minimization of a convex function where the feasible set of solutions is non-convex. Can projected gradient descent (PGD) be used here to obtain a stationary solution?
...

**47**

votes

**7**answers

22k views

### Is all non-convex optimization heuristic?

Convex Optimization is a mathematically rigorous and well-studied field. In linear programming a whole host of tractable methods give your global optimums in lightning fast times. Quadratic ...