Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [convex-optimization]

A convex optimization problem consists of either minimizing a convex objective or maximizing a concave objective over a convex feasible region.

Convex Optimization is a special case of mathematical optimization where the feasible region is convex and the objective is to either minimize a convex function or maximize a concave function. Linear Programming is a special case. Convex Optimization problems as a class are easier to solve numerically than general mathematical optimization problems.

The following problems are all convex minimization problems, or can be transformed into convex minimizations problems via a change of variables:

  • Least squares
  • Linear programming
  • Convex quadratic minimization with linear constraints
  • Quadratic minimization with convex quadratic constraints
  • Conic optimization
  • Geometric programming
  • Second order cone programming
  • Semidefinite programming
  • Entropy maximization with appropriate constraints
7419 questions
1
vote
1 answer

Understanding Lagrangian for LP

From Boyd & Vandenberghe's Convex Optimization: While it is rue that a linear function is bounded below only when it is ZERO, in the highlighted part didn't we ignored the constrained that $x \succ 0$? Why? If x is all positive than minimum value…
user1953366
  • 191
  • 7
1
vote
0 answers

Understanding dual characterization of minimal elements

From Boyd & Vandenberghe's Convex Optimization: where Fig 2.25 is: I have two questions (First para makes sense to me): Q1: The first line of second para describes what it means for $x$ to be minimal. I am confused what is $K$ here? It seems that…
user1953366
  • 191
  • 7
1
vote
0 answers

composition generalized to K-convexity

I am self-studying Convex Optimization by Boyd and Vandenberghe. I am currently at page 111 where the author states: If $g : R^n → R^p$ is K-convex, $h : R^p → R$ is convex, and $\tilde{h}$ (the extended-value extension of h) is K-nondecreasing,…
Daniel
  • 11
1
vote
0 answers

Artin's vanishing theorem: a line restricts to a circle in order to calculate critical points

Two different ways of calculating critical points are given from the formulas (I hand wrote them at a class so it's not 100% the formulas but they're close): $(-1)^{dim} \mathcal{X}(X)$ = # of critical points of the product…
Priocapybara50
  • 53
  • 4
1
vote
0 answers

Convexity of a function.

I am interested in this function: $$ y(\boldsymbol{v})= \left\| ~~~\begin{array}{l} (\boldsymbol{v} - \boldsymbol{a}_{1} )^{T} \boldsymbol{v} \\ (\boldsymbol{v} - \boldsymbol{a}_{2} )^{T} \boldsymbol{v} \end{array}~~ \right \|^{2}， $$ where…
holloh
  • 11
1
vote
1 answer

Is the conjugate function of a strictly convex function continuously differentiable?

I saw a claim that for function $f$ which is strictly convex, we know that $f(z) - y^Tz$ has a unique minimizer over $z$ and it must be $\nabla f^{*}(y)$. It would be $\nabla f^{*}(y)$ instead of $\partial f^{*}(y)$ only if $f^{*}(y)$ is…
QualsPassed
  • 101
1
vote
0 answers

Harvard Cutting Planes Algorithm

Given two formulations P1 and P2 for the same integer programming (IP) problem, where Pi denotes the formulation for a problem and the corresponding polytope. We say that P1 is a stronger formulation than P2 if P1 ⊂ P2. Why do we prefer stronger…
user207558
  • 98
1
vote
0 answers

a resource allocation optimization problem

I have the following optimization problem: \begin{equation} \begin{aligned} \max_{\vec{\alpha}} \quad & \sum_{i=1}^{M}\alpha_i f_i(\alpha_i)\\ \textrm{s.t.} \quad & \sum_{i=1}^{M} \alpha_i = \alpha \\ &\alpha_i \geq 0, i = 1,2,\ldots,M …
Xuhong
  • 11
1
vote
0 answers

Can someone help me derive the inequality?

Consider the function $g(a) = \frac{1}{2}a^TQa-b^Ta$ Suppose we have the number condition of Q which is defined as $τ=\frac{v_n}{v_1}$ where $v_n$ is the largest eigenvalue and $v_1$ is the smallest eigenvalue. How can we show…
Blake
  • 107
1
vote
1 answer

Optimality Condition in Convex Optimization

$f(x)\in C^1(D)$ is convex. $D\subset\mathbb{R}^n$ is a closed and convex. Show that $x^*$ is a global minimizer of the problem $$ (P)\qquad\qquad\qquad \text{min}\{f(x):x\in D\} $$ if and only if $$ {\nabla f(x)}^T(x^*-x)\leq 0 \ \ \ \ \forall x\in…
Eric LAN
  • 21
1
vote
0 answers

How to prove convexity of this function?

How to prove convexity of this function?I want to prove the convexity of the following function: $f(\gamma)=$\begin{equation} \begin{aligned} log(\sum^{n+1}_{i=1} i^{-\gamma})-log(\sum^{n}_{i=1} i^{-\gamma}) \end{aligned} …
taiat
  • 1,137
1
vote
1 answer

Can this convex optimization problem be done in polynomial time?

Let $f:[0,1]^N\rightarrow \mathbb{R}$ be a convex function. I am trying to understand whether is it possible to find an optimal solution to the problem. What is known about the problem: Evaluating $f$ at any point can be done in polynomial…
RandomAsker889
  • 11
  • 1
1
vote
1 answer

Projection onto a convex

I am implementing a projected gradient ascent technique. I suspect that the projection is computable in closed form but I am not able to derive it. The projection can be formulated as $$ \min_x \|x - x_0\| $$ $$\text{s.t.}\quad x^\intercal B x \leq…
Sam
  • 357
1
vote
0 answers

Interpretation of Lagrange Multiplier with Absolute Value Constraint?

I'm working on a problem where $N$ agents want to trade $M$ goods. Each agent $j$ has an initial allocation of goods $\omega_j = (\omega_{j1},...,\omega_{jN})$, and---through trade---ends up with a final allocation $C_j = (C_{j1},...,C_{jN})$. Each…
Asterix
  • 567
1
vote
2 answers

How are linear programs always convex?

In Convex Optimization by Boyd, it is stated that Since any linear program is therefore a convex optimization problem, we can consider convex optimization to be a generalization of linear programming. An optimization problem is called linear, if…
willtryagain
  • 13
1 2 3
…
24 25