Questions tagged [non-convex-optimization]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
57 views

Under which condition, such that all second-order critical points satisfy $\sum_j\cos(\theta_i-\theta_j)>0$ for all $i\in[n]$?

Consider the following non-convex function $$E(\theta):=-\sum_{i,j}A_{ij}\cos(\theta_i-\theta_j)$$ where $A$ is a symmetric, diagonal-free matrix whose non-diagonal element are $\pm 1$. In other words,...
0 votes
0 answers
30 views

Efficient algorithms to find the global minimum of a non-convex quadratically-constrained quadratic program

I am working on a problem involving a non-convex quadratically-constrained quadratic program and am seeking efficient algorithms to find its global minimum. The problem is structured as follows: Fix ...
4 votes
2 answers
182 views

Minimal norm of Fréchet subdifferential for function Lipschitz over its domain

Let $f:\mathbb{R}^n\rightarrow\mathbb{R}\cup\{+\infty\}$ be an extended real-valued function that is proper, lower semicontinuous, and Lipschitz continuous over its domain $\newcommand{\dom}{\text{dom}...
0 votes
1 answer
102 views

An optimization problem with variables on the exponential of a complex number

$$\min_t \quad\operatorname{Re} \sum\limits_{i = 1}^N {\left( {{e^{ - j2\pi {f_i}t}}{r_i}} \right)}, $$where $\operatorname{Re}$ refers to get the real part of a complex number, $\{f_i\}$ is an ...
0 votes
0 answers
70 views

How to solve mckp (multiple-choice knapsack problem) problem with non-linear constraint

How to solve the below optimization problem? $P$ is a probability matrix, $0\le P_{ij}\le 1$. Are there any developed tools to solve this? Thanks a lot. \begin{equation*} \begin{aligned} &\...
1 vote
0 answers
100 views

Maximisation of a convex (quadratic) function

This post is a continuation of A variant of (discrete) optimal transport problem For $\alpha=(\alpha_1,\ldots,\alpha_m)\subset\mathbb R^m_+$, $\beta=(\beta_1,\ldots,\beta_n)\subset\mathbb R^n_+$ and $...
6 votes
2 answers
435 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{...
0 votes
0 answers
46 views

Trying to transform a minimization problem to a saddle point problem for the primal–dual algorithm

I’m reading about a problem, and the author goes from a classical minimization problem to a saddle point problem in order to perform a primal–dual algorithm on it [1]. However, It’s my first problem ...
0 votes
0 answers
41 views

Convergence and convergence rate of projected gradient method with any nonconvex contraints

If I want to use projected gradient method, and the function is convex/strongly convex, but feasible set is nonconvex, can I get a linear or sublinear rate of convergence. (In particular, the feasible ...
1 vote
1 answer
300 views

Is non-convex optimisation really in NP class?

Crossposted on Mathematics SE I've seen in many optimisation papers the statement that general non-convex optimisation problem is NP-hard. If we assume that non-convex optimisation is in NP class, it ...
0 votes
1 answer
149 views

Prove zero slope point is global maximum for constrained function with binomials. Without restriction, objective function is non-concave

How to prove the zero slope point is a global maximum in this non-concave program for a function with binomials? I need to find the (global) maximum of the following constrained problem: $$\max_{CAP} \...
1 vote
0 answers
121 views

Can I solve this quadratic program "fast"?

We are given a matrix $D \in \mathbb{Z}^{C \times C}$ of non-negative entries, an integer $k \geq 1$ and we need to maximize the quadratic form $x^T D x$ under some simple constraints. For all ...
4 votes
2 answers
121 views

$O(n^{2-\epsilon})$ bound on choosing $n$ points on the hypersphere to maximize $\pm 1$ weighted sum of their $\binom{n}{2}$ inner products

Given $n,d\in\mathbb{N}, n\gg d$, I'm looking for a bound on the maximum (or minimum) expected value of the following game: Draw a vector $\epsilon\in\{\pm 1\}^{\binom{n}{2}}$, uniformly at random. ...
1 vote
1 answer
640 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, ...
1 vote
0 answers
64 views

Minimize smooth function $(x,y) \to f(x,y)$ subject to $x \perp y$

Let $V$ be a finite-dimensional real vector space (e.g space of $m \times n$ real matrices equiped with Hilbert-Schmidt inner product $(A,B) \to \mathrm{tr}(AB^\top)$, and let $f:V^2 \to \mathbb R$, $(...
0 votes
1 answer
77 views

PCA, relation between the error and variance

As is known, the rank-1 PCA aims to solve the following optimization problem $$\min_{x\in\mathbb{R}^d}\quad -x^T \Sigma x\quad\quad\quad \text{s.t.}\quad \Vert x\Vert_{2}=1,$$ where $\Sigma\in\mathbb{...
2 votes
0 answers
383 views

Global minimum of sum of a non-convex and convex function, where minima of the non-convex function can be found

I'm interested in finding $\arg\min_{x \in X} (f(x) + \lVert x\rVert_2^2)$ where $X$ is a $[0,1]^n$, $f$ is Lipschitz but non-convex and we already have a procedure to find some $x^* \in \arg\min_{x\...
1 vote
0 answers
101 views

Minimising kurtosis (non-convex). Can I use algebraic geometry or alternate methods to show uniqueness of a particular solution?

I consider a weighted sum of $n$ identically-distributed correlated random variables. The weights in the sum, $w_i$ for $i=1, 2,...,n$, satisfy $w_i>=0$ and $\sum_{i=1}^{n}w_i=1$. I am ...
3 votes
1 answer
206 views

Nonconvex optimization with linear constraints

Which algorithms are suitable for solving problems of the form $$ \min_x \lbrace f(x) \; | \; Ax \leq b \rbrace $$ with nonconvex, differentiable obfective $f$. Unfortunately, $f$ cannot be assumed to ...
1 vote
0 answers
451 views

Minimizing the Frobenius norm of a quadratic matrix expression

Given matrices $R \in \mathbb R^{m \times n}$ and $Y \in \mathbb R^{p \times n}$, where $R$ is full rank, how can I solve the following optimization problems? $$\min_{X \in \mathbb R^{p \times m}} \| ...
1 vote
1 answer
330 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} - \...
0 votes
0 answers
53 views

Why the result of the non-convex optimization problem will be farther and farther away from the optimal

When I try to solve a optimization problem by Riemannian stochastic variance reduced gradient algorithm(RSVRG), the formulation of problem like $\frac{1}{N}\sum_{i=1}^Nf_i(x)$ and $f_i(x)$ is a non-...
1 vote
0 answers
61 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
282 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 $\...
5 votes
1 answer
1k 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
2 answers
4k 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? ...
2 votes
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
0 answers
86 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 ...
3 votes
0 answers
150 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 ...
6 votes
1 answer
660 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 ...
3 votes
2 answers
310 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 ...
50 votes
7 answers
23k 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 ...
2 votes
0 answers
224 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
66 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} & ...
7 votes
2 answers
509 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,\...
5 votes
1 answer
375 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_{\...
3 votes
2 answers
5k 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 ...
0 votes
0 answers
171 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 ...
2 votes
1 answer
96 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\\ &...
2 votes
1 answer
1k 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
1 answer
489 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
3k 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$, $$...
4 votes
1 answer
4k 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
1 answer
649 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
277 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 ...
3 votes
1 answer
578 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{ ...
1 vote
0 answers
389 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
1 answer
2k 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 ...
7 votes
2 answers
682 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\\ & \...
15 votes
2 answers
6k 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\\ && \...