Skip to main content

Questions tagged [convex-optimization]

Convex optimization, a subfield of optimization, studies the problem of minimizing convex functions over convex sets. The convexity property can make optimization in some sense "easier" than the general case - for example, any local minimum must be a global minimum.

Filter by
Sorted by
Tagged with
2 votes
1 answer
37 views

Modeling $-\ln(1 - w \cdot \sigma(x))$ as disciplined convex programming

Given $0 < w \leq 1$, I would like to use the function: $$ -\ln(1 - w \sigma(t)), $$ where $\sigma(t) = 1 / (1 + \exp(-t))$ is the sigmoid function, in my objective. It's a bit tedious, but this ...
Alex Shtoff's user avatar
1 vote
1 answer
64 views

How is this function piece-wise linear?

I encountered this lemma in a research paper related to End-to-End inventory management model. Please note that $d_{[t_1,t_2]} = \sum_{t=t_1}^{t_2} d_i$, where $d_t$ denotes demand at time instance t. ...
Abhilash Mishra's user avatar
0 votes
0 answers
39 views

Time complexity of QP solver

Could you suggest any papers or other resources that report the computational time complexity (e.g., O(n^3)) of the OSQP solver for Quadratic Programming (convex optimization), or at least the ...
Enk9456's user avatar
  • 11
0 votes
1 answer
101 views

Minimal example using MOSEK API in python

I want to solve (simplified version) \begin{equation*} \begin{aligned} & \underset{}{\text{find}} & & X\in\mathbb{S}^{n}_{+}, x \in \mathbb{R}^{m}, \nu \in \mathbb{R}, \lambda\...
BasicUser's user avatar
  • 101
1 vote
1 answer
63 views

Inconsistent solutions to linear optimal control problem

Consider the following optimal control problem: \begin{align} J(t) = \inf_{u(t)} \ & \frac{1}{2} \int_0^\infty e^{-\delta t} \left( x(t)^2 + \lambda y(t)^2 \right) dt \\ s.t. \ &u(t) \geq - \...
NC520's user avatar
  • 123
0 votes
0 answers
24 views

Understanding different norms in the p-Wasserstein distance

The generalized p-Wasserstein distance, for $p\geq 1$, is given by $$d_W(Q_1,Q_2):=inf \left\{\int_{\Xi_2}||\xi_1-\xi_2||^p \Pi(d\xi_1,d\xi_2)\right\}$$ where $\Pi$ is the joint distribution of $\xi_1$...
Lyft's user avatar
  • 1
1 vote
1 answer
88 views

How to do the scaling to remove bias in QP problem?

I have a MIQP problem as below minimize $$\min {\bf x}^T{\bf Qx}-{\bf c}^T{\bf x}$$ ${\bf x}$ is a binary variable. The range of values in ${\bf Q}$ and ${\bf x}$ are quite different. The elements of $...
KGM's user avatar
  • 2,377
2 votes
1 answer
122 views

How to model the constraints of min and max in cvxpy

I have a continuous variable $x_{ij}\in[0,1]$ and I need to write the following constraint: $$M_i-m_i+1\leq C_i$$ where $M_i=\max\{j: x_{ij}>0\}$ and $m_i=\min\{j: x_{ij}>0\}$
zdm's user avatar
  • 403
3 votes
0 answers
38 views

Is the following constraint a second-order cone constraint?

We all know that the following constraint is called second-order cone constraint $$ \|Ax + b\|_2 \leq c^T x + d $$ where $x \in \mathbb{R}^n$, $A \in \mathbb{R}^{(k-1) \times n}$, $b \in \mathbb{R}^{k-...
Kaiming Zhang's user avatar
0 votes
1 answer
104 views

How to model this constraint in a better way?

I have a resource allocation problem. There are $M$ users and $N$ resources (machines). One user can be assigned to multiple resources/machines. But maximum $B$ machines can be activated at a time for ...
KGM's user avatar
  • 2,377
2 votes
1 answer
81 views

Is the linearization with first-order Taylor approximation correct?

I have a QP problem as $\min \hspace{2mm} x^TQx-c^Tx$ here $x$ in binary I want to transform it into a MILP by writing the objective function as $\min \hspace{2mm} z-c^Tx$ and then adding a constraint ...
KGM's user avatar
  • 2,377
1 vote
1 answer
51 views

Why is there a separate area for PSD constraints and PSD variables in the Conic Benchmark Format?

This question pertains to the Conic Benchmark Format (CBF) for specifying a convex optimization problem. Here's a link to the specification. In the CBF specification, there are separate areas for ...
Robert Bassett's user avatar
2 votes
1 answer
113 views

Approximating a convex program

As I understand it, "approximating" a convex program usually refers to finding a solution that is approximately-feasible approximately-optimal. For example, in the book "Geometric ...
eden hartman's user avatar
0 votes
0 answers
40 views

Projection of QP problem solved with Gradient Descent

Lets say we have a QP problem as shown below $$\min {\bf x}^T {\bf R}{\bf x}+{\bf c}^T{\bf x}$$ subject to $${\bf A_{eq}x}={\bf e}_{eq}$$ $${\bf Ax}\le {\bf e}$$ $${\bf x}\in \lbrace 0,1\rbrace$$ ${\...
KGM's user avatar
  • 2,377
2 votes
1 answer
213 views

How to transform a binary QP into an MILP?

I have a binary quadratic problem with objective ${\bf{x}}^T{\bf{Qx}}+{\bf{c}}^T{\bf{x}}$ subject to ${\bf{A}}{\bf{x}}\le{\bf{b}}$ ${\bf{A}}_{eq}{\bf{x}}={\bf{b}}_{eq}$. here ${\bf{x}}$ is binary. ...
KGM's user avatar
  • 2,377
0 votes
1 answer
66 views

Does strong duality hold for this semidefinite program?

$\DeclareMathOperator{\Tr}{Tr}\DeclareMathOperator*{\argmax}{\arg\!\max}$Consider the following semidefinite program (SDP) $$ \begin{aligned} \max_V \quad & \Tr(V) \\ \textrm{s.t.} \quad & \...
mhdadk's user avatar
  • 639
1 vote
1 answer
121 views

How can I convert this semidefinite program into standard form?

$\DeclareMathOperator{\Tr}{Tr}\DeclareMathOperator*{\argmax}{\arg\!\max}$Consider the following semidefinite program (SDP) $$ \begin{aligned} \min_V \quad & \Tr(V) \\ \textrm{s.t.} \quad & AVB ...
mhdadk's user avatar
  • 639
1 vote
0 answers
101 views

Converting a Linear Program with TU Constraint Matrix to a Nonlinear Convex Model: Solver Performance?

I'm currently working on a large Mixed Integer Program (MIP) where the constraint matrix is Totally Unimodular (TU), allowing me to model it as a Linear Program (LP) for efficiency, as total ...
graphtheory123's user avatar
2 votes
0 answers
161 views

Global optimizers handling minimization of an expression arising from the likelihood of a multivariate normal

I am interested in converting the following optimisation problem into a form that an exponential cone and/or SDP solver such as MOSEK can handle. This is a multivariate version of the question I ...
cfp's user avatar
  • 259
0 votes
0 answers
44 views

Can ADMM be applied to "latently coupled" variables?

I've been studying a paper where the authors employ the ADMM in a way that has left me somewhat perplexed. The paper focuses on addressing a robust principal component analysis (RPCA) problem, ...
Piko Mone's user avatar
0 votes
0 answers
25 views

Differences between non-convex and convex optimization problem with l0-Norm Regulization

I'm currently in the process of writing my bachelor's thesis and trying to deal with the theory behind the model in this paper Risk-calibrated Super-sparse Linear Integer Model (Berk Ustun and Cynthia ...
user13121's user avatar
5 votes
2 answers
175 views

Global optimizers handling minimization of expressions like $\log{v}+\frac{1}{v}$

Consider the simple problem of maximum likelihood estimation of the variance of a mean zero normal distribution. The expression to be minimised is: $$N \log{v}+\frac{1}{v}\sum_{n=1}^N{b_n^2},$$ where $...
cfp's user avatar
  • 259
2 votes
1 answer
140 views

Is it possible to show that this problem is convex?

$\DeclareMathOperator{\Tr}{Tr}\DeclareMathOperator*{\argmax}{\arg\!\max}$Consider the following problem $$ \begin{aligned} \min_x \quad & \Tr(WF(x)) \\ \textrm{s.t.} \quad & 0 < x \leq 1 \...
mhdadk's user avatar
  • 639
1 vote
1 answer
130 views

Which combinations of python modeling libraries and solvers support logarithmic objective functions?

As I understand it, if a modeling library (pyomo, amplpy, cvxpy, etc.) allows one to define a logarithmic objective function a solver may not support it. And even if a solver does support a ...
Nick Laws's user avatar
3 votes
1 answer
132 views

How is semidefinite programming a special case of convex programming?

In this image from Wikipedia, semidefinite programming is presented as a special case of convex programming. I do not see how this can be. Consider the following two constraints (where $\succeq$ means ...
Erel Segal-Halevi's user avatar
0 votes
1 answer
53 views

Lagrange multiplier associated to an active inequality constraint

Why is the Lagrange multiplier associated to an active inequality constraint is positive. How can we see this from the KKT conditions?
DSPinfinity's user avatar
0 votes
1 answer
89 views

How is this problem quasi-convex?

I'm currently reading the following paper B. Sinopoli, L. Schenato, M. Franceschetti, K. Poolla, M. I. Jordan, and S. S. Sastry, “Kalman filtering with intermittent observations,” IEEE Transactions ...
mhdadk's user avatar
  • 639
3 votes
3 answers
922 views

Do convex quadratic problems always have sparse solutions?

It is known that a feasible bounded linear program with $m$ constraints always has a solution with at most $m$ non-zero variables (a basic feasible solution). Since the number of constraints might be ...
Erel Segal-Halevi's user avatar
2 votes
2 answers
140 views

Can the following problem be solved recursively?

Consider the following problem \begin{equation} \begin{aligned} \min_{x,y,z} \quad & \sum_{i=0}^1 \sum_{j=0}^1 \sum_{k=0}^1 a_{ijk} \cdot f_{ijk}(x,y,z), \\ \textrm{s.t.} \quad &...
mhdadk's user avatar
  • 639
2 votes
1 answer
172 views

Convexity of p power of the q norm (0<p<1, q>1)

I encountered a minimization problem involving the following function: $f(\mathbf{x})=\|\mathbf{x}\|_q^p$ Here, $q>1$ and $0<p<1$. Naturally, each entry of $\mathbf{x}$ is greater than $0$. I ...
Piko Mone's user avatar
0 votes
1 answer
154 views

Bilinear programming

Let us assume I have an optimization problem as follows: The first feasible region is an ellipsoid, meaning that a and b belong to a known ellipsoid. The second feasible region is polyhedral (a set ...
naghi pakdaman's user avatar
0 votes
0 answers
76 views

Solving a max-min convex optimization problem with interior-point methods

I would like to solve the following problem: \begin{align} \text{ minimize } && t \\ \text{ subject to } && f_i(x) - t \leq 0 \text{ for all $i\in 1,\ldots,n$,} \\ && 0\leq ...
Erel Segal-Halevi's user avatar
2 votes
1 answer
104 views

Basic question about definition of a convex optimization problem

In lecture notes by Nemirovsky and BenTal (2023), I found the following definition of a convex optimization problem: MY QUESTION: why do we need both the functions $f_i$ and the domain $G$? ...
Erel Segal-Halevi's user avatar
2 votes
2 answers
162 views

How can I relax the equality constraint in this problem?

Consider the following problem \begin{equation} \begin{aligned} \min_{x,y} \quad & f(x,y), \\ \textrm{s.t.} \quad & \exp(x) + \exp(y) = 1 \end{aligned} \tag{1} \end{...
mhdadk's user avatar
  • 639
1 vote
0 answers
65 views

transform minimize weighted sum of absolute value into a linear optimization

For example, we have an optimization problem $$ \min \sum_{i=1}^{n} |w_{i} - a_{i}| b_{i} \quad \text{s.t.} \quad \sum_{i=1}^{n} c_i w_i = 0 $$ and $a_i, b_i, c_i$ are given. How to convert it into a ...
Pique's user avatar
  • 11
1 vote
0 answers
56 views

Convex programming without a lower bound on the feasible region size

I need to solve a convex minimization problem of the form: minimize $f(x)$ such that $g_i(x)\leq 0$, where the $g_i$ are convex functions given by a value oracle. As far as I know, to use the ...
Erel Segal-Halevi's user avatar
0 votes
1 answer
98 views

Convex approximation of an expression with fraction for CVX

I have the optimization problem $$\underset{\mathbf{x} \in \Bbb C^N}{\max} \left| \frac{\mathbf{x}a-b}{\mathbf{x}c+b} \right|^2$$ where $a$, $b$ and $c$ are some scalars. I want to solve this ...
Muhammad's user avatar
1 vote
0 answers
273 views

MOSEK via fusion vs API vs CVXPY

In Python, I would like to solve a collection of problems, that are all solvable via MOSEK's conic optimization solvers (ExpCone, SOCP, etc.) I have tried CVXPY. I get very robust and reliable results,...
independentvariable's user avatar
0 votes
1 answer
278 views

Convex approximation of an expression

I am trying to transform an expression given by $$ \operatorname{trace} \left( {\bf{X} } \right) + \left( \sum_{n=1}^N \mathcal{R}(x_n) \right) $$ into convex from where $\mathbf{x}$ is complex in ...
Muhammad's user avatar
1 vote
0 answers
58 views

Distributionally Robust Stochastic Programming - Help with derivation

I've been working through this book on robust optimization of electric energy systems, and in particular chapter 4 on distributionally robust optimization. In following the derivation of section 4.2.1....
asfiwefewrno's user avatar
5 votes
0 answers
550 views

How to write this objective in CVXPY for quasiconvex programming?

I have the following objective that I want to maximize: \begin{equation} \max_{U_T\in \mathbb{R}, x\in\mathbb{R}^T} J_\alpha(U_T) = \frac{\alpha}{\alpha-1}\log\left(\frac{\cosh(U_T)}{\cosh(\alpha U_T)^...
Uomond's user avatar
  • 86
2 votes
0 answers
38 views

I need help with finding a library or tutorial to parallel optimize given a black box function, assuming it's convex

I have a black box function to optimize with respect to 1-D input,$\beta$, and I also have other inputs, which I don't need to optimize, say (x,y). So, I need to optimize f($\beta$, x,y) over $\beta$. ...
Thiha Aung's user avatar
2 votes
0 answers
98 views

log-log regression as reward function in optimization problem

Consider the model $\hat{y}_t = e^{\text{trend} + \text{seasonality}} \prod_k^K x_{k, t}^{b_k}$ where $K$ denotes different investment alternatives. You can think that trend and seasonality are ...
pete lewis's user avatar
2 votes
1 answer
244 views

Quadratic optimisation with $\ell_1$ constraints with CVXPY

Crossposted on Mathematics SE I seek to minimize a convex quadratic objective subject to linear and $\ell_1$-based equality constraints. When I turn to CVXPY, an error is raised indicating that it ...
jam123's user avatar
  • 21
1 vote
2 answers
87 views

Relaxing non-affine equality constraints in convex optimization

Consider the convex function $f$. In section 4.2.1 in these lecture notes, the author writes: 4.2.1 Relaxing non-affine equality constraints For functions $g_i(x)$, $i \in \{1,\dots,d\}$ that are ...
mhdadk's user avatar
  • 639
1 vote
0 answers
53 views

What is the use of solvers that return approximately-feasible solutions?

Common methods for solving convex programs return solutions that are only approximately-feasible solutions. Here is an example (from lecture notes by Nemirovski on interior-point methods for convex ...
Erel Segal-Halevi's user avatar
3 votes
1 answer
67 views

Finding a starting ellipsoid and a minimum volume to approximate a convex optimization problem

Suppose we have a convex optimizatiom program: \begin{align} \min &\quad f_0(x)\\ s.t. &\quad h_i(x) = 0 && i=1,\ldots, p\\ &\quad g_i(x) \leq 0 && i=1,\ldots, m\\ &\...
eden hartman's user avatar
3 votes
1 answer
84 views

Is it possible to make a posynomial concave using a change of variables?

Note: this question was already posted on Math.SE but received no answers, so I'm re-posting it here for better reach. Consider the following posynomial with respect to the variables $x_1,\dots,x_n$: ...
mhdadk's user avatar
  • 639
0 votes
1 answer
93 views

Algorithms for maximizing the sum of power functions with linear constraints?

I’m working on an optimization problem that arises from maximizing the return obtained from investing in different marketing levers. The return from each lever exhibits diminishing returns, and is ...
Carlos Zanini's user avatar
3 votes
0 answers
54 views

Are there algorithms for minimizing a sum of convex and non-convex/non-concave functions?

Consider the problem \begin{equation} \begin{aligned} \min_{x} \quad & f(x) + g(x), \\ \textrm{s.t.} \quad & x \in X \end{aligned} \tag{1} \end{equation} where $X \subset \...
mhdadk's user avatar
  • 639

1
2 3 4 5