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
2answers
264 views

Optimization problem: Maximize the sum of minimum.

Given positive integers $L$ and a set of non-negative integers $N$. Find maximum of: $$\large \sum_{i = 1}^{4L}\ N_i\cdot(\min(\vert i - c\vert, 4L - \vert i - c\vert))$$ with $c \in \{1, 2,\dots ...
4
votes
1answer
68 views

Division of plane into equal area regions

We divide a plane ($\mathbb{R}^2$) into infinite number of regions each of area equal $1$. We can use only (one-dimensional) curves which may meet at points. Fix a point $p$ on a plane and consider ...
0
votes
1answer
19 views

Rank degenerate non negative least squares

I'm following an algorithm in the book "Solving Least Squares Problems" by Lawson and Hanson (#15 in Siam's Classics in Applied Mathematics) for solving non negative least squares. That is, minimize ...
0
votes
0answers
30 views

Minimizing a multivariable function in several variables

I would like to show that a certain function is negative, to help establish asymptotic stability via a Lyapunov function for a system of differential equations. This is exactly what I need help on: ...
0
votes
0answers
15 views

Estimating objective function weights from Pareto front

Let's say I have 2 functions $f_1(x)$ and $f_2(x)$. I ran a multi-objective optimization method to obtain the Pareto Front. Now, take any point P on the Pareto front. Assuming the Pareto Front to be ...
0
votes
0answers
51 views

The dual simplex algorithm

Following is the dual simplex algorithm, adapted from p. 283 of Daniel Solow's "Linear Programming, An Introduction to Finite Improvement Algorithms", Elsevier Science Publishing Co., Inc., 1984. I ...
1
vote
3answers
845 views

gradient descent optimal step size

Suppose a differentiable, convex function $F(x)$ exists. Then $b = a - \gamma\bigtriangledown F(a)$ imples that $F(b) <= F(a)$ given $\gamma$ is chosen properly. The goal is to find the optimal ...
0
votes
0answers
22 views

Linear assignment problem - would this constraint also be correct?

In the linear assignment problem, could the constraint $\sum_i x_{ij} = 1$ also be replaced by $\sum_j \sum_i x_{ij} = n$? Because I think this also ensures that all tasks are executed, and the ...
11
votes
1answer
330 views

Can a dynamic programming problem be transformed into a linear algebra problem?

Here is a simple standard economic problem: Let Robin Crusoe have an endowment $w_0$ of lembas bread. She is immortal and discounts at a rate of $\beta$ per period. Each period (from $t=0$ on) she ...
1
vote
1answer
51 views

How can I modelize a weekly menu and minimize the total number of ingredients it contains

Hi and many thanks for reading this question. I want to create an algorithm that will minimize the total number of ingredients that are in a weekly menu. A menu is made of several recipes, for ...
2
votes
1answer
55 views

Solving $ \inf \left\{ F[\nu] : \nu \in L^2 , \nu \geq 0, \int _0 ^1 \nu=1\right\}$

Let $\phi \in \mathcal ( [0,1]^2)$ symetric , can we find a solution to the following minimisation problem? $$ \inf \left\{ F[\nu] : \nu \in L^2 , \nu \geq 0, \int _0 ^1 \nu=1\right\}$$ with $$ ...
0
votes
0answers
14 views

Understand and an algorythm to Maximize number of triangles from a set of points on XY plane

Given: Set of points (x, y) Looking to: Maximize count of triangles that can be formed. Each triangle which is enclosed within another (with/without shared edge) will be counted again. Specifics on ...
0
votes
2answers
53 views

Optimizing elementary symmetric polynomial on the unit sphere

I'd like to optimize $x_1 x_2 x_3 + x_1 x_2 x_4 + x_1 x_3 x_4 + x_2 x_3 x_4$ on the unit 4-sphere. I'm thinking I should do lagrangian optimization, but I'm having trouble solving the resulting ...
0
votes
0answers
15 views

Threshold in a maximisation problem (with KKT conditions)

I'm looking to maximise with respect to $x_i$ $$L = \sum_{i= 1}^n y_i \frac {x_i^{1 - \epsilon}}{1 - \epsilon}$$ subject to $ \sum_{i= 1}^n x_i = B $ and $x_i \ge 0$ for all $i$, where $y_i$, $B$ ...
1
vote
1answer
61 views

maximizing a quadratic over linear function

Recently I am trying to solve the following optimization problem: $$ \begin{array}{cl} \text{maximize} & \frac{\left(c_1^T x\right)\left(c_2^T x\right)}{d^T x}\\ \text{subject to} & a^Tx\leq b ...
7
votes
1answer
351 views

Graph theory problem (edge-disjoint matchings)

Find the smallest number $x$ so that if an $n$-vertex simple graph has at least $x$ edges then it contains $k$ pairwise edge-disjoint perfect matchings* ($k$ is a positive integer, $n$ is an even ...
11
votes
5answers
290 views

How find this maximum of the $\sin^2{\theta_{1}}+\sin^2{\theta_{2}}+\cdots+\sin^2{\theta_{n}}$

Question: let $\theta_{1},\theta_{2},\cdots,\theta_{n}\ge 0$,and such $$\theta_{1}+\theta_{2}+\theta_{3}+\cdots+\theta_{n}=\pi$$ find the $P$ the maximum of value $P(n)$ ...
1
vote
2answers
72 views

When are there no critical points?

Is there ever a time when there are no critical points of a function? For example, I am trying to find the critical points and the extrema of $\displaystyle f(x)= \frac{x}{x-3}$ in $[4,7]$ I am not ...
1
vote
2answers
74 views

Formulation and computation of “the” unique median of an even-sized list

Consider an even-sized set of numbers $X = \{x_k\}$, such as $X = \{1, 2, 7, 10\}$. The median $m$ is defined as: $$m = \mathrm{arg \min_x} \sum_k \lvert x_k - x\rvert^1$$ Any $m \in [2, 7]$ is a ...
0
votes
1answer
25 views

Projection theorem for compact differentiable manifold

By Hilbert projection theorem, if $x\in\mathbb{R}^n$ and $D$ is a closed subset of $\mathbb{R}^n$ then the optimization problem $$\underset{y}{\min} \|x-y\| \ s.t. \ y \in D \quad\quad (P1)$$ has an ...
1
vote
2answers
75 views

Maximizing discrete probability

I'm stuck with the following problem: Let's assume we have two buckets: bucket one contains $k$ white spheres and $l$ red spheres. Bucket two contains $n-k$ white spheres and $n-l$ red spheres (n a ...
0
votes
2answers
1k views

Solving a set of equations with Newton-Raphson

I want to solve this set of equations with Newton-Raphson. Can anybody help me? $$ \cos(x_1)+\cos(x_2)+\cos(x_3)= \frac{3}{5} $$ $$ \cos(3x_1)+\cos(3x_2)+\cos(3x_3)=0 $$ $$ ...
1
vote
2answers
66 views

Forbidden range for a linear programming variable

I would like to express a linear program having a variable that can only be greater or equal than a constant $c$ or equal to $0$. The range $]0; c[$ being unallowed. Do you know a way to express this ...
1
vote
2answers
25 views

optimization problem: finding an hyperplane separating one point from a set of pointy maximizing the distance

I have this problem: I have a set of n-dimensional points $P$. I have one more n-dimensional point $q$. The points in $P$ are linearly separable from $q$ (i.e. it always exists an hyperplane $n^t x ...
1
vote
1answer
532 views

hessian matrix not positive definite at a minimum?

I have a function for which I want to find the global minimum. The function is: ...
1
vote
2answers
47 views

Extreme value problem, maximize ratio of volume to surface area

For a cylindrical can, how to choose the ratio of the height to the radius such that the ratio of the volume to the surface area gets maximized? The volume ist $V = \pi r^2 h$ and the surface ...
3
votes
2answers
53 views

Minimize Sum a_i / Sum b_i over subsets

I have two positive finite sequences $a_i$ and $b_i$, with $0 \leqslant i \leqslant n$. The problem is to find the subset $I$ of $\{0, ..., n\}$ that minimizes: $$\frac{\sum_{i \in I} a_i}{\sum_{i ...
1
vote
1answer
57 views

minimize distance

consider a two dimensional system. two points are given whose co-ordinates are $(h1,h2)$ and $(k1,k2)$. I want to minimize the distance between these two points with the condition that person has to ...
0
votes
0answers
53 views

Linear Programming with percentage constraints

I need some guidance with this Linear Programming problem, I want to maximize profits subject to different constraints, the problem is Maximize Goods subject to Min and Max Percentage Volume and ...
0
votes
1answer
680 views

How to describe minimization of L1 norm error using linear programming?

Given a set of $n$ pair points $(x_1, y_1), ..., (x_n, y_n)$ in the plane, I need to find a line $ax + by = c$ that fits the points of the L1 norm error points as closely as possible. I need a linear ...
0
votes
1answer
32 views

Sufficient condition on convex function such that $f(x) > -\infty$ for all $x$.

Let $f : \mathbb R^n \to [-\infty, \infty]$ convex and let $f(\overline x) > -\infty$ for $\overline x \in \mbox{int}(\mbox{dom}(f)$. Show that $f(x) > -\infty$ for all $x \in \mathbb R$. ...
1
vote
2answers
20 views

Is this condition sufficient to ensure the locally convexity of a function at a given point?

Given $\bar x\in \mathbb R^n$. Let $f:\; \mathbb R^n\to \mathbb R$ be a nonconvex continuous function on $\mathbb R^n$ satisfying the followings (i) $f$ is not differentiable at $\bar x$, (ii) There ...
0
votes
0answers
18 views

Proof of sufficient condition of existence of Lagrange multipliers

Consider the optimization problem $$ (P) \quad \inf\{ f(x) : g_i(x) \le 0, i = 1,\ldots, m, x \in \mathbb R^m \} $$ where $f, g_i : \mathbb R^n \to (-\infty, \infty]$ are convex and $0 \ne ...
0
votes
0answers
42 views

Generate primitive integer triangles

I am working on a program where I need to generate all primitive integer sided triangles with lengths $x,y,z$ such that $1\leq x \leq y \leq z$ and $x+y \leq m$. A primitive integer sided triange is ...
0
votes
1answer
37 views

Binomial Coefficient: monotonically decreasing in this range?

relating to this question, I'd like to ask a further one. Again we have $$f(x)={k-1 \choose x-1} p^x (1-p)^{k-x}$$ We know that this term is maximal for $x=kp$, before increasing, afterwards ...
0
votes
0answers
13 views

Solve for transform of rotating frame to fixed frame given points in rotating frame and a planar constraint

Say there are 2 coordinate systems, with one orbiting around the other. Call one fixed ƒ and the other rotating ρ. The goal is to find the transform between the two frames. What's known is A set of ...
9
votes
1answer
4k views

What is the best strategy for Cookie-Clicker-esque games?

Today, I stumbled across the game Cookie Clicker, which I recommend you avoid until you have at least a few hours of time to waste. The basic idea behind the game is this: You have a large stash of ...
0
votes
1answer
44 views

binomial coefficient: maximum value

For $n\rightarrow \infty$ we consider $$f(p)=\sum_{j=c}^n {n\choose j} p^j (1-p)^{n-j}.$$ We are interested in $\hat{p}:=\arg \max_p f(p)$. Can we say something about $\hat{p}$ dependent on $n$ and ...
1
vote
2answers
136 views

Clarification on optimization problem

While reading a combinatorics paper about packing densities in compositions, I encountered the following optimization problem. Maximize $$f(\alpha_1, \dots, \alpha_5) = \sum_{1 \le i < j ...
1
vote
1answer
31 views

Optimization with both equality and inequality constraints

I need to minimize the following quantity: $$\min x_1^{-1/n}- \left(1-x_2 \right)^{-1/n}$$ subject to: $1-x_1-x_2=\gamma$ and $0<x_1+x_2<1$ $\gamma$ being a constant. Had it been two ...
0
votes
1answer
23 views

monotonicity of binomial coefficient

I am interested in $$f(x):={k-1 \choose x-1} p^{x} (1-p)^{k-x}.$$ How do I find out in which Domain this function is monotonically increasing, in which it is monotonically decreasing? For which $x$ ...
1
vote
1answer
42 views

Elegant way to solve this extreme value problem

I want to show that $$ \sup_{(x,y)\in \mathbb{R}^2 \setminus \lbrace (0,0) \rbrace} \frac{(ax+by)^2}{x^2+y^2} =a^2+b^2 $$ where $a,b \in \mathbb{R}$ are fixed (this problem appears when one tries to ...
2
votes
0answers
25 views

what does “modular” mean?

I find some similarity of the concept "modular set functions" to the cardinality function. But I don't see the cardinality function is also called "modular" or something else. I wonder what "modular" ...
0
votes
0answers
9 views

Non-convex maxmin optimization

I am dealing with the following maxmin optimization problem: $c^*, x^* = \arg\max\limits_{c \in C, x \in X} [f(c, x) + \min\limits_{\tilde{x} \in X} g(c, \tilde{x})] $ $f$ and $g$ are differentiable ...
0
votes
0answers
25 views

How to characterise this non-linear optimisation (linear objective function, non-linear constraints)

I was wondering if someone may be able to help me characterise this optimisation problem as I am struggling to find a numerical library that will solve it and I suspect it is because I am using the ...
1
vote
2answers
49 views

Lagrange Multiplier inconsistent

max $f(x,y,z)$ subject to $x+y+z=1$ $$f(x,y,z)= - (x+0.5y)\log(x+0.5y) -2(0.25y+0.5z)\log(0.25y+0.5z)-\log(2)(1.5y+z)$$ $$\frac{\partial F}{\partial x} = - (1+\log(x+0.5y))$$ $$\frac{\partial ...
0
votes
0answers
14 views

closest points on two Line Segments

I am looking for a general formulation to find the closest points on two line segments: What I was thinking about is to define our lines as: $ P1 + s * (P2-P1)$ $ Q1 + t * (Q2-Q1)$ Where $P1 , P2, ...
6
votes
4answers
181 views

Minimizing $\int_0^1|f'(t)|^2dt$ subject to $f(0)=0$ and $f(1)=1$.

Say you want to minimize $$ \int_0^1 \!|f'(t)|^2 \,dt, $$ subject to $f(0)=0$ and $f(1)=1$, amongst infinitely differentiable functions. Is this even possible? My guess is the minimizing function ...
0
votes
1answer
27 views

The convexity of convex function's range

Given a convex function $f\colon X \to \mathbb R$ with convex domain $X \subseteq \mathbb R^n$, is the range of $f$ a convex set also?
0
votes
0answers
15 views

How to find iso function value points without exploring all points in 2D space

Consider a 2D graph with dim1 and dim2 represented as X and Y respectively. The range of X and Y are 1 to 100. Hence there are 10000 points in the 2D space. Each point in the space is some function of ...