Skip to main content

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
0 votes
0 answers
4 views

Non-convex programming

I want to solve a non-convex optimization problem of the form : \begin{array}{cl} \displaystyle \min_{x} & f(x)\\ \textrm{s.t.} & c(x) = 0,\\ \end{array} where $f$ is a concave smooth function ...
Ramufasa's user avatar
1 vote
0 answers
64 views

Converting $x^3$ Optimization to an Equivalent LP Problem

Suppose we want to find the minimum of a a strictly increasing function $f: [-a, a] \to \mathbb{R} $, for some $a > 0$, which is also concave in $[-a, 0]$ and convex in $[0, a]$ (exactly like the $...
Apostolos's user avatar
1 vote
1 answer
43 views

Co-ordinate ascent update for $B$

I want to solve the optimization problem by getting the update step for: $\tilde{B} = \arg \max_{B} \{-\text{tr}(M^{T}M \Omega) + \sum_{j=1}^{p} \sum_{k=1}^{q} \text{pen}(\beta_{jk}|\theta)\}$ where $...
Maths Freak's user avatar
1 vote
0 answers
58 views

How to set up a convex concave procedure for the minimization of $abc$?

From this post, it seems that there are a lot of advantage of approximating nonconvex problem with the convex concave procedure. Out of curiosity, suppose that I have a simple problem that is $\begin{...
Tuong Nguyen Minh's user avatar
2 votes
0 answers
20 views

Maximizing a semi-concave function

A function $f:\mathbb{R}^d\to\mathbb{R}$ is called semi-concave if $x\rightarrow f(x)-\frac{\lambda}{2}\|x\|^2$ is concave for some $\lambda>0$. Suppose I want to maximize a function $f$ which is ...
Jay's user avatar
  • 301
0 votes
0 answers
15 views

Question on the Necessity of $Q_U Q^\top _U$ in Norm Calculation (from a semidefinite optimization).

I've been reading a paper titled "S. Bhojanapalli, A. Kyrillidis, and S. Sanghavi, Dropping convexity for faster semi-definite optimization, in Proc. Conf. Learn. Theory, 2016, pp. 530–582 (https:...
happyman's user avatar
0 votes
0 answers
19 views

Can changing Gradient Descent step size/learing rate from constant 1/L to Armijo or exact line search change the convergence rate?

If instead of the classical $1/L$ constant step size we have adaptive step sizes chosen with exact line search or Armijo (let's say) can this alter the Big-O complexity of the convergence rate? Here: ...
ufghd34's user avatar
  • 81
0 votes
0 answers
63 views

Suggest a method to minimize non-linear function

in my program I need to minimize two following separate functions in real-time (initial approximations $(x_0, y_0)_i, i\in\overline{1, n}$ are given, all other letters represent constants which are ...
dimkky's user avatar
  • 1
0 votes
0 answers
57 views

How does McCormick envelope work for inequality constraints?

I have a question regarding the McCormick envelope in mathematical optimization. The McCormick envelope allows to create a convex relaxation for a bilinear term. Given the bilinear constraint $w = x \...
Michael's user avatar
  • 53
0 votes
0 answers
28 views

Is it possible to convexify the inequality constraint $z \leq x^3 \cdot y$?

Is there a way to convexify the inequality constraint $z \leq x^3 \cdot y$ in a nonlinear optimization problem with $x, y, z$ being nonnegative variables?
Michael's user avatar
  • 53
0 votes
1 answer
43 views

Correctly understand the implication of approximation ratio for the set cover problem?

I am currently reading this wikipedia article about the set cover problem and it said here that "it cannot be approximated to $\left[ {1 - o\left( 1 \right)} \right]\ln \left( n \right)$ unless $...
Tuong Nguyen Minh's user avatar
0 votes
1 answer
46 views

Matrix subset selection

We aim to select rows and columns of any matrix $\mathbf{A}\in\mathbb{R}^{m\times n}$. Define a selection matrix $\mathbf{S}\in\mathbb{R}^{m\times n}$ where $S(i,j)=x_i \cdot y_j$, the matrix after ...
Hao WANG's user avatar
1 vote
1 answer
53 views

Is it possible or practical to just solve integer optimization problem by penalizing?

I am an engineer who is currently working in network optimization problem. I have finised my master degree a long time ago. During my studies I have learnt about the penalty technique to turn a ...
Tuong Nguyen Minh's user avatar
1 vote
1 answer
59 views

Reformulating Mixed-integer Bilevel program into MINLP

I am working on a problem where I have this Bilevel programming problem: $ Max \quad a+b $ $s.t.\quad \quad \alpha \in \{0, 0.5, 0.8\} $ $\quad \quad \quad \; \ a = min \ \lambda$ $ \quad \quad \; \ ...
frgoe's user avatar
  • 51
1 vote
1 answer
66 views

Assessing the Convexity of an Optimization Problem

I am trying to analyze the following optimization problem Objective Function: The objective is to maximize the total yield (alloc_yield) obtained from allocating assets to different pools. $$\text{...
Muhammad Adeel Zahid's user avatar
0 votes
0 answers
69 views

Conditions for convergence of gradient flow/descent with non-isolated critical points

I am trying to show the convergence of gradient flow for a function $f(x(t))$ where $\frac{d}{dt}(x(t)) = -\nabla_x(f(x))$ which will be some polynomial in $x(t)$. $f$ is the square of a 3rd degree ...
kik lik's user avatar
2 votes
0 answers
39 views

Can the following optimization problem be reformulated into a standard form convex problem?

I have the following optimization problem given: $$ \begin{aligned} \max \quad & E \cdot p - c_A * A - c_h * h - c_C * C \\ \textrm{subject to:} \quad & v \leq \log(h) \\ & E \leq v^3 \...
Michael's user avatar
  • 53
1 vote
2 answers
85 views

A simple constrained optimization problem

Let $v\in \mathbb{R}^n$. Define $E(v) = \sum_{i=1}^n (v_i^2-1)^2$ be the energy to be minimized. Define the constraint $\sum_{i=1}^n v_i = cn$. This means the average value of all $v_i$'s is $c$. ...
900edges's user avatar
  • 2,039
1 vote
1 answer
49 views

Finding the global minimum of a convex-like optimization problem

Given an optimization problem of the following form: $$ \begin{aligned} \min_{x \in \mathbb{R}^n} \quad & f(x)\\ \textrm{s.t.} \quad & g_i(x) \leq 0 \\ & h_j(x) = 0 \end{aligned} $$ with $...
Michael's user avatar
  • 53
0 votes
0 answers
20 views

Convexifying a Non-Linear Fractional Function

I am working on a problem that involves a non-convex, non-linear fractional function: $$ Y(X_1, X_2) = \frac{X_1 + X_2}{\alpha X_1 + \beta X_2} $$ Where $X_{1}$, $X_{2}$, $Y$ are decision variables ...
HarrisFatehein's user avatar
4 votes
1 answer
157 views

Bounding a sequence involving minimizers of strictly convex quadratic functions

Suppose that $H\succ 0$ and we have a sequence $\{x_j\}_{j\ge 1}$ such that each one is the unique solution of the following problem: $$ x_{j} = \text{argmin}_{x\in \mathbb R^n}(x-x_{j-1})^T\nabla f(...
Sam's user avatar
  • 366
0 votes
0 answers
17 views

Convexity of cubic affine and quartic affine?

I am a post graduate student who is currently study the subject of convex optimization. From my class I know that affine function is convex and also $x^r$ for $r>=1$ is convex for non-negative $x$. ...
Tuong Nguyen Minh's user avatar
1 vote
1 answer
56 views

Existence of a lower-bound for an interesting function!

Suppose that $$h(x,z):= (x-z)^T\nabla f(z)+\frac{1}{2}(x-z)^TH(x-z),$$ where $f$ is a smooth function in $\mathbb R^n$. Also, suppose $H\succ 0$ and $\|\nabla f(u)\|\le \gamma; \forall u\in \mathbb R^...
Sam's user avatar
  • 366
3 votes
2 answers
154 views

Why having a global convex upper bound is considered as an advantage for the convex-concave procedure?

I am reading this paper "Variations and extension of the convex–concave procedure" and on page 5/25, second paragraph, the authors state that "Another advantage of CCP is that the over ...
Tuong Nguyen Minh's user avatar
0 votes
0 answers
43 views

Are KKT necessary optimality conditions in general non-convex problems? (with non-zero duality gap)

I have seen similar questions here, but have not been able to clarify mine. KKT are necessary conditions for optimality if strong duality holds (Boyd and Vandenberghe, section 5.5.3). However, strong ...
joselo's user avatar
  • 1
2 votes
0 answers
37 views

Changing convexity by changing metrics

I was wondering if for a given functional $F$ on some space $X$, is it possible to construct explicit metrics $(X,d_1)$ and $(X,d_2)$ such that $F$ is convex w.r.t $d_1$ while $F$ is non convex w.r.t $...
Silentmovie's user avatar
1 vote
0 answers
22 views

Can a function be converted into a Voronoi diagram of its local extremum points and basins of convergence?

Let's say I know the position $e \in \mathbb{R}^N$ of a local extremum point of a non-convex function $f: \mathbb{R}^N \mapsto \mathbb{R}$. Is there an efficient method for finding $K$ closest "...
jordi's user avatar
  • 279
0 votes
0 answers
15 views

Generalizations of maximum theorem in parameterized optimization

I have a parameterized optimization problem \begin{eqnarray} \max_{x\in D(\theta)} f(x,\theta) \end{eqnarray} Here state space $\Theta=(0,1)$; constraint correspondence $D:\Theta\to (0,+\infty)$ is a ...
William Wang's user avatar
-1 votes
1 answer
73 views

What's the purpose of the KKT condition when first-order optimality condition exists?

Given a convex optimization problem $$\min f(x), x \in D$$ $f, D$ convex. The first-order optimality condition says $x$ is the minimizer if and only if $\nabla f(x)^T (x-y) \geq 0, \forall y\in D.$ ...
Shamisen Expert's user avatar
5 votes
1 answer
194 views

Optimality condition inspired by subdifferential of square root: $y\in \text{argmin}(g(x)-a^Tx ) \Rightarrow y\in \text{argmin}(g^2(x)-2g(y)a^Tx).$

Let $f:\mathbb R^d\to\mathbb R\cup\{+\infty\}$ be a proper convex lower semicontinuous function. Suppose that $f$ is bounded by below, and for simplicity that $\inf f = 0$. Set $\varphi:\mathbb R^d\to\...
Alberto's user avatar
  • 243
0 votes
1 answer
50 views

Variance of Concave Function

Let $X:=[X_1,\dots, X_n]$ be a random vector with $X_i \in (0,2)$ and having a joint distribution $F_X$. Take a constant vector $a:=[a_1,\dots, a_n]$ with $a_i \in [0,1]$ and $\sum_{i=1}^n a_i = 1$. ...
Fianra's user avatar
  • 1,248
4 votes
1 answer
355 views

Optimizing sum of a quadratic function and $l_1$ norm on a sphere

I am currently attempting to derive the dual and KKT conditions for the following optimization problem: \begin{equation} \min_{x\in \mathbb R^n} \quad x^TMx+a ||x||_1^2 \quad \text{subject to} \quad ||...
Sam's user avatar
  • 366
1 vote
0 answers
38 views

How to deal with the optimization problem with non-convex feasible set?

How to deal with the problem with non-convex feasible set. \begin{align} &({\rm P1})\ \underset{\bf x}{\min} f({\bf x})={\bf x}^T{\bf x}+{\bf f}^T{\bf x}\\ &{s.t.}\\ &\|{\bf x}-{\bf x}_z\|...
Cuz Taylor's user avatar
0 votes
0 answers
64 views

How to find vertices of intersection of two hyperplanes?

According to Shapiro and Wilk(1965) in lemma 3, $W$ has lower bound: $na_1^2/(n-1).$ To find this value, they solve the problem: $$Max\quad y'y$$ $$ s.t.\quad 1'y=0,\quad and\quad a'y = 1,\quad and \...
박원빈's user avatar
5 votes
2 answers
333 views

Maximization of Linear Least Squares with a Triangular Matrix over The ${L}_{2}$ Unit Ball

I have the following optimization \begin{align} \max_{\|x\|^2\le1} \|Lx - y\| \end{align} where $L$ is a lower triangular and $y$ is a given vector. Does it admit a closed-form solution? I am ...
Morad's user avatar
  • 547
0 votes
0 answers
39 views

Are there practical problems in optimization where its dual problem is computationally easier to solve?

In a class I learned that optimization problems can have "dual counterparts" For example, a problem of the type $$\min_{x} f(x) + g(x)$$ has a "Fenchel" dual problem: $$\max_{y} -f^...
Olórin's user avatar
  • 5,483
0 votes
0 answers
75 views

Minimizer of two matrix energies

I am looking for a solution $X \in \mathbb{R}^{n \times n}$ which minimizes the following energy: $$ \textrm{min}_X \| X A X^T - B\|^2 + \mu \|X \Lambda X^T - \Lambda \|^2 $$ where $A, B \in \mathbb{...
tommym's user avatar
  • 421
1 vote
0 answers
56 views

Smoothness of the Fréchet Function on Riemannian Manifolds

Suppose $M$ is a compact Riemannian manifold and let $d$ be the induced distance function on $M$. Let $\mu$ be a probability measure on $M$ with continuous density. The Fr$\acute{\mathrm{e}}$chet ...
Yueqi's user avatar
  • 11
0 votes
1 answer
35 views

what are the generic methods to prove solution existence!?

Suppose we are in $\mathbb R^n$ and consider $$\min f(x) \qquad s.t. \qquad x\in P.$$ Under what conditions on $f$ and $P$, we can guarantee this problem obtains a solution? The most generic ...
Sam's user avatar
  • 366
0 votes
0 answers
23 views

Constrained optimization for non-convex function.

I have a non-convex function say $f(x,y)$. I'm trying to find the minimum value of $y$ with $f(x,y)<0$ in the vicinity of some known starting point $p_0=(x_0, y_0)$ such that $f(x_0,y_0)<0$. ...
Kvothe's user avatar
  • 233
1 vote
1 answer
76 views

Is it possible to split the optimization problem into multiple sub problem if the objective function are product of univariate function?

I am a post graduate electrical engineering student who is working with some optimization. Particularly, the objective function of my problem has the form $\begin{array}{*{20}{c}} {\left( P \right)}&...
Tuong Nguyen Minh's user avatar
1 vote
1 answer
45 views

Is there any method that can optimize the problem whose regularizer is kurtosis term?

I recently worked on an optimization problem, whose regularizer $g(x)$ is kurtosis. The overall optimization formula is as follows. $$\begin{align} \arg \min_x \frac12 \Vert Ax-b\Vert_2^2 + \lambda g(...
Leung Joe's user avatar
0 votes
0 answers
30 views

Can this constraint be cast as a second order cone constraint?

Can someone please explain if it possible to convert the following constraint into a second order cone programming formulation: $xy \ge ay + b$ Here $x,y$ are non negative decision variables, $a,b$ ...
Tuong Nguyen Minh's user avatar
0 votes
1 answer
24 views

How to linearize or reformulate an implication constraint that implies that a decision variable belong to an interval?

I am an electrical engineer who is working in computer network and I need to model my delay with respect to a binary variable $x$ as folow $\left\{ {\begin{array}{*{20}{c}} {x = 1 \Rightarrow \left( {...
Tuong Nguyen Minh's user avatar
0 votes
0 answers
53 views

Dynamics of Loss in Homogeneous, Non-Smooth Models Using Clarke Subdifferential

tl;dr: Seeking insights on the application of Clarke subdifferential for analyzing the optimization differential inclusion with smooth objective and homogeneous model. I'm interested in its validity, ...
Zach466920's user avatar
  • 8,361
1 vote
2 answers
114 views

Proof or counterexample for the convergence of projected gradient descent with summable stepsizes

Suppose we want to solve the following optimization problem: $$ \min_{x\in\mathcal{X}\subset\mathbb{R}^n} f(x) $$ where $\mathcal{X}$ is closed and convex and $f$ can be nonconvex but still smooth. ...
Jason Li's user avatar
0 votes
1 answer
135 views

If $f$ and $g$ are functions with the same stationary points satisfying the PL Inequality does it hold for f + g?

The Polyak-Łojasiewicz (PL) inequality is an important condition in optimization, known for its role in analyzing convergence rates to global minima. It's given for a function $h$ as: $$ \frac{1}{2} \|...
njwfish's user avatar
  • 61
1 vote
1 answer
79 views

Writing a nonconvex program as a linear program

I want to write the following non-convex program $\texttt{P}_1$ as a linear program (LP) $$ \begin{align} \min_x \sum_i \frac{a_i^Tx+b_i}{c^Tx+d} \\\\ s.t. \ Ax \geq b \end{align} \tag{$\texttt{P}_1$}$...
abc's user avatar
  • 409
1 vote
1 answer
102 views

Single constraint quadratic optimization dual form expression using the Schur complement

Strong duality result for non-convex problem with two quadratic functions is a related question. However, I am trying to understand how the dual form problem comes about. This dual form ...
FXQuantTrader's user avatar
0 votes
0 answers
6 views

Which divergence or measure is more suitable for graph clustering application using symmetric NMF

Symmetric NMF is a well know tool used for graph clustering applications. Given a similarity matrix $X \in \mathcal{R}^{n\times n}$, symmetric NMF seek to factorize it into o production of the form $...
MathLearner's user avatar

1
2 3 4 5
14