Questions tagged [convex-optimization]

Question 1

I understand why the constraint $x_1 \geq 0$ in the primal, implies $p'A_1 \leq c_1$ in the dual in the presence of a constraint involving an $A$ and a vector $b$ in the primal ($A_1$ being the first ...

Question 2

I want some minimalistic/easy to remember statements that relate someone's willingness to solve an optimization problem with the strong duality property of that problem. Of course, you would only want ...

Question 3

Let $f:\mathbb{R}^N\to[0, \infty)$ be a non-convex function of $w\in\mathbb{R}^N$ for $N\in\mathbb{N}$. Suppose the entries in $w$ can be partitioned into two vectors $u\in\mathbb{R}^m$ and $v\in\...

Question 4

Let $f:\mathbb{R}^N\to[0, \infty)$ be a non-convex function of $w\in\mathbb{R}^N$ for $N\in\mathbb{N}$. Suppose the entries in $w$ can be partitioned into two vectors $u\in\mathbb{R}^m$ and $v\in\...

Question 5

In Section 5.2 of Boyd & Vandenberghe's Convex Optimization, the dual problem given a primal problem with only inequality constraint is, $$ \max \quad g(\alpha) \\ \text{ s. t.} \quad \alpha \...

Question 6

I am a network engineer currently studying optimization problems. Out of curiosity, I was fascinated by the fact that the Simplex Method has an exponential worst-case complexity, a property famously ...

Question 7

The following is an algebraic problem I encountered in my research direction. Let $x_1, \dots, x_n \ge 0 $ be non-negative real numbers satisfying $\sum\limits_{i=1}^n x_i = S,$ where $S \ge 0 $ is ...

Question 8

Hello — I’m implementing an active-set method to solve a convex quadratic min-cost flow problem as a project university (I’m studying Computer Science, not Mathematics) of the form: $min\{x^TQx + qx: ...

Question 9

In section $3.1$ of Introduction to Linear Optimization from Bertsimas and Dimitris, there's this figure given (represented in the image below) given as an example to illustrate that if a basic ...

Question 10

In this lecture, Professor Stephen Boyd begins to draw a commutativity diagram to raise the question of whether transforming a program with strong duality into an equivalent problem and computing its ...

Question 11

Let's consider a two-player finite strategic form game. Suppose $A$ is the payoff matrix for the row player playing mixed strategy $x$, $B$ is the payoff matrix for the column player playing mixed ...

Question 12

Consider a finite family $F=\{f_i\}_{i=1}^n$ of nonconstant linear functions $f_i(x)=m_ix+b_i$ (where $m_i$, $b_i$ and $x$ are real numbers). Is there a simple way to determine the index $I(x)$ such ...

Question 13

This is a refinement of the question Minimal representation of element in convex hull of $v_1,...,v_n\in\mathbb{R}^n$ Let $C$ a convex polyhedron in $\mathbb{R}^n$ and $v_1,..,v_k$ its extreme points ...

Question 14

Let $v_1,...,v_n\in \mathbb{R}^n$ linearly independent, $C=\mathrm{conv}(v_1,...,v_n)$ their convex hull and $x\in C$. Is there always a unique minimal representation of $x$ with respect to $v_1,...,...

Question 15

In a Linear Program, introducing non-negativity and/or non-positivity constraints into the Primal turns equality constraints into "regular inequality constraints" (a.k.a., inequality ...

Stack Exchange Network

Questions tagged [convex-optimization]

How to see $x_1\geq 0$ in the primal implies $p' A_1 \leq c_1$ in the dual, when there are no other constraints than just $x_1\geq 0$?

When does an optimization problem that is "worth solving" also satisfy strong duality?

Is there a numerical method for finding the critical points of constrained optimization problems? [closed]

Does block coordinate descent lead to a constrained critical point?

It seems that the definition of dual problem in Boyd & Vandenberghe does not apply to SVM

Does the Interior Point Method Solve Klee-Minty Cubes adversarial instances in Polynomial Time?

Minimizing $\sum\limits_{i=1}^n (x_i^3 - x_i^2)$ subject to $\sum\limits_{i=1}^n x_i = S$

Active set method applied on the min-flow problem

How come this example given in my book leave the feasible set in either of the sides of a certain direction ? Analytically it seems it is impossible

Graph of Optimization Problem Transformations

Are all finite games linear programs? Why is my formulation not correct?

Maximum of a family of linear functions

Minimal representation of element in convex polyhedron

Minimal representation of element in convex hull of $v_1,...,v_n\in\mathbb{R}^n$

Non-negativity and/or non-positivity constraints

Hot Network Questions