Optimization is the process of choosing the "best" value among possible values. They are often formulated as questions on the minimization/maximization of functions, with or without constraints.

learn more… | top users | synonyms (5)

1
vote
1answer
34 views

What is the easiest way to optimize the weighted sum of L2 norms?

I have the following cost function (solving for $M$ - the $x_i$s are known): minimize $\sum_i\sum_j(w_{ij} \cdot (x_i-x_j)^T\cdot M\cdot(x_i-x_j))$ ($w_{ij} \in [-1,1] $) subject to: $M \succeq 0$ (...
1
vote
1answer
15 views

Proof: $\underset{\|q\|=1}{\max} q^TAq = \lambda_{\max}$ with $q$ the corresponding eigenvector ($A$ symmetric)

This problem is quite old and there should be similar problems. I know the following technique: \begin{equation} \begin{aligned} q^TAq=q^TU\Lambda U^Tq=(U^Tq)^T\Lambda (U^Tq) \end{aligned} \...
1
vote
2answers
631 views

Absolute extrema

Find the absolute extrema of the function $f(x,y)=2xy-x-y$ over the region of the xy-plane bounded by the parabola $y=x^2$ and the line $y=4$ I was wondering if I needed to use Lagrange multipliers to ...
1
vote
1answer
41 views

Linear programming with a product term in the objective function

The title might sound a little weird. I actually want to ask if this problem can be solved as a LP. And if so, how to convert the product term? set $P=\{1,2,3,\ldots,n\}$ for index $i$. Variables $...
2
votes
1answer
67 views

Ideal shape for underwater habitat

Is there an analytic solution to this problem or do I need to compute a discrete approximation using a relaxation procedure - or something similar? I want to find the shape of a roughly spherical ...
1
vote
1answer
4k views

Linear programming vs. Integer programming

I was trying to solve a problem where I want to choose which items to choose where each item has a number b_i associated with it and a reward r_i associated with it. I need to choose items that ...
2
votes
0answers
36 views

Showing the integrality property for an Integer Linear Program

I am trying to figure out why solving a relaxed Integer Linear Program (ILP) always give an integral solution. The ILP can be summarized as: $$\min \sum_{t\in T} \sum_{s \in S} c_s k_s^t $$ subject to:...
0
votes
1answer
92 views

How to solve the coupled integer programming problem?

I have the following integer linear programming problem: $$\begin{equation*} \begin{aligned} & \underset{x}{\text{maximize}} && \sum_{k=1}^K\sum_{t=1}^Tx_{kt} \\ & \text{subject to} &...
1
vote
0answers
131 views

Is 0-1 integer programming always NP-hard?

I have the following problem. Maximize $\sum\limits_{m=1}^M\sum\limits_{n=1}^N x_{mn}$ subject to: $\sum\limits_{\substack{m^\prime=1\\ m^\prime \neq m}}^M\sum\limits_{\substack{n^\prime=1\\ n^\...
1
vote
0answers
226 views

Modeling propositional formulas in integer programming

Say I have an binary integer programming problem: \begin{equation*} \begin{aligned} & \underset{\mathbf{x,y}}{\text{minimize}} & & f_0(\mathbf{x,y}) \\ & \text{subject to} & &...
2
votes
1answer
22 views

Model cost for a state change in an integer program

I have a problem involving tool selection I am trying to model right now. (I am fairly new to this). I have a series of manufacturing operations I need to perform for $i \in \{1,\dots,n\}$. Each ...
1
vote
1answer
652 views

Find the shortest distance between $9x^2+9y^2-30y+16=0$ and $y^2=x^3$

Find the shortest distance between $9x^2+9y^2-30y+16=0$ and $y^2=x^3$. I know the shortest distance exists between the curves on the common normal line. Is there any other shorter way to attempt?
2
votes
4answers
126 views

What is the minimum value for $(\frac{1}{a}-1)(\frac{1}{b}-1)(\frac{1}{c}-1)$ if $a+b+c=1$ and $a,b,c\in\mathbb{R}^+$?

The primary question was: What is the minimum value for $(1-\frac{1}{a})(1-\frac{1}{b})(1-\frac{1}{c})$ if $a+b+c=1$ and $a,b,c\in\mathbb{R}^+$? $\color{red}{\text{But sorry guys! I messed it up! my ...
2
votes
4answers
67 views

Find the maximum of $U (x,y) = x^\alpha y^\beta$ subject to $I = px + qy$

Let be $U (x,y) = x^\alpha y^\beta$. Find the maximum of the function $U(x,y)$ subject to the equality constraint $I = px + qy$. I have tried to use the Lagrangian function to find the solution for ...
0
votes
0answers
11 views

Interpolate Initial step length for line search methods

I was learning interpolation techniques in initial step length guess. Below is an approach from Nocedal and Wright's book, Numerical Optimization. Interpolate a quadratic to the data $f(x_{k-1})$, $f(...
4
votes
1answer
722 views

Matlab: need help with optimization

Minimize the following objective function over $(x_1,x_2)$ $$f (x_1, x_2) := \exp(x_1) \, (4 x_1^2 + 2 x_2^2 + 4 x_1 x_2 + 2 x_2 + 1) + b$$ subject to the constraints $$x_1^2 + x_2 = 1 -...
2
votes
0answers
37 views

Minimize a huge two-variable logarithmic-trigonometric-radical expression (MSU entrance early July 2016)

Minimize \begin{align}R(a,x)&=\sqrt{13+\log_a\left(\cos\left(\frac xa\right)\right)^2+\log_a\left(\cos\left(\frac xa\right)^4\right)}+\sqrt{97+\log_a\left(\sin\left(\frac xa\right)\right)^2-\...
0
votes
0answers
13 views

How to find (GEV) distribution parameters with optimization?

I'm currently trying to replicate this study with python. http://pages.stern.nyu.edu/~sfiglews/Docs/RND_draft7.pdf The section I'm currently working on is between p.17-20 in the study. The study ...
0
votes
1answer
108 views

How can we find minimum of $f(x,y,z)?$

Let $k\in\mathbb{N}$ and $x,y$ and $z$ are positive real number such that $x+y+z=1$. How can we find minimum of $f(x,y,z)$ where $$f(x,y,z)=\frac{x^{k+2}}{x^{k+1}+y^{k}+z^{k}}+\frac{y^{k+2}}{y^{k+1}+z^...
2
votes
1answer
32 views

Finding $\min f(x)$ where $f(x)=\int_0^1 |t-x|t\,dt \quad \forall x \in \mathbb{R}$

Can I write the integral as $f(x)=\int_0^{x} |t-x|t\,dt + \int_{x}^1 |t-x|t\,dt$ so that $f(x)=\frac{2x^3-x}{2}+\frac{1-2x^3}{3}$ But here I'm restricting $x$ to the interval $(0,1)$ and I need $x$ ...
0
votes
0answers
10 views

Under which conditions discretization of convex\concave function is submodular?

Say, I have $f(x)$ with $x \in [0,1]$, then by discretization I mean $f(x_h)$ with $x_h \in \{0, h, 2h, \dots, 1\}$. I know about Lovasz extension, but it works in other way: given submodular ...
2
votes
2answers
162 views

Constant such that $\max\left(\frac{3}{3-2c},\frac{3a}{3-2d},\frac{3b}{3-2e}\right)\geq k\cdot\frac{2+3a+4b}{9-c-2d-3e}$

What is the greatest constant $k>0$ such that $$\max\left(\frac{3}{3-2c},\frac{3a}{3-2d},\frac{3b}{3-2e}\right)\geq k\cdot\frac{2+3a+4b}{9-c-2d-3e}$$ for any $0\leq b\leq a\leq 1$ and $0\leq c\...
1
vote
2answers
45 views

Optimization with L_infinity norm regularization

I'm trying to solve an optimization problem of the form $$\text{minimize } \; f(x) + \|x\|_\infty$$ where $x$ ranges over all of $\mathbb{R}^n$ and $f:\mathbb{R}^n \to \mathbb{R}$ is a nice, smooth, ...
0
votes
0answers
12 views

random pursuit without function evaluations

Assume we want to minimize a convex function $f(x)$ with $x\in \mathbb{R}^n$. Function $f(x)$ represents cost of a system which we cannot compute directly but can observe if system is at state $x$. My ...
4
votes
2answers
34 views

Find the highest point of intersection

Find the highest point of intersection of the sphere $x^2+y^2+z^2=30$ and the cone $x^2+2y^2-z^2=0$. Am I supposed to use the Lagrange multiplier for this? EDIT: So this is what I've tried... $z^2=...
0
votes
1answer
29 views

Find a minimum of a quantity

Let $n$ a positive integer. I have the following quantity: $$Q = 3205 \cdot 3^{i-1} + 64i + 64i(3^{i-1}-1)-64(3^{i-1}-1)-32\times3^{i-1}(2i-5)+3$$ I would like to find the integer $i$ which ...
0
votes
0answers
17 views

Solve $\max_{\lambda} \mathrm{sum} (\lambda \vec{u} \geq_c \vec{v})$

Let $\vec{u},\vec{v} \in R^n$ be known vectors. I want to find out the optimum scalar multiplier $\lambda$, to maximize the number of elements in $\lambda \vec{u}$ which are above $\vec{v}$. In other ...
3
votes
1answer
135 views

Minimize $\operatorname{tr}(X^TA^TAX(X^T(I-P)X)^{-1})$ by solving an eigenproblem?

My optimization problem is $$\min_X\operatorname{tr}(X^TA^TAX(X^T(I-P)X)^{-1}),$$ where $P$ is a projection matrix. I was told this could be solved as an eigenproblem: columns of $X^*$ (the solution) ...
1
vote
1answer
28 views

Properties on proximal term

If the equation $x_i$-subproblem showed below is not strictly convex $\arg \min_{x_i}=f_i(x_i)+\frac{\rho}{2}\|A_ix_i+\sum_{j\neq i}A_jx_j^k-c-\frac{\lambda^k}{\rho}\|_2^2$ Why adding the proximal ...
0
votes
1answer
68 views

Gradient descent and penalty method

I am seeking a minimum of a function under an inequality constraint. How can I set stop condition? The problem is that $\nabla f_p$ never goes to zero. The function: $$f(x_1, x_2)=\left(x_1 - 1\right)...
0
votes
1answer
100 views

Gradient descent in inequality constrained optimization problems

I want to solve an optimization problem using a gradient descent algorithm maximize $$ max \log( \frac{Ax + b}{ Cx + b} ) $$ $$s. t. \quad 0 \le x \le 1 $$ where x is a vector and the ...
2
votes
1answer
57 views

Optimize $\max _{x_1,x_2,…,x_N} N , \text{ s.t.} \sum_{i=1}^N f(x_i) \le a$

$Is there general theory for solving optimization problem of the following kind \begin{align} &\max _{x_1,x_2,...,x_N} N \\ \text{ s.t.}& \sum_{i=1}^N f(x_i) \le a\\ &\sum_{i=1}^N g(x_i) \...
1
vote
1answer
29 views

argmin as projection in the dual averaging algorithm

I am struggling to understand the dual averaging algorithm as presented in this paper. More precisely the update of the parameters given as $$\Pi^\psi_\chi (z,\alpha) := \operatorname{argmin}_{x \in \...
1
vote
2answers
53 views

Optimization with box constraints - via nonlinear function

I have the following convex optimization problem over $\mathbb{R}^n$ with box constraints: $$\begin{align}\text{minimize }&\;f(x)\\ \text{subject to }&\;x \in [-1,1]^n\end{align}$$ I can see ...
0
votes
0answers
20 views

How do I model the optimization of haircuts (price vs. frequency vs. satisfaction)?

My goal is to use a simple, real world situation to apply optimization algorithms to and find optimal choices based on computation. What information do I need to gather and what questions do I need to ...
4
votes
2answers
68 views

Find the smallest $\alpha$ such that, for all $x,y,z$, $\alpha\,\left(x^2-x+1\right)\left(y^2-y+1\right)\left(z^2-z+1\right)\ge(xyz)^2+|xyz|+1$.

Find the smallest $\alpha\in\mathbb{R}$ such that, for all $x,y,z\in\mathbb{R}$, the following inequality holds $$\alpha\,\left(x^2-x+1\right)\left(y^2-y+1\right)\left(z^2-z+1\right)\ge(xyz)^2+|xyz|+1\...
1
vote
1answer
46 views

Binary Stochastic Programming with Independent or Positively Correlated Co-efficients

A manufacturer can select a maximum of $N$ stores to fulfill orders from a total of $M$ stores who are looking for inventory, $N\le M$. The case when $N\geq M$ is trivially solved when all stores ...
1
vote
1answer
34 views

how to project optimal parameters on to feasible region

Hi: I'm trying to understand the concept of projection and I created a toy example that might help me to do that. Suppose that I have a non-linear optimization with 3 parameters theta_1, theta_2 and ...
0
votes
1answer
39 views

Proximal operators on Balls (Projection)

I was following this tutorial, In section 21 it is given Proximal operator over a ball $B_\epsilon$ of radius $\epsilon$ as $$\text{Proj}_{B_\epsilon(y)}(u) = y + (u-y) \max({1 , \frac{\epsilon}{||{u-...
3
votes
1answer
39 views

Is there a way to measure how (non)convex a function is, maybe analogous to condition number?

Consider the functions $f(x) = \sin x$ and $g(x) = (x+1)^2 (x-1)^2$. We know that $f$ has an infinite number of local minimizers and is nonconvex on a non-compact subset of $R$. We know that $g$ has ...
1
vote
1answer
32 views

how to find closely related values from a set?

I have a set of values, for eg. {20, 1, 1, 21, 8, 22, 11, 40, 5, 21} and will need to find n closely related values. If n is 4 in the given example, the result should be {20, 21, 21, 22} because these ...
2
votes
0answers
21 views

Introduction to morse theory with applications to optimization

I am wondering if there are any easy-to-read introduction materials on morse theory (especially with applications to nonconvex optimization) for people with non-math background.
1
vote
1answer
55 views

Invertibility of bordered Hessian

I have an optimization problem: $max_{x \in C} f(x)$ s.t. $Ax=b$, where $x \in R^n$ and $b \in R^m$, $m \le n$, adn $C$ compact. I know that $f$ is strictly quasi-concave, and that $A$ has rank $m$ (...
1
vote
1answer
20 views

Optimization: Via manifolds point of view of Lagrange multipliers method

My basis on differential manifolds calculus and differential geometry being very superficial, I'm trying to understand this section on WP's article. I'm not being able to realize why most of the ...
0
votes
1answer
625 views

Maximize profit with dynamic programming

I have 3 tables… $$\begin{array}{rrr} \text{quantity} & \text{expense} & \text{profit}\\ \hline 0 & 0 & 0 \\ 1 & 100 & 200 \\ 2 & 200 & 450 \\ 3 & 300 & 700 \\...
2
votes
1answer
68 views

Finding the nonnegative integer exponents that minimize a product

I've been trying to solve a problem which seems to be a multiplicative optimization problem: Given a threshold $T > 0$, and a set of integers $b_1, b_2,\dots, b_n > 0$, find integer ...
1
vote
3answers
44 views

Calculus 1 - Optimization of a Box

Can you guys help me out with it? i try to solve it but my answer is so weird that i think im wrong... Question- Someone want to build cardboard box with rectangular base. Knowing thatthe rectangle ...
8
votes
6answers
250 views

Extreme of $\cos A\cos B\cos C$ in a triangle without calculus.

If $A,B,C$ are angles of a triangle, find the extreme value of $\cos A\cos B\cos C$. I have tried using $A+B+C=\pi$, and applying all and any trig formulas, also AM-GM, but nothing helps. On this ...
0
votes
1answer
1k views

How do I construct the Jacobian for use in a Levenberg-Marquardt algorithm.

I am working on a 3D reconstruction system and I am looking to use a Levenberg-marquardt algorithm to do bundle adjustment. I am not too sure about how LM works and what it requires. The model I am ...
2
votes
0answers
31 views

Sup of a linear function

Let $X$ be a banach space or simply a normed space and $C$ a convex (closed) subset of $X$. It is true that if $x \in C$ is such that $f(x)=\sup f(C)$, (in other words $x$ is a supporting point for $C$...