Questions tagged [non-convex-optimization]

A non-convex optimization problem is one where either the objective function is non-convex in a minimization problem (or non-concave in a maximization problem) or where the feasible region is not convex.

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

Feasible approximations for programs with bilinear constraints

I have an optimisation problem of the form \begin{array}{cccll} \min &f(x) \\ \text{s.t.}& g_{1}(x) \leq s \\ & g_{2}(x) \leq t \\ & st \leq C \\ \end{array} where my variables ...
user avatar
2 votes
0 answers
16 views

How can I find a point that is close to a minimizer for a Lipschitz function?

Imagine there is some unknown $L$-Lipschitz function $f\colon [0,1] \to \mathbb R$ that, for the sake of simplicity, has a unique maximizer $x^\star$. Are there algorithms that, for any given budget ...
user avatar
1 vote
0 answers
29 views

Feasibility problem with polynomial inequalities

I have several nonconvex quadratic polynomials $(f_i)_{i\in I}$ for which I need to find a point $\overline{x}$ such that $$(\forall i\in I)\quad f_i(\overline{x})\leq 0.$$ I feel like there should be ...
user avatar
  • 3,588
0 votes
0 answers
34 views

Frobenius inner product, Frobenius norm objective function with quadratic equality constraints.

I would like to solve the following optimization problem: given $\mathbf{K} \in \mathbb{R}^{n \times n}$, $\mathbf{P_{0}} \in \mathbb{R}^{n \times 3}$, $\mathbf{M} \in \mathbb{R}^{m \times n}$, $\...
user avatar
  • 35
0 votes
0 answers
58 views

Maximize sharpe ratio. Is $x_0 x_1 \ge x_2$ convex?

I'm dealing with the portfolio optimization case study of mosek and want to add limits on the total number of assets to be re-weighted and the turnover of each asset. The objective is to maximize ...
user avatar
  • 11
0 votes
0 answers
11 views

Does the negative log likelihood of Discrete Weibull have Lipschitz gradients?

I am working on different convergence analyses of optimization algorithms for machine learning. However, almost all of them are based on the assumption that the objective function $f(x)$ has Lipschitz ...
user avatar
0 votes
0 answers
9 views

Intuition of measure of local optimality in non-convex second order optimization

I am reading in [1] that a good measure of local optimality in non-convex unconstrained optimization is $$\mu_M(x) = \max \left\{\sqrt{\frac{2}{L+M} \|f'(x) \|}, -\frac{2}{2L+M}\lambda_\min (f'' (x)) \...
user avatar
  • 699
0 votes
0 answers
16 views

Analysis of Theorems 1 and 2 from Nesterov & Polyak paper

I am reading Theorem 2 from [1] which results in $$f(x^*) = f^*, \quad f'(x^*) = 0, \quad f''(x^*) \succeq 0.$$ The proof of Theorem 1 is "The proof of this theorem can be derived from Theorem 1 ...
user avatar
  • 699
0 votes
0 answers
15 views

Optimizing a linear function over a set $S$ for which $v,w \in S$ implies $\mu v+(1-\sqrt{\mu})^2w \in S$, $\mu \in [0,1]$?

Consider a set $S \subset \mathbb{R}^n$ which has the following property: Given $\mu \in [0,1]$ and two elements $v,w$ in $S$, then $\mu v + (1-\sqrt{\mu})^2 w$ is also in $S$. An example for such a ...
user avatar
  • 1,029
0 votes
1 answer
30 views

Simple non convex optimization

I am trying to solve the following optimization problem. I'd appreciate any tips or directions. $ \text{minimize } |x|^2 + |y|^2$ $ \text{subject to } |x-y|^2 \geq 1$ where $|.|$ is the absolute ...
user avatar
1 vote
1 answer
50 views

How to transform two non-convex problems to convex problems?

I came cross two non-convex problems, and I wanted to transform them to standard form of convex problems. However, I don't know how to do it. If anyone can provide ideas or give answers, I would like ...
user avatar
  • 431
1 vote
1 answer
22 views

Subgradient method for nonconvex nonsmooth function

Gradient descent or stochastic gradient descent are frequently used to find stationary points (and in some cases even to local minimum) of a nonconvex function. I was wondering if the same can be said ...
user avatar
1 vote
0 answers
65 views

Minimize $Q(t,s) = \mathbf{w}^\top \begin{pmatrix} r(t, t) & -r(t, s) \\ -r(t,s) & r(s, s) \end{pmatrix}^{-1} \mathbf{w}$ in $(t, s)$

This question is a repost from mo. Let $0 \leq r(t,s) \leq 1$, $t, \ s \in [0, T]$ be a smooth enough function, such that $r(t,t)$ increases in $t$ $r(t, s) = r(s, t)$ decreases as $t$ and $s$ move ...
user avatar
1 vote
1 answer
56 views

why gradient descent does not always land at the global minimum closest to the starting point?

I am given this function $\boxed{f(x,y)=((x^2+y^2)-1)^2}$. I need to do gradient descent analysis on it. I have studied that it's not trivial to show mathematically "ball reaches to the global ...
user avatar
0 votes
1 answer
21 views

Why reformulate composite optimization using equality constraints?

On the “Practical Optimization” section in Mosek’s documentation, it recommends reformulating composite functions $f(g(x))$ where $f$ is convex by moving the inner $g(x)$ into a new equality ...
user avatar
  • 167
1 vote
0 answers
15 views

Example of local convergence to a global optimum for nonconvex gradient descent

These slides give an overview of some results in nonconvex optimization with gradient descent (GD). They suggest a few types of results that are proven about nonconvex GD: Convergence to a local ...
user avatar
0 votes
0 answers
29 views

Parametrically enlarge one ellipsoid to fit another one

I'm trying to figure out the smallest enlargement factor which I need to apply to one ellipsoid $E_1$ in order to fit another one $E_2$. Precisely, let $E(c, S) := \{x | (x-c)^T S (x-c) \leq 1\}$ be ...
user avatar
0 votes
0 answers
50 views

Non-convex optimization problem

I am trying to solve the following non-convex optimization problem. I'd appreciate any tips or directions. $ \text{minimize } ||C_1||_2^2 + ||C_2||_2^2$ $ \text{subject to } ||H(C_1 -C_2)||_2^2 \geq ...
user avatar
0 votes
0 answers
20 views

Proximal operator for an $L$-smooth but nonconvex function

Proximal operator definition is: \begin{align} \operatorname{prox}_{\eta f}(x) := \arg\min_{z} \ \eta f(z) + \frac{1}{2}\| z - x \|_2^2, \end{align} where typically $f$ is assumed to be closed convex ...
user avatar
  • 2,475
1 vote
1 answer
80 views

Algorithms/Solvers for Hard Constrained Non-Linear Optimization Problems - Model Predictive Control Example

I have an autonomous robotic swarm path planning/control problem where a set of "leader" robots have predefined (nontrivial) dynamics in the control set, and "follower" robots are ...
user avatar
0 votes
0 answers
18 views

Can Constraint Qualifications guarantee non-negativity of Lagrange multipliers for any first-order stationary points?

Let the problem $$\begin{cases} \min f(x) \\ \text{s.t.}\\ g_i(x) \leq 0 \end{cases}$$ and its Lagrangian: $\mathcal{L}(x, \mu) = f(x) + \sum_{i}\mu_i g_i(x)$. Consider a stationary point of the ...
user avatar
  • 115
0 votes
1 answer
52 views

how to show that the quadratic function strongly convex iff A positive definite and parameter min eigenvalue?

I have the following question: Show that the quadratic function $$f(x) = x^T Ax+2b^T x+c$$ with $$A = A^T ∈ R^{n×n}, b ∈ R^n, c ∈ R$$ is strongly convex if and only if $$A ≻ 0$$, and in that case the ...
user avatar
0 votes
0 answers
36 views

Large number of absolute value expressions in constrained, non-convex optimization problem

Say I have a problem given by \begin{align} \min_{x\in\mathbb{R}^n} & \ ||g(x)||_1, \\ \text{s.t. } &z_i(x)+||c^{(i)}(x)||_1 \leq d_i, \ i\in\{1,...,N\}, \end{align} where $g:\mathbb{R}...
user avatar
  • 274
0 votes
0 answers
19 views

Lagrangian formulation of an optimization problem

I am a bit puzzled on how the constraints of a given optimization problem pass through the Lagrangian. Given, say, the following problem: \begin{align} (P) \qquad \inf_x \,\,\, f(x) \quad \text{such ...
user avatar
  • 2,119
0 votes
0 answers
33 views

The dual function of non-convex QP

I am trying to find the dual function of the follwoing non-convex QP \begin{equation*} \min \frac{1}{2}x^T Q x \\ Ax = b, 0\leq x \leq e \end{equation*} The Lagrangian function is given by \begin{...
user avatar
  • 31
2 votes
0 answers
95 views

Does ADMM promise to converge if there are binary variables in each agent's constraints?

As is stated in chapter 9 of Boyd et al.1, ADMM can be used as a heuristic method for solving non-convex problems. Here, my case contains binary variables and it is more special since the binary ...
user avatar
0 votes
0 answers
9 views

Is it possible to analytically partition a domain based on convexity/concavity?

while recently exploring (thinking about) possible new methods for global nonconvex optimization, I generated a question: Can a domain in R2 be analytically partitioned into convex and concave (with ...
user avatar
1 vote
1 answer
122 views

Fréchet derivative of the total variation norm for measures on a manifold

Let $\Theta$ be a compact $d$-dimensional Riemannian manifold without boundary and $M(\Theta)$ (resp. $M_+(\Theta)$) denote the set of signed (resp. nonnegative) finite Borel measures on $\Theta$. ...
user avatar
  • 4,281
0 votes
0 answers
10 views

Uniqueness of non-convex optimization problem

For the following optimization problem,$$ \min f(x_i,y_i)= \sum_{i=1}^n[(x_i)^{4y_i} +(1-y_i )\ln (x_i) ] $$ subject to $$ D=\sum_{j=1}^n(p_j) $$ $$ x_i = \sum_{j=1}^m (a_j \cdot p_j)$$ Decision ...
user avatar
  • 1
0 votes
1 answer
38 views

Lagrange function and strong duality in an optimization problem

Suppose we have an (not necessarily convex) optimization problem : $$\begin{split}\min_x f_0(x)\\ f_1(x)\leq 0. \end{split}$$ Let $L(x,\lambda)=f_0(x)+\lambda(f_1(x))$. Then the above problem can be ...
user avatar
0 votes
0 answers
16 views

Transforming an unconstrained optimization problem into a two-step constrained optimization problems

I have the following problem: Problem 1: $\arg\min_{x,\vec{y}} g\left(\frac{f(x, \vec{y})}{\|\vec{y}\|}\right)\|\vec{y}\|$ where $g$ is monotonically increasing, $f$ is convex and $\|\cdot\|$ is some ...
user avatar
  • 1
0 votes
0 answers
8 views

Semi Definite Relaxation (SDR) Optimization

I want to optimize the function in the figure using Semi Definite Relaxation method, can anyone of you give me idea on how could i do so !
user avatar
4 votes
0 answers
35 views

Non-trivial example of a local optimum without satisfying Karush-Kuhn-Tucker (KKT) optimality conditions

I am looking for an example of a locally optimal point of the nonlinear program: $$\{ \min f(x) , g_i(x) \geq 0 \}$$ that does not have a singleton feasibility set. e.g. not the example of $\{ \min x, ...
user avatar
  • 115
0 votes
1 answer
36 views

Is there an "easy" way to find the minimum of $\frac{f(x) + g(y)}{x+y}$ where $f$ and $g$ are convex but $\frac{f(x) + g(y)}{x+y}$ is not?

Suppose I have a problem of the form $$min_{x \geq \epsilon, y \geq 0} \frac{f(x) + g(y)}{x+y}$$ subject to some (convex) inequality constraints and some affine equality constraints, and where $f$ and ...
user avatar
  • 1,482
0 votes
0 answers
60 views

How to check whether a point is inside the black regions or not?

I have a huge map which is similar to bellow, Problem: I want to find feasible path between two points in the map. Since size of map is huge it takes enormous time to calculate the path. The ...
user avatar
  • 139
0 votes
0 answers
37 views

Optimize a non-positive-definite quadratic form

Given vectors $a, b \in \mathbb{R}^d$, consider the following optimization problem in $x,y\in \mathbb{R}^d$. $$ \underset{x, y \in \mathbb{R}^d}{\text{maximize}} \quad x^\top y + a^\top x+b^\top y \...
user avatar
1 vote
0 answers
45 views

Converting a non-convex optimization problem into a convex one

I have this optimization problem to solve $$\begin{array}{ll} \underset{{\bf m},x}{\text{minimize}} & \| {\bf m} \|^2 \\ \text{subject to} & {\bf h}_k^\ast {\bf m} = x_k, \quad \forall k \\ &...
user avatar
0 votes
0 answers
7 views

How to run Difference of Convex Algorithm (DCA) in complex number field?

There's a function $f(\boldsymbol{x})=g(\boldsymbol{x})-h(\boldsymbol{x})$. $g$ and $h$ are all convex functions. To optimize the Difference of Convex functions, there's an algorithm called DCA [1]. ...
user avatar
0 votes
1 answer
51 views

Is there an analytical solution for the following optimization problem?

We need to solve the following least square problem $$\min_x (Y-Ax)^T(Y-Ax)$$ $$s.t. x^TA^TAx=1$$ in a closed form, where $Y \in \mathbb{R}^{n\times 1}$ and $A \in \mathbb{R}^{n\times n}$ are given. ...
user avatar
0 votes
0 answers
42 views

Convex objective but non-convex feasible set

I have an optimization problem of the form $$\min_{\boldsymbol{x\in \mathbb{R}^{n+1}_+}} f(x_0,x_1,\cdots,x_n)\\ \text{s.t. } \sum_{i=0}^{n} x_i \le C_1\\ g(x_0) \le C_2 $$ the objective $f(x_0,\cdots,...
user avatar
  • 2,829
2 votes
0 answers
33 views

nonconvex QCQP formulation

I am trying to solve a QCLP problem of the type \begin{equation*} \begin{aligned} & \underset{x,y}{\text{max}} & & \sum_xx_iU_i + \sum_yy_iVi \\ & \text{subject to} & & \frac{\...
user avatar
  • 21
0 votes
0 answers
24 views

How to convert coefficient of determination to a convex problem

I am trying to set the coefficient of determination as a constraint but I have trouble rewriting the CoD into a convex problem. In my problem y is a fixed variable, can I eliminate it?
user avatar
  • 101
2 votes
0 answers
58 views

Confused with a sufficient (and necessary?) condition (KKT?) for (local or global?) optimality in a nonconvex optimization problem

Let an optimization problem reads \begin{alignat}{2} \text{(P1)} \quad \text{minimize}_{x \in \mathbb{R}^{n \times 1}} \quad & f(x) \\ \text{subject to }\quad & g_m(x) \leq 0 \quad m=1,\...
user avatar
  • 579
1 vote
0 answers
22 views

Initial choice of lambda in Trust Region with indefinite Hessian

In the case where the Hessian, B, is indefinite, it is required that we find a $\lambda \in (-\lambda_1, \infty)$, s.t. $Q(\Lambda+\lambda \text{I})Q^T$ is definite, where $\lambda_1$ is the smallest ...
user avatar
3 votes
0 answers
63 views

Necessary conditions for unique minimum of quadratic functions over convex compact sets

I am curious if there are any results that give both sufficient and necessary conditions for having a unique solution to the quadratic optimization problem $$ min_{x} f(x)\\ \text{subject to }x\in K $$...
user avatar
  • 106
0 votes
0 answers
17 views

How to compute this expectation with Gaussian term and how to compute the eigenvalue?

Now i am doing the problem called phase retrieval. People take it as a non-convex optimization. They use a way called spectrum initialization method to initialize the value. The detail is in the paper ...
user avatar
  • 41
1 vote
1 answer
34 views

Which is better for optimization, tight inequality constraint or equality constraint?

I have a constrained optimization problem, $$ \min_x f(x) \quad\mathrm{s.t.}\quad g(x)\leq0. $$ The feasible region of this optimization problem is a convex set. I can prove that the optimal solution ...
user avatar
1 vote
1 answer
72 views

Move optimization constraint into objective by reformulating

I have an optimization problem roughly of the form $$ \max_{\mathbf x} f(\mathbf x) \quad \text{s.t. } g(\mathbf x) \leq 0$$ where $f(\mathbf x)$ is convex and $g(\mathbf x)$ is convex in $x_i$, $i\in\...
user avatar
  • 123
0 votes
1 answer
42 views

Optimal way to pour cups of water into buckets

Say that I have $n$ cups and that the $i$-th cup contains $c_i$ ml of water, where $c_i$ is some non-negative but not necessarily integer number. Also denote the total volume of water as: $V=\sum_i^n ...
user avatar
0 votes
2 answers
80 views

Showing that $x^*(t)=\sin(t)$ minimizes the functional $J(x(t)) = \int_0^{\pi/2} [\dot x(t)^2 - x(t)^2 ]dt$

We are given the functional $$J(x(t)) = \int_0^{\pi/2} [\dot x(t)^2 - x(t)^2 ]dt$$ with the fixed boundary condition $x(0)=0$ and $x(\frac{\pi}{2})=1$. Could anyone help me prove that $x^*(t)=\sin(t)$ ...
user avatar
  • 21

1
2 3 4 5
12